Rennan Dantas

Frédéric Havet

Rudini M Sampaio

Identifying codes for infinite triangular grids with a finite number of rows

Keywords: identifying code, grid, discharging method identifiant, grille, méthode de déchargement

Let G T be the infinite triangular grid. For any positive integer k, we denote by T k the subgraph of G T induced by the vertex set {(x, y)

where N [x] denotes the closed neighborhood of x in G. The minimum density of an identifying code in G is denoted by d * (G). In this paper, we prove that d * (T 1 ) = d * (T 2 ) = 1/2, d * (T 3 ) = d * (T 4 ) = 1/3, d * (T 5 ) = 3/10, d * (T 6 ) = 1/3 and d * (T k ) = 1/4 + 1/(4k) for every k ≥ 7 odd. Moreover, we prove that 1/4 + 1/(4k) ≤ d * (T k ) ≤ 1/4 + 1/(2k) for every k ≥ 8 even.

Introduction

Let G be a graph G. The neighborhood of a vertex v in G, denoted by N (v), is the set of vertices adjacent to v i G. It closed neighborhood is the set The problem of finding low-density identifying codes was introduced in [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] in relation to fault diagnosis in arrays of processors. Here the vertices of an identifying code correspond to controlling processors able to check themselves and their neighbors. Thus the identifying property guarantees location of a faulty processor from the set of "complaining" controllers. Identifying codes are also used in [START_REF] Ray | Robust location detection with sensor networks[END_REF] to model a location detection problem with sensor networks.

N [v] = N (v) ∪ {v}. A set C ⊆ V (G) is an identifying code in G if (i) for all v ∈ V (G), N [v] ∩ C = ∅,
Particular interest was dedicated to grids as many processor networks have a grid topology. There are three regular infinite grids in the plane, namely the hexagonal grid, the square grid and the triangular grid.

Regarding the infinite hexagonal grid G H , the best upper bound on d * (G H ) is 3/7 and comes from two identifying codes constructed by Cohen et al. [START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF]; these authors also proved a lower bound of 16/39. This lower bound was improved to 12/29 by Cranston and Yu [START_REF] Cranston | A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid[END_REF]. Cukierman and Yu [START_REF] Cukierman | New bounds on the minimum density of an identifying code for the infinite hexagonal graph grid[END_REF] further improved it to 5/12.

The infinite square grid G S is the infinite graph with vertices in Z × Z such that N ((x, y)) = {(x, y ± 1), (x ± 1, y)}. Given an integer k ≥ 2, let [k] = {1, . . . , k} and let S k be the subgraph of G S induced by the vertex set {(x, y) ∈ Z × [k]}. In [START_REF] Cohen | Improved identifying codes for the grid[END_REF], Cohen et al. gave a periodic identifying code of G S with density 7/20. This density was later proved to be optimal by Ben-Haim and Litsyn [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]. Daniel, Gravier, and Moncel [START_REF] Daniel | Identifying codes in some subgraphs of the square lattice[END_REF] showed that d * (S 1 ) =

7 20 + 1 20k ≤ d * (S k ) ≤ min 2 5 , 7 20 + 3 10k
.

They also proved d * (S 3 ) = 3 7 . The infinite triangular grid G T is the infinite graph with vertices in Z×Z such that N ((x, y)) = {(x, y ± 1), (x ± 1, y), (x -1, y + 1), (x + 1, y -1)}. Given an integer k ≥ 2, let [k] = {1, . . . , k} and let T k be the subgraph of G T induced by the vertex set {(x, y) ∈ Z × [k]}. Karpovsky et al. [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] showed that d * (G T ) = 1/4. Trivially, T 1 = S 1 . Hence d * (T 1 ) = 1 2 In this paper, we prove several results regarding the density of an identifying code of T k , k > 1. We prove that d * (T k ) = 1/4 + 1/(4k) for every odd k. Moreover, we prove

d * (T 2 ) = 1/2, d * (T 4 ) = 1/3 = d * (T 6 ) = 1/3, and
1/4 + 1/(4k) ≤ d * (T k ) ≤ 1/4 + 1/(2k) for every even k ≥ 8.
The upper bounds are obtained by showing periodic identifying codes with the desired density.

In general, the lower bounds are obtained via the Discharging Method. The general idea is the following. We consider any identifying code C of T k . The vertices in C receive a certain value q k > 0 of charge and the vertices not in C receive charge 0. Then we apply some local discharging rules. Here local means that there is no charge transfer from a vertex to a vertex at distance more than d k for some fixed constant d k , and that the total charge sent by a vertex is bounded by some fixed value m k . Finally, we prove that after the discharging, every vertex v has final charge chrg * (v) at least p k for some fixed p k > 0. We claim that it implies d(C, G) ≥ p k q k . Since a vertex sends charge at most m k to vertices at distance at most d k , a charge of at most

m k • |B r+s (v 0 ) \ B r (v 0 )| ≤ 2d k • k • m k enters B r (v 0 ) during the discharging phase. Thus |C ∩ B r (v 0 )| = 1 q k v∈Br(v0) chrg 0 (v) ≥ 1 q k   v∈Br(v0) chrg * (v) -m k • |B r+s (v 0 ) \ B r (v 0 )|   ≥ p k |B r (v 0 )| -2d k • k • m k q k . But |B r (v 0 )| ≥ 2(k + 1)r -k 2 , thus d(C, S k ) ≥ lim sup r→+∞ p k q k - 1 q k • 2d k • k • m k 2(k + 1)r -k 2 = p k q k
. This proves our claim. As the claim holds for any identifying code, we have

d * (T k ) ≥ p k /q k .
Observe that T k has many isomorphisms. Let ∈ Z. A horizontal translation is a mapping τ : (x, y) → (x + , y), a vertical symmetry is a mapping φ: (x, y) → (x + y + , k + 1 -y), a horizontal symmetry is a mapping ψ : (x, y) → (-x + 2y + , y), and all combinations of them are isomorphisms of T k . For example, for every vertex (x, y), by applying a horizontal symmetry, we can obtain an isomorphism θ such that θ((x, y)) = (x, y), θ((x, y + 1)) = (x + 1, y + 1), θ((x + 1, y + 1)) = (x, y + 1), θ((x -1, y)) = (x + 1, y), θ((x + 1, y)) = (x -1, y), θ((x -1, y -1)) = (x, y -1), θ((x, y -1)) = (x-1, y -1). See Figure 1, where the black vertex is (x, y) and u = θ(u) for each vertex u. If C is an identifying code in S k and σ is an isomorphism of S k , then σ(C) is clearly an identifying code of C with same density as C. Moreover all the discharging rules we consider are stable under isomorphism. Henceforth, in our proof,s when we write without loss of generality, we often mean free to consider σ(C), for some isomorphism σ of S k .

Inria

We also use some common notation in all proofs. Given an identifying code C of T k , we denote by U the set V (T k ) \ C. For any set X ⊆ V (T k ), we denote X k (resp. X ≥i , X ≤i ) the set of vertices x in X such that N

[x] ∩ C = i (resp. N [x] ∩ C ≥ i, N [x] ∩ C ≤ i). let U i be the set of vertices outside C with i neighbors in C. A vertex of C is isolated if all neighbors are not in C. If v ∈ C is isolated, then no neighbor u of v is in U 1 ,
since, otherwise, u and v have the same code {v}. We say that a vertex v is in the line i if v = (x, i) for some x ∈ Z.

In the proof, the discharging rules are applied one after another. at any step of the procedure, we denote by chrg(v) the charge of a vertex v (usually the step is clear from the context). We say that a vertex is unsatisfied if chrg(v) < p k . Let exc(v) = chrg(v) -p k be the amount of charge that v can transfer to other vertices. Given a set X of vertices, let chrg(X) = v∈X chrg(v) and exc(X) = v∈X exc(v). Let N (X) = ∪ v∈X N (v) \ X be the neighbors not in X of the vertices of X. Let uns(X) be the number of unsatisfied neighbors of X, that is, the unsatisfied vertices of N (X).

2 The infinite triangular grid with two, three or six rows

In this section, we prove the following theorem.

Theorem 1. d * (T 2 ) = 1/2, d * (T 3 ) = 1/3 and d * (T 6 ) = 1/3.
From the identifying codes of Figures 2, 3 and4, we obtain the following upper bounds:

d * (T 2 ) ≤ 1/2, d * (T 3 ) ≤ 1/3 and d * (T 6 ) ≤ 1/3. In other words, consider the sets C 2,a , C 2,b , C 3,a , C 3,b , C 6 given below. C 2,a = {(x, 1) | x ≡ 1, 3 mod 5} ∪ {(x, 2) | x ≡ 1, 2, 4 mod 5}; C 2,b = {(x, 1) | x ≡ 1, 2, 3, 4 mod 5} ∪ {(x, 2) | x ≡ 2 mod 5}; C 3,a = {(x, 1) | x ≡ 1 mod 2} ∪ {(x, 3) | x ≡ 1 mod 2}; C 3,b = {(x, 1) | x ≡ 1 mod 3} ∪ {(x, 2) | x ≡ 2 mod 2} ∪ {(x, 3) | x ≡ 3 mod 3}; C 6 = {(x, 1), (x, 3) | x odd } ∪ {(x, 5) | x ∈ Z}.
It is easy to check that C 2,a and C 2,b are identifying codes of T 2 with density 1/2, C 3,a and C 3,b are identifying codes of T 3 with density 1/3, and C 6 is an identifying code of T 6 with density 1/3.

In order to prove the lower bounds, we introduce the notion of quasi-identifying code of T 3 . Roughly speaking, a quasi-identifying code of T 3 does not care about the last line. Formally, a quasi-identifying code

C of T 3 is a subset C ⊆ V (T 3 ) such that (i) for all v ∈ V (T 2 ), N [v] ∩ C = ∅, and (ii) for all u, v ∈ V (T 2 ), N [u] ∩ C = N [v] ∩ C.
The main technical result of this section is the following. Before proving this lemma, we show that this result implies Theorem 1.

Proof of Theorem 1. Notice that every identifying code C 3 of T 3 is obviously a quasi-identifying code of T 3 . Then, from Lemma 2, d(C 3 , T 3 ) ≥ 1/3.

Also notice that every identifying code

C 2 of T 2 is also a quasi-identifying code of T 3 . Then, since d(C 2 , T 3 ) = 2 • d(C 2 , T 2 )/3, we obtain from Lemma 2 that d(C 2 , T 2 ) ≥ 1/2.
Finally notice that every identifying code C 6 of T 6 induces the following two quasi-identifying codes of T 3 : Proof of Lemma 2. Let C be a quasi-identifying code of T 3 and let U = V (T 3 ) \ C. We shall prove that the density of C in V (T 3 ) is at least 1/3. Given x ∈ Z, the quasi-column Q x is the set {(x, 1), (x, 2), (x -1, 3)}. We shall use the Discharging Method on the quasi-column. Initially every quasi-column

C 3,a = {(x, y) | (x, y) ∈ C 6 and y ∈ {1, 2, 3}}; C 3,b = {(x, 7 -y) | (x, y) ∈ C 6 and y ∈ {4, 5, 6}}. Then d(C 6 , T 6 ) ≥ 1/3, since, from Lemma 2, d(C 3,a , T 3 ) ≥ 1/3 and d(C 3,b , T 3 ) ≥ 1/3.
Q x receives a charge chrg 0 (Q x ) = |Q(x) ∩ C|.
A quasi-column is said to be full, (resp. heavy, average, empty) if it initial charge is 3 (resp. 2, 1, 0). We apply the following rules:

• (R1) Every full quasi-column sends 1 to the two closest empty columns to its right if they are at distance less than 5.

• (R2) Every heavy quasi-column whose right column is not heavy sends 1 to the closest empty column to its right if it is at distance less than 5.

• (R3) Every heavy quasi-column whose right column is heavy sends 1 to the second closest empty column to its right if it is at distance less than 5.

Note that the condition of distance less than 5 is here to guarantee that charge is only sent locally. We shall prove that the final charge of every quasi-column is at least 1. Since a quasi-column contains three vertices, this implies that the density of C is clearly at least 1/3.

A full column sends (at most) 2 by (R1), so its final charge is at least 1. A heavy column sends (at most) 1 by (R2) or (R3), so its final charge is at least 1. An average column sends and receives nothing so its final charge receives 1. Hence it only remains to prove that the final charge of every empty quasi-column is at least 1.

Let Q(x) be an empty quasi-column. Assume first that Q(x-1) is also empty.

Then (x-2, 2), (x-2, 1) ∈ C, because C[(x-1, 2)] = ∅ and C[(x -1, 1)] = C[(x -1, 2)]. If (x -3, 3) ∈ C, then Q(x -2) is full and both Q(x -1) and Q(x) receives 1 from Q(x -2) by (R1).If (x -3, 3) ∈ C, then (x -3, 2), (x -3, 1) ∈ C, since C[(x -2, 2)] = C[(x -1, 1)] and C[(x -2, 1)] = C[(x -2, 2)]. Hence Q(x -1) receives 1 from Q(x -2) by (R1) and Q(x) receives 1 from Q(x -3) by (R1) or (R3). If Q(x -1
) is heavy or full, then Q(x) receives 1 from it by (R1) or (R2). Henceforth we may assume that Q x-1 is average.

If Q x-1 ∩ C = {(x -1, 1)}, then (x -2, 1) ∈ C, because C[(x -1, 1)] = C[(x -1, 2)]. If Q x-2 is
full or heavy, then Q(x) receives 1 from it by (R1) or (R2). Hence we may assume

Q x-2 ∩ C = {(x -2, 1)}. Then (x -3, 2), (x -3, 1) ∈ C, since C[(x -2, 2)] = C[(x -1, 1)] and C[(x -2, 1)] = C[(x -2, 2)]. Hence Q x-3 sends 1 to Q x , by (R1) or (R2). Assume now Q x-1 ∩ C = {(x -1, 2)}. Then (x -2, 1) ∈ C, since C[(x -1, 1)] = C[(x -1, 2)]. If Q x-2 is
full or heavy, then Q(x) receives 1 from it by (R1) or (R2). Hence we may assume

Q x-2 ∩ C = {(x -2, 1)}. Furthermore (x -3, 2) ∈ C, since C[(x -2, 2)] = C[(x -1, 1)]. If Q x-3
is full or heavy, then Q(x) receives 1 from it by (R1) or (R2). Hence we may assume

Q x-3 ∩ C = {(x -3, 2)}. Now (x -4, 2), (x -4, 1) ∈ C, since C[(x -3, 2)] = C[(x -2, 1)] and C[(x -3, 1)] = C[(x -3, 2)]. Thus Q x-3 sends 1 to Q x by (R1) or (R2). Finally suppose that Q x-1 ∩C = {(x-2, 3)}. Since C[(x-1, 1)] = ∅, then either (x-2, 1) ∈ C or (x -2, 2) ∈ C. If Q x-2 is
full or heavy, then Q(x) receives 1 from it by (R1) or (R2). Hence we may assume that Q x-2 is average.

-Firstly assume that (x-2, 1)

∈ C. Since C[(x-2, 1)] = C[(x-1, 1)], then either (x-3, 1) ∈ C or (x -3, 2) ∈ C. If Q x-3
is full or heavy, then Q(x) receives 1 from it by (R1) or (R2).

Hence we may assume that

Q x-3 ∩C = {(x-3, 1)} or Q x-3 ∩C = {(x-3, 2)}. In both cases (x -4, 2), (x -4, 1) ∈ C, since C[(x -3, 2)] = C[(x -2, 1)] and C[(x -3, 1)] = C[(x -3, 2)]. Thus Q x-4 sends 1 to Q x by (R1) or (R2).
-Secondly assume that (x -2, 2)

∈ C. Then (x -3, 2) ∈ C, since C[(x -2, 2)] = C[(x -1, 2)]. If Q x-3
is full or heavy, then Q(x) receives 1 from it by (R1) or (R2). Hence we may assume that

Q x-3 ∩C = {(x-3, 2)}. Now (x-4, 2) ∈ C, since C[(x-3, 2)] = C[(x-2, 1)]. Moreover since C[(x -3, 1)] = C[(x -4, 3)], either (x -4, 1) or (x -5, 2) is in C. Therefore Q(x -4) is heavy or full, so Q x-4 sends 1 to Q x by (R1) or (R2).
3 The infinite triangular grid with four rows

In this section, we prove the following theorem.

Theorem 3. d * (T 4 ) = 1/3.
Proof. Consider the two codes C 4 and C 4 defined by

C 4 = {(x, 2) | x ≡ 0, 3 mod 3} ∪ {(x, 3) | x ≡ 0, 1 mod 3}; C 4 = {(x, 1) | x ≡ 1 mod 1} ∪ {(x, 2) | x ≡ 2 mod 3} ∪ {(x, 3) | x ≡ 0 mod 3} ∪ {(x, 4) | x ≡ 1 mod 3}.
See Figure 5.

It is easy to see that those codes have density 1/3, so d * (T 4 ) ≤ 1/3.

Let us now prove that d * (T 4 ) ≥ 1/3. Let C be an identifying code of T 4 and let U = V (T 4 )\C. We want to prove by the discharging method that the density of C in V (T 4 ) is at least 1/3. Set q 4 = 3 and p 4 = 1. Every vertex of C begins with charge q 4 and every vertex of U begins with charge 0. We say that a vertex v is unsatisfied if chrg(v) < p 4 . We will prove that, after the application of some discharging rules, every vertex of T 4 is satisfied. This yields d(C, T 4 ) ≥ p 4 /q 4 = 1/3.

We say that a vertex (x, y) ∈ V (T 4 ) is in the border if y ∈ {1, 4}, otherwise it is in the center. We will apply the following discharging rules. We apply the following discharging rules, one after another. It is important to note tat the order of the rules is important and that the set of unsatisfied vertices and the excess of every vertex are updated after each rule is applied. For every v ∈ C and every unsatisfied neighbor u ∈ U of v:

• Rule 1a: v sends 1 to u, if either u ∈ U 1 or exc(v) ≥ uns(v);

• Rule 1b: v sends 1 to u, if exc(v) ≥ uns(v);

• Rule 2a: v sends 1/2 to u, if v is in the border and exc(v) ≥ uns(v)/2;

• Rule 2b: v sends 1/2 to u, if exc(v) ≥ uns(v)/2;

• Rule 2c: v sends 1/2 to u, if exc(v) ≥ uns(v)/2;

• Rule 2d: v sends 1/2 to u, if exc(v) ≥ uns(v)/2;

• Rule 3: v sends 1/2 to u, if u ∈ U 2 and v did not send charge to u in the previous rules;

• Rule 4: v sends 1/4 to u if u ∈ U ≥3 and v did not send charge to u in the previous rules.

We have to prove that the final charge of every vertex is at least 1.

Claim 3.1. (i) At Rule 2a, every border vertex in C sends 1/2 to each of its unsatisfied neighbors.

(ii) If a center vertex has at most three neighbors in U , or at most four neighbors in U , none of them in U 1 , then at Rule 2b, it sends 1/2 to each of its unsatisfied neighbors.

Subproof. (i) Let v be a border vertex in C.

If it has at most two neighbors in U , then it sends 1 to each by 1a, and all its neighbors satisfied after Rule 1a. Henceforth, we assume that v has at least three neighbors in U .

Assume moreover that v has a neighbor u ∈ U 1 , then its identifier is {v}. Hence, any vertex

w ∈ N [v] \ {u} is adjacent to a vertex of C \ {v} because C[w] = C[u] = {v}.
Hence, v has a neighbor in C, and so exactly two neighbors u 2 and u 2 in U ≥2 . If those are unsatisfied after Rule 1b, then v only sent 1 to its u 1 by Rule 1a. Hence after Rule 1b exc(v) = 1 = uns(v)/2. Hence u 2 and u 2 receive 1/2 at Rule 2a.

Assume finally that v has no neighbors in U 1 , then it has at most four neighbors in U ≥2 . If they are unsatisfied after Rule 1b, v did not send anything at Rule 1a and 1b. Therefore, after Rule 1b exc(v) = 2 ≥ uns(v)/2. So each unsatisfied neighbor of v receives 1/2 at Rule 2a.

The proof of (ii) is identical to the one of (i). It remains to prove that every vertex u ∈ U 3 has final charge at least 1. By the above remark, it suffices to prove that it receives at least 1/2 from one of its three neighbors in C. If one of those neighbors is in the border, then we have the result by Claim 3.1-(i). Hence, we may assume that v has no neighbor in C in the border. In particular, u is in the center. Without loss of generality, we may assume u = (3, 2) and that we are in one of the following two cases.

♦
Thus (1, 2) ∈ C, since C[(2, 2)] = C[(2, 3)] = {(2, 2), (2, 3)}. If (0, 4) ∈ C, then, since C[(1, 2)] = C[(2, 1)], either (0, 2) ∈ C or (0, 3) ∈ C. If (0, 2) ∈ C, then (1, 2
) has at most four neighbors in U , none of them in U 1 . Thus, by Claim 3.1, (1, 3) is satisfied by (0, 4) and (1, 2) at Rule 2b (or earlier). If (0, 3) ∈ C, then (0, 3) has at most four neighbors in U , none of them in U 1 ), so (1, 3) is satisfied by (0, 4) and (0, 3) at Rule 2b (or earlier). In both cases, if u was not satisfied before, at Rule 2c exc((2, 2)) = 1 ≥ uns((2, 2)). So (2, 2) sends 1/2 to u. Henceforth we assume (0, 4) ∈ C. Subproof. This is equivalent to prove that every vertex in C has non-negative final excess or that it sends at most 2 in total. Let v be a vertex in C. It has initial excess 2 and at most one neighbor in U 1 (of such neighbors have identifier {v}) and so v sends at most 1 to vertices in U 1 . Hence afer Rule 1a, v has non-negative excess. Therefore it also has non-negative excess after Rule 2d because at each of the Rules 1b to 2d it cannot send more than its excess. Hence a vertex can have negative only if sends charge by Rule 3 or Rule 4. If v is in the border, then by Claim 3.1, it sends at least 1/2 to each unsatisfied neighbor at Rule 2a. Therefore, Rule 3 and Rule 4 never applies to it, and so its final charge is at least 1. Henceforth we assume that v is in the center. Without loss of generality, v = (2, 2).

Consequently, (0, 3) ∈ C, since C[(1, 3)] = C[(2, 2)]. Now (3, 4) ∈ C because C[(2, 4)] = C[(1, 4)] = {(2, 3)}. Suppose that (4, 3) ∈ C. Notice that (4, 3) has no vertex in U 1 , since C[(4, 4)] = C[(3, 4
Furthermore, if v sends charge to a neighbor by Rule 3 or Rule 4, then its has not sent any charge by Rules 1b to 2d, because it always send to all its unsatisfied neighbors. Let exc (v) be the excess of v before Rule 3: exc (v) = 2 if v has no neighbor in U 1 and exc (v) = 1 if it has a neighbor in U 1 . For any j, let u j (v) (resp. u ≥j (v)) be the number of neighbors of v in U j (resp. U ≥j ), and let u j (v) (resp. u ≥j (v)) be the number of neighbors of v in U j that are unsatisfied after Rule 2. We need to prove

1 2 u 2 (v) + 1 4 u 3 (v) ≤ exc (v). (1)
This equation holds trivially when u ≥2 (v) ≤ 2 and u 1 (v) = 1, or u ≥2 (v) ≤ 4 and u 1 (v) = 0.

Henceforth we assume that v has either one neighbor in U 1 and at least three neighbors in U ≥2 , or no neighbor in U 1 and at least five neighbors in U ≥2 . We will consider all possibilities for the neighborhood of v under this condition. We distinguish the three following cases : v has a neighbor in U 1 which is in the border (Case 1); v has a neighbor in U 1 which is in the center (Case 2); v has no neighbor in U 1 (Case 3).

Case 1: v has a neighbor in U 1 which is in the border. By symmetry, we may assume that this neighbor is [START_REF] Cohen | Improved identifying codes for the grid[END_REF][START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]. Since u ≥2 (v) ≥ 3, at least one vertex in {(1, 2), (1, 3), (2, 3)} is in U ≥2 . We consider five subcases: Proof. Let C be an identifying code of T k and U = V (T k )\C. We want to prove by the discharging method that the density of C in V (T k ) is at least 1/4 + 1/4k. Every vertex of C begins with charge 1 and every vertex of U begins with charge 0. We say that a vertex (x, y) ∈ V (T k ) is in the border if y ∈ {1, k}; otherwise it is in the center. If v is in the center, exc(v) = chrg(v) -1/4. If v is in the border, exc(v) = chrg(v) -3/8. We say that a vertex v is satisfied if exc(v) ≥ 0. We will prove that, after the application of some discharging rules, every vertex of T k will be satisfied, and we are done, since

((k -2) • (1/4) + 2 • (3/8))/k = 1/4 + 1/4k.
Given a vertex v of T k , let B 1 (v) be the set of neighbors of v in the border and let B 2 (v) be the set of vertices in the border that are at distance 2 of v. When we say that v sends full-excess (resp. half-excess) to B i (v) (i ∈ {1, 2}), this means that v sends exc(v)/b (resp. exc(v)/(2b)) to every unsatisfied vertex of B i (v), where b is the number of unsatisfied vertices of B i (v).

We will apply the following discharging rules.

• Rule 1: Every vertex in C sends 1/4 to its neighbor in U 1 (if one exists) and 1/8 to each of its neighbors in U ≥2 ;

• Rule 2: Every vertex v in the border with positive excess sends full-excess to B 1 (v);

• Rule 3: Every vertex v in the row 2 or k -1 with positive excess sends full-excess to B 1 (v);

• Rule 4: Every vertex v in the border with positive excess sends full-excess to B 2 (v);

• Rule 5: Every vertex v in the row 2 or k -1 with positive excess sends full-excess to B 2 (v);

• Rule 6: Every vertex v in the row 3 or k -2 with positive excess sends half-excess to

B 2 (v) ∩ (Z × {1}) and half-excess to B 2 (v) ∩ (Z × {k}).
Notice that, after the application of Rule 1, every vertex has charge at least 1/4. Indeed every vertex u ∈ U receives either charge 1/4, if u ∈ U 1 , or charge at least 2 • (1/8) = 1/4, if u ∈ U ≥2 , and every vertex v ∈ C has either charge at least 1 -6 • (1/8) = 1/4, if v has no U 1 -neighbor, or charge 1 -(1/4) -4 • (1/8) = 1/4, if v has a U 1 -neighbor, since this implies that v has a C-neighbor.

In particular, all vertices in the center are already satisfied. Moreover, some of them have positive excess:

(a) if v ∈ C is in the border, then chrg 1 (v) ≥ 1 -4 • (1/8) = 1/2 so exc 1 (v) ≥ 1/8; (b) if v ∈ C 3 is in the center, then chrg 1 (v) ≥ 1 -(1/4) -3 • (1/8) = 3/8 so exc 1 (v) ≥ 1/8; (c) if v ∈ C ≥4 is in the center, then chrg 1 (v) ≥ 1 -(1/4) -2 • (1/8) = 1/2 so exc 1 (v) ≥ 1/4; (d) if u ∈ U ≥3 , then chrg 1 (u) ≥ 3 • (1/8) = 3/8 and exc 1 (u) ≥ 1/8; (e) if u ∈ U ≥4 , then chrg 1 (u) ≥ 4 • (1/8) = 1/2 and exc 1 (u) ≥ 1/4.
In particular, the vertices both in C and the border are also satisfied.

Observe that at Rules 2 to 6 a vertex with positive excess divides its excess and sends it to its unsatisfied neighbors. Hence once a vertex is it never becomes unsatisfied after the application of those rules. Thus, we only have to prove that every vertex u in U and in the border is satisfied after some rule. It is equivalent to show that u receives at lest 1/8 after Rule 1. Without loss of generality, let u = (1, 1). u has a neighbor in C, since C[u] = ∅.

If both (0, 1) and (2, 1) are in C, then exc 1 ((0, 1)) ≥ 1/8 and exc 1 ((0, 1)) ≥ 1/8. Therefore, (0, 1) and (2, 1) send charge at least 1/16 each to u at Rule 2, and u is satisfied. Assume now that k ≥ 6 is even. Let C 2 be the second identifying code of T 2 in Figure 2 and let C 2 = {(x + k -2, y) : (x, y) ∈ C 2 }. Let C k = C k-3 ∪ C 2 , where C k-3 is the code defined above in the odd case. It is not difficult to see that C k is an identifying code of T k : suppose for a contradiction that two vertices (x, y) and (x , y ) have the same identifier. Since C k-3 is an identifying code of T k-3 , we cannot have both x ≤ k -3 and x ≤ k -3, and since C 2 is an identifying code of T 2 we cannot have both x ≥ k -1 and x ≥ k -1. Observe moreover that every vertex in rows k -3 and k -2 has a neighbour in row k -3 and that every vertex in rows k -2 and k -1 has a neighbour in row k -1. Hence necessarily y = y = k -2. Moreover, (x, y) and (x , y ) are at distance at most two. Hence, without loss of generality, we may assume that x =∈ x -1, x -2. Now observe that either

  and(ii) for all u, v ∈ V (G),N [u] ∩ C = N [v] ∩ C. The identifier of v by C, denoted by C[v], is the set N [v] ∩ C.Hence a identifying code is a set such that the vertices have non-empty distinct identifiers.Let G be a (finite or infinite) graph with bounded maximum degree. For any non-negative integer r and vertex v, we denote byB r (v) the ball of radius r in G, that is B r (v) = {x | dist(v, x) ≤ r}. For any set of vertices C ⊆ V (G), the density of C in G, denoted by d(C, G), is defined by d(C, G) = lim sup r→+∞ |C ∩ B r (v 0 )| |B r (v 0 )| ,where v 0 is an arbitrary vertex in G. The infimum of the density of an identifying code in G is denoted by d * (G). Observe that if G is finite, then d * (G) = |C * |/|V (G)|, where C * is a minimum-size identifying code in G.

Figure 1 :

 1 Figure 1: A symmetry of the triangular grids.

Lemma 2 .

 2 Every quasi-identifying code C of T 3 has density d(C , T 3 ) at least 1/3.

Figure 2 :

 2 Figure 2: Two optimal identifying codes of T 2 : C 2,a (top) and C 2,b (bottom). The grey vertices are those of the code.

Figure 3 :Figure 4 :

 34 Figure 3: Identifying codes C 3,a (top) and C 3,b (bottom) of T 3 with density 1/3.

Inria

Figure 5 :

 5 Figure 5: Two identifying codes of T 4 with minimum density 1/3.

1 .

 1 C[(3, 2)] = {(2, 2), (2, 3), (3, 3)}. Since C[(2, 3)] = C[(3, 2)], then at least one vertex of {(1, 3), (1, 4), (2, 4)} belongs to C. Thus, (2, 3) has at most three neighbors in U , none of them in U 1 . Then (2, 3) sends 1/2 to u = (3, 2) at Rule 2b (or 1 earlier).

2 .

 2 C[(3, 2)] = {(2, 2), (4, 2), (2, 3)}. If (2, 1) ∈ C, then (2, 2) has at most four neighbors in U , none of them in U 1 . Hence, by Claim 3.1-(ii), (2, 2) sends 1/2 to u = (3, 2) at Rule 2b (or 1 earlier), and we are done. Henceforth we assume (2, 1) ∈ C. Thus (3, 1) ∈ U 1 , and (2, 2) sends 1 to it at Rule 1a. If (1, 3) ∈ C, then C[(2, 2)] = C[(2, 3)] implies that either (2, 2) or (2, 3) has at most three neighbors in U and consequently (by Claim 3.1-(ii)) sends 1/2 to u = (3, 2) at Rule 2b (or 1 earlier). Henceforth, we assume (1, 3) ∈ C. If either (1, 4) ∈ C or (2, 4) ∈ C, then (2, 3) has at most four neighbors in U , none of them in U 1 . Hence, by Claim 3.1-(ii), (2, 3) sends 1/2 to u = (3, 2) at Rule 2b. Henceforth, we assume that (1, 4), (2, 4) ∈ C.

Claim 3 . 3 .

 33 )] implies that either (5, 3) ∈ C or (5, 4) ∈ C. Hence by Claim 3.1, (3, 3) Inria and (4, 4) are satisfied by (3, 4) and (4, 3) at Rule 2b, and so (2, 4) is satisfied by (3, 4) at Rules 2b and 2c. Hence, at Rule 2d, exc(2, 3) = 1 (because it sends 1 to (1, 4) at Rule 1.a) and uns(2, 3) ≤ 1. Therefore (2, 3) sends 1/2 to (3, 2) at Rule 2d. Henceforth, we assume (4, 3) ∈ C. Then (5, 2), (6, 1) ∈ C, since C[(4, 2)] = C[(4, 1)] and C[(5, 1)] = C[(4, 2)]. Notice that either (5, 3) ∈ C or (6, 2) ∈ C, since C[(5, 2)] = C[(5, 1)]. In both cases, (5, 2) has no vertex in U 1 . Then, at Rule 2b, (4, 3) is satisfied by (3, 4) and (5, 2), and (5, 1) is satisfied by (5, 2) and (6, 1). Consequently (4, 2) sends 1/2 to (3, 2) at Rule 2c. ♦ Every vertex in C has final charge at least 1.

  [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF], (1, 3) ∈ C and (2, 3) ∈ U (Subcase 1.1),[START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF],[START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] ∈ C and (1, 2) ∈ U (Subcase 1.2), (2, 3) ∈ C and (1, 3) ∈ U (Subcase 1.3), v has only a horizontal neighbor in C (Subcase 1.4), v has only a diagonal neighbor in C (Subcase 1.5). Subcase 1.1: (1, 2), (1, 3) ∈ C and (2, 3) ∈ U . If (1, 1) ∈ C, then u 1 ((1, 2)) = 0 and u ≥2 ((1, 2)) ≤ 4, so (1, 1) and (1, 2) send 1/2 each to (2,1) by Rule 2b by Claim 3.1. Hence u ≥2 (v) ≤ 2 and v satisfies Eq. (1). Similarly, we get the result if (1, 4) ∈ C. Henceforth we assume that (1, 1), (1, 4) ∈ C.If (0, 4) ∈ C, then u 1 ((1, 3)) = 0 and u ≥2 ((1, 3)) ≤ 3. Consequently (0, 3) and (1, 4) are satisfied by (0, 4) and (1, 3) at Rule 2b, (2, 3) is satisfied by (1, 3) at Rules 2b and 2c, and so u ≥2 (v) ≤ 2 and v satisfies Eq. (1). Henceforth we assume that (0, 4) ∈ C.Then (0, 3) ∈ C (since C[(1, 3)] = C[(2, 2)]) and consequently (0, 2) ∈ C (since C[(1, 2)] = C[(1,3)]). Hence (1, 2) satisfies (2, 1) at Rule 1a, and u ≥2 (v) ≤ 2 and v satisfies Eq. (1).

C

  [(x, y)] = {(x, y-1), (x, y+1)}, if x odd and y even, and C[(x, y)] = {(x-1, y+1), (x+1, y-1)}, if x, y even.Since C k has (k + 1)/2 rows with density 1/2 and (k -1)/2 rows with density 0, Henced(C k , T k ) = 1 k • 1 2 • k+1 2 = 1/4 + 1(4k).Thus by Theorem 4, we have d * (T k ) = 1/4 + 1/(4k).

Figure 6 :

 6 Figure 6: Identifying code C 5 of T 5 with density 3/10.

  (x -2, k -1) or (x, k -1) is in C k , by definition of C k and C 2 . So C k [(x, y)] = C k [(x , y )], a contradiction.Since C k has (k -2)/2 rows with density 1/2, (k -2)/2 rows with density 0, and two rows with average densityd(C 2 , T 2 ) = 1/2, d(C k , T k ) = 1 by Theorem 4, we have 1 4 + 1 4k ≤ d * (T k ) ≤ 1 4 + 1 2k .

  Claim 3.2. Every vertex in U has final charge at least 1.Subproof. Every vertex in U 1 receives 1 by Rule 1a, so it is satisfied. Every vertex in U 2 receives at least 1/2 from each neighbor in C by Rule 3 or a preceding rule. So it receives at least 1 in total. Every vertex in U ≥3 receives at least 1/4 from each neighbor by the rules. Therefore every vertex in U ≥4 receives at least 1.

RR n°8951

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgements

This research was supported by FAPERJ, Capes (Project STIC-AmSud 2012), CNPq (Project Universal/Bolsa de Produtividade), and the FUNCAP/CNRS project GAIATO INC-0083-00047.01.00/13.

Partially supported by ANR under contract STINT ANR-13-BS02-0007. grilles triangulaires ayant un nombre fini de lignes par l'ensemble des sommets {(x, y)

est le voisinage fermé de x dans G. La densité minimum d'un code identifiant de G est notée d * (G). Dans ce rapport, nous montrons que d * (T 1 ) = d * (T 2 ) = 1/2, d * (T 3 ) = d * (T 4 ) = 1/3, d * (T 5 ) = 3/10, d * (T 6 ) =

Suppose that (1, 4) ∈ C. If either (0, 4) ∈ C or (2, 4) ∈ C, then [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] satisfies [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] at Rule 1a, [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] is either in C or [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] satisfied by [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] at Rule 1a, and (3, 2) and [START_REF] Cohen | Improved identifying codes for the grid[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] are satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] at Rule 1b. Consequently u ≥2 (v) ≤ 2 and v satisfies Eq. [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]. If (0, 4), [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] ∈ C, then either (3, 3) ∈ C or (3, 4) ∈ C (since C[(2, 4)] = C[(1, 4)] = {(1, 4), (2, 3)}). Therefore, (2, 3) has at most four neighbors in U , none of them in U 1 . If (3, 3) ∈ C, then [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] and [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] are satisfied by [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] and [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] at Rule 2b, [START_REF] Cohen | Improved identifying codes for the grid[END_REF][START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF] is satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] at Rules 2b and 2c, so u ≥2 (v) ≤ 2 and v satisfies Eq. [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]. If [START_REF] Cohen | Improved identifying codes for the grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] ∈ C, then (2, 4) is satisfied by [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] and [START_REF] Cohen | Improved identifying codes for the grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] at Rule 2a, (1, 3) is satisfied by [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] and (2, 3), [START_REF] Cohen | Improved identifying codes for the grid[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] is satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] and [START_REF] Cohen | Improved identifying codes for the grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF], [START_REF] Cohen | Improved identifying codes for the grid[END_REF][START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF] is satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] at Rules 2b and 2c, so u ≥2 (v) ≤ 2 and v satisfies Eq. ( 1). Henceforth we assume that (1, 4) ∈ C.

Therefore either (-2, 4)

) is satisfied by (0, 4) and (2, 4) at Rule 2a, (1, 3) is satisfied by (0, 4) and (2, 3) at Rule 2b, (3, 3) is satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] and (2, 3), (3, 2) is satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] at Rules 2b and 2c, so u ≥2 (v) ≤ 2 and v satisfies Eq. ( 1). If (0, 4) ∈ C, then either

, and consequently (1, 4) is satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] at Rule 1a, (3, 3) is either in C or satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] at Rule 1a, and (1, 3) and (3, 2) are satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] at Rules 2b and 2c, so u ≥2 (v) ≤ 2 and v satisfies Eq. ( 1). Henceforth, we assume that [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF]

If (0, 4) ∈ C, then (1, 3) is satisfied by (0, 4) and (2, 3) at Rule 2b. So u 2 (v) ≤ 1 and u ≥3 (v) ≤ 2, and v satisfies Eq. ( 1). Henceforth we assume (0, 4) ∈ C. [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]] implies that either (-1, 1) ∈ C or (-1, 2) ∈ C. Consequently (1, 2) is satisfied by (1, 1) and (0, 2) at Rule 2b, so u 2 (v) ≤ 1 and u ≥3 (v) ≤ 2, and v satisfies Eq. ( 1). Henceforth we assume (0, 2) ∈ C.

Therefore (-1, 3) ∈ C since C[(0, 3)] = C[(0, 4)], and (-2, 4)

) is satisfied by (-2, 4) and (-1, 3) at 2b, (0, 2) is satisfied by (-1, 3) and (1, 1) at Rule 2b, and consequently (1, 2) is satisfied by (1, 1) and (0, 3) at Rules 2b and 2c. Hence u 2 (v) ≤ 1 and u ≥3 (v) ≤ 2, and v satisfies Eq. (1).

) is satisfied by (1, 1) at Rule 1a, (1, 3) is satisfied by (1, 2) at Rule 1b, and so u ≥2 (v) ≤ 2, and v satisfies Eq. [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF]. Henceforth, we assume (0, 2) ∈ C.

, (1, 2), (2, 2)}. Therefore, (0, 2) and (2, 1) are satisfied by (1, 1) and (1, 2) at Rule 2b, (1, 3) is satisfied by (1, 2) at Rules 2b and 2c, and so u ≥2 (v) ≤ 2, and v satisfies Eq. (1). Subcase 1.5:

is satisfied by (1, 3) at Rule 1b, and so u ≥2 (v) ≤ 2, and v satisfies Eq. ( 1). If (2, 4) ∈ C and (0, 4) / ∈ C, then (0, 4) and (2, 3) are satisfied by [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] at Rule 1a, (1, 2) is satisfied by (1, 3) at Rule 1b, and so u ≥2 (v) ≤ 2, and v satisfies Eq. ( 1). If (0, 4), (2, 4) ∈ C, then (1, 3) has at most four neighbors in U , none of them in U 1 (since C[(0, 4)] = C[ [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF]] implies that either (-1, 4) ∈ C or (0, 3) ∈ C). Consequently (1, 2) is satisfied by [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] and (1, 1) at Rule 2a, (2, 3) is satisfied by [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] and (1, 4) at Rule 2a, so u ≥2 (v) ≤ 2, and v satisfies Eq. ( 1). Henceforth we assume [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] [START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF]] implies that either (-1, 4) ∈ C or (0, 3) ∈ C. In both cases, (1, 4) is satisfied by (0, 4) at Rule 1a, (0, 3) is either in C or satisfied by (0, 4) at Rule 1a, (1, 2) and (2, 3) are satisfied by [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Improved identifying codes for the grid[END_REF] at Rule 1b, so u ≥2 (v) ≤ 2, and v satisfies Eq. ( 1). Henceforth we assume (0, 4) ∈ C.

It follows that (0, 3

) is satisfied by (1, 1) and (0, 3) at Rule 2a (since (0, 3) has at most four neighbors in U , none of them in U 1 ). If (0, 2) ∈ C, then (1, 2) is satisfied by (1, 1) and (0, 2) at Rule 2a (since C[(0, 1)] = C[(1, 1)] implies that either (-1, 1) ∈ C or (-1, 2) ∈ C and consequently (0, 2) has at most four neighbors in U , none of them in U 1 ) and (2, 3) receives charge 1/2 from (1, 3) at Rule 2c. In both cases, (1, 2) is satisfied at Rule 2b by (1, 1) and either (0, 3) or (0, 2), and (2, 3) receives charge 1/2 from (1, 3) at Rule 2b or 2c. Therefore, if we prove that (2, 3) receives charge 1/2 at Rule 2a from a vertex distinct of (1, 3), then u ≥2 (v) ≤ 2, and v satisfies Eq. ( 1).

If Case 2: v has a neighbor u in U 1 which is in the center.

Without loss of generality, we may assume that u = (3, 2) (Subcase 2.1) or u = (2, 3)

and (1, 2) are satisfied by (2, 1) at Rule 1a, so u ≥2 (v) ≤ 2, and v satisfies Eq. ( 1). Henceforth we assume (1, 1) ∈ C. Recall that in that case exc (v) = 2, and so we assumed that u ≥2 (v) ≥ 5. In particular, v has at most one neighbor in C. Furthermore if u 2 (v) ≤ 2, then u (v) ≤ 2 and so v satisfies Eq. ( 1). Henceforth we assume that u 2 (v) ≥ 3. Thus, without loss of generality, we must be in one of the following cases:

Suppose that (0, 3) ∈ C. Then, (0, 2)

0, 2) has no U 1 -vertex, so (0, 1) and (1, 2) are satisfied by (0, 2) and (1, 1) at Rule 2b, (2, 1) is satisfied by (1, 1) at Rules 2b and 2c; hence u ≥2 (v) ≤ 4 so v satisfies Eq. ( 1). Henceforth we assume that (-1, 3

As above, if (0, 3) ∈ U 1 , we get that u ≥2 (v) ≤ 4 and v satisfies Eq. ( 1). Thus we assume that (0, 3) ∈ U 1 and consequently (-1, 4), (0, 4) ∈ C. Therefore (1, 4), [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF]}, then (2, 3) is satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] at Rule 1a, (1, 3) is satisfied by [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] at Rule 1b, so u ≥2 (v) ≤ 4 so v satisfies Eq. ( 1). Henceforth we assume that (0, 3) ∈ C.

It follows that (0, 4), [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] [START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF]]. Hence either (3, 3) ∈ C or (3, 3) is satisfied by [START_REF] Cohen | Improved identifying codes for the grid[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] at Rule 1a, (2, 3) is satisfied by [START_REF] Bouznif | Minimum-density identifying codes in square grids[END_REF][START_REF] Cohen | Bounds for Codes Identifying Vertices in the Hexagonal Grid[END_REF] at Rule 1b, so u 2 (v) ≤ 3 and u 3 (v) ≤ 2 and v satisfies Eq. ( 1). Henceforth we assume that (3, 4) ∈ C.

It follows that Hence half-excess of (1, 2) at Rule 6 is at least 1/16. We claim that (2, 1) is satisfied before Rule 6 and that (1, 1) receives charge at least 1/16 from a vertex other than (1, 3) before Rule 6. This claim implies that u is satisfied because it will be the only unsatisfied vertex of B 2 ((1, 3)) before Rule 6 and so it will receive half-excess (i.e at least 1/16) from (1, 3) at Rule 6. It remains to prove the claim.

If


Olivier Cador

Fabien Grasset

H Haneda

Jean Etourneau

published or not. The documents may come

Memory effect and super-spin-glass ordering in an aggregated nanoparticle sample

Memory effect and super-spin-glass ordering in an aggregated nanoparticle sample

Cador O. Grasset F., Haneda H., Etourneau J.

Abstract :

A system consisting of aggregated nonstoichiometric zinc ferrite nanoparticles has been studied using AC and DC magnetization measurements. A superparamagneticsuper-spin-glass phase transition at T g has been identified.

The relaxation time diverges at T g and the nonlinear susceptibility shows an abrupt increase. The critical behavior vanishes when the nanoparticles are not in close contact. The observation of the memory effect identical to that which has been already discovered in canonical spinglass supports the existence of a true thermodynamic transition in agglomerated magnetic nanoparticles.

There has been an increasing number of publications focusing on the magnetic properties of nanoparticle systems in the last few decades [1]. One of the most fascinating problems that researchers have focused on recently is the possible appearance of interparticle long-range magnetic ordering at low temperatures when the interactions between nanoparticles are sufficiently strong. Because of the size distribution of the particles and the randomness inherent to these systems, fingerprints of a possible superparamagneticsuper-spin-glass phase transition, in agreement with canonical spin-glasses, have been pursued and found: (i) the critical slowing down of the relaxation time τ on approaching the transition temperature T g [2, 3 and 4]; (ii) the divergence of the nonlinear susceptibility χ nl at T g [5, 6 and 7]; (iii) the magnetic aging in the ordered phase [4, 8, 9 and 10]. So far, most of the investigations have been performed on nanoparticles dispersed in a diamagnetic matrix, which can be a solid or a liquid. The magnetic fluids offer great advantages because the interactions between the particles can be tuned by changing nanoparticle concentration. But the main drawback is that the possibility of forming aggregates in the fluid can never be completely discounted. In aggregated nanoparticle samples this is not a problem and, furthermore, the interactions between the particles are stronger making them suitable for observation of collective behaviors.

Consequently, Dormann et al. [4] found that in aggregated samples the low-temperature regime is close to that of a canonical spin-glass. However, they did not put in evidence the critical divergence of the nonlinear susceptibility on approaching the transition temperature.

Lately, the spectacular memory effect has been found in concentrated ferrofluids [10 and 11]. In a typical memory experiment the sample is cooled in zero external magnetic field. At a given temperature, T w , the cooling process is halted for a certain time, t w , then the cooling is resumed.

After cooling the AC magnetic response is measured during the warming up of the sample. An infinitesimal cusp appears at T w when T w is lower than the blocking temperature, T B , of the particles [11]. This cusp does not exist when the cooling process is not halted. The memory effect had been previously reported below the freezing temperature, T g , in some spin-glasses [12]. This phenomenon can also be seen as a thermally hidden magnetic inscription. Indeed, at the lowest temperatures (far below T w ), the magnetization is strictly identical if the cooling has been paused or not. In other words, the system has memorized information but the reading is possible only at temperatures in the vicinity at which the information has been stored.

In this paper it is shown that the relaxation time of a sample of aggregated nanoparticles of nonstoichiometric zinc ferrite exhibits a critical slowing down and that the nonlinear susceptibility increases strongly on approaching T g . In addition, it was found that the sample does show the memory effect. These observations support the presence of interactions between the nanoparticles, which may be of dipolar origin and/or exchange. The synthesis and the physical characterizations of these nanoparticles are described elsewhere [13]. From the observations of 50 nanoparticles it has been concluded that their size is 1) is in good agreement with the experimental data (see inset of Fig. 1) with the values τ * =6×10 -10 s, zν=8.4 and T g =31.5 K. In systems of nanoparticles, values of zν between 6.9 and 11 have been reported [2, 3, 4, 17 and 18], which are similar to those found in spin-glasses [19]. Attempts to fit the data with the Néel-Brown model gave poor agreements with unrealistic values, especially from the microscopic relaxation time τ 0 which is of the order of 10 -25 s. The strictest criterion to identify a spin-glass is the divergence of the nonlinear susceptibility at T g . The magnetization can be written as follows:

where the a i 's reflect the nonlinear behavior. In spinglasses the coefficient a 3 diverges at T g with a 3 ∝(T g / (T-T g )) γ , while for a paramagnet, it is temperature independent and derives from the Taylor expansion of the Brillouin function. One of the simplest ways to probe the nonlinear coefficients is to record the zero-field-cooled magnetization (ZFCM) at several fields and to compare the M/H curves (see Fig. 2). It can be seen that the ratios M/H are superimposed except around T g which, according to Eq. ( 2), means that the nonlinear terms are insignificant away from T g but significant near T g . In order to show the thermal variation of the a i 's the thermal variation of (M-χ 0 H)/(χ 0 H) 3 an experimental point of view that the initial susceptibility χ 0 is, obviously, field independent. However, at 1 Oe the nonlinear terms might already contribute significantly near T g . This might induce a small error on χ 0 and consequently on the ratios (M-χ 0 H)/(χ 0 H) 3 . Measurements in extremely low fields, which were not reachable with the apparatus used, would be required to extract the true χ 0 vs. T curve.

However, this uncertainty is not responsible for the observed gap between the two curves because it affects both measurements. Other terms in Eq. (3), for example a 5 , might significantly contribute to (M-χ 0 H)/(χ 0 H) 3 . No attempt was made to fit the data with the exponent law a 3 ∝(T g /(T-T g )) γ because of this field dependence. One of the problems dealing with systems in which the particles interact is the distinction between collective and individual behaviors. Pileni et al. [21] have recently reported unusual magnetic properties of nonstoichiometric zinc ferrite nanoparticles dispersed in PVA. The ZFCM-FCM (fieldcooled magnetization) curves show unexpected nonlinear response at a low field (H<10 Oe), also centered on the maximum of the ZFCM, but over a wide temperature range. In our case we have determined (not represented) that a ferrofluid containing our particles does not present such a low-field effect, so intrinsic phenomena can be ruled out. The nonlinearity of the particles themselves appears at a field higher than 50 Oe. In order to get more information on the glassy phase the presence of the memory effect was probed. To do so a slightly different strategy from Jönsson et al. [11] Inset: temperature dependence of the nonlinear terms in Eq. (2).

Fig. 3. The temperature dependences of the ZFCM recorded at 1 Oe with and without a stop of 1 h at T w during the cooling process. We have plotted the difference between the two curves in the inset.

  between 4 and 6 nm. The nonstoichiometry associated with the partial inversion of the occupancy of the octahedral and tetrahedral sites by the Fe(III) gives ferrimagnetism to the particles. The saturation magnetization is equal to 64 emu g -1 . The magnetization measurements were carried out with a Quantum Design MPMS2 SQUID magnetometer equipped with the low-field option which gives remnant field lower than 50 mOe. The DC measurements were performed with the reciprocating sample option (RSO). In ZFC mode the instrument was paused for 2 min at each temperature before recording the data. AC measurements were performed with the AC driving field amplitude equal to 3 Oe and a frequency range of 0.1-1000 Hz. The frequency dependence of the in-phase AC susceptibility χ′ is represented in Fig. 1. In the superparamagnetic model the maximum of χ′ at T max corresponds to the average blocking temperature of the sample. This point is not clear however, and it might be the maximum of χ″ that could be used [14]. When the particles interact, authors use different criteria to extract the characteristic relaxation time [15]. Calculations based on the Néel-Brown model describe the variation of T max with the frequency of the oscillating driving field [1]. This model developed first for noninteracting particles remains quantitatively valid in the case of weakly interacting particles [1 and 16]. If the interactions are too strong a dynamic scaling analysis of the data is more appropriate. This has been shown in concentrated ferrofluids and aggregates of nanoparticles [2, 3 and 4]. The characteristic relaxation time varies with temperature according to τ=τ * (T/ T g -1) -zν , where T g is the transition temperature, zν the critical exponent and τ * is related to the relaxation time of individual particles. The freezing temperature T f at a given frequency f=1/τ is taken at the maximum of χ′. The fitting procedure with Eq. (

  for H=5 and 10 Oe, with χ 0 =M/H recorded at 1 Oe, 1 has been plotted in the inset of Fig. 2. According to Eq. (2) we can write Both curves show an abrupt negative peak near T g . The nonlinear coefficient a 3 is close to zero at temperatures higher than 40 K and increases abruptly below 40 K. The results resemble those which have been observed in the genuine spin-glass Ag (11 at% Mn) [20. P. Jönsson, T. Jonsson, J.L. García-Palacios and P. Svedlindh. J. Magn. Magn. Mater. 222 (2000), p. 219.and suggest a phase transition at T g , though the divergence is much less accentuated. The difference between the 5 and 10 Oe curves is difficult to elucidate. It is possible to argue from

  was employed. Indeed the ZFCM curves were measured with a stop and without a stop (called reference) during the cooling process. The measurements were performed under 1 Oe with and without a halt, t w =3600 s, at T w =15 K. The two curves are shown in Fig. 3. The reference ZFCM shows a cusp at T max =31.5 K. Below T g , ZFCM ref increases steadily without any apparent change of regime. The halted and the reference ZFCM curves do superimpose for all temperature other than around T w . The ZFCM halted shows a dip centered on T w . The difference curve ZFCM ref -ZFCM halted is shown in the inset of Fig.3. The maximum lies exactly at T w . It seems that the effect is more pronounced in this sample than in the ferrofluid studied by Jönsson et al.[11]. It can be noted that the memory effect vanishes when the particles are dispersed in a liquid. It is also worth mentioning that a ferrofluid containing the zincferrite nanoparticles does not show any abrupt increase of the nonlinear susceptibility as well as the critical behavior of the relaxation time. The occurrence of a true magnetic phase transition in magnetic particle systems has been the subject of debate in recent times. What has been established previously is that when the interactions between the particles are strong enough the lowtemperature regime is close to that of a canonical spinglass. Most of the investigations have been performed on ferrofluids in which the magnetic interactions between the particles are dipolar. In agglomerated systems the juxtaposition of the particles may switch on exchange interactions between the atoms at the surface. To our knowledge the problem of the exchange interaction between nanoparticles in compacted systems has not been intensely investigated, neither from the theoretical nor the experimental point of view[22]. This very interesting problem has to be tackled in order to figure out whether exchange interactions between particles can or cannot lead to a spin-glass state. To summarize, the superparamagnetic-super-spin-glass phase transition at T g in a sample of aggregated nonstoichiometric zinc ferrite nanoparticles has been identified. The relaxation time diverges and the nonlinear susceptibility increases abruptly at T g almost in perfect agreement with the laws of the 'classical' paramagnetic-spin-glass phase transition. These critical behaviors vanish when the interactions between the particles are cut (when the particles are dispersed in a diamagnetic medium). The observation of the memory effect identical to canonical spin-glass supports the existence of a true thermodynamic transition in agglomerated magnetic nanoparticles.

Fig. 1 .

 1 Fig. 1. The temperature dependence of the real part of the AC susceptibility measured at various frequencies of the oscillating magnetic field. Inset: analysis of the critical slowing down of the relaxation time (see text).

Fig. 2 .

 2 Fig. 2. The temperature dependence of M/H recorded at different DC magnetic fields and in zero-field-cooled modes.Inset: temperature dependence of the nonlinear terms in Eq. (2).

Acknowledgements :

Two of the authors (O.C. and F.G.) want to thank the Japan Science and Technology Exchange Center (JISTEC) for the


Yann Bouret

Alexandre Cohen

Nathalie Fraysse

Médéric Argentina

Christophe Raufaste

Solitary-like waves in a liquid foam microchannel

Keywords: numbers: 47.57.Bc, 68.03.-g, 47.55.nb

Plateau borders are liquid microchannels located at the contact between three bubbles in liquid foams. They are stable, deformable and can be thought of as quasi-1D model systems to study surface waves in fluid dynamics. We show that the burst of a bubble trapped in a PB produces local constrictions which travel along the liquid channel at constant velocity, without significant change in shape. These patterns are reminiscent of the depression solitary waves encountered in nonlinear systems. By coupling flow inertia to capillary stresses, we derive a simple model that admits solitonic solutions, which we characterized numerically and analytically in the limit of small deformation. These solutions capture most of the features observed experimentally.

I. INTRODUCTION

The stability of liquid foams significantly depends on the flow properties of the Plateau borders (PBs), which are wall-free liquid microchannels found at the contact between three bubbles [START_REF] Cantat | Foams: structure and dynamics[END_REF]. Each Plateau border (PB) is held by three soap films and has the very specific geometry highlighted in Fig. 1: the PB is inscribed in a triangular prism and its cross section can be approximated by the tangential contact of three arcs of circles of identical radius of curvature [START_REF] Princen | Osmotic pressure of foams and highly concentrated emulsions. i. theoretical considerations[END_REF]. At the foam scale, the PBs form an interconnected porous network through which the liquid runs off (see [START_REF] Saint-Jalmes | Physical chemistry in foam drainage and coarsening[END_REF][START_REF] Cohen-Addad | Flow in Foams and Flowing Foams[END_REF] for a review on foam drainage). The flow properties inside a single PB have also been the subject of several studies [START_REF] Desai | Flow through a plateau border of cellular foam[END_REF][START_REF] Koczò | Flow in a plateau border[END_REF][START_REF] Panhuis | New variations on the soap film experiments of Plateau I. Experiments under forced drainage[END_REF][START_REF] Koehler | Drainage of single Plateau borders: Direct observation of rigid and mobile interfaces[END_REF][START_REF] Pitois | Hydrodynamic resistance of a single foam channel[END_REF][START_REF] Piroird | Capillary Flow of Oil in a Single Foam Microchannel[END_REF][START_REF] Mensire | Capillary imbibition of aqueous foams by miscible and nonmiscible liquids[END_REF]. Structures made of PBs are robust and most of the perturbations -produced for example by adding liquid in excess -relax to recover steady-state Plateau borders of homogeneous radius profile. The dynamics of the flow triggered in each PB results from the coupling between the deformation of the PB, the fluid properties and the stress at the liquid/gas interface [START_REF] Cohen-Addad | Flow in Foams and Flowing Foams[END_REF][START_REF] Koehler | Liquid Flow through Aqueous Foams: The Node-Dominated Foam Drainage Equation[END_REF]. In all the aforementioned studies, the flow was assumed viscous, due to the small radius of the channel (typically 10 to 100 microns) and the small velocities measured (typically millimeters per second or less).

We recently showed that the perturbation brought to a single PB by making a droplet coalesce with it may actually relax rather quickly (typical velocities are 0.1 to 1 meter per second), according to what we proved to be an inertial regime [START_REF] Cohen | Inertial mass transport and capillary hydraulic jump in a liquid foam microchannel[END_REF][START_REF] Cohen | Drop coalescence and liquid flow in a single plateau border[END_REF]. Under identified experimental conditions [START_REF] Cohen | Inertial mass transport and capillary hydraulic jump in a liquid foam microchannel[END_REF], the perturbation is dispersed through the formation of structures analogous to hydraulic jumps driven by capillarity instead of gravity [START_REF] Argentina | One-dimensional capillary jumps[END_REF]. The occurrence and the dynamics of these capillary hydraulic jumps were satisfactorily modeled by assuming an inertia-dominated plug flow in the PB. * corresponding author: Christophe.Raufaste@unice.fr

The present study differs from the drop-injected experiment in the way we perturb the PB, leading to a drastically different response of the system. Here, a small bubble is brought to the PB, before being burst. Capillary suction triggers a transient flow in the liquid microchannel and the relaxation process develops local constrictions of the PB. Each constriction travels at constant velocity, without significant deformation over a distance that is large compared to the size of the depression zone. These localized-in-space patterns are reminiscent of solitary waves first introduced by Russell [START_REF] Russell | Report on waves[END_REF] and found in numerous non-linear systems [START_REF] Remoissenet | Waves called solitons: concepts and experiments[END_REF]. Theory predicts depression solitary waves as well as elevation ones [START_REF] Dauxois | Physics of solitons[END_REF]. In addition to the well-known dark solitons in optics, depression solitary waves were reported at the surface of a thin layer of mercury [START_REF] Falcon | Observation of depression solitary surface waves on a thin fluid layer[END_REF] and at the surface of a levitated water cylinder [START_REF] Perrard | Capillary solitons on a levitated medium[END_REF]. In this article, we aim at investigating these new structures observed to travel along PBs. We show that they might be identified to depression solitary waves.

The manuscript is organized as follows. We first depict the bubble-burst experiment and report systematic measurements. Then, we introduce a theoretical model which leads to an ordinary differential equation, whose solutions successfully capture the dynamics of the PB radius of curvature.

II. MATERIAL AND METHODS

The setup is similar to the one implemented for the drop-injected experiment (see [START_REF] Cohen | Drop coalescence and liquid flow in a single plateau border[END_REF] for details). By dipping a triangular-prism frame into a surfactant solution, we create a few-centimeter-long, horizontal PB held by three soap films (Fig. 1a,b). The initial radius of curvature of the PB is homogeneous and kept constant by continuously injecting liquid into it; its value can be set by tuning the flow rate. We deduce the local radius of curvature of the PB, R, from its apparent thickness, e, easily measurable on the side view (Fig. 2). The cali- FIG. 2. Image sequence of a typical bubble-burst experiment (small bubble, 10 ms between consecutive images). The bubble can be seen in the first picture; the dark spot which appears above the PB in each of the pictures is the tip of the needle used to burst the bubble. Dashed lines are guides to the eyes to follow the positions of two constrictions visible in the pictures. These constrictions move at constant velocity (0.13 m/s leftward for the constriction on the left, 0.27 m/s rightward for the one on the right). See text for notations.

bration procedure that we perform prior to any experiment (details can be found in [START_REF] Cohen | Drop coalescence and liquid flow in a single plateau border[END_REF]) shows that these two quantities are proportional, and that the proportionality constant is very close to 1. For the sake of simplicity, we will hereafter speak of radius of curvature only. The surfactant solution used in the present study was composed of TTAB (tetradecyl trimethyl ammonium bromide) dissolved into de-ionized water to a concentration of 3 g/l. It is characterized by tangential stress-free interfaces and the physical properties of this solution are its density ρ = 1030 ± 50 kg.m -3 , its surface tension γ = 38 ± 1 mN/m and its dynamic viscosity η = 1.04 ± 0.02 mPa.s [START_REF] Cohen | Drop coalescence and liquid flow in a single plateau border[END_REF].

A bubble, with an initial size small compared to the length of the PB, is gently inserted and held in place into the PB. The tip of a needle pierces the bubble to burst it: this provokes a strong perturbation of the PB at short times. The subsequent relaxation of the PB is recorded with a fast camera at 4000 fps. Fig. 2 displays a set of snapshots that shows the time evolution of the PB. Space-time diagrams of the radius of curvature of the PB are useful to highlight the relaxation dynamics: a color is assigned to the local value of the PB radius of curvature using a color scale that ranges here from dark blue for the thinnest parts of the PB to light blue for the thickest parts. At each time step of a given experiment, the radius profile yields a vertical line of color pixels; the horizontal stack of the columns computed from the whole set of pictures generates the space-time diagram. Two examples of such diagrams are shown in Fig. 3 for two different initial bubble sizes.

III. RESULTS

A few milliseconds after the bubble bursts, the PB radius profile shows constriction zones of small lateral extension, moving apart from the initial bubble location, as evidenced in Fig. 2 and in the movie of the Supplemental Material [21]. Although the variations in radius defining these localized patterns remain small (of the order of ten percent), they can be detected unambiguously and characterized.

Remarkably, the shape of each constriction zone is almost preserved during its propagation along the PB and the constriction remains visible far from the initial bubble position, over distances much larger than its typical size. The minimal radius of curvature of the PB and the width of the depression are denoted R -and w, respectively. A slight asymmetry in the PB radius of curvature is observed, with a small overshoot at the rear of the constriction. The difference between the PB radius of curvature in front of and behind the constriction is nevertheless very small, of a few percent at most. We note R + the radius of curvature of the PB as it overshoots. Ahead of the constriction zone, the deformation of the PB tends to zero, and its radius converges to its initial value. Another noteworthy feature of the localized depression patterns is that they travel along the PB at constant velocity, noted c. All these characteristics appear straightforwardly by considering space-time diagrams. The example of Fig. 3a shows a dark-blue, straight stripe that reveals a thinner, narrow zone of the PB, which travels at constant speed, over more than 10 mm in distance. The lighter stripe adjacent to the previous one stands for the overshoot of the PB radius at the rear of the constriction.

The size of the initial bubble does not significantly affect the constriction shape and dynamics. An increase in the bubble size may only increase the number of constrictions that are created. On the space-time diagram of Fig. 3b, which was obtained after the burst of a large bubble, two constrictions traveling in the same direction, away from the bubble location, are discernible on one half of the PB. Note that a third constriction is also noticeable, going in the reverse direction, as the result of the reflection of some perturbation on the vertex. Interestingly, when this third constriction collides with one of the two others, they cross each other without any significant change in velocity and nor in shape.

Measurements of R -, R + , w and c were performed on 41 constriction waves, for various values of the initial radius of curvature of the PB and of the bubble size. R -, w and c are plotted as a function of the radius R + in Fig. 4a, b, andc, respectively. R -and w appear to be proportional to R + (Fig. 4a andb), while c decreases with R + (Fig. 4c). Linear fits for R -and w give: R -= (0.80 ± 0.15)R + and w = (1.10 ± 0.15)R + .

An estimation of the Reynolds number around 100 is found given typical values of c ∼ 0.2 m/s and R + ∼ 0.5 mm. This shows that the physics is controlled by a balance between inertia and capillary forces, like in the drop-injected experiment [START_REF] Cohen | Inertial mass transport and capillary hydraulic jump in a liquid foam microchannel[END_REF]. We thus introduce the capillary-inertial velocity c 0 = γ/ρR + .

Given the experimental dispersion, the data on the velocity c scale reasonably well with the R -0.5 + dependence expected from c 0 : the black line in Fig. 4c corresponds to the best fit by a power-law of exponent -0.5. The adjustment leads to c exp = (0.61 ± 0.12)c 0 .

(

The capillary hydraulic jumps observed in the dropinjected experiment are characterized by a velocity proportional to c 0 as well [START_REF] Cohen | Inertial mass transport and capillary hydraulic jump in a liquid foam microchannel[END_REF][START_REF] Cohen | Drop coalescence and liquid flow in a single plateau border[END_REF]. The prefactor is equal to 1.07, which is roughly twice the one obtained for the depression waves in the bubble-burst experiment. However, it is important to note that hydraulic jumps and depression waves are two different kinds of responses of the PB to a perturbation. Both their geometry and dynamics are different. A capillary hydraulic jump separates two extended regions of distinct, uniform radii of curvature. In that sense it can be regarded as a positive and extended perturbation that requires a significant mass of liquid to be added to the PB to occur. Conversely, depression waves are localized and negative perturbations to an otherwise uniform PB. They do not need an excess of mass to appear. We have observed them in the bubble-burst experiment but they could appear in other situations, including in the drop-injected experiment. However, because their amplitude and velocity are small, the presence of hydraulic jumps are likely to hide them.

IV. MODEL

As for capillary hydraulic jumps, the observations of localized depression patterns traveling at constant velocity along the PB call for a capillary-inertial description of the underlying flow. Assuming that the PB profile and the flow are steady in a reference frame moving with velocity c, Argentina et al. [START_REF] Argentina | One-dimensional capillary jumps[END_REF] wrote the mass and horizontal momentum balance equations as:

∂ Z uR 2 = 0 (2) ρu 2 + γ 1 R -β 1 ∂ ZZ R -β 2 (∂ Z R) 2 R -3η∂ Z u = d R 2 . ( 3
)
ρ, γ and η are the density, the surface tension and the viscosity of the liquid, respectively. The velocity u is assumed uniform on the PB cross section, so that both the radius of curvature R and u are functions only of Z = z -ct which defines the longitudinal distance along the Plateau border in the reference frame moving with velocity c. In Eq. ( 3), the mean curvature of the liquidgas interface involves two geometrical prefactors β 1 ∼ β 2 ∼ 0.1 related to the specific shape of a PB. For the sake of simplicity, we set β 1 = β 2 = β. Finally, d is an integration constant fixed by the boundary conditions at infinity. The last term in the l.h.s. of Eq. ( 3) stands for the viscous shear. This ODE was able to retrieve the existence of the hydraulic jumps observed in the drop-injected experiment. A quantitative agreement was found with the experimental data, and the theoretical prediction that all velocities should fulfill c > c 0 / √ 2 proved to be satisfied. Remarkably, it was found that other solutions, localized in space and traveling at velocities c < c 0 / √ 2, could also exist. Their shape was numerically computed and found to be a symmetric constriction [START_REF] Argentina | One-dimensional capillary jumps[END_REF]. Therefore, these solutions appear as good candidates to explain the observations of the bubble-burst experiment. They obey the boundary conditions:

R(±∞) = R + (4) u(±∞) = -c (5)
which fixes d = ρ(cR + ) 2 + γR + . As done in [START_REF] Argentina | One-dimensional capillary jumps[END_REF], we rewrite the equations in a dimensionless form by choosing the scalings

u = cv, Z = R + s and R = R + a: v = - 1 a 2 (6)
1 a 4 - 1 + 1/W e a 2 + 1 W e 1 a -β (∂ ss a+ (∂ s a) 2 a - 1 Re 6 a 3 ∂ s a = 0, (7)
where we have introduced the Reynolds number, Re, and the Weber number, W e:

Re = ρcR + η , W e = ρc 2 R + γ . (8)
For large values of the Reynolds number, we omit the last term of Eq. [START_REF] Panhuis | New variations on the soap film experiments of Plateau I. Experiments under forced drainage[END_REF]. Following [START_REF] Argentina | One-dimensional capillary jumps[END_REF], the resulting equation multiplied by a 2 ∂ s a is integrated once with respect to s:

a(s) 2 1 -βa (s) 2 2W e - (W e + 1)a(s) W e - 1 a(s) = - 1 + 4W e 2W e . (9)
The right-hand side of Eq. ( 9) is the integration constant imposed by the boundary conditions a(±∞) = 1. By setting the local minimum of the constriction at Z = 0, we have a(0) = a -= R -/R + , and a (0) = 0, from what we deduce the following relation between W e and a -:

a 2 - 2W e - (W e + 1)a - W e - 1 a - = - 1 + 4W e 2W e , (10)
which reduces to a -= 2W e. From Eq. ( 8), the velocity c can thus be expressed as function of the constriction aspect ratio a -:

c = c 0 a - 2 (11)
FIG. 5. Measured velocity cexp as a function of the prediction c th for solitary waves of Eq. ( 11).

As a consequence, since a -< 1, the velocity is bounded: c < c 0 / √ 2. This upper limit of the velocity can define the group velocity. For flows with velocity higher than this critical velocity, shock waves are expected to occur and take the form of hydraulic jumps [START_REF] Argentina | One-dimensional capillary jumps[END_REF]. For their part, the constrictions can be identified to subsonic solitary waves, in a similar way as the surface waves observed for the mercury and levitated water cylinder systems mentioned previously [START_REF] Falcon | Observation of depression solitary surface waves on a thin fluid layer[END_REF][START_REF] Perrard | Capillary solitons on a levitated medium[END_REF].

In Fig. 5, the experimental velocity of each constriction is compared to the velocity predicted by Eq. ( 11) when using the experimentally measured value for a -. The agreement is satisfying considering that there is no free parameter. In most of the experimental profiles we measured a -∼ 0.8, such that c th ∼ 0.63c 0 : the numerical prefactor is very close to the 0.61 value that has been measured experimentally (Eq. ( 1)).

To proceed further, we compute the radius of curvature profile of a depression solitary wave, analytically to the first order in the limit of small deformations. Eq. ( 9) can be integrated once with respect to s; we do not report this calculation here neither its weighty resulting expression. From this expression and using perturbation theory, a simple analytical expression for the constriction can be explicitly computed as follows. In the limit of small deformations, we write a -= 1 -ε, assuming ε 1. By inserting the Ansatz:

a = 1 -εa 1 s √ ε 2 √ β + O ε 2 (12)
into Eq. ( 9), we obtain 1/ cosh(t) 2 as a solution. Finally, the profile of the localized structure obeys

1 4 (∂ t a 1 (t)) 2 -a 1 (t) 2 + a 1 (t) 4 = O(ε), (13)
a(s) = 1 - (1 -a -) cosh 2 s √ 1-a- 2 √ β + O (1 -a -) 2 . ( 14
)
The above formula was tested by looking for the best fit of the experimental profile reported in Fig. 6a with β as a free parameter. The adjustment yields the theoretical profile superposed with the experimental profile in Fig. 6b. The value 0.04 is obtained for β, which is consistent with the expected 0.1 value as mentioned above and in [START_REF] Argentina | One-dimensional capillary jumps[END_REF].

V. CONCLUSIONS

By means of an experimental study, we have shown that the relaxation dynamics of Plateau borders may exhibit structures having the characteristics of depression solitary waves [START_REF] Dauxois | Physics of solitons[END_REF]: these newly observed structures are localized in space, travel at constant velocity without deformation and cross each other without significant change in shape nor in velocity; their velocity depends on their amplitude.

We derived a model which admits two kinds of solutions, namely shock waves and subsonic depression solitary waves. The former were identified to the capillary hydraulic jumps reported in [START_REF] Cohen | Inertial mass transport and capillary hydraulic jump in a liquid foam microchannel[END_REF]. The latter compare very well to the experimental data from the bubble-burst experiment, in favor of identifying the constrictions observed to solitons.

The present model is unable to predict the value of the dimensionless contraction amplitude a -, which is found experimentally to be almost constant, close to 0.8. This feature might be explained by dissipative effects that we neglected at the first order. As it is the case for the capillary hydraulic jumps [START_REF] Argentina | One-dimensional capillary jumps[END_REF], a selection mechanism for the velocity could arise from the viscous shear. The slight asymmetry of the patterns observed experimentally could also result from some difference in dissipation on the two sides of the constriction in relation to the convergent/divergent nature of the flow.

To conclude, this study emphasizes the role of inertia in the relaxation dynamics of a Plateau border and that this liquid foam microchannel can be used as a quasi-1D model system to study highly non-linear surface waves in fluid dynamics.

VI. ACKNOWLEDGMENTS

FIG. 1

 1 FIG. 1. a) Sketch of the geometry of the Plateau border and its three holding films. b) Cross section of the PB seen through the liquid meniscus formed at the contact with a glass plate.

FIG. 3

 3 FIG.3. a) Space-time diagram of the PB radius of curvature built using the left half of the images recorded during the experiment reported in Fig.2. b) Space-time diagram for an experiment performed with a larger bubble. The red and yellow stripes on top of both diagrams arise from the images of the bubble at short times and of the needle tip at all times. Dark-blue straight stripes reveal constrictions moving along the PB (dashed black lines were plotted slightly offset to emphasize these features).

FIG. 4 .

 4 FIG. 4. Geometry and velocity dependence of the constrictions with respect to R+. a) Amplitude of the constrictions R-. b) Width of the constrictions w. c) Velocity of the constrictions c. The black lines correspond to the adjustment of the data as stated in the text.

where t = s √ ε 2 √

 2 FIG. 6. a) Enlargement of a constriction zone. The width of the constriction w, the radius of the constriction R-and of the overshoot R+ are emphasized. b) Radius of curvature profile measured experimentally (light gray) and adjustment by Eq. (14) of the model (dark dashed curve).

We thank Laurent Limat, Thierry Dauxois and Evgeny Ermanyuk for fruitful discussions.