Alan Frieze

Juan Vera
email: jvera@andrew.cmu.edu

On randomly colouring locally sparse graphs

Keywords: Counting Colourings, Sampling, Markov Chains

We consider the problem of generating a random q-colouring of a graph G = (V, E). We consider the simple Glauber Dynamics chain. We show that if for all v ∈ V the average degree of the subgraph Hv induced by the neighbours of v ∈ V is ≪ ∆ where ∆ is the maximum degree and ∆ > c1 ln n then for sufficiently large c1, this chain mixes rapidly provided q/∆ > α, where α ≈ 1.763 is the root of α = e 1/α . For this class of graphs, which includes planar graphs, triangle free graphs and random graphs Gn,p with p ≪ 1, this beats the 11∆/6 bound of Vigoda [20] for general graphs.

Introduction

Markov Chain Monte Carlo (MCMC) is an important tool in sampling from complex distributions. It has been successfully applied in several areas of Computer Science, most notably volume computation [START_REF] Dyer | A random polynomial time algorithm for approximating the volume of convex bodies[END_REF], [START_REF] Kannan | Random walks and an O * (n 5 ) volume algorithm for convex bodies[END_REF], [START_REF] Lovász | Simulated annealing in convex bodies and an O * (n 4 ) volume algorithm[END_REF] and estimating the permanent of a non-negative matrix [START_REF] Jerrum | A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries[END_REF]. It was used by Jerrum [START_REF] Jerrum | A very simple algorithm for estimating the number of k-colourings of a low-degree graph[END_REF] to generate a random q-colouring of a graph G, provided q > 2∆. This has led to the challenging problem of determining the smallest value of q for which it is possible to generate a (near)-uniform sample from the set Q of proper q-colourings of G in polynomial time. We cannot expect the chain to mix for q ≤ ∆ + 1 and at present it is unknown as to whether or not it mixes rapidly for say q = ∆+2. Vigoda [START_REF] Vigoda | Improved bounds for sampling colorings[END_REF] improved Jerrum's result by reducing the lower bound on q to 11∆/6. This is still the best lower bound on q for general graphs.

The lack of complete success on the general problem has led to the analysis of restricted classes of graphs. Suppose that we consider Glauber dynamics on the set Q. Specifically we will consider the heat bath dynamics, which may be described as follows. We start from an arbitrary proper q-colouring X 0 ∈ Q. At step t > 0 of the process, in state X t-1 ∈ Q, we choose a vertex v t ∈ V uniformly at random. Then we choose j t uniformly at random from the colours with which v t may be properly coloured, given X t-1 (V \ v t ). We recolour v t with j t to give X t ∈ Q.

Dyer and Frieze [START_REF] Dyer | Randomly colouring graphs with lower bounds on girth and maximum degree[END_REF] considered this process restricted to the class of graphs G(c 1 , c 2 ): the set of graphs with n vertices, maximum degree ∆ ≥ c 1 log n and girth g ≥ c 2 log ∆. They showed using the idea of "burn-in" that for c 1 , c 2 sufficiently large, Glauber Dynamics mixed in O(n log n) time, provided q > α∆ where α ≈ 1.763 is the root of α = e 1/α . Molloy [START_REF] Molloy | The Glauber dynamics on colorings of a graph with high girth and maximum degree[END_REF] improved this result by reducing the lower bound on q to being more than β∆ where β ≈ 1.489 is the root of (1 -e -1/β ) 2 + βe -1/β = 1. The girth asumptions were then relaxed by Hayes [START_REF] Hayes | Randomly coloring graphs of girth at least five[END_REF] to g ≥ 5 for k/∆ > α and g ≥ 6 for k/∆ > β. Subsequently, Hayes and Vigoda [START_REF] Hayes | A Non-Markovian Coupling for Randomly Sampling Colorings[END_REF] made considerable progress, using a non-Markovian coupling, and reduced the lower bound on k/∆ to (1 + ǫ) for all ǫ > 0, which is nearly optimal. Their result requires girth g ≥ 9.

However, the large maximum degree restriction remained. This was replaced by ∆ ≥ ∆ 0 in Dyer, Frieze, Hayes and Vigoda [START_REF] Dyer | Randomly coloring constant degree graphs[END_REF], with the same restrictions on girth as in [START_REF] Hayes | Randomly coloring graphs of girth at least five[END_REF]. Dyer, Flaxman, Frieze and Vigoda [START_REF] Dyer | Randomly colouring sparse random graphs[END_REF] show that for sparse random graphs, the number of colours required for rapid mixing is of order the average rather than maximum degree whp. Goldberg, Martin and Paterson [START_REF] Goldberg | Strong spatial mixing for graphs with fewer colours[END_REF] prove results on the related notion of strong spatial mixing.

In this paper we avoid girth restrictions and consider locally sparse graphs instead. We say that a graph G = (V, E) is γ-locally sparse if for all v ∈ V , the average degree of the graph induced by the neighbourhood N (v) is at most γ. Thus planar graphs are always 6-locally-sparse and triangle free graphs are 0-locally-sparse.

Theorem 1.1 Suppose that q ≥ (α + ǫ)∆ where ǫ is a small positive constant. Let G be an n-vertex γ-locally sparse graph with γ ≤ ǫ 2 ∆/10 and ∆ ≥ c 1 log n. If c 1 = c 1 (ǫ) is sufficiently large then the Glauber dynamics converges to within variation distance e -1 from uniform over Q in at most O(n ln n).

Notice that if G = G n,p and c1 log n n ≤ p ≤ ǫ 2 /11 then whp G satisfies the conditions of the theorem. Note also that the chromatic number of a triangle-free graph is O(∆/ log ∆) -see Johansson [START_REF] Johansson | Asymptotic choice number for triangle-free graphs[END_REF] or Molloy and Reed [START_REF] Molloy | Graph Colouring and the Probabilistic Method[END_REF] or Alon, Krivelevich and Sudakov [START_REF] Alon | Coloring graphs with sparse neighborhoods[END_REF] or Vu [START_REF] Vu | An upper bound on the list chromatic number of locally sparse graphs[END_REF].

Our proof uses coupling and relies on a recent idea from Hayes and Vigoda [START_REF] Hayes | Coupling with the stationarity distribution and improved sampling fror colorings and independent sets[END_REF] that utilises the fact that we can couple against the steady state distribution of the chain. Note that the theorem generalises Theorem 4 of [START_REF] Hayes | Coupling with the stationarity distribution and improved sampling fror colorings and independent sets[END_REF].

In what follows we will assume that n is sufficiently large and ǫ is sufficiently small to satisfy our inequalities.

Preliminaries

We will consider two copies of Glauber Dynamics, (X t , t ≥ 0) and (Y t , t ≥ 0). Here X 0 is an arbitrary colouring and Y 0 is chosen from the uniform (stationary) distribution over Q. At time t, the Hamming distance between X t , Y t is defined by

H(X t , Y t ) = v∈V 1 Xt(v) =Yt(v) .
We will couple the two processes as in Jerrum [START_REF] Jerrum | A very simple algorithm for estimating the number of k-colourings of a low-degree graph[END_REF]. Here v t is the same in both processes and then the choice of colours is maximally coupled. For vertex w let

A(X t , w) = {c ∈ [q] : c / ∈ X t (N (w))}
be the set of colours available to colour w in X t if v t = w. Let a(X t , w) = |A(X t , w)| and define the terms A(Y t , w), a(Y t , w) analogously. It is shown in [START_REF] Hayes | Coupling with the stationarity distribution and improved sampling fror colorings and independent sets[END_REF] that

E(H(X t+1 , Y t+1 ) -H(X t , Y t )) ≤ - 1 n H(X t , Y t ) + 1 n w∈V |{u ∈ N (w) : X t (u) = Y t (u)}| max{a(X t , w), a(Y t , w)} . (1)
We will show that for w ∈ V and δ = ǫ/10,

Pr(a(Y t , w) ≤ ∆/(1 -δ)) ≤ n -4 . (2)
Assuming that a(Y t , w) ≥ ∆/(1 -δ) in (1) we get

E(H(X t+1 , Y t+1 ) -H(X t , Y t )) ≤ - 1 n H(X t , Y t ) + 1 n H(X t , Y t )∆ ∆/(1 -δ) ≤ - δ n H(X t , Y t ).
So conditional on an event of probability 1 -O(n -3 ), we have

E(H(X t+1 , Y t+1 ) | X t , Y t ) ≤ 1 - δ n H(X t , Y t ).
Thus if T = n(1 + ln n)δ -1 then conditional on an event of probability 1 -O(n -2 log n), we have

E(H(X T , Y T )) ≤ e -1
and so unconditionally E(H(X T , Y T )) ≤ e -1 + o(1).

Hence the mixing time of the Glauber Dynamics is O(n ln n) as claimed.

Bounding the number of available colours

Fix v ∈ W and let H v be the subgraph of G induced by N (v). Let B(v) be the vertices of N (v) that have degree at least γδ -1 in H v . Note that γδ -1 ≤ ǫ∆ and

|B(v)| ≤ δ|N (v)|, (3)
since G is γ-locally-sparse.

Let N * (v) = N (v) \ B(v) = {w 1 , w 2 , . . . , w d }.
Now let let us fix the colours κ(v) used at

v ∈ W v = V \ N * (v).
Let us use the term allowable for colorings of N * (v) which respect this conditioning. Let Ω be the set of allowable colourings of N * (v).

Let a * (σ, v) be the number of colours not used on N * (v). Note that (3) implies

a(σ, v) ≥ a * (σ, v) -δ|N (v)|. (4)
Now consider the following process P σ for producing an allowable colouring of H v . Here σ ∈ Ω. We let σ 0 = σ and for j = 1, 2, . . . , d let σ j be obtained from σ j-1 as follows: Keep σ j (w k ) = σ j-1 (w k ) for k = j and choose σ j (w j ) randomly from what is available to it.

Let Z σ be the number of colours not appearing on a vertex in N * (v) if we start with σ 0 = σ.

Lemma 3.1 If σ is chosen uniformly from Ω then for any c > 0,

Pr(a * (σ, v) ≥ c) = Pr(Z σ ≥ c).

Proof

We first prove that If σ 0 is chosen uniformly from Ω then σ d is also uniform over Ω.

(

) 5
We do this by induction on j, with base case j = 0.

Pr(σ j = σ) = σ ′ ∈Ω Pr(σ j = σ | σ j-1 = σ ′ ) Pr(σ j-1 = σ ′ ) = 1 |Ω| σ ′ ∼σ Pr(σ j = σ | σ j-1 = σ ′ )
Here σ ′ ∼ σ if σ, σ ′ differ only at w j .

= 1 |Ω| σ ′ ∼σ 1 |{σ ′ : σ ′ ∼ σ}| = 1 |Ω| . Now a * (σ d , v) = Z σ0 and so Pr(a * (σ d , v) ≥ c) = Pr(Z σ0 ≥ c)
and the lemma follows from ( 5)

✷ For w ∈ N * (v) let L(w) = [q] \ {κ(u) : u ∈ N (w) \ N * (v)}
be the colours not specifically barred from w by the current conditioning. Then let

L * (w j ) = [q] \ {σ j-1 (u) : u = w j } for j = 1, 2, . . . , d
be the colours available to w j when it is re-coloured by σ j .

We will first estimate the (conditional) expectation of Z σ for arbitrary σ. Suppose that x ∈ [q]. Let θ x,j = 1 x∈L(wj ) and let θ *

x,j = 1 x∈L * (wj ) . Then we have

Pr(x / ∈ σ d (N * (v))) = d j=1 Pr(σ d (w j ) = x | σ d (w i ) = x, 1 ≤ i < j) = d j=1 E 1 - 1 |L * (w j )| θ * x,j ≥ d j=1 1 - 1 |L(w j )| -γδ -1 θx,j since |L * (w j )| ≥ |L(w j )| -γδ -1 and L * (w j ) ⊆ L(w j ) implying θ *
x,j ≤ θ x,j . Then, following [START_REF] Dyer | Randomly colouring graphs with lower bounds on girth and maximum degree[END_REF],

E(Z σ ) ≥ x∈[q] d j=1 1 - 1 |L(w j )| -γδ -1 θx,j ≥ q   x∈[q] d j=1 1 - 1 |L(w j )| -γδ -1 θx,j   1/q = q   d j=1 1 - 1 |L(w j )| -γδ -1 |L(wj )|   1/q ≥ q exp    - 1 q d j=1 |L(w j )| |L(w j )| -1 -γδ -1    , using 1 -x ≥ e -x/(1-x) for 0 < x < 1, ≥ q exp - ∆ q • q -∆ q -∆ -1 -γδ -1 ≥ 1 + ǫ 2 ∆. (6)
(If f (x) = xe -1/x then f (α) = 1 and f ′ (α) ∼ .891.)

We will now prove that for all σ ∈ Ω, Z σ is concentrated around its mean via the use of the Azuma-Hoeffding martingale inequality. To this end, let x 1 , x 2 , . . . , x d be the colours assigned to w 1 , w 2 , . . . , w d . Thus we can write

Z σ = Z σ (x 1 , x 2 , . . . , x d ). Now let Z σ,i = Z σ,i (x 1 , x 2 , . . . , x i ) = E(Z | x 1 , x 2 , . . . , x i ).
We will show next that for all feasible colours x 1 , x 2 , . . . , x i , x ′ i that

|Z σ,i (x 1 , x 2 , . . . , x i-1 , x i ) -Z σ,i (x 1 , x 2 , . . . , x i-1 , x * i )| ≤ 2. (7)
The aforementioned inequality will then imply that for any t ≥ 0,

Pr(Z σ -E(Z σ ) ≤ -t) ≤ e -t 2 /(2d)
and then taking t = ǫ∆/4 and using (6) we get

Pr Z σ ≤ 1 + ǫ 4 ∆ ≤ e -ǫ 2 ∆/32 .
This together with Lemma 3.1 and ( 4) implies (2).

To prove [START_REF] Hayes | Randomly coloring graphs of girth at least five[END_REF], fix i, x 1 , x 2 , . . . , x i , x * i . In one instance of P σ we start by colouring w 1 , w 2 , . . . , w i with x 1 , x 2 , . . . , x i to produce colouring τ . In another instance we start by colouring w 1 , w 2 , . . . , w i with x 1 , x 2 , . . . , x * i to produce colouring τ * . We couple these two constructions in order to minimise the expected difference in the number of vertices U with a different colour. A paths of disagreement argument gives that

E(U ) ≤ 1 + d j=i+1 γδ -1 |L(w j )| -γδ -1 j-i ≤ 2 (8)
and ( 7) follows. ✷ Explanation of (8): We claim that if c j , c * j is the colour of v j in σ d , σ * d respectively, then

Pr(c j = c * j ) ≤ γδ -1 |L(w j )| -γδ -1 j-i
. This is because if c j = c * j then there is a path of disagreements v i1 , v i2 , . . . , v is where i = i 1 < i 2 < • • • < i s = j such that c ir = c * ir for 1 ≤ r ≤ s. There are at most (λδ -1 ) j-i such paths and each has probability at most (|L(w j )| -γδ -1 ) i-j of all vertices being coloured differently. ✷

† Research supported by NSF grant CCR-0200945. 1365-8050


Tiziana Calamoneri
email: calamo@di.uniroma1.it

Optimal L(h, k)-Labeling of Regular Grids †

Keywords: L(h, k)-labeling, cellular grids, triangular grids, hexagonal grids, squared grids

The L(h, k)-labeling is an assignment of non negative integer labels to the nodes of a graph such that 'close' nodes have labels which differ by at least k, and 'very close' nodes have labels which differ by at least h. The span of an L(h, k)-labeling is the difference between the largest and the smallest assigned label. We study L(h, k)-labelings of cellular, squared and hexagonal grids, seeking those with minimum span for each value of k and h ≥ k. The L(h, k)labeling problem has been intensively studied in some special cases, i.e. when k = 0 (vertex coloring), h = k (vertex coloring the square of the graph) and h = 2k (radio-or λ -coloring) but no results are known in the general case for regular grids. In this paper, we completely solve the L(h, k)-labeling problem on cellular grids, finding exact values of the span for each value of h and k; only in a small interval we provide different upper and lower bounds. For the sake of completeness, we study also hexagonal and squared grids.

Introduction

The L(h, k)-labeling problem consists in assigning non negative integer labels to the nodes of a graph such that nodes at distance two have labels which differ by at least k, and adjacent nodes have labels which differ by at least h. The span of an L(h, k)-labeling is the difference between the largest and the smallest assigned frequency. The aim of the L(h, k)-labeling problem is to satisfy the distance constraints using the minimum span. This graph theoretical problem arises from the problem of assigning frequencies to the transcievers of a wireless network in order to avoid some kinds of interference (i.e. direct and hidden collision); in this setting, the nature of the environment and the geographical distance are the major factors determining parameters h and k, and it is usually assumed h ≥ k. Since its formal definition [START_REF] Griggs | Labeling graphs with a Condition at Distance 2[END_REF] the L(h, k)-labeling problem has been widely studied by means of techniques from disparate research areas and receiving many names (for a survey see [START_REF] Calamoneri | the L(h, k)-Labelling Problem: an Annotated Bibliography[END_REF]). However, almost all the literature concerns the special case of k = 1 and h = 2 or h = 1, and very few papers (8; 14; 15; 16; 20) investigate on the more general problem. Nevertheless, the solution of the problem for any h and k is worthy since it allows one to handle more realistic scenarios. Observe that, when k = 0, for any fixed h, the problem is equivalent to the classical vertex coloring problem, and when h = k it becomes the problem of optimally coloring the nodes of the square of the input graph; finally, when h = 2k the problem has been called radio-or λ-coloring problem. All these problems have been intensively studied.

The decisional version of the L(h, k)-labeling problem is NP-complete even for small values of h and k (2). This motivates seeking optimal solutions on particular classes of graphs.

In this paper, we completely solve the L(h, k)-labeling problem on cellular grids, finding exact values of the span for each value of h and k; only in a small interval we provide different upper and lower bounds. For the sake of completeness, we study also hexagonal and squared grids.

Exploiting the upper bounds presented in this paper, a label can be assigned to any node in a distributed fashion in constant time in all considered grids, provided that the relative position of the node in the graph is locally known. In this paper, the presented upper bounds will be described by means of formulas determining the color of a node as function of its own coordinates; nevertheless, figures will help to have the intuition of the labeling schemes.

Preliminaries and Discussion of the Results

For any non negative real values k and h ≥ k, an L(h, k)-labeling of a graph G = (V, E) is a function

L : V → IR such that -|L(u) -L(v)| ≥ h if (u, v) ∈ E and -|L(u) -L(v)| ≥ k if there exists w ∈ V such that (u, w) ∈ E and (w, v) ∈ E.
The span of an L(h, k)-labeling is the difference between the largest and the smallest value of L, so it is not restrictive to assume 0 as the smallest value of L. We denote by λ h,k (G) the smallest integer λ such that graph G has an L(h, k)-labeling of span λ.

In this paper, we consider the infinite cellular hexagonal and squared grids, where the position of each node is defined by a couple of integer coordinates, as shown in Fig. 1. Given a certain node (x, y) in a cellular grid, its neighbors are (x + 1, y), (x -1, y), (x, y -1), (x, y + 1), (x -1, y -1), (x + 1, y + 1). The nodes at distance 2 from (x, y) are (x + 2, y), (x -2, y), (x, y + 2), (x, y -2), (x + 2, y + 1), (x -2, y -1), (x + 1, y -1), (x -1, y + 1), (x + 2, y + 2), (x -2, y -2), (x + 1, y + 2) and (x -1, y -2).

The reader can easily determine the neighbors of (x, y) and the nodes at distance 2 from (x, y) in a hexagonal and squared grid (highlighted by grey areas in Fig. 1.)

We will use these sets of nodes to prove that the presented labelings are feasible. For the regularity of the grids, it is not restrictive to consider only nodes whose coordinates are lexicographically greater than (x, y) (otherwise it is enough to swap the role of the nodes).

In this paper we study the L(h, k)-labeling problem on the cellular grid C, proving that:

2h + 4k ≤ λ h,k (C) ≤ min(6h, 8k) if k ≤ h ≤ 2k; 3h + 2k ≤ λ h,k (C) ≤ min(4h, 11k) if 2k ≤ h ≤ 3k; λ h,k (C) = 3h + 2k if 3k ≤ h < 4k; λ h,k (C) = 2h + 6k if h ≥ 4k.
For the sake of completeness we study also the hexagonal grid H, showing that:

(0,0) (1,0) (0,1) (x,y) (x,y+1) (x+1,y+1) (x+1,y) (x,y-1) (x-1,y) (x-1,y-1) (0,0) (1,0) (0,1) (x,y) (x-1,y) (x,y+1) (x,y-1) (0,0) (1,0) (1,0) (x,y) (x+1,y) (x-1,y) (x,y+1) (x,y-1)
Fig. 1: Cellular, hexagonal and squared grids, where the nodes at distance 1 and 2 from the general node (x, y) are higlighted. Observe that in the hexagonal grid the coordinates of these nodes change according to the parity of x.

2h + k ≤ λ h,k (H) ≤ min(3h, 5k) if k ≤ h ≤ 2k; λ h,k (H) = 2h + k if 2k ≤ h < 3k; λ h,k (H) = h + 4k if h ≥ 3k;
Finally, we improve the results by Georges and Mauro (13) achieved as a special case of the more general L(h, k)-labeling problem on product of paths. Here we state only the results achieved in this paper; see Figure 2(a) for the complete results.

2h + 2k ≤ λ h,k (S) ≤ min(4h, 2h + 3k -1, 6k) if k ≤ h ≤ 2k; 2h + 2k ≤ λ h,k (S) ≤ min(3h, 2h + 3k -1, 8k) if 2k ≤ h ≤ 3k.
The really important parameter is the ratio h/k. This is the reason why, in the graphical summary of results depicted in Fig. 2(a), h is a function of k.

The L(h, k)-labeling problem on regular grids has already been studied in (3) for h = 2 and k = 1, and in [START_REF] Calamoneri | L(h, 1)-Labeling Subclasses of Planar Graphs[END_REF] for h = 0, 1, 2 and k = 1. Of course, the results obtained in this paper include as special case the previous ones. Also Griggs and Jin (17) have independently studied the same problem using completely different techniques.

In [START_REF] Van Den Heuvel | Graph Labelling and Radio Channel Assignment[END_REF] the distance between two labels i, j ∈ {0, 1, . . . , n -1} is defined as min{|i -j|, n -|i -j|}. Using this definition and restricting h and k to be integer, the authors study a variant of L(h, k)-labeling on triangular and squared grids (for a summary of their results see Fig. 2(b)). We will call L c (h, k)labeling problem this variant. The authors of (20) approach the L c (h, k)-labeling problem from a purely combinatorial point of view, with completely different techniques, for each integer h and k. Furthermore, observe that -despite the similarity of L(h, k)and L c (h, k)-labeling problems -it does not seem possible to shift from results in [START_REF] Van Den Heuvel | Graph Labelling and Radio Channel Assignment[END_REF] to ours (compare Fig. 2(a) and Fig. 2(b)).

Before proving one by one all bounds listed above, we state some general results that will be useful in the following.

Theorem 2.1 (13) Given any regular grid of the plane G with degree ∆ (∆ = 3, 4 or 6), the following conditions for λ h,k (G) hold:

λ h,k h k k k 2k 3k 4k 5k 6k 7k 8k 9k 10k 11k 12k 13k 14k 15k k 4/ 3k 2k 3k 4k 2 h + 6 k 3 h + 2 k 8k 6 h ∆=6 2 h + 2 k 6k 4 h ∆=4 5/ 2k 3 h 3 h ∆=3 2 h + k 5k 5/ 3k 4 h h + 4 k 11k 8k h + 6 k 2 h + 4 k 2 h + 3 k -1 2 h + 3 k -1
(a) Summary of the results: grey areas denote gaps between the upper and the lower bounds. Bold lines represent already known results.

. λ h,k (G) ≥ 2h + (∆ -2)k for any k ≤ h ≤ ∆k; b. λ h,k (G) ≥ h + 2(∆ -1)k for any h ≥ ∆k.
Thanks to the generality of its statement, Theorem 2.1 will be exploited in the following in order to obtain immediate lower bounds on λ h,k . Before concluding this section, we depict in Fig. 3 optimal L(1, 1)-, L(2, 1)and L(3, 1)-labelings of the regular grids that will be used in the following.

Cellular Graphs

Given a cellular grid with an optimal L(h, k)-labeling, for any node x we call a 1 , a 2 , . . . a 6 its neighbors arranged around x (see Fig. 4). It is not restrictive to assume that a 1 has the smallest label, and that L(a 2 ) < L(a 6 ).

In this section, we derive exact values of λ h,k (C) by proving coinciding upper and lower bounds, except for interval k ≤ h ≤ 3k, where bounds are slightly different. This labeling is feasible, indeed

k

≤ h ≤ 2k Theorem 3.1 If k ≤ h ≤ 2k, then 2h + k ≤ λ h,k (C) ≤ min (6h, 8k).
|L((x + 1, y)) -L((x, y))| ≥ h, |L((x, y + 1)) -L((x, y))| ≥ 3h and |L((x + 1, y + 1)) -L((x, y))| ≥ 2h, so the distance 1 constraint is always respected. Analogously, the distance 2 constraint is respected, too; indeed: |L((x + 2, y)) -L((x, y))| ≥ 2h, |L((x, y + 2)) - L((x, y))| ≥ h, |L((x + 2, y + 1)) -L((x, y))| ≥ h, |L((x + 1, y -1)) -L((x, y))| ≥ 3h, |L((x + 2, y + 2)) -L((x, y))| ≥ 3h and |L((x + 1, y + 2)) -L((x, y))| ≥ 2h, i.e.
the minimum distance between L((x, y)) and the label of any node at distance 2 from (x, y) is at least h ≥ k.

The span of the presented labeling is 6h. Observe that the resulting labeling is essentially identical to an optimal L(1, 1)-labeling of the cellular grid, where all values are multiplyied by h.

Consider now the following labeling function (see Fig. 5.b):

L((x, y)) = ((3x + 4y)mod 9)k.

Also this labeling is feasible:

|L((x + 1, y)) -L((x, y))| ≥ 3k, |L((x, y + 1)) -L((x, y))| ≥ 4k and |L((x + 1, y + 1)) -L((x, y))| ≥ 2k ≥ h.
Analogously, the distance between L((x, y)) and the label of any node at distance 2 from (x, y) is always ≥ k. The span of the presented labeling is 8k.

3 k ≤ h ≤ 2k.
Observe that this labeling is exactly the same as an optimal L(2, 1)-labeling, where each value has been multiplied by k. It follows that, when k ≤ h ≤ 2k, λ h,k (C) ≤ min (6h, 8k). Combining the results for the two labelings, it follows that, when k < h ≤ 5 3 k then λ h,k (C) ≤ 6h, and when

5 3 k ≤ h ≤ 2k then λ h,k (C) ≤ 8k. ✷ 3.2 2k ≤ h < 4k Theorem 3.2 If 3k < h < 4k, then λ h,k (C) = 3h + 2k; if 2k ≤ h ≤ 3k then 3h + 2k ≤ λ h,k (C) ≤ min(4h, 11k).
Proof: Analogously to the previous proofs, it is easy to check that both labelings are feasible, comparing L((x, y)) with the label of all nodes at distance 1 and 2 from (x, y). Furthermore, the span of the presented labelings are 4h and 11k, respectively. It follows that λ h,k (C) ≤ min(4h, 11k). Combining the results for the two labelings, it follows that when 2k < h ≤ 11 4 k then λ h,k (C) ≤ 4h and when

Upper bound. If 2k ≤ h ≤ 3k,
11 4 k ≤ k < 3k then λ h,k (C) ≤ 11k.
Observe that also the labeling in Fig. 6.a can be obtained from an optimal L(2, 1)-labeling by the following substitutions:

(0, 0), (1, k), (2, h), (3, h + k), (4, 2h), (5, 2h + k)
, (6, 3h), (7, 3h+k) and (8, 4h), while the labeling in Fig. 6.b can be obtained from an optimal L(3, 1)labeling multiplying each value by k. If 3k < h < 4k consider the labeling function defined by the following formula (see Fig. 7.a):

L((x, y)) = ((y mod 4 + x mod 3)mod 4)h + (x mod 3)k.

The produced coloring is a feasible L(h, k)-labeling and its span is 3h + 2k. Lower bound. Let be given a cellular graph with any optimal L(h, k)-labeling, 2k ≤ h < 4k. We consider a node a and all possible relative orders of the 7 distinct labels of a and its neighbors.

The proof is based on a systematic way of describing all the different cases in which a labeling of smaller span could be achieved. Then, the proof examines these cases and establishes that none of them could result in a feasible L(h, k)-labeling.

We prove -by contradiction -that

λ h,k (C) ≥ 3h+2k if 2k ≤ h < 4k. So, assume λ h,k (C) < 3h+2k.
For the nomenclature, we refer to Fig. 8. Let us focus on any node a of C. Seven cases can occur:

A B C D E F G A B C D E F G A B C D E F G
Case 5 -a -1: Suppose first that a has 5 neighbors whose labels are smaller than L(a) and only one with label bigger than L(a) (see Fig. 8.a). Hence, L(a) is in position

F while L(a 1 ) is in position A.
First of all, observe that two adjacent nodes a i and a i+1 cannot have their labels in consecutive positions (e.g. L(a i ) in C and L(a i+1 ) in D), otherwise the span would become too large, against the hypothesis λ h,k (C) < 3h + 2k. In the same way, two adjacent nodes a i and a i+1 cannot have their labels separated by only one label (e.g. L(a i ) in C and L(a i+1 ) in E) otherwise the span would be ≥ 3h + 2k. Therefore, L(a 2 ) can be neither in position B, nor in C. Since L(a 2 ) cannot be in G because L(a 2 ) < L(a 6 ), it follows that L(a 2 ) lies either in D or in E.

If L(a 2 ) is in D, then L(a 3 ) must be in G and hence L(a 6 ) must be in E. In this way, L(a 4 ) and L(a 5 ) would be in B and C, in some order, achieving in any case a too large span.

Lastly, if L(a 2 ) is in E, then L(a 6 ) > L(a 2 ) must necessarily be in G and L(a 3 ), L(a 4 ) and L(a 5 ) occupy positions B, C and D in some order, leading again to a too large span.

Then -under the hypothesis λ h,k (C) < 3h + 2k -this configuration never occurs. ) is larger than L(a), then the only possibility is that L(a 2 ) lies in F and L(a 6 ) in G. In this case, L(a 3 ), L(a 4 ) and L(a 5 ) must be in B, C and D in sopme order, leading to a too large span. Therefore, even this case never occurs when λ h,k (C) < 3h + 2k.

The cases in which a has either two neighbors or one neighbor whose labels are smaller than L(a) are symmetrical to the previous two cases and then omitted for the sake of brevity.

Cases 0 -a -6 and 6 -a -0: If the labels of all a's neighbors are larger (smaller) than L(a), then L(a) lies in A (G). These cases are both feasible in the hypothesis λ h,k (C) < 3h + 2k.

Case 3 -a -3: Finally, suppose that a has 3 neighbors whose labels are smaller than L(a) and 3 with label bigger than L(a) (see Fig. 8.c). In this case, L(a 1 ) is in position A and L(a) is in position D.

Since this case does not lead to any contradiction, it can occur when λ h,k (C) < 3h + 2k.

We have proven that only three cases can occur, i.e. the six labels of a's neighbors are: i. all smaller than L(a), ii. all bigger than L(a), iii. three smaller and three bigger than L(a). Now we want to study which values L(a) can assume and prove that no value is feasible, i.e. our hypothesis λ h,k (C) < 3h + 2k is false. To this aim, we move L(a) along interval [0, 3h + 2k) and see what happens. 0 ≤ L(a) < 2h -3k In this interval L(a) has all six labels of a's neighbors to its right. If L(x) was ≥ 2h -3k then the space to its right would be not sufficient to keep the span strictly smaller than 3h + 2k and, at the same time, to fit six labels at mutual distance k and at distance ≥ h from L(a).

2h -3k ≤ L(a) < h + 2k L(a) never lies inside this interval because there is not enough room to fit six labels to the right of L(a) and not enough room to fit three labels to the left of L(a). From the previous part of the proof, we know that other configurations are not possible.

h + 2k ≤ L(a) < 2h If L(a) lies in this interval, three labels are smaller than L(a) and three labels are bigger than it.

2h ≤ L(a) < h + 5k L(a) never lies here, for analogous reasons with respect to the second interval.

h + 5k ≤ L(a) < 3h + 2k In this interval L(a) has all six labels of a's neighbors to its left.

So, only three intervals are feasible for L(a): [0, 2h -3k), [h + 2k, 2h] and [h + 5k, 3h + 2k). In view of the generality of a, it follows that all seven considered labels must lie in these three intervals.

The second interval is h -2k wide; since h -2k < 2k when h < 4k, we deduce that inside this interval we can fit at most two labels at mutual distance k. It follows that the other two intervals must contain at least four labels and hence they must be at least 3k wide each. If 2k ≤ h < 3k this is a contradiction and the proof is concluded. If 3k ≤ h < 4k let us consider the general L(a) in the first (third) feasible interval. All six a's neighbors must have label bigger (smaller) than L(a), and only two can be in the second feasible interval while four are in the third (first) one. Let us focus on the labels L(a i ) and L(a j ) lying inside the second feasible interval, implying that the third (first) interval is at least h + k wide. If a i and a j are neighbors, then the second interval must be at least h wide, and this is a contradiction. If a i and a j have distance two in the cycle induced by a's neighbors, then consider the three nodes different from a i , a j and their common neighbor; they must all lie in the third (first) interval. If a i and a j have distance three in the cycle induced by a's neighbors, then there exist two pairs of neighbors whose labels all lie in the third (first) interval. Again, this configuration implies that the third (first) interval is at least h + k wide, possible if and only if h ≥ 4k, i.e. a contradiction. ✷

In the interval 2k ≤ h ≤ 3k, the achieved upper and lower bounds for λ h,k (C) are not coinciding. The following result ensures us that the lower bound is not tight, at least in a subinterval:

Theorem 3.3 If 2k < h < 5 2 k, then λ h,k (C) > 3h + 2k.
Proof: Let be given a cellular graph C with any optimal L(h, k)-labeling. We consider any node a of C and study all possible values that L(a) can assume, taking into account the positions of the labels of a's neighbors with respect to L(a). We assume, by contradiction, that λ h,k (C) ≤ 3h + 2k.

Case 0 -a -6: Let us suppose first that all the labels of a's neighbors lie to the right of L(a). It must hold that L(a 1 ) ≥ L(a) + h and that the biggest one among the labels of the a's neighbors is ≥ L(a) + h + 5k; the same label must also be ≤ 3h + 2k for our hypotesis. It follows that L(a) + h + 5k ≤ 3h + 2k, that is L(a) ≤ 2h -3k. Observe that the width of interval [0, 2h -3k] is strictly less than 2k when 2k < h < 5 2 k.

k 2 h -3 k 2 k h 2 h -2 k h + k 2 h -k h + 2 k 2 h 2 h + k h + 3 k 2 h + 2 k h + 4 k 3 h h + 5 k 3 h + 2 k

I II III IV V VI VII L(x)
Fig. 9: The feasible intervals in the proof of Theorem 3.3.

We found seven feasible intervals for the general L(a) (see Fig. 9) and we must assume that all the used labels must fall in someone of these intervals. From now on we will call big intervals the first one and the last one and small intervals all the other ones. These names derive from their widths.

Of course, for each general label L(a) there are at least six labels at distance h from L(a) itself, and mutually at distance k. Because of the widths of the considered intervals, we cannot fit more than two labels at mutual distance ≥ k inside the big intervals and no more than one label inside the small ones. So, the cardinality of the set U of used labels is no more than 9. It can also be seen that it is at least 9 because if we consider any label L(v) in a small interval and any other label L(w) in a neighbor small interval (e.g. L(v) in the second interval and L(w) in the third one), then

|L(v) -L(w)| ≤ h -k < h.
So L(v) eliminates two labels, that are too close, and must have other 6 labels for all v's neighbors. We can conclude that small intervals must contain one label each and that big interval must contain two labels each.

We will prove that there exists a position for L(a) such that L(a) cannot have other six labels at distance at least h and at mutual distance k inside the feasible intervals, proving that the hypothesis λ h,k (C) ≤ 3h + 2k is a contradiction, and hence λ h,k (C) > 3h + 2k. Let us focus on L(a) belonging to the forth interval, i.e. to [h + 2k, 2h].

If L(a) lies on the left extreme of the interval, i.e. L(a) = h + 2k, the label L(b) of each a's neighbour b must be either ≤ 2k or ≥ 2h + 2k. We can fit at most two labels in the first interval. The second, third and fifth intervals are forbidden since too close to L(a); we can fit at most one label in the sixth one and at most two labels in the seventh one. So, globally, we have room for at most five labels, that is not enough (see Fig. 9).

The same reasonings apply when L(a) coincides with the right extreme of the interval, i.e. L(a) = 2h. So, assume L(a) in the open interval (h+2k, 2h). Again, each L(b) must be ≤ L(a)-h < 2h-h = h and ≥ L(a) + h > h + 2k + h = 2h + 2k. It follows that we can fit at most four labels, two for each big interval (see Fig. 9). This concludes the proof. ✷

On the base of the previous theorem and of the continuity of function λ h,k (C) we conjecture that

λ h,k (C) = 4h if 2k ≤ h ≤ 5 2 k and λ h,k (C) = 2h + 5k if 5 2 k ≤ h ≤ 3k. 3.3 h ≥ 4k Theorem 3.4 If h ≥ 4k, then λ h,k (C) = 2h + 6k.
Proof:

Upper bound. Consider the labeled portion of cellular graph limited by bold lines in Fig. 7.b and replicate it in all directions. The definition of the labeling function is left to the interested reader. The produced coloring is a feasible L(h, k)-labeling and its span is 2h + 6k.

Lower bound. Let be given a cellular graph with an optimal L(h, k)-labeling. Let a be any node in C. By contradiction, let us assume λ h,k (C) < 2h + 6k.

Cases 1 -a -5 and 2 -a -4: There exist either one or two neighbors of a whose labels are smaller than L(a). With considerations very similar to those presented in the proof of Theorem 3.2 concerning adjacent nodes having their labels to the right of L(a), we deduce that we always get a span λ h,k (C) ≥ 2h + 6k; hence these cases cannot occur under the hypothesis λ h,k (C) < 2h + 6k.

Case 3 -a -3: There exist exactly three neighbors of a whose labels are smaller than L(a) and three neighbors whose labels are bigger than L(a).

Since L(a 1 ) is the minimum label, if L(a 2 ) < L(a) we achieve a too large span. It follows that L(a 2 ) > L(a). With similar reasonings, we deduce that L(a 1 ), L(a 3 ) and L(a 5 ) lie to the left of L(a) in some order, and L(a 2 ), L(a 4 ) and L(a 6 ) lie to right side.

Cases 4 -a -2 and 5 -a -1: These cases are symmetrical to cases 2 -a -4 and 1 -a -5, and hence they never occur.

Cases 0 -a -6 and 6 -a -0: These cases are both feasible in the hypothesis λ h,k (C) < 2h + 6k.

Up to now, we have proved that either all labels of a's neighbors lie to the same side with respect to L(a) or they are three to Upper bound. Observe that any labeling assigning to a node a label among 0 k 2k (respectively among h + 2k, h + 3k, h + 4k) and to all its neighbors labels h + 2k h + 3k h + 4k (respectively 0, k, 2k) is feasible and optimal. One of these labelings is shown in Fig. 10.c. ✷

h ≥ 3k

Squared Grids

In this section we study the L(h, k)-labeling problem on squared grids. Some partial results can be found in [START_REF] Georges | Generalized Vertex Labelings with a Condition at Distance Two[END_REF], where the L(h, k)-labeling problem on the product of paths is studied. As a special case of this more general problem, the authors prove the following:

Theorem 5.1 (13) If h ≥ 4h, then λ h,k (S) = h + 6k; if 3k < h < 4k, then λ h,k (S) = 2h + 2k; if k ≤ h ≤ 4k, then 2h + 2k ≤ λ h,k (S) ≤ 2h + 3k -1.
Here we improve the upper bound on λ h,k (S) in the interval where it is not tight. Fig. 11: Two optimally labeled portions of squared grid, when a. k ≤ h ≤ 3 2 k and when b.

k

≤ h ≤ 2k Theorem 5.2 If k ≤ h ≤ 2k, then 2h + 2k ≤ λ h,k (S) ≤ min (4h, 2h + 3k -1, 6k
3 2 k ≤ h ≤ 2k.
We can replicate pattern 0 h 2h 3h 4h horizontally. When we move to the next row, we shift it by two positions (see Fig. 11.a), obtaining in this way a vertical pattern 0 3h 2h 4h h. This labeling is the same as an optimal L(1, 1)-labeling.

Consider now the horizontal pattern 0 2k 4k 6k k 3k 5k. Each time we replicate it on successive rows, we shift it by two positions obtaining vertical pattern 0 3k 6k 2k 5k k 4k (see Fig. 11.b). Observe that this labeling can be obtained by replacing color i in an optimal L(2, 1)-labeling with color ik.

It is easy to see that these two L(h, k)-labelings are feasible and their span are 4h and 6k, respectively. So, in view of these reasonings and of Theorem 5.1, we have: λ h,k (S) ≤ min (4h, 2h + 3k -1, 6k). The first value is the best one when h ≤ (3k -1)/2, the second one is the best one when (3k -1)/2 ≤ h ≤ (3k + 1)/2, and the third value is the best one when h ≥ (3k + 1)/2. ✷

2k

≤ h < 4k Theorem 5.3 If 2k ≤ h ≤ 3k then 2h + 2k ≤ λ h,k (S) ≤ min(3h, 2h + 3k -1, 8k).
Proof: As in the previous proof, we only have to prove the upper bounds 3h and 8k. Two L(h, k)labelings can be obtained either by replicating vertical pattern 0 h + k 3h h 2h + k k 2h, as shown in Fig. 12.a, or by replicating vertical pattern k 6k 2k 7k 3k 8k 4k 0 5k, as shown in Fig. 12.b. Both patterns must be shifted down by three positions when changing column. Such labelings are both feasible and their spans are 3h and 8k, respectively. So, combining these results with those in Theorem 5.1, we have that the bound 3h is better than 8k when 2k ≤ h ≤ 8 3 k, while the second one is better than the first one when 8 3 k ≤ h ≤ 3k. Finally the bound 2h + 3k -1 is better than the other two in the interval 3k -1 ≤ h ≤ (5k + 1)/2, but it has positive length only when k ≤ 3. Observe that the labeling in Fig. 12.b can be obtained from an optimal L(2, 1)-labeling by the following substitutions: (0, 0), (1, k), (2, h), (3, h + k), (4, 2h), (5, 2h + k) and (6, 3h). ✷

As for cellular graphs, also for squared grids, in the interval 2k ≤ h ≤ 3k we do not achieve tight upper and lower bounds for λ h,k (S). Nevertheless, we conjecture that λ h,k (S) = 3h if 2k ≤ h ≤ 5 2 k and λ h,k (C) = h + 5k if 5 2 k ≤ h ≤ 3k. Observe that these values guarantee the continuity of function λ h,k (S).

Conclusions and Open Problems

In this paper we have studied the L(h, k)-labeling problem on cellular, hexagonal and squared grids.

Concerning cellular and hexagonal grids, for each value of k and h ≥ k we have obtained exact values of the span, except in a small interval, where we provide slightly different upper and lower bounds for λ h,k (C) and λ h,k (H). Concerning the squared grid, we have improved some previously known upper bounds, reducing the gap with the lower bound.

It is easy to see that the replication schemes presented for the upper bounds lead to simple distributed algorithms to label the whole grid in constant time, provided that each node knows its coordinates in the grid.

Three open problems arise from this work.

1. The first one is to prove (or disprove) our conjectures and close the gap between upper and lower bound when k ≤ h ≤ 3k and ∆ = 4 and ∆ = 6, and when k ≤ h ≤ 2k and ∆ = 3.

2. The second one is to understand if there exists some shifting method to go from the results collected in the present paper and those presented in [START_REF] Van Den Heuvel | Graph Labelling and Radio Channel Assignment[END_REF] (see Fig. 2) and vice-versa. Indeed, it is not surprising that the values of λ h,k under the 'cyclicity' assumption are bigger than ours, but it is not clear the reason why our λ h,k function is fragmented in a bigger number of segments.

3. Lastly, it would be interesting to study the L(h, k)-labeling problem for other (not regular) tilings, built with different shaped tiles (i.e. the edge-clique graph of the cellular graph, having degree 4, constituted by triangular and hexagonal tiles).

  Summary of the upper bounds for λ c h,k presented in[START_REF] Van Den Heuvel | Graph Labelling and Radio Channel Assignment[END_REF], where h and k are integer values.

Fig. 2 :

 2 Fig. 2: Summaries of bounds.

  a

2 L( 2 , 1 )-labeling of G 4 Fig. 3 :

 22143 Fig. 3: L(1, 1)-, L(2, 1)and L(3, 1)-labelings of regular grids.

Fig. 4 :

 4 Fig.4: A general node x and all its neighbors in a cellular graph.

Fig. 5 :

 5 Fig.5: Feasible labelings of a cellular graph when a. k ≤ h ≤4 3 k and when b.4 3 k ≤ h ≤ 2k.

4

 4 Fig.5: Feasible labelings of a cellular graph when a. k ≤ h ≤4 3 k and when b.4 3 k ≤ h ≤ 2k.

  consider the two following labeling functions (see Figs. 6.a and 6.b): L((x, y)) = ⌊((3x + 4y)mod 9)/2⌋h + ((3x + 4y)mod 9)mod 2)k and L((x, y)) = ((7x + 9y)mod 12)k.

Fig. 6 :

 6 Fig. 6: Two feasible labelings of a cellular graph when 2k ≤ h ≤ 3k. Their span is a. 4h and b. 11k.

Fig. 7 :

 7 Fig. 7: Two optimally labeled portions of cellular graph when a. 3k < h < 4k and b. h ≥ 4k.

Fig. 8 :

 8 Fig. 8: Some possible relative positions of L(a) and of labels of a' neighbors.

Cases 4 -

 4 a -2, 2 -a -4 and 1 -a -5: If a has 4 neighbors whose labels are smaller than L(a) and 2 with label bigger than L(a) (see Fig. 8.b), then L(a) is in E and L(a 1 is in A. With considerations similar to the previous ones, L(a 2 ) can be either in D or in F or in G. L(a 2 ) in D leads to a contradiction, as L(a 6 ) > L(a 2 ) and L(a 3 ) are in F and G in some order and, hence, L(a 4 ) and L(a 5 ) must lie in B and C. If L(a 2

Case 1 -a - 5 :

 15 If the label of one neighbor is to the right of L(a), then it must be L(a) ≥ h. On the other hand, the biggest one among the labels of the a's neighbors must be ≥ L(a) + h + 4k and, at the same time, ≤ 3h + 2k.It follows L(a) ∈ [h, 2h -2k]. The width of this interval is strictly smaller than k 2 since h < 5 2 k. Cases 2 -a -4, 3 -a -3, 4 -a -2and 5 -a -1: With reasonings identical to the previous ones, we deduce that if a has two neighbors whose label is smaller than L(a) then L(a) ∈ [h + k, 2h -k]. If the neighbors whose labels are smaller than L(a) are three, then L(a) ∈ [h + 2k, 2h]. When four labels are smaller than L(a) and two are bigger, then L(a) must belong to interval [h + 3k, 2h + k]. Lastly, when only one neighbor has its label bigger than L(a) then L(a) ∈ [h + 4k, 2h + 2k]. The width of all these intervals is strictly less than k 2 since h < 5 2 k. Case 6 -a -0: This case is symmetrical to the first one, and we obtain L(a) ∈ [h + 5k, 3h + 2k]. The width of this interval is < 2k when h < 5 2 k.

  the left and three to the right of L(a). Now, let us examine which values L(a) can assume. 0 ≤ L(a) < h + k If L(a) lies in this interval, we have labels of all a's neighbors to the right of L(a). h + k ≤ L(a) < h + 2k It is not possible to put L(a) in this interval because neither case 0 -a -6 (not enough space to the right of L(a)) nor case 3 -a -3 (not enough space to the left of L(a)) can apply. h + 2k ≤ L(a) ≤ h + 4k When L(a) is in this interval, we have three labels to the left of L(a) and three labels to the right of L(a).h + 4k ≤ L(a) ≤ h + 5k This interval cannot be used for the same reasones as the second interval.h + 5k ≤ L(a) ≤ 2h + 6k If L(a)is in this interval, then all neighbors of a have labels smaller than L(a), and it is feasible.Very similarly to the proof of Theorem 3.2, it is possible to show that the assumption λ h,k (C) < 2h+6k leads to a contradiction.

Fig. 10 :

 10 Fig. 10: Three optimally labeled portions of hexagonal grid, when a. k ≤ h ≤ 5 3 k, when b. 2k ≤ h ≤ 3k and when c. h ≥ 3k.

Theorem 4 . 3

 43 If h ≥ 3k, then λ h,k (H) = h + 4k.Proof: Lower bound. The claim directly descends from Theorem 2.1 b.

Fig. 12 :

 12 Fig.12: a. and b. two feasible L(h, k)-labelings when when 2k ≤ h ≤8 3 k and when 8 3 k ≤ h ≤ 3k.

  ).

	0	h	2h	3h	4h	0	2h	0	2k	4k	6k	k	3k	5k
	3h	4h	0	h	2h	3h	4h	3k	5k	0	2k	4k	6k	k
	h	2h	3h	4h	0	h	2h	6k	k	3k	5k	0	2k	4k
	4h	0	h	2h	3h	4h	0	2k	4k	6k	k	3k	5k	0
	2h	3h	4h	0	h	2h	3h	5k	0	2k	4k	6k	k	3k
	0	h	2h	3h	4h	0	h	k	3k	5k	0	2k	4k	6k
	3h	4h	0	h	2h	3h	4h	4k	6k	k	3k	5k	0	2k
				a.							b.
	Proof: In view of Theorem 5.1, we only have to prove the upper bounds 4h and 6k.

Hexagonal Grids

In this section we deal with the L(h, k)-labeling problem on hexagonal grids and we prove coinciding upper and lower bounds on λ h,k (H) for all possible values of k and h ≥ k, except when h is in the interval (k, 2k), in which case we provide sligthly different upper and lower bounds.

k

Proof:

Lower bound. The claim directly descends from Theorem 2.1 a.

Upper bound. Consider the portion of labeled grid limited by bold lines in Fig. 10.a. We get a feasible L(h, k)-labeling by replicating the shown pattern of labels, and the span is 3h. this labeling is defined by the following function:

if y is even and

The produced labeling is substantially identical to an L(1, 1)-labeling, where all values are multiplied by h.

We can also label the hexagonal grid by an optimal L(2, 1)-labeling, substituting each value i with ik. It is easy to see that such a coloring is feasible and its span is 5k. It follows that λ h,k (H) ≤ min (3h, 5k). Combining the results for the two labelings, it follows that when k ≤ h ≤ 5 3 k λ h,k (H) ≤ 3h and when

2k ≤ h < 3k

In order to make easier the reading of the proofs, in the rest of the paper we will not express anymore each label as explicit function of the coordinates of nodes in the grid, but we will refer to figures. The interested reader can easily deduce these functions from the depicted labelings. Upper bound. Consider the upper labeled portion of hexagonal grid limited by bold lines in Fig. 10.b and constituted by three hexagons. The L(h, k)-labeling is performed by replicating either this portion of labeled grid or its specular image (lower labeled portion in Fig. 10.b). It is straighforward to see that the produced L(h, k)-labeling is feasible and its span is 2h + k. ✷


Richard Palluel-Germain

Estelle Gilet

Julien Diard

Pierre Bessière

Bayesian Action-Perception loop modeling: Application to trajectory generation and recognition using internal motor simulation

Keywords: Sensorimotor loop, Bayesian modeling, Motor simulation PACS: 87.85.Ng

published or not. The documents may come

Bayesian Action-Perception loop modeling: Application to trajectory generation and recognition using internal motor simulation

Estelle Gilet, Julien Diard,

INTRODUCTION

Some people enjoy watching sport events, while others do not. The reason, the "why", is probably irrelevant to scientific curiosity; tastes differ, personalities and temperaments also. However, the manner, the "how" of these differences, is worthy of attention. Indeed, the general principles underlying the numerous and complicated processes involved in perception and (in this case) in perception of actions, are yet to be understood.

Recent observations suggest that perception of performed actions is based not only on sensory cues, but also on internal simulation of actions [1,[START_REF] Berthoz | The Brain's Sense of Movement[END_REF], especially if the action performed is part of the perceiving subject's action repertoire [START_REF] Calvo-Merino | [END_REF].

Instead of sport actions, which usually involve complicated articulated systems, we study here the perception-action loop involved in handwriting and reading. In the case of this simpler system, too, one finds evidence that the motor system is involved in letter recognition. Behavioral [4,5,6,7] and neuro-imaging studies [8,9] both support this idea.

For instance, Longcamp et al. have studied the activation of motor areas of the brain during writing and reading tasks [8]. They observed that a part of the motor cortex is significantly activated during both tasks. This is surprising for the reading task: although the subjects remain still, a motor area was activated. Another class of stimuli was presented: pseudo-letters, which are visually as complex as letters, but for which the subjects have no previous experience in writing. When such pseudo-letters were visually presented, the same motor area was not activated.

A much discussed interpretation of these observations is that perceiving a letter would entail a motor simulation of movements associated with the writing of that letter. This mechanism would, it is supposed, improve perceptual recognition.

The Bayesian Action-Perception (BAP) model is a model of the entire perception action loop involved in reading and writing cursive, isolated letters [START_REF] Gilet | Modélisation Bayésienne d'une boucle perception-action : application à la lecture et à l'écriture[END_REF]. It is composed of perception, action and internal representation components, and also includes a model of internal simulation of movements, in the form of a feedback loop. This loop starts from the letter representation, goes to generated trajectories and back to the letter representation: it it both simulated action and simulated perception.

In this paper, we first show how this proposed mechanism for internal simulation is defined mathematically. We then use it to compare perception processes with and without internal simulation of movements. The analysis of recognition performance indicates that, in easy situations, the internal simulation does not improve performance, whereas, in difficult situations, it helps in retrieving some of the missing information. This observation is the basis for an experimental prediction, which we detail.

BAP MODEL: ASSUMPTIONS AND MODEL ARCHITECTURE

We briefly here summarize the main components of the BAP model. Its global architecture is shown Fig. 1.

The model is articulated around internal representations C LV and C LP of letters, one for each considered letter L and writer W . These act as a pivot between the perception model and the action model.

Letter representation models are based on two main hypotheses. First, letters are encoded in the Cartesian reference frame (the workspace). This is an effector-independent representation and ensures motor equivalence, which is the fact that writing can be performed with any effector without preliminary learning and with recognizable resulting writing style [START_REF] Bernstein | The Co-ordination and Regulation of Movements[END_REF]. Second, letters are not encoded as complete trajectories, but are summarized as sequences of via-points along the trajectory. These via-points are placed at the starting position, the ending position, at cusps and points of the trajectory where either the vertical or horizontal velocity is zero (in other words, where the tangent is either vertical or horizontal). At each of these via-points, probability distributions about the X,Y positions and velocities are memorized.

The perception model relates the input (visual) trajectory V to the letter representation model, using a probabilistic term P(C LV | V ) that describes how via-points are extracted. The action model is composed of two parts. The first is a trajectory generation phase, which relates the letter representation to a complete prepared trajectory. It is centered on a P(P | C LP ) term, which uses the acceleration-minimization algorithm to provide intermediary trajectories between given via-points. The second part of the action model is an effector model P(E | P), which describes the geometric and kinematic models of the effector, in order to translate the generated trajectory P to effector commands.

The BAP model is translated, in the Bayesian Programming framework, into a joint probability distribution. However, the schema of Fig. 1 cannot be directly encoded as a probabilistic dependency structure. Indeed, the feedback loop does not correspond to any valid application of Bayes' rule. We circumvent this problem with duplication of nodes: the motor model is coupled with a simulated perception model. In other words, the generated trajectory is copied, with P(S | P), as an input to a simulated perception model P(C S | S).

The other technicality is that we include, in the model, λ coherence variables [START_REF] Pradalier | Expressing Bayesian Fusion as a Product of Distributions: Applications in Robotics[END_REF]. These serve as probabilistic switches, allowing us to deactivate sub-models explicitly during inference. For instance, this is used to compare perception with internal simulation (the whole model is activated) with perception without internal simulation (the action model and simulated perception are deactivated). The technical overhead is a duplication of nodes around the λ variables. For instance, C LP is duplicated into C LP and C P , and the P(P | C LP ) term described above becomes P(P | C P ), etc.

The resulting joint decomposition is as follows (see Fig. 1, right):

P(L W C LV C V C LP C P C LS C S V P E λ L λ V λ P λ S ) = P(L)P(W ) P(C LV | L W )P(C LP | L W )P(C LS | L W ) P(C V | V )P (
P(C 0:N L | L W ) = P(C 0 Lx | L W )P(C 0 Ly | L W )P(C 0 L ẋ | L W )P(C 0 L ẏ | L W ) N ∏ n=1 P(C n Lx | C n-1 Lx L W )P(C n Ly | C n-1 Ly L W )P(C n L ẋ | C n-1 L ẋ L W )P(C n L ẏ | C n-1 L ẏ L W ) .
For full mathematical definitions of the terms in this model, the reader should refer to Gilet's PhD thesis [START_REF] Gilet | Modélisation Bayésienne d'une boucle perception-action : application à la lecture et à l'écriture[END_REF].

BAP MODEL SIMULATION EXPERIMENTS

We now present experimental results using the BAP model: we simulate recognition tasks both with and without internal simulation of movements.

Experimental environment and parameter identification

We first set the parameters of the internal representation of letters, by a data collection procedure and learning phase. Using a Wacom Intuos 3 pen tablet, we asked 4 adults to write 40 sample trajectories for each of 22 letters, providing a complete database of 3,520 trajectories. We considered only letters without pen-up: we removed is, js, ts and xs (as in [START_REF] Wada | [END_REF]).

For each letter L, writer W and via-point position C n-1 Lx , C n-1 Ly and velocity C n-1 L ẋ , C n-1 L ẏ , we obtain the number of observations p i of each via-point position and velocity (at index N). These are then used to compute the parameters of Laplace succession laws for the terms of the form P(C n Lx | C n-1 Lx L W ) in letter representation models. With all the parameters of the model defined, Bayesian inference is used to automatically compute any probabilistic term of interest. A general-purpose probabilistic engine (ProBT© of ProBayes) is used for all of the following inferences.

Reading letters without internal simulation of movement

The cognitive task of letter recognition comprises identifying an input trajectory. In other words, the question is: "given a trajectory produced by a known writer, what is the letter?" Based on Bayesian inference in the BAP model, with only the perception and letter representation models activated, this amounts to:

P(L | [V 0:M x = v 0:M x ][V 0:M y = v 0:M y ][W = w][λ V = 1]) ∝ P([C LV = f (v 0:M x , v 0:M y )] | L [W = w]) ,
where V 0:M x ,V 0:M y is the input trajectory, w is the specified writer and f is the via-point extraction function. This probabilistic equation can be explained by an algorithmic equivalent. Indeed, the computation proceeds as if the via-points extracted from the input trajectory were matched to the representations learned. For each via-point and each possible letter, both positions and velocities are compared, using the memorized probability distributions: "if the letter was an a, what would be the probabilities of observing the positions and velocities of the first observed via-point?", etc.

When presented with input trajectories, the model computes the probability distribution over letters; it is usually very close to a delta (Dirac) probability distribution. Fig. 2 shows an example where the model correctly classifies the input trajectory as an l.

We ran a systematic experiment over our database of sample trajectories: out of our 40 trajectories, 35 were used for learning parameters and 5 were used for testing. We repeated this procedure using a classical K-fold cross-validation method. The result was a complete confusion matrix (which we do not detail here for lack of space). However, aggregating the correct classifications yields a performance indicator: overall, we obtained a satisfying correct recognition rate of 93.4%. Misclassifications arose due to the geometric similitude of some letters.

Reading letters with internal simulation of movements

We reproduced the same experiment as above in a different setting: we allowed the entire BAP model to function during the perception task. This is done by setting all λ variables to one and computing:

P(L | [V 0:M x = v 0:M x ][V 0:M y = v 0:M y ][W = w][λ V = 1][λ L = 1][λ P = 1][λ S = 1]) ∝ P([C LV = f (v 0:M x , v 0:M y )] | L [W = w])P([C LS = h(g(C LV ))] | L [W = w]
) . The result of this inference is the product of two terms: the first term is the same as previously, when the internal simulation of movements was deactivated. The second term is the result of the simulation loop: given the via-points extracted from the input trajectory, a trajectory is generated internally by the action model (function g), which is then analyzed by simulated perception (function h).

In the same setting as before, with our 40-trajectory database, we obtain a correct recognition rate of 90.2%. An analysis of the confusion matrices of both experiments (not shown) indicates that specific errors differ: some letters which were misclassified in Second, we have designed a preliminary psychology experiment in which participants have to recognize letters in various difficulty settings. The protocol is as follows. Letters are shown to the participant in a manner similar to the way trajectories are given to the model: since the model is given both sequence and velocity information, the participants see a moving point that follows the trajectory (contrary to just seeing the resulting trace, which would be a more natural task). The trajectory is either a complete letter or a truncated letter. In order to minimize the impact of particularities of the presented trajectories, we asked an elementary school teacher to provide reference trajectories to be used as stimuli (assuming that letters used to teach children are canonical in some way).

The truncated versions of trajectories have been designed by removing 25% of their points, either in the first or the second half of the trajectory, with a random starting position for deletion (protecting the first and last 5%, however). Deletions are treated as pen-ups: instead of showing a white dot on a black background, the dot turns black for the truncated portion, so that it is invisible. This guarantees that temporal properties of the trajectories are not affected.

The task is letter recognition, under two conditions: a control condition, and a condition in which a concurrent motor task is performed. Indeed, it has been demonstrated that a simple task like squeezing a ball tightly would be sufficient to affect, and possibly prevent, the use of internal motor simulation [14]. It is also known that motor interference influences letter recognition [7]. The expected observation is an interaction effect between condition and difficulty of the stimulus, as shown in Fig. 4.

CONCLUSION

We have presented some features of the BAP model, which is a model of the perceptionaction loop involved in recognition and production of handwritten characters. More precisely, we have focused on the internal simulation of movement loop. This is used to simulate and compare two cognitive tasks of letter recognition, depending on whether this loop is activated or not. Experimental results show that internal motor simulation does not improve performance for easy stimuli, whereas it does for difficult stimuli such as truncated trajectories. This finding generates a prediction, which is the basis of a psychology experimental protocol that is currently underway.

In conclusion, we wish to highlight another issue that could benefit from our modeling of the internal simulation of movements. This concerns what is called "online" and "offline" character recognition. Online character recognition is the situation we have treated so far: the input includes velocity and sequence information. This corresponds to tasks in which the observer sees the letter as it is being traced. It is arguably less natural than offline recognition, where the input is the resulting static trace.

Offline recognition can be tackled in two ways. On the one hand, it can be treated as a problem of a different nature than online recognition, with approaches such as common optical character recognition methods (OCR). On the other hand, offline recognition can be reduced to online recognition, after a first step that finds the time sequence of the trajectory, given the input static image. To illustrate this, consider the simpler problem of finding the starting point of the trajectory, given a sequence of pixels. We believe that motor knowledge could play a crucial role, by ruling out most points that would be perceptual candidates, but would not be associated with typical motor programs.

FIGURE 1 .

 1 FIGURE 1. Left: architecture of the BAP model. Right: corresponding acyclic graph for defining the joint decomposition, including λ variables used as probabilistic switches.

  V )P(P | C P )P(C P )P(E | P)P(S | P)P(C S | S) P(λ V | C LV C V )P(λ P | C LP C P )P(λ S | C LS C S )P(λ L | C LV C LP ) . Each term of the form P(C L | L W ) is itself structured, because a sequence of N viapoints is actually represented using a series of N variables C L = C 0:N L . Furthermore, each C n L is itself the conjunction of position C n Lx ,C n Ly variables and velocity C n L ẋ,C n L ẏ variables. This yields the following decomposition:

FIGURE 2 .

 2 FIGURE 2. X and Y position profiles (left and center), and the resulting input trajectory (an l), with extracted via-points shown as vectors (right).

FIGURE 4 .

 4 FIGURE 4. Experimental prediction of recognition performance as a function of stimulus difficulty (complete vs. truncated letters) and use of motor simulation (control vs. concurrent motor task).

To whom correspondence should be addressed.

ACKNOWLEDGMENTS

We thank J.-P. Orliaguet, E. Gentaz, J.-L. Schwartz, G. Baud-Bovy, J. Droulez and P. Baraduc for countless helpful discussions. This work has been supported by the BACS European project (FP6-IST-027140).

the reading task without simulated perception were recognized correctly using simulated perception, and vice versa. Overall, the misclassification rates are of the same magnitude in both conditions (90 vs. 93%).

Reading truncated letters

We also designed another experiment with a more difficult scenario. Instead of presenting complete trajectories as input, we designed truncated versions of trajectories, that is to say, trajectories where we erased a set of consecutive points.

In this context, we found several cases where reading without motor simulation would fail to recognize the input trajectory, whereas reading with motor simulation would succeed. We show in Fig. 3 some examples of truncated letters.

Consider for instance the letter g shown on the left of Fig. 3. Without internal simulation, the perception algorithm incorrectly classifies the input trajectory as a q. However, when internal simulation is activated, the motor model "fills the gap" by generating a complete trajectory joining the via-points; the resulting complete trajectory is analyzed back by simulated perception. This added information causes the perception algorithm to recognize the letter correctly as a g.

EXPERIMENTAL PREDICTION

We summarize our observations as follows: in the BAP model, in the easy case of complete letters, internal simulation of movements does not improve performance. In the harder case of truncated letters, however, internal simulation helps to correct misclassifications.

This is a hypothesis that we now pursue experimentally, in two directions. First, it would be fruitful to make this prediction more precise by quantifying the difference in performance in the case of truncated letters. This would require a more complete (or a reference) learning database, which is as yet unavailable.