Camino Balbuena

A construction of small regular bipartite graphs of girth 8

Keywords: Incidence matrices, Latin squares, cages, girth

Let q be a prime a power and k an integer such that 3 ≤ k ≤ q. In this paper we present a method using Latin squares to construct adjacency matrices of k-regular bipartite graphs of girth 8 on 2(kq 2q) vertices. Some of these graphs have the smallest number of vertices among the known regular graphs with girth 8.

Introduction

Throughout this paper, only undirected simple graphs without loops or multiple edges are considered. Unless otherwise stated, we follow the books by Godsil and Royle [START_REF] Godsil | Algebraic Graph Theory[END_REF] and by Lint and Wilson [START_REF] Van Lint And R | A course in Combinatorics[END_REF] for terminology and definitions.

Let G = (V (G), E(G)) be a graph with vertex set V = V (G) and edge set E = E(G). The girth of a graph G is the number g = g(G) of edges in a smallest cycle. The degree of a vertex v ∈ V is the number of vertices adjacent to v. A graph is called regular if all the vertices have the same degree. A cage is a k-regular graph with girth g having the smallest possible number of vertices. Simply counting the numbers of vertices in the distance partition with respect to a vertex yields a lower bound n 0 (k, g) on the number of vertices n(k, g) in a cage, with the precise form of the bound depending on whether g is even or odd.

n 0 (k, g) = 1 + k + k(k -1) + . . . + k(k -1) (g-3)/2 if g is odd; 2(1 + (k -1) + . . . + (k -1) g/2-1 )
if g is even.

(

) 1
As defined by Biggs [START_REF] Biggs | Algebraic Graph Theory[END_REF], the excess of a k-regular graph G is the difference |V (G)| -n 0 (k, g). A (k, g)-cage with even girth g and n 0 (k, g) vertices is said to be a generalized polygon graph. Generalized polygon graphs exist if and only if g ∈ {4, 6, 8, 12} [START_REF] Biggs | Algebraic Graph Theory[END_REF]. The question of the construction of graphs with small excess is a difficult one. When g = 6, the existence of a graph with n 0 (k, 6) = 2(k 2 -k + 1) vertices called generalized triangle, is equivalent to the existence of a projective plane of order k -1, that is, a symmetric ((n 0 (k, 6))/2, k, 1)-design. It is known that these designs exist whenever k -1 is a prime power, but the existence question for other values remains unsettled. Generalized quadrangles when g = 8, and generalized hexagons when g = 12 are also known to exist for all prime power values of k -1 [START_REF] Batten | Combinatorics of finite geometries[END_REF][START_REF] Godsil | Algebraic Graph Theory[END_REF][START_REF] Van Lint And R | A course in Combinatorics[END_REF].

Cages have been studied intensely since they were introduced by Tutte [START_REF] Tutte | A family of cubical graphs[END_REF] in 1947. Erdős and Sachs [START_REF] Erd Ös | Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl[END_REF] proved the existence of a graph for any value of the regularity k and the girth g, thus most of work carried out has been focused on constructing a smallest such graph [START_REF] Abreu | On (minimal) regular graphs of girth 6[END_REF][START_REF] Araujo | On upper bounds and conectivity of cages[END_REF][START_REF] Bannai | On finite Moore graphs[END_REF][START_REF] Benson | Minimal regular graphs of girth eight and twelve[END_REF][START_REF] Brinkmann | The smallest cubic graphs of girth nine[END_REF][START_REF] Exoo | A Simple Method for Constructing Small Cubic Graphs of Girths 14, 15 and 16[END_REF][START_REF] Feit | The non-existence of certain generalized polygons[END_REF][START_REF] Éger | On geometric constructions of (k, g)-graphs[END_REF][START_REF] Meringer | Fast generation of regular graphs and construction of cages[END_REF][START_REF] Wong | A smallest graph of girth 10 and valency 3[END_REF][START_REF] Wong | The smallest graph of girth 6 and valency 7[END_REF][START_REF] Wong | A regular graph of girth 6 and valency 11[END_REF][START_REF] Wong | Cages-a survey[END_REF]. Biggs is the author of an impressive report on distinct methods for constructing cubic cages [START_REF] Biggs | Construction for cubic graphs with large girth[END_REF]. For some time, Royle [26] kept a web-site in which all the cages known so far appear. More details about constructions on cages can be found in the survey by Wong [START_REF] Wong | Cages-a survey[END_REF], the survey by Holton and Sheehan [START_REF] Holton | The Petersen Graph, Chapter 6: Cages[END_REF] or on the more recent dynamic cage survey by Exoo and Jajcay [START_REF] Exoo | Dynamic Cage Survey[END_REF].

It is conjectured that cages with even girth are bipartite [START_REF] Pisanski | The 10-cages and derived configurations[END_REF][START_REF] Wong | Cages-a survey[END_REF]. A graph is bipartite if its vertex set V can be partitioned into two partite sets, V 1 and V 2 , such that any edge has one end in V 1 and the other in V 2 . If the vertices are ordered in such a way that the vertices of V 1 come first, then the adjacency matrix of a bipartite graph can be written in the form

A = 0 N N ⊤ 0 . ( 2
)
An incidence graph is a bipartite graph in which the elements of one part V 1 are declared as lines and the elements of the other part V 2 are declared as points. The terminology for incidence graphs is geometric.

A point and a line are said to be incident if they are adjacent, thus the submatrix N of ( 2) is called an incidence matrix of the bipartite graph. If the number of points and the number of lines coincide, then N is clearly a square matrix. An incidence matrix N defines a partial plane when -any line has at least two points, and -two points are incident with at most one line.

Consequently, two lines of a partial plane have at most one point in common. The corresponding bipartite graph is called the incidence graph of the partial plane, which clearly has even girth g ≥ 6. Thus for simplicity we shall say that the partial plane has girth g/2 if and only if the corresponding incidence graph has girth g. Let q be a prime power and k an integer such that 3 ≤ k ≤ q. In [START_REF] Balbuena | Incidence matrices of projective planes and other bipartite graphs of few vertices[END_REF], incidence matrices of (k, 6)bipartite graphs of order 2(kq-1) were given. In this paper we present a method to construct the incidence matrices of k-regular bipartite graphs of girth g = 8 on 2q(kq -1) vertices.

Position matrices

Let S denote a set of symbols and let A be a matrix whose elements are subsets of S. Given x ∈ S let P x (A) be a (0, 1)-matrix of the same dimension as A that satisfies

(P x (A)) ij = 1 if and only if x ∈ A ij .
Thus, P x (A) is called the position matrix of the symbol x in A. Suppose that S = {0, x 1 , . . . , x n }. The position matrices of all the symbols in A different from 0 give rise to the following (0, 1)-matrix P(A) called position matrix of A:

[P(A)] = [P x1 (A) • • • P xn (A)].
Let {A 1 , A 2 , . . . , A r } be a family of matrices of the same number of columns whose elements are subsets of S. Then the (0, 1)-matrix spanned by the position matrices of all of them

     P(A 1 ) P(A 2 )
. . .

P(A r )      =      P x1 (A 1 ) • • • P xn (A 1 ) P x1 (A 2 ) • • • P xn (A 2 ) . . . P x1 (A r ) • • • P xn (A r )      , (3)
is said to be the position matrix of the family F = {A 1 , A 2 , . . . , A r }. The following example shows two matrices of order 2×2 whose elements are subsets of S = {0, a, b} and the position matrix of them. From now on, if there is no confusion the 1-sets will be indicated as integers.

MATRICES SYMBOLS

a b A 1 a a 1 1 0 0 b b 0 0 1 1 A 2 {a, b} 0 1 0 1 0 0 {a, b} 0 1 0 1 (4)
As already mentioned in the Introduction, our main aim is to obtain incidence matrices of bipartite k-regular graphs of girth 8 with small excess. Such incidence matrices may be seen also as incidence matrices of partial planes which will be obtained by identifying row i of P z (A α ) as line i(α), and column j of P z (A α ) as point j(z), for any matrix A α ∈ F and z ∈ S -0. To achieve our goal we propose the following definitions. Definition 2.1 Let g ≥ 4 be an even number. A family of matrices F = {A 1 , A 2 , . . . , A r } of the same number of columns whose elements are subsets of a set of symbols S is said to have girth g if the position matrix of F is the incidence matrix of a bipartite graph of girth g.

Each matrix of (4) has girth g = ∞, and the two matrices A 1 , A 2 form a family of girth 8.

Let us recall that a Latin square of order q is a q × q matrix with entries from a set of q symbols such that each symbol occurs exactly once in each row and exactly once in each column. A Latin square has clearly girth g = ∞ because the position matrices of its elements are permutation matrices yielding the incidence matrix of a partial plane consisting in a set of parallel lines (since they have no common point).

In [START_REF] Balbuena | Incidence matrices of projective planes and other bipartite graphs of few vertices[END_REF] we introduced the notion of quasi row-disjoint matrices as follows.

Definition 2.2 [3]

Let A 1 and A 2 be two matrices of the same number of columns whose elements are subsets of a set of symbols S such that 0 ∈ S. A pair (x, y) with x, y ∈ S belongs to the cartesian product of any two rows

(A 1 ) i × (A 2 ) h if and only if (x, y) ∈ (A 1 ) ij × (A 2 )
hj for some j. Then A 1 and A 2 are said to be quasi row-disjoint if and only if the cartesian product of any two rows (A 1 ) i , (A 2 ) h contains at most one pair (x, x) ∈ (A 1 ) i × (A 2 ) h with x = 0.

The pair of matrices of the example (4) are quasi row-disjoint matrices. Moreover, in [START_REF] Balbuena | Incidence matrices of projective planes and other bipartite graphs of few vertices[END_REF] we have stated the following theorem which roughly speaking says that a family of r matrices is quasi row-disjoint if and only if its girth is at least 6.

Theorem 2.1 [START_REF] Balbuena | Incidence matrices of projective planes and other bipartite graphs of few vertices[END_REF] Let A 1 and A 2 be two matrices each one of girth at least 6 of the same number of columns and whose elements are subsets of a set of symbols S such that 0 ∈ S. Then A 1 and A 2 are quasi row-disjoint if and only the family {A 1 , A 2 } has girth at least 6.

In the next theorem we give a sufficient condition for a family of matrices to have girth at least 8.

Theorem 2.2 Let F = {A 1 , . . . , A r } be a set of r ≥ 2 quasi row-disjoint matrices of the same number of columns whose elements are subsets of a set of symbols S such that 0 ∈ S.

Let (A u ) i , (A v ) i ′ , (A w ) i ′′ denote any three mutually distinct rows of matrices A u , A v , A w ∈ F. Then the girth of F is at least 8 if the sets (A u ) i × (A v ) i ′ , (A v ) i ′ × (A w ) i ′′ , (A u ) i × (A w ) i ′′ contains at most two distinct pairs (x, x),
(y, y) with x, y = 0, x, y ∈ S.

Proof: Suppose (x, x) ∈ (A u ) i × (A v ) i ′ , x = 0.
Therefore the position matrix of F has the following entries equal to 1:

P x (A u )(i, j) = P x (A v )(i ′ , j) = 1, (5)
where P x (A u ) and P x (A v ) are the position matrix of the element x in A u and A v respectively. Recall that for any given matrix A α ∈ F and z ∈ S -0, row i of P z (A α ) is line i(α), and column j of P z (A α ) is point j(z). Consequently, ( 5) means that lines i(u) and i ′ (v) have point j(x) as a common point. Analogously, (y, y)

∈ (A v ) i ′ × (A w ) i ′′ , y = 0, is equivalent to: P y (A v )(i ′ , j ′ ) = P y (A w )(i ′′ , j ′ ) = 1,
or in other words, lines i ′ (v) and i ′′ (w) have the point j ′ (y) in common, with j ′ (y) = j(x) because y = x. Thus if there exists z = 0, z = x, y, such that (z, z) ∈ (A u ) i × (A w ) i ′′ , then lines i(u) and i ′′ (w) have the point j ′′ (z) in common, j ′′ = j, j ′ , yielding that the partial plane defined by the position matrix of F contains the triangle j(x)j ′ (y)j"(z). In other words, the position matrix of F is the incidence matrix of a bipartite graph of girth less than 8. ✷

Our immediate goal is to derive a method for constructing a family of matrices with girth 8, because the position matrix of this family will be the incidence matrix of a bipartite graph of girth 8.

Method

Throughout this work let [[n]

] denote the set of non negative integers {0, 1, . . . , n} and

(n]] = [[n]] \ {0}.
Let I n be the identity matrix and denote by (t × F )I n the matrix obtained from I n by replacing each one with a subset {t} ×

F of {t} × [[n]] for some t ∈ [[n]] and F ⊆ [[n]].
In the following theorem we demonstrate a method for obtaining a family of matrices with girth 8 using Latin squares. Theorem 3.1 Let q be a prime power, and let F q be the Galois field of order q. For each u, t ∈ F q , define the q × q matrix L u,t by L u,t (i, j) = i + uj + ut, i, j ∈ F q .

Then the following assertions hold:

(i) For all u, v ∈ F q \ {0}, u = v, and t, t ′ ∈ F q the matrices L u,t and L v,t ′ are quasi row-disjoint Latin squares with entries from [[q -1]].

(ii) For any given u, t ∈ F q , u = 0, the matrix L u,t × L u+u -1 ,t has q 2 distinct entries. Moreover, the position matrix of the family

{L u,t × L u+u -1 ,t : t ∈ F q }
is a (0, 1)-matrix of order q 2 × q 3 considering symbol (0, 0) different from 0, and it is the incidence matrix of a partial plane consisting in q 2 parallel lines with q points on each.

(iii) The family {L u,t × L u+u -1 ,t : u, t ∈ F q , u = 0} has girth 8 and its position matrix has order (q 3 -q 2 ) × q 3 and q ones in each row and q -1 ones in each column.

(iv) The position matrix of the family

{L u,t × L u+u -1 ,t : u, t ∈ F q , u = 0} ∪ { (t × [[q -1]])I q : t ∈ F q }
is the incidence matrix of a q-regular bipartite graph of girth 8 with q 3 vertices in each partite set.

Proof: (i) Clearly L u,t and L v,t ′ are q × q Latin squares on

[[q -1]].
Let us show that they are quasi row-disjoint. Otherwise, there exists i, i ′ j, j ′ ∈ F q with j = j ′ such that

L u,t (i, j) = L v,t ′ (i ′ , j), L u,t (i, j ′ ) = L v,t ′ (i ′ , j ′ ).
Equivalently, i + uj

+ ut = i ′ + vj + vt ′ , i + uj ′ + ut = i ′ + vj ′ + vt ′ .
Therefore u(j -j ′ ) = v(j -j ′ ) implying that u = v or j = j ′ , a contradiction in either case.

(ii) Note that L u+u -1 ,t is also a Latin square if u + u -1 = 0, otherwise L 0,t (i, j) = i. In either case it is very easy to check that L u,t and L u+u -1 ,t are orthogonal, which implies that L u,t × L u+u -1 ,t has q 2 distinct entries. Hence, the position matrix of the family {L u,t × L u+u -1 ,t : t ∈ F q } is a (0, 1)-matrix of order q 2 × q 3 by considering entry (0,0) different from 0.

Let us show now that for every i, i ′ , j, t, t ′ ∈ F q such that t = t ′ we have

(L u,t × L u+u -1 ,t )(i, j) = (L u,t ′ × L u+u -1 ,t ′ )(i ′ , j).
Otherwise we would have

i + uj + ut = i ′ + uj + ut ′ , i + (u + u -1 )j + (u + u -1 )t = i ′ + (u + u -1 )j + (u + u -1 )t ′ , implying t = t ′ ,
which is a contradiction. As a consequence, the position matrix of the set {L u,t × L u+u -1 ,t : t ∈ F q } has one unique entry equal to 1 in each column. Considering the rows of this (0, 1)matrix as lines and the columns as points, this is equivalent to say that each point belongs to a unique line. Thus, this (0, 1)-matrix is the incidence matrix of q 2 parallel lines with q points on each.

(iii) First, let us show that the position matrix of the family M = {L u,t × L u+u -1 ,t : u, t ∈ F q , u = 0} has q entries equal to 1 in each row and q -1 entries equal to 1 in each column. By (ii) the position matrix of each set {L u,t × L u+u -1 ,t : t ∈ F q } contributes with a unique 1 in each column, yielding that each column of the position matrix of M has q -1 entries equal to 1. Since each matrix L u,t × L u+u -1 ,t has q 2 distinct entries, then the q position matrices of symbols starting with the same x for any x ∈ F q contribute with one unique 1 in each row. So the position matrix of M has q entries equal to 1 in each row. Therefore, we conclude that the position matrix of M has order (q 3 -q 2 ) × q 3 and q entries equal to 1 in each row and q -1 entries equal to 1 in each column.

Next, let us show that the girth of M is at least 6. Otherwise, there exists u, v ∈ F q \ {0}, u = v and i, i ′ j, j ′ ∈ F q with j = j ′ for which

(L u,t × L u+u -1 ,t )(i, j) = (L v,t ′ × L v+v -1 ,t ′ )(i ′ , j), (L u,t × L u+u -1 ,t )(i, j ′ ) = (L v,t ′ × L v+v -1 ,t ′ )(i ′ , j ′ ).
This implies that L u,t and L v,t ′ are not quasi row-disjoint, a contradiction with item (i). Thus the family {L u,t × L u+u -1 ,t : u, t ∈ F q , u = 0} has girth at least 6. Next let us show that the girth is 8 applying Theorem 2.2. By way of contradiction assume that for three elements u, v, w of F q \ {0} there exist three pairwise distinct columns j, j ′ , j ′′ for which

(L u,t × L u+u -1 ,t )(i, j) = (L v,t ′ × L v+v -1 ,t ′ )(i ′ , j) (L v,t ′ × L v+v -1 ,t ′ )(i ′ , j ′ ) = (L w,t ′′ × L w+w -1 ,t ′′ )(i ′ , j ′ ) (L w,t ′′ × L w+w -1 ,t ′′ )(i ′′ , j ′′ ) = (L u,t × L u+u -1 ,t )(i, j ′′ ). (6)
Note that u, v, w must be three distinct elements because by (ii) each matrix L u,t × L u+u -1 ,t has q 2 distinct entries. Then from the equality between the first coordinates we have:

(u -v)j = i ′ -i + vt ′ -ut; (v -w)j ′ = i ′′ -i ′ + wt ′′ -vt ′ ; (w -u)j ′′ = i -i ′′ + ut -wt ′′ . Hence (v -u)j + (w -v)j ′ = (w -u)j ′′ . (7)
Moreover, from equalities between the second coordinates in [START_REF] Benson | Minimal regular graphs of girth eight and twelve[END_REF] and taking into account [START_REF] Biggs | Algebraic Graph Theory[END_REF] we obtain

(v -1 -u -1 )j + (w -1 -v -1 )j ′ = (w -1 -u -1 )j ′′ .
Multiplying this equality by uvw we get

w(u -v)j + u(v -w)j ′ = v(u -w)j ′′ . (8)
Multiplying ( 7) by w we also obtain

w(v -u)j + w(w -v)j ′ = w(w -u)j ′′ . (9)
Thus adding both equalities (8) and ( 9) we have

(u -w)(v -w)j ′ = (v -w)(u -w)j ′′ .
Taking into account that u, v, w are mutually distinct we get that j ′ = j ′′ which is a contradiction. Therefore M = {L u,t × L u+u -1 ,t : u, t ∈ F q , u = 0} has girth 8 as claimed.

(iv) By (iii) and applying Theorem 2.2, we only need to prove that for all u, v ∈ F q \ {0} with u = v, any three matrices L u,t × L u+u -1 ,t , L v,t ′ × L v+v -1 ,t ′ and (t ′′ × [[q -1]])I q have girth 8. Otherwise we would have

L u,t × L u+u -1 ,t (i, j) = L v,t ′ × L v+v -1 ,t ′ (i ′ , j) L v,t ′ × L v+v -1 ,t ′ (i ′ , j ′ ) ∈ (t ′′ × [[q -1]])I q (j ′ , j ′ ) L u,t × L u+u -1 ,t (i, j ′ ) ∈ (t ′′ × [[q -1]])I q (j ′ , j ′ ) Then L u,t (i, j) = L v,t ′ (i ′ , j) and L u,t (i, j ′ ) = L v,t ′ (i ′ , j ′ ) = t ′′
, meaning that L u,t and L v,t ′ are not quasi row-disjoint, contradicting item (i). Further, by (iii, we know that the position matrix of {L u,t × L u+u -1 ,t : u, t ∈ F q , u = 0} has q ones in each row and q -1 ones in each column. Since the rows of the position matrix of (t × [[q -1]])I q contributes with one additional one, then the result follows. ✷

To illustrate the method of Theorem 3.1, both the matrices provided by this theorem and their position matrix for the first case q = 2 are shown in Table 1. From now on, if there is no confusion an entry (x, y) will be denoted as xy. Thus this (0,1)-matrix is the incidence matrix of a 2-regular graph of girth 8, which consists of two cycles of girth 8. In Table 2 the matrices for q = 3 are also depicted. The corresponding position matrix is the incidence matrix of a 3-regular graph of girth 8 on 27 vertices in each partite set. Table 3 contains the matrices for q = 4. Their position matrix is the incidence matrix of a 4-regular bipartite graph on 64 vertices in each partite set.

MATRICES

SYMBOLS 00 01 10 11 L 1,0 × L 0,0 00 10 1 0 0 0 0 1 0 0 11 01 0 0 0 1 0 0 1 0 L 1,1 × L 0,1 10 00 0 1 0 0 1 0 0 0 01 11 0 0 1 0 0 0 0 1

(0 × [[1]])I 2 {00, 01} 0 1 0 1 0 0 0 0 0 0 {00, 01} 0 1 0 1 0 0 0 0 (1 × [[1]])I 2 {10, 11} 0 0 0 0 0 1 0 1 0 0 {10, 11} 0 0 0 0 0 1 0 1 Tab. 1: Case q = 2.
Let us call array of r symbols and n columns the matrix of order r

× n O r,n =      1 • • • 1 2 • • • 2 . . . . . . . . . r • • • r     
.

When r = n the array is denoted by O n . It is easy to see that the position matrix of O r,n is the incidence matrix of a partial plane consisting in r parallel lines, each one having n points. Using the position matrices of these arrays denoted by P(O r,n ) and applying Theorem 3.1, we now present the method for constructing the desired (k, 8)-bipartite graphs. Tab. 2: Matrices for the case q = 3. Tab. 3: Matrices for the case q = 4.

L 1,t × L 2,t L 2,t × L
L 1,t × L 0,t L 2,t × L 1,t L 3,t × L
Theorem 3.2 Let q be a power prime, and let F q be the Galois field of order q. For each u, t ∈ F q , u = 0, let L u,t be the matrix L u,t (i, j) = i + uj + ut, i, j ∈ F q , and let M be the position matrix of the family

{L u,t × L u+u -1 ,t : u, t ∈ F q , u = 0} ∪ { (t × [[q -1]])I q : t ∈ F q }.
Then the following assertions hold:

(i) The (0, 1)-matrix

M P(O q 2 ,q ) ⊤ ( 10
)
is the incidence matrix of a bipartite graph of girth 8 with q 3 + q 2 vertices in one partite set having degree q + 1, and q 3 vertices in the other partite set having degree q.

(ii) Let (L u,t × L u+u -1 ,t ) 0 denote the matrix obtained from L u,t × L u+u -1 ,t by replacing each entry 0x with 0 for all x ∈ F q . Let M 0 be the position matrix of the family

{(L u,t × L u+u -1 ,t ) 0 : u, t ∈ F q , u = 0} ∪ { (t × [[q -1]])I q : t ∈ F q , t = 0}. Then M 0 P(O q 2 -q,q ) ⊤ [0] ( 11
)
is the incidence matrix of a q-regular bipartite graph of girth 8 with q 3 -q vertices in each partite set.

(iii) Let k be an integer such that 3 ≤ k ≤ q -1 and let (L u,t × L u+u -1 ,t ) q-k denote the matrix obtained from L u,t × L u+u -1 ,t by replacing with 0 the entries 0y and (x, x + s) for all x, y, s ∈ F q for s = 0, . . . , q -1 -k. Let M q-k be the position matrix of

{(L u,t ×L u+u -1 ,t ) q-k : u = 1, . . . , k-1}∪{ (t×([[q-1]]\{t, t+1, . . . , t+q-1-k}))I q : t = 0}.
Suppose that the q columns of O kq-q,q are indexed by j ∈ F q . Let O * kq-q,q be the matrix obtained from O kq-q,q by changing for 0 the entries (i, -u 2 s) for all u = 1, . . . , k-1, i = (u-1)q+1, . . . , uq and s = 0, . . . , q -1 -k. Then

M q-k P(O * kq-q,q ) ⊤ [0] ( 12
)
is the incidence matrix of a k-regular bipartite graph of girth 8 with kq 2 -q vertices in each partite set.

Proof: (i) From Theorem 3.1, it follows that M is the incidence matrix of a bipartite graph of girth 8 with q 3 lines and q 3 points. Thus we need to prove that the q 2 columns of P(O q 2 ,q ) ⊤ can be added to M without decreasing the girth 8. It is readily seen that after adding these columns, the girth is at least 6, because by Theorem 3.1, for each u ∈ F q \ {0} the set {L u,t × L u+u -1 ,t : t ∈ F q , } consists of q 2 parallel lines. Thus suppose that (10) contains as a sub-matrix the incidence matrix of a cycle of length 6. Then there exists u, v ∈ F q \ {0} and i, i ′ , i ′′ , j, j ′ ∈ F q with u = v, i = i ′ and j = j ′ such that

(L u,t × L u+u -1 ,t )(i, j) = (L v,t ′ × L v+v -1 ,t ′ )(i ′′ , j), (L u,t × L u+u -1 ,t )(i ′ , j ′ ) = (L v,t ′ × L v+v -1 ,t ′ )(i ′′ , j ′ ).
From the equalities between their coordinates we obtain 12 21 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 11 20 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 22 0 10 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 12 21 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 20 0 11 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 10 22 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 21 0 12 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 11 20 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 10 22 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 21 12 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 11 0 20 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 22 10 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 21 12 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 20 11 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 10 0 22 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 12 0 21 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 20 11 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 22 10 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 {10, 11, 12} 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 {10, 11, 12} 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 {10, 11, 12} 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 {20, 21, 22} 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 {20, 21, 22} 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 {20, 21, 22} 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 Tab. 4: Case q = 3 for (ii) of Theorem 3.2. Incidence matrix of a (3,8)-graph on 48 vertices.

i -i ′ + u(j -j ′ ) = v(j -j ′ ), i -i ′ + (u + u -1 )(j -j ′ ) = (v + v -1 )(j -j ′ ). Hence u -1 (j -j ′ ) = v -1 (j -j ′ ), implying u = v or j = j ′ , a contradiction in either case. Further if (L u,t ×L u+u -1 ,t )(i, j) ∈ (t ′ ×[[q -1]]I q )(i ′′ , j), and (L u,t ×L u+u -1 ,t )(i ′ , j ′ ) ∈ (t ′ ×[[q -1]]I q )(i ′′ , j ′ ), then then i ′′ = j = j ′ which
(ii) This item follows directly from the fact that M 0 is a sub-matrix of M obtained by deleting the first q 2 columns, which correspond to the position of the symbols starting by 0. Hence M 0 has q 3 -q 2 columns. Moreover, the total number of rows of M 0 is the number of matrices L u,t × L u+u -1 ,t , (that is, (q -1)q) plus the number of matrices (t × ([[q -1]]))I q , t = 0, (a total of q -1) multiplied by q, that is, q(q 2 -q + q -1) = q 3 -q. Thus M 0 is a matrix of order (q 3 -q) × (q 3 -q 2 ). Since P(O q 2 -q,q ) ⊤ contributes with q 2 -q more columns, then [START_REF] Exoo | A Simple Method for Constructing Small Cubic Graphs of Girths 14, 15 and 16[END_REF] is a square matrix of order q 3 -q. Reasoning as in (iii) of Theorem 3.1, we obtain that [START_REF] Exoo | A Simple Method for Constructing Small Cubic Graphs of Girths 14, 15 and 16[END_REF] is the incidence matrix of a bipartite graph of girth 8, which has q 3 -q columns and q 3 -q rows both having q ones, so this item is valid. By way of example, both the matrices provided by this item (ii) and their position matrix for the case q = 3 are shown in Table 4. Thus this (0,1)-matrix is the incidence matrix of a 3-regular graph of girth 8 on 24 vertices in each partite set.

(iii) Note that ( 12) is a sub-matrix of (10), then it is the incidence matrix of a bipartite graph of girth 8. Moreover, M q-k is obtained from M by deleting the first q 2 columns which corresponds to the position matrix of symbols starting by 0, and by deleting also (q -k)(q -1)q columns corresponding to the symbols (x + s, x + 2s) for all s = 0, 1, . . . , q -1 -k which have been changed for 0. Then the total number of columns of M q-k is

q 3 -q 2 -(q -k)(q -1)q = kq(q -1).
The total number of rows of M q-k is given by the number of matrices (L u,t × L u+u -1 ,t ) q-k , u = 1, . . . , k -1, t ∈ F q , plus the number of matrices (t × ([[q -1]] \ {t, t + 1, . . . , t + q -1 -k}))I q : t = 0, t = 0, (a total of q -1) multiplied by q, that is (k -1)q 2 + (q -1)q = kq 2 -q.

Thus M q-k is a matrix of order (kq 2 -q) × (kq 2 -kq). Since P(O * kq-q,q ) ⊤ contributes with kq -q more columns, then ( 12) is a square matrix of order kq 2 -q.

To finish the proof of this item, we only need to show that [START_REF] Exoo | Dynamic Cage Survey[END_REF] has k ones in each row and k ones in each column. To see this, let us show that given a fixed s = 0, 1, . . . , q -1 -k, the entries (y, y + s) for all y ∈ F q , are in the same column of each matrix L u,t × L u+u -1 ,t . Suppose L u,t × L u+u -1 ,t (i, j) = (y, y + s), that is i + uj + ut = y, and i + (u + u -1 )j + (u + u -1 )t = y + s.

Then u -1 (j + t) = s, which implies j = us -t. Thus our claim is true since the symbols (y, y + s) are placed in the same column us -t of the matrix L u,t × L u+u -1 ,t . Therefore, after changing for 0 the symbols 0x and (y, y + s) for all x, y ∈ F q and for all s = 0, . . . , q -1 -k we obtain a new matrix having k entries different from 0 in the rows i such that i + u 2 = 0, and in the remaining rows k -1 entries different from 0. Since in the rows i of P(O * qk-q,q ) ⊤ such that i + u 2 s = 0 there is a 1 by hypothesis, then P(O * qk-q,q ) ⊤ contributes with one additional entry equal to 1 in the same rows as those having k -1 entries different from 0. Hence ( 12) is a square matrix of order kq 2 -q having k ones in each row and clearly in each column.

By way of example, both the matrices provided by this item (iii) and their position matrix for the case q = 4 and k = 3 are shown in Table 5; and the corresponding matrices for q = 5 and k = 3 are shown in Table 6. Thus, these (0,1)-matrices are the incidence matrix of a 3-regular graph of girth 8 on 44 vertices in each partite set for q = 4 and 70 vertices in each partite set for q = 5. ✷

Conclusion

For q a prime power and 3 ≤ k ≤ q we have presented a method providing the incidence matrices of k-regular bipartite graphs of girth 8 with kq 2 -q vertices in each partite set. Thus if n(k, 8) denotes the order of a (k, 8)-cage, it follows from (1) that 2k(k 2 -2k + 2) ≤ n(k, 8) ≤ 2q(kq -1).

Hence the q-regular bipartite graphs constructed in this work have an excess of 4q 2 -6q. And the (q -1)regular bipartite graphs have an excess of 8q 2 -20q + 10.

As regards to known upper on n(k, g), Lazebnik, Ustimenko and Woldar [START_REF] Lazebnik | New upper bounds on the order of cages[END_REF] gave the following result: Let k ≥ 2 and g ≥ 5 be integers, and let q denote the smallest odd prime power for which k ≤ q. Then, n(k, g) ≤ 2kq

3 4 g-a , (13)
where a = 4, 11/4, 7/2, 13/4 for g ≡ 0, 1, 2, 3 (mod 4), respectively. According to [START_REF] Feit | The non-existence of certain generalized polygons[END_REF], n(k, 8) ≤ 2kq 2 , therefore the graphs provided by our method also improve this result for g = 8. A construction giving this upper bound (13) for g = 8 appeared for the first time in [START_REF] Lazebnik | New constructions of bipartite graphs on m, n vertices with may edges and without small cycles[END_REF] and was used later in [START_REF] Furedi | Graphs of prescribed girth and bi-degree[END_REF] and probably, the simplest exposition of it is in Section 2.4 of [START_REF] Lazebnik | General properties of some families of graphs defined by systems of equations[END_REF]. In [START_REF] Éger | On geometric constructions of (k, g)-graphs[END_REF], (q, 8)-graphs with 2q(q 2 -2) vertices were constructed using geometrical techniques. But for regularities k < q the graphs constructed in this paper have the smallest number of vertices among the known regular graphs with girth 8. SYMBOLS 10 12 13 20 21 23 30 31 32 0 10 20 30 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 31 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 32 0 12 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 23 13 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 10 0 30 20 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 32 0 12 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 23 0 0 13 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 20 30 0 10 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 31 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 12 0 32 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 13 0 0 23 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 30 20 10 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 12 0 32 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 13 23 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 21 32 13 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 30 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 10 31 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 12 0 20 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 21 0 13 32 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 30 0 0 23 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 31 10 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 12 0 20 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 32 13 0 21 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 23 0 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 10 31 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 20 0 12 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 13 32 21 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 23 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 31 10 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 20 0 12 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 {10, 12, 13} I4 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 {20, 21, 23} I4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 {30, 31, 32} I4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 Tab. 5: Case q = 4 for k = 3 of Theorem 3.2 (iii). Incidence matrix of a (3,8)-graph on 88 vertices. Tab. 6: Matrices for q = 5 and k = 3 according to Case (iii) of Theorem 3.2.

  is also a contradiction.

	MATRICES		SYMBOLS
	10	11	12	20	21	22
	0

Acknowledgements

I would like to thank the anonymous referees for their suggestions and for their valuable comments.

This research was supported by the Ministry of Science and Innovation, Spain, and the European Regional Development Fund (ERDF) under project MTM2008-06620-C03-02/MTM.

1365-8050


Louis H Kauffman
email: kauffman@uic.edu

Pedro Lopes
email: pelopes@math.ist.utl.pt

Determinants of Rational Knots

Keywords: Rational knots, colorings, determinants of knots, checkerboard graphs, spanning trees

We study the Fox coloring invariants of rational knots. We express the propagation of the colors down the twists of these knots and ultimately the determinant of them with the help of finite increasing sequences whose terms of even order are even and whose terms of odd order are odd.

Introduction

A knot is an embedding of the circle into three-dimensional space. Knots that are obtained from one another by continuous deformation of their embeddings are said to be equivalent. The classification of these equivalence classes is still an open problem. In order to study a knot one usually resorts to projecting it into a plane in such a way that the singularities of the projection look locally like the crossing of two line segments. At these crossings the line that goes under in the embedding is broken in the projection giving rise to the so-called knot diagram (see Figure 1). Knot diagrams are planar networks of arcs. The Reidemeister moves ( [START_REF] Kauffman | Knots and physics[END_REF]) are defined to be local transformations on the diagrams. The Reidemeister theorem states that, given two diagrams, the knots corresponding to these diagrams are equivalent if and only if these diagrams are obtained from one another by a finite number of the Reidemeister moves. Whenever a mathematical object is associated to a knot diagram in such a way that this object remains the same when Reidemeister moves are performed on the diagram, then this object is called a knot invariant. By Reidemeister's theorem, a knot invariant is an invariant of the equivalent class of the knot. The knot invariant we will be concerned with in this article is called Fox coloring ( [START_REF] Kauffman | Knots and physics[END_REF]).

We now elaborate on Fox colorings. Given any knot diagram of the knot under study, the arcs of the diagram stand for algebraic unknowns and the equation "the sum of the under-arcs equals twice the over-arc" is read off at each crossing (see Figure 2). The system of equations so obtained has a matrix of coefficients over the integers.

112 Louis H. Kauffman

and Pedro Lopes

The equivalence class of this matrix under elementary operations on matrices (as listed on page 50 of [START_REF] Lickorish | An introduction to knot theory[END_REF]) over the integers constitutes an invariant of the knot under study. The elementary operations on matrices over the integers are standard row and column operations plus enlarging the matrix by a row and column of zeros except for the diagonal entry of 1, or removing such a row and column.

Other invariants of the knot stemming from this one are the following. The invariant factors of the equivalence class of the matrix; any first minor (also known as the determinant of the knot); the number of solutions of the system of equations over the integers modulo r (also known as the number of Fox r-colorings). The minimum number of distinct colors it takes to represent such a nontrivial solution (i.e., a solution such that at least two unknowns take on different values) across the diagrams that represent this knot, is a subtle and interesting invariant ( [START_REF] Kauffman | On the minimum number of colors for knots[END_REF]).

Some of these invariants are easy to calculate and, at the same time, seem to be effective enough to be interesting (number of colorings, see [START_REF] Lopes | Quandles at finite temperatures I[END_REF], [START_REF] Dionísio | Quandles at finite temperatures II[END_REF]). Others are hard to determine and related to elusive conjectures (minima of colors, see [START_REF] Harary | Knots and graphs I. Arc graphs and colorings[END_REF], [START_REF] Kauffman | On the classification of rational tangles[END_REF], [START_REF] Asaeda | Kauffman-Harary conjecture holds for Montesinos knots[END_REF], [START_REF] Kauffman | On the minimum number of colors for knots[END_REF]).

In [START_REF] Dionísio | Quandles at finite temperatures II[END_REF] a brute force approach was used: a knot diagram was introduced into a computer program that converted it into a coloring system of equations. Then, candidates for solutions of the coloring system of equations were tested. Finally, the actual solutions were counted ( [START_REF] Dionísio | Quandles at finite temperatures II[END_REF]).

In [START_REF] Kauffman | On the minimum number of colors for knots[END_REF] the focus was on a particular class of knots and a general formula was obtained for the number of colorings. For this class of knots, a Gaussian reduction of the systems of equations was developed by inspection of the knot diagram under study. Some unknowns were enough to express the rest of them. This led to the development of a black-box approach to diagrams. What is inside a given part of the diagram, the so-called blackbox, is ignored. All that matters is that there is a "color input" and a "color output" to this part of the diagram. By calculating the propagation of the "color input" down the black-box, the "color output" is specified in terms of the "color input" and the "size" of the black-box. Finally we equate this "color output" to the "color input" in order to obtain the coloring system of equations and other invariants like the determinant of the knot (we elucidate this below, see Section 2). This technique can then be applied to more complicated situations. Whenever a knot diagram involves some combination of these black-boxes, we use this approach, thus reducing the number of unknowns and the number of equations we have to work with.

A particular situation comes up with a "twist", which is obtained by twisting two line segments an assigned number of times (see the left-hand side of Figure 3 for a particular twist). Since the propagation of colors down a twist is well-understood (see [START_REF] Kauffman | On the minimum number of colors for knots[END_REF]) and since rational knots (see Section 3 below) can be regarded as special stackings of twists , we look into calculating the propagation of colors down the twists of a rational knot. We denote R(n 1 , n 2 , . . . , n N ) the rational knot with n i crossings on the i-th twist. The formulas we obtain involve three polynomials in the number of crossings on each twist, the n i 's. These polynomials are closely related to the set of increasing sequences of integers from {1, 2, . . . , N } whose terms of even order are even and whose terms of odd order are odd, call this set IEO[N ]. The coefficients of these polynomials are all equal to 1. In each monomial the power of each n i is either 1 or 0. One of the polynomials, call it p N , has as many monomials as there are sequences in IEO[N ]. As for the other two, one of them, call it p e N , is obtained from p N by deleting the monomials which are products of an odd number of n i 's. The other polynomial, call it p o N , equals p Np e N . Moreover, the relation between the monomials of p N and the sequences in

IEO[N ] is as follows. If (u 1 , u 2 , . . . , u k ) ∈ IEO[N ], (1 ≤ k ≤ N ), then n u1 n u2 . . . n u k is a monomial in p N (

and conversely).

We prove the following result in Section 6.

Theorem 1.1 Given a non-negative integer

I, consider 2I + 1 integers n 1 , n 2 , . . . , n 2I , n 2I+1 .
1. The coloring system of equations of R(n 1 , n 2 , . . . , n 2I ) and its determinant are, respectively

(b -a)p e 2I = 0 and det R(n 1 , n 2 , . . . , n 2I ) = p e 2I .
2. The coloring system of equations of R(n 1 , n 2 , . . . , n 2I , n 2I+1 ) and its determinant are, respectively

(b -a)p o 2I+1 = 0 and det R(n 1 , n 2 , . . . , n 2I , n 2I+1 ) = p o 2I+1 .
This article is organized as follows. In Section 2 we introduce the background material and the notion of blackbox in the context of knot diagrams and colorings. In Section 3 we introduce the diagrammatics of rational knots. In Section 4 we calculate the coloring equation and the determinant of a few particular rational knots and single out patterns in their expressions which involve the polynomials referred to above. The polynomials are formally introduced in Section 5 and relations among them are proved. In Section 6 we prove Theorem 1.1 stating the form of the coloring equation and the determinant of a rational knot R(n 1 , . . . , n N ). In Section 7 we give an alternative approach to the determinants of rational knots and links by counting the spanning trees in their checkerboard graphs. This leads to a simple recursion formula for these determinants. The outputs of these formulas are identical to the results of Theorem 1.1

The Black-box Approach

We introduce some of the objects we will be dealing with in this article.

Definition 2.1 (Twist) A twist is a portion of a diagram which is given by σ n

1 where σ 1 is a standard generator of the braid group on two strands, B 2 (see [START_REF] Birman | Braids, links, and mapping class groups[END_REF]). The left hand-side of Figure 3 depicts σ 3 1 . "the sum of the under-arcs equals twice the over-arc". Furthermore, these equations and their solutions will be considered modulo r for given integers r > 1.

Definition 2.2 (Fox Coloring, [6]) A Fox coloring of a knot or tangle diagram is the assignment of integers to the arcs of the diagram such that at each crossing twice the integer assigned to the over-arc equals the sum of the integers assigned to the under-arcs meeting at this crossing, see

In the present work, we do not specify this modulus so that the formulas we obtain are as general as possible. Moreover, in the literature, the modulus is often taken to be a prime number. Here we allow the modulus to take on any composite integer value greater than 2, r ∈ Z + \ {1, 2}.

Definition 2.3 (Coloring System of Equations)

A Coloring System of Equations (CSE) of a knot diagram is the system of equations assigned to the knot diagram by regarding the arcs as unknowns and reading the equation 2b = a + c at each crossing (see Figure 2). Usually we solve these CSE's over the integers mod r, for some modulus r. The solutions of this CSE are the Fox colorings of the knot diagram with respect to the specified modulus. The Coloring Matrix (CM) of the knot diagram is the matrix of the coefficients of the CSE of this knot diagram. This is a square matrix since any diagram of a non-trivial knot has as many arcs as crossings. Any matrix obtained from the CM by elementary matrix operations - [START_REF] Lickorish | An introduction to knot theory[END_REF], page 50 -is also known as a coloring matrix . The system of equations associated to this new matrix is also a coloring system of equations for this knot. Proposition 2.1 Consider a modulus and a knot K. The number of Fox colorings in this modulus for any knot diagram of K is an invariant of the knot. Also, the absolute value of any first minor of the coloring matrix is an invariant of the knot known as the "determinant of the knot" and denoted det K.

Non-trivial colorings occur only for those moduli which are not relatively prime to the determinant of the knot.

Proof: See [START_REF] Kauffman | Knots and physics[END_REF]. ✷

Consider the trefoil knot regarded as the closure of σ 3 1 (∈ B 2 ) (see left hand-side of Figure 3). Endowing this diagram with a Fox coloring amounts to assigning integers to the arcs of the diagram and making sure that, at each crossing, the rule "2b = a + c" holds (in a given modulus). On the other hand, working our way down from the top of the braid in the left hand-side of Figure 3, we can regard each crossing as a rule that sets the emerging under-arc equal to twice the over-arc minus the in-coming under-arc.

We believe the assignments to arcs in Figures 3 and4 to be self-explanatory, Figure 3 for the n = 3 case and Figure 4 for the general n case (see also [START_REF] Kauffman | On the minimum number of colors for knots[END_REF]). Eventually the bottom arcs are reached and in order to obtain a coloring from this assignment, the color obtained at the bottom right arc has to equal b and the color at the bottom left arc has to equal a. These two equations are equivalent to each other and to:

n(b -a) = 0 0 = 0.
The determinant of the trefoil is then 3, which is the n = 3 case. We kept here the 0 = 0 equation for consistency. In the sequel we will drop it whenever we arrive at a situation where two equations in a system are equivalent. It was not the specifics at each crossing of the braid that allowed us to write down the coloring system of equations (and consequently the determinant of the knot) but the fact that the colors at the bottom strands are expressed in a linear fashion in terms of the colors at the top strands and the number of crossings. This led us to the black-box approach which is depicted on the right-hand side of Figure 3 The following Proposition summarizes the situation so far and includes a formula for the calculation of the number of colorings for a T (2, n) knot. A proof can be found in [START_REF] Kauffman | On the minimum number of colors for knots[END_REF]. a). This ensemble stands for a twist equipped with a Fox-coloring induced by the input a and b on the top. We denote this the Black Box (for the twist) when we ignore the color input. Otherwise we denote it the Black Box (for the twist) endowed with a Fox coloring.

Rational Knots and Their Representation

In this section we describe the diagrammatic representation of rational knots that fits our needs herein. A formal introduction to this material may be found in [START_REF] Kauffman | On the classification of rational knots[END_REF] and [START_REF] Kauffman | On the classification of rational tangles[END_REF].

Rational Knots as Special Closures of 4-Strand Braids.

A rational knot can be regarded as a special composition of twists using the generators σ 1 and σ 2 as well as their inverses, from the braid group on four strands B 4 .

For each positive integer N , we choose N integers n 1 , n 2 , . . . , n N and form the braid:

σ n1 2 σ n2 1 . . . σ nN-1 2 σ nN 1 ,
for even N, and

σ n1 2 σ n2 1 . . . σ nN-1 1 σ nN 2 ,
for odd N.

See Figure 5 for illustrating examples with N = 4 and N = 5 (ignore the broken lines for the moment). We elucidate the sign convention below. Finally, a special closure of these braids is performed in order to obtain the corresponding rational knot which we have been denoting R(n 1 , n 2 , . . . , n N ). These plat closures are depicted by the broken lines in Figure 5. We believe Figure 5 is now self-explanatory for the N = 4 and N = 5 cases, elucidating the general case. We note that the special closure in the bottom for the even N case (called denominator closure) is different from the odd N case (called numerator closure).

n 1 n 1 n 2 n 2 n 3 n 3 n 4 n 4 n 5

Checkerboard shadings and sign convention for crossings

The signs at crossings we define for diagrams of rational tangles are consistent with the checkerboard shading of knot diagrams in the way defined below.

Definition 3.1 (Checkerboard shadings and sign conventions) A checkerboard shading of a knot diagram is the shading of some regions of the knot diagram such that the four regions meeting at each crossing have the following property. Whenever two of these four regions share a common boundary (which is an arc of the diagram), then

one of them is shaded and the other one is not. The signs at crossings are then induced by the checkerboard shading in the following way. Consider a crossing of the diagram along with its over-arc. Rotate this over-arc counterclockwise about the crossing. If the region swept out by the over-arc is the shaded region then the crossing is positive. Otherwise it is negative (see Figure 6 and7). As a rule, we do not shade the unbounded region around the diagram. See Figure 7 for the illustrative examples of the sign convention and its connection to the checkerboard shadings.

R(4, -3) R(4, 3)

The Coloring System of Equations of a Rational Knot: Particular Examples

In this section we will be always referring to a rational knot with N given twists (1 ≤ N ≤ 5) where the i-th twist has n i crossings, R(n 1 , n 2 , . . . , n N ). The signs of the n i 's are induced by the checkerboard shading of the diagram where the unbounded exterior of the diagram is not shaded, in the way described by Definition 3.1. The general look of the diagrams of these knots that we will be using in the sequel, materializes into the left-and right-hand sides of Figure 5 for N = 4 and N = 5, respectively. We usually do not draw the rightmost strand for the rational knots nor do we perform all the plat closures (as we did in Figure 5), in order to graphically bring out the colors the arcs at the bottom are receiving. Nonetheless, the relevant closure of R(n 1 , n 2 , . . . , n N ) is to be assumed. In particular, in Figure 8 the arc assigned m 2 should be connected to the arc assigned r 2 and the arc assigned l 2 should be connected to the arc assigned a, following the pattern established in Figure 5 (even case).

4.1

The rational knots R(n 1 ) through R(n 1 , n 2 , n 3 , n 4 , n 5 ).

In the next subsections we work out the coloring system of equations and the determinant of the indicated rational knots.

R(n 1 ).

R(n 1 ) is the torus knot T (2, n 1 ). As was seen above (Proposition 2.2), the coloring system of equations reduces to:

(b -a)n 1 = 0 and the determinant is det R(n 1 ) = n 1 . 4.1.2 R(n 1 , n 2 )
See Figure 8. Using the black-box approach developed above, we have, at the cross-section (l 1 , m 1 , r 1 ):

l 1 = b, m 1 = b + (b -a)n 1 , r 1 = a + (b -a)n 1 , a b l 1 m 1 r 1 l 2 m 2 r 2 n 1 n 2
Fig. 8: R(n1, n2) upon denominator closure.

and so at the (l 2 , m 2 , r 2 ) cross-section we have:

l 2 = l 1 + n 2 (m 1 -l 1 ) = b + (b -a)n 1 n 2 = a + (b -a)(1 + n 1 n 2 ), m 2 = m 1 + n 2 (m 1 -l 1 ) = b + (b -a)(n 1 + n 1 n 2 ) = a + (b -a)(1 + n 1 + n 1 n 2 ), r 2 = r 1 = a + (b -a)n 1 .
At this point, we perform a special closure of this rational tangle for even N i.e., we identify the arcs that receive colors m 2 and l 2 , and the arcs that receive colors a and l 2 . From setting the corresponding pairs of colors equal we obtain two equations which are equivalent to:

(b -a)(1 + n 1 n 2 ) = 0 and thus the determinant of R(n 1 , n 2 ) is det R(n 1 , n 2 ) = 1 + n 1 n 2 . 4.1.3 R(n 1 , n 2 , n 3 )
We have (see Figure 9)

a b l 1 m 1 r 1 l 2 m 2 r 2 l 3 m 3 r 3 n 1 n 2 n 3
l 3 = l 2 , m 3 = m 2 + (r 2 -m 2 )n 3 , r 3 = r 2 + (r 2 -m 2 )n 3 .
For N = 4 we obtain, besides the empty sequence, ∅, the sequences:

(1) (3) (1, 2) (1, 4) (3, 4) (1, 2, 3) (1, 2, 3, 4).
Definition 5.2 For each positive integer N , we set:

p N := u∈IEO[N ] n u p e N := ′ u∈IEO[N ] n u
where the ′ denotes deletion of the monomials which are products of an odd number of n i 's; and

p o N := p N -p e N
For N = 4 we obtain,

p 4 = 1 + n 1 + n 3 + n 1 n 2 + n 1 n 4 + n 3 n 4 + n 1 n 2 n 3 + n 1 n 2 n 3 n 4 , p e 4 = 1 + n 1 n 2 + n 1 n 4 + n 3 n 4 + n 1 n 2 n 3 n 4 , p o 4 = n 1 + n 3 + n 1 n 2 n 3 ,
Moreover, we recognize that these polynomials were obtained in Subsubsection 4.1.4 in the expressions of the l 4 , m 4 , and r 4 . In particular, we can now write: Analogous relations are now clear between the polynomials of Definition 5.2 and other calculations performed in Subsection 4.1. We prove below that these relations do not depend on the magnitude of N , the number of twists in the rational knots. Before we do that we prove recurrence formulas for the these polynomials which will be useful in the sequel. Lemma 5.1 Given a positive integer I, consider the 2I + 1 variables n 1 , n 2 , . . . , n 2I . We keep the notation above concerning the p polynomials.

1.

p

2I = p 2I-1 + n 2I p o 2I-1 .
In particular,

p o 2I = p o 2I-1 and p e 2I = p e 2I-1 + n 2I p o 2I-1 . 2. p 2I+1 = p 2I + n 2I+1 p e 2I .
In particular,

p o 2I+1 = p o 2I + n 2I+1 p e 2I
and p e 2I+1 = p e 2I .

Proof:

1. It is enough to realize that IEO[2I] is the union of IEO[2I -1] with the sequences with an odd number of terms from IEO[2I -1] augmented with the term 2I.

2. Omitted since it is analogous to the proof of 1. above.

✷ 6 The Coloring System of Equations of a Rational Knot: The General Case

In this section we prove Theorem 1.1. In order to do that we first establish the following result. There is an edge between two vertices whenever there is a crossing between the corresponding shaded regions. In particular, two vertices may be connected by more than one edge.

Fig. 1 :

 1 Fig. 1: A diagram of the trefoil knot.

Figure 2 .Fig. 2 :

 22 Fig. 2:The equation associated to the unknowns at a crossing.

bFig. 3 :

 3 Fig. 3: The braid σ 3 1 whose closure yields a diagram of the trefoil, and setting up a Fox coloring. Left: the integral view. Right: the black box approach.

bFig. 4 :

 4 Fig. 4: The braid σ n 1 whose closure yields a diagram of the T (2, n) torus knot, and endowed with a Fox coloring. Left: the integral view. Right: the "black box" approach.

Proposition 2 . 2 Definition 2 . 4

 2224 Given a non-zero integer n and integers a, b, and r(> 1), consider σ n 1 (∈ B 2 ). Assume a and b is the color input on the top of the braid (see Figure 4). Then the arc emerging from the n-th crossing receives color b + n(ba). The coloring system of equations of the T (2, n) torus knot is formed by n(ba) = 0 mod r (and the trivial equation). It has gcd(n, r)r solutions. Moreover, det T (2, n) = n. Furthermore, and in view of the preceding discussion, we set forth the following Definition. Consider the right-hand side of Figure 4. It is formed by a rectangular box with two strands on top of it and two strands on the bottom. The box has a label n inside. The top strands are labeled a and b from left to right and the bottom strands are labeled a + n(ba) and b + n(b

Fig. 5 :

 5 Fig. 5: Rational knots on 4 and 5 twists.

Fig. 6 :

 6 Fig. 6: The signs of the crossings induced by the checkerboard shading.

Fig. 7 :

 7 Fig. 7: Sign convention and checkerboard shadings.

Fig. 9 :

 9 Fig. 9: R(n1, n2, n3) upon numerator closure.

l 4 =

 4 a + (ba)p e 4 , m 4 = a + (ba)p 4 , r 4 = a + (ba)p o 4 . with the coloring system of equations: (ba)p e 4 = 0, and det R(n 1 , n 2 , n 3 , n 4 ) = p e 4 .

Proposition 6 . 1 1 = 1 = 1 = 1 =✷ 7

 6111117 Given a positive integer N , fix N integers, n 1 , n 2 , . . . , n N . Consider the rational knot R(n 1 , n 2 , . . . , n N ) given by the special closure of a 4-braid. Then, keeping the notation above, for any 1 ≤ i ≤ N ,l i = a + (ba)p e i , m i = a + (ba)p i , r i = a + (ba)p o i .Proof: By induction on N . The preceding examples show us that the proposition is true for several particular cases, from N = 1 through N = 5. Assume the statement is true for a given N = 2I -1 and consider Figure10. Then,l 2I = l 2I-1 + n 2I (m 2I-1l 2I-1 ) = a + (ba)p e 2I-1 + n 2I a + (ba)p 2I-1a -(ba)p e 2Ia + (ba)p e 2I-1 + n 2I (ba) p 2I-1p e 2I-1 = a + (ba)p e 2I-1 + n 2I (ba)p o 2Ia + (ba) p e 2I-1 + n 2I p o 2I-1 = a + (ba)p e 2I .The second equality above is a consequence of the induction hypothesis and the last equality is a consequence of Lemma 5.1. Analogously,m 2I = m 2I-1 + n 2I (m 2I-1l 2I-1 ) = a + (ba)p 2I-1 + n 2I a + (ba)p 2I-1a -(ba)p e 2Ia + (ba)p 2I-1 + n 2I (ba) p 2I-1p e 2I-1 = a + (ba)p 2I-1 + n 2I (ba)p o 2Ia + (ba) p 2I-1 + n 2I p o 2I-1 = a + (ba)p 2I ,and clearly, r 2I = r 2I-1 = a + (ba)p o 2I-1 = a + (ba)p o 2I , using the induction hypothesis and Lemma 5.1.In a similar way, assuming now the statement is true for N = 2I, we obtain,l 2I+1 = a + (ba)p e 2I+1 , m 2I+1 = a + (ba)p 2I+1 , r 2I+1 = a + (ba)p o 2I+1 .This completes the proof. ✷ Proof: of Theorem 1.1. We will only prove statement 2. for 1. is similar. As a consequence of Proposition 6.1, the coloring system of equations for R(n 1 , n 2 , . . . , n 2I , n 2I+1 ) reduces to a = a + (ba)p o 2I+1 which yields at once (ba)p o 2I+1 = 0 and det R(n 1 , n 2 , . . . , n 2I , n 2I+1 ) = p o 2I+1 . Counting Spanning Trees of the Graphs Induced by the Checkerboard Shadings of Rational Knots The checkerboard shadings of a knot diagram (Definition 3.1) suggest the definition of a checkerboard graph in the following way.

Definition 7 . 1 (

 71 The checkerboard graph) Given a checkerboard shading of a knot diagram, we associate to it a graph in the following way. The vertices of the graph are the shaded regions of the diagram.

Acknowledgements P.L. acknowledges support by Programa Operacional "Ciência, Tecnologia, Inovac ¸ão" (POCTI) of the Fundac ¸ão para a Ciência e a Tecnologia (FCT) cofinanced by the European Community fund FEDER. He also thanks the staff at IMPA and especially his host, Marcelo Viana, for hospitality during his stay at this Institution.

We thank the referee for useful suggestions which improved this article.

Louis H. Kauffman and Pedro Lopes

Making use of the results obtained in the preceding subsection,

We perform a special closure on the tangle in Figure 9 and so the coloring system of equations is here

Analogously,

The coloring system of equations is

And analogously,

The coloring system of equations is

5 The p N , p e N , and p o N Polynomials

The following definitions help us understanding the structure of the formulas for the l N , m N , and r N obtained in Subsection 4.1.

Definition 5.1 For each positive integer N , let IEO[N ] stand for the set of increasing sequences of terms from {1, 2, . . . , N }, whose even terms are even and odd terms are odd, along with the empty sequence (denoted ∅). It is a fact that the determinants of alternating knots are given by the counting of the spanning trees of their checkerboard graphs (see [START_REF] Crowell | Genus of alternating link types[END_REF]). Here we can prove this for rational knots by directly counting the trees and getting the same formula we have derived for rational knots.

We will assume that an infinite sequence of positive integers (n 1 , n 2 , n 3 , . . . ) has been fixed. Proposition 7.1 below yields a recursive relation for the number of spanning trees as well as a set of instructions to obtain the new ones from the old ones. Proposition 7.1 Letting T (N ) stand for the number of spanning trees of R(n 1 , n 2 , . . . , n N ), then

.

Proof: See Figure 11. In this figure we illustrate how the checkerboard graph is obtained from a diagram of a rational knot, and how the edges in that graph come in either parallel clusters or consecutive sequences depending upon whether the term n N has odd or even index, respectively. With this in mind, one sees that there are two linked formulas for counting the spanning trees in the graph. These formulas are shown in Figure 11. In the figure, the instructions, "delete one", "keep all", "keep one", "delete all" are appended below the terms in the formulas. These are the instructions for forming the spanning trees from the corresponding sequences and clusters. The reader will find this notation self-explanatory. Once both formulas are written down, we see that they can be summarized by the single recursion formula of this proposition. This completes the proof. ✷ Remark 7.1 It is a fact that the determinant of an alternating knot or link is equal to the number of spanning trees in its checkerboard graph. Thus we can state as a corollary to this proposition that T (N ) = D N where D N denotes the determinant of the rational knot corresponding to the fixed sequence described above. Thus the formula above gives a recursion formula for the determinants of rational knots and links. The reader will enjoy verifying that this formula yields our previous formulas for these determinants. As a final remark, note that if all the n N equal 1, then the sequence D N is the Fibonacci sequence.


Therese C Biedl

Erik D Demaine
email: eddemaineg@uwaterloo.ca

Sylvain Lazard
email: lazard@loria.fr

Steven M Robbins

Michael A Soss
email: sossg@cgm.cs.mcgill.ca

Convexifying Monotone Polygons

This paper considers recon gurations of polygons, where each polygon edge is a rigid link, no two of which can cross during the motion. We prove that one can recon gure any monotone polygon into a convex polygon; a polygon is monotone if any vertical line intersects the interior at a (possibly empty) interval. Our algorithm computes in O(n 2 ) time a sequence of O(n 2 ) moves, each of which rotates just four joints at once.

Introduction

An interesting area in computational geometry is the recon guration of (planar) linkages: collections of line segments in the plane (called links) joined at their ends to form a particular graph. A recon guration is a continuous motion of the linkage, or equivalently a continuous motion of the joints, that preserves the length of each link. We further enforce that links do not cross, that is, do not intersect during the motion. For a survey of work on linkages where crossing is allowed, see the paper by Whitesides 9].

The case of noncrossing links has had a recent surge of interest. The most fundamental question 7] is still open: Can every chain be recon gured into any other chain with the same sequence of link lengths? Here a chain is a linkage whose underlying graph is a path. Because recon gurations are reversible, an equivalent formulation of the question is this: Can every chain be straightened, that is, recon gured so that the angle between any two successive links is ? This question has been posed independently by several researchers, including Joseph Mitchell, and William Lenhart and Sue Whitesides 6]. It has several applications, including hydraulic tube and wire bending, and sheet metal folding 7].

At rst glance, it seems intuitive that any chain can be \unraveled" into a straight line, but experimentation reveals that this is a nontrivial problem. Indeed, no such \general unraveling" motions have been formally speci ed. Because the problem is so elusive, it is natural to look at special classes of linkages and prove that at least they can be straightened. For example, consider the class of monotone chains, where every vertical line intersects the chain at a point or ? Research performed during a post-doctoral position at McGill University. not at all. Such a chain can easily be straightened by repeatedly [START_REF] Biedl | Locked and unlocked polygonal chains in 3D. Manuscript in preparation[END_REF] rotating the rst link until it lines up with the second link, and (2) fusing these links together into a single \ rst link." This motion induces no crossings because it preserves monotonicity throughout.

This paper addresses the analogous question of straightenability for polygons (a linkage whose underlying graph is a cycle): Can every polygon be recon gured into a convex polygon? In other words, can every polygon be convexi ed? This question was also raised by the researchers mentioned above. Note that a convex polygon can be recon gured into any other convex polygon with the same clockwise sequence of link lengths, and hence the question is equivalent to the fundamental question for polygons 7]: Can every polygon be recon gured into any other polygon with the same clockwise sequence of link lengths? B C A Fig. 1. A monotone polygon.

In this paper we focus on the case of monotone polygons. Similar to the case of chains, a polygon is monotone if the intersection of every vertical line with the interior of the polygon is an interval, that is, either a single vertical line segment, a point, or the empty set. See Fig. 1 for an example. A monotone polygon consists of two chains, the upper chain and the lower chain. Each chain is weakly monotone in the sense that the intersection with a vertical line is either empty, a single point, or a vertical edge. 1 The left right] ends of the upper and lower chains may be identical (like point A in Fig. 1), or they may be connected by a vertical edge (like edge (B; C) in Fig. 1). The vertical edge (B; C) belongs to neither chain.

In contrast to monotone chains, it is nontrivial to convexify monotone polygons. In this paper, we show that this is possible by a fairly simple motion consisting of a sequence of O(n 2 ) moves. We use just a single type of move, changing the angles of only four joints, which we show is the fewest possible. While the proof of correctness is nontrivial, our algorithm for computing the motion is simple and e cient, taking O(n 2 ) time.

Related Work

Let us brie y survey the work on recon guring linkages whose links are not allowed to cross. The most related result, by Bose, Lenhart, and Liotta 3], is that all monotoneseparable polygons can be convexi ed. A monotone-separable polygon is a monotone polygon whose upper and lower chains are separated by a line segment (connecting the common ends of the chains). Their motion involves translating almost all joints in the upper chain at once, and appears not to extend to general monotone polygons.

The only other result about convexifying classes of polygons is that every star-shaped polygon can be convexi ed 5]. A polygon is star-shaped if its bound-ary is entirely visible from a single point. This motion rotates all joints simultaneously, and it seems di cult to nd a motion involving few joints 10].

The remaining related results are for types of linkages other than polygons. For tree linkages, it is known that the answer to the fundamental problem is \no" 2]: There are some trees which cannot be recon gured into other trees with the same link lengths and planar embedding. Indeed, there can be an exponential number of trees with the same link lengths and planar embedding that are pairwise unreachable. The complexity of determining whether a tree can be recon gured into another remains open.

Another way to change the problem is to allow linkages in higher dimensions. If we start with a polygon in the plane, and allow motions in three dimensions, then every polygon can be convexi ed 8]. Indeed, a 1935 problem by Erd} os asks whether a particular sequence of moves through 3D, each rotating only two joints (called a \ ip"), converges in nite time. While the answer is positive, the number of moves is unfortunately unbounded in n. Recently, it was shown that O(n) moves of a di erent kind su ce 1]; each rotates at most four joints.

If the polygon lies in three dimensions and we want to convexify it by motion through three dimensions, then it is surely not convexi able if it is knotted. But there are unknotted polygons that cannot be convexi ed 1]. The complexity of determining whether a polygon in 3D can be convexi ed also remains open. Amazingly, Cocan and O'Rourke 4] have shown that every polygon in d dimensions can be convexi ed through d dimensions for any d 4.

Outline

The rest of this paper is organized as follows. Section 2 begins with a more formal description of the problem. Section 3 describes our algorithm for computing the motion. Sections 4 and 5 prove its correctness and bound its performance, respectively. We conclude in Section 6.

De nitions

This section gives more formal de nitions of the concepts considered in this paper: linkages, con gurations, and motions. Consider a graph, each edge labeled with a positive number. Such a graph may be thought of as a collection of distance constraints between pairs of points in a Euclidean space. A realization of such a graph maps each vertex to a point, also called a joint, and maps each edge to the closed line segment, called a link, connecting its incident joints. The link length must equal the label of the underlying graph edge. If a graph has one or more such realizations, we call it a linkage.

An embedding of a linkage in space is called a con guration of the linkage. In a simple con guration, any pair of links intersect only at a common endpoint, and in this case the links must be incident at this joint in the linkage. We consider only simple con gurations in this paper. A motion of a linkage is a continuous movement of its joints respecting the link lengths such that the con guration of the linkage remains simple at all times.

In this paper, we consider linkages embedded in the plane whose graph is a single cycle. The con gurations are simple polygons, and so divide the plane into the exterior and interior regions (distinguished by the fact that the interior region is bounded). Joints of an n-link linkage are labeled j 0 ; j 1 ; : : : ; j n 1 in a counterclockwise manner: traversing the boundary in sequence j 0 ; j 1 ; : : : ; j n 1 keeps the interior region on the left. The joint angle i is the interior angle at joint j i : i = 6 j i+1 j i j i 1 2 (0; 2 ). We call a joint straight if the joint angle is , convex if the joint angle is strictly less than , and re ex otherwise. A con guration is convex if none of its joints are re ex.

The question considered is whether every monotone con guration of a cyclic linkage (or polygon) can be convexi ed, that is, moved to a convex con guration. We show this is true by giving an algorithm to compute such a motion.

Algorithm

As input, the algorithm requires a description (that is, the joint coordinates) of a polygon with n links. In each main step, the algorithm computes a sequence of O(n) moves that ultimately straighten a joint. This joint angle is then held xed so that it remains straight forever after, e ectively reducing the number of joints. As the algorithm continues, the con guration has fewer and fewer nonstraight joints. We stop when no re ex joint is left, and so the polygon is convex as desired.

First we need some notation for basic geometric concepts. Let p and q be two points in the plane. De ne kpqk to be the Euclidean distance between p and q.

If p and q are distinct, de ne ray(p; q) to be the ray originating at p and passing through point q. We use \left" and \right" in two di erent senses, one for points and one for rays. A point r is left or right of ray(p; q) if it is strictly left or right (respectively) of the oriented line supporting ray(p; q). A point p is left or right of point q if p has a strictly smaller or larger x coordinate than q, respectively.

In both cases, we use nonstrictly left/right to denote left/right or equality, i.e., neither left nor right.

The algorithm works as follows:

Algorithm Convexify { Until the polygon is convex:

Find a rightmost re ex joint (a joint with maximum x coordinate, breaking ties arbitrarily). Relabel joints counterclockwise along the polygon so that this rightmost re ex joint is j 1 , and all straight joints are ignored.

If j 1 belongs to the lower chain: 1. Compute the largest index p such that j 2 ; : : : ; j p 1 are right of ray(j 0 ; j 1 ).

2. Until a joint has straightened:

(a) Perform the following move (see Fig. 2) until either the joints j 0 , j 1 , and j p 1 become collinear; or one of the joints fj 0 ; j 1 ; j p 1 ; j p g straightens:

i. Fix the positions of joints j p , j p+1 , . . . , j n 1 , and j 0 .

ii. Fix all joint angles except those at j 0 , j 1 , j p 1 , and j p . iii. Rotate j 1 clockwise about j 0 . iv. Move joint j p 1 as uniquely de ned by maintaining the distances kj 1 j p 1 k and kj p 1 j p k. (b) Update the coordinates of j 1 and j p 1 . (c) If j 0 , j 1 , and j p 1 are collinear, then decrement p, because with the new positions, j p 1 is on ray(j 0 ; j 1 ). Also update the coordinates of the new j p 1 .

3. Update the coordinates of any remaining joints that have moved.

If j 1 belongs to the upper chain, the algorithm is similar.

First let us justify that the algorithm is well-de ned.

Lemma 1. The de nition of p in Step 1 is well-de ned and at least 3.

Proof. Because j 1 is re ex, ray(j 0 ; j 1 ) must intersect the polygon elsewhere than the segment (j 0 ; j 1 ). This implies that there are joints on both sides of the ray, and hence p is well-de ned. Furthermore, because j 1 is re ex and the joints are oriented counterclockwise on the polygon, j 2 is right of ray(j 0 ; j 1 ). Hence, 2 is a valid value for p 1, so p 3. 2

Note further that the number of simultaneously rotating joints (four) is the best possible, because any motion of a polygon that rotates just three joints recon gures a virtual triangle, which is rigid.

Proof of Correctness

In this section, we prove the following theorem.

Theorem 1. Given any monotone polygon, Algorithm Convexify computes a convexifying motion, during which the polygon remains simple and monotone.

The di culty is in showing that the polygon remains monotone and simple during the motion. For the remainder of this section, assume without loss of generality that the link (j 0 ; j 1 ) is on the lower chain. First we need some trivial but important observations. Lemma 2. During each move, no re ex angle becomes convex and no convex angle becomes re ex.

Proof. Because all other joint angles are xed, any such transition means that a joint j 0 , j 1 , j p 1 , or j p straightens, which stops the move. 2

Lemma 3. Joints j 2 ; : : : ; j p 1 are convex.

Proof. Consider such a joint j i . Because j 1 is a rightmost re ex vertex, j i is convex if it is right of j 1 . By monotonicity and the property that j i is right of ray(j 0 ; j 1 ), j i cannot be left of j 1 . The only case that remains is when j i has the same x coordinate as j 1 . Because we ignore straight joints, j i must in fact be j 2 in this case. Because j 1 is re ex, j 2 must be below j 1 . Now j 3 must be strictly right of j 2 , and hence the angle at j 2 is convex. Next we need a general result about quadrangles.

Lemma 4. 1] Consider a simple quadrangle j 0 ; j 1 ; j 2 ; j 3 (in counterclockwise order) with j 1 re ex.

(See Fig. 3.) Let i denote the interior angle at joint j i . If the linkage moves so that j 1 rotates clockwise about j 0 , then 1 decreases and i increases for all i 2 f0; 2; 3g, until 1 straightens. In other words, all of the angles approach .

By the de nition of p, j 1 is re ex in the quadrangle Q = (j 0 ; j 1 ; j p 1 ; j p ), so we can apply Lemma 4 to Q and obtain the following result about our motion: Lemma 5. During each move in Step 2a, j p 1 rotates counterclockwise about j p , and the joint angles 1 and p 1 both approach .

Next we analyze the movement of j 1 relative to j p 1 's reference frame, determined by xing the position of j p 1 and keeping the axes parallel to the world frame's. This can be visualized by imagining that during the motion we translate the entire linkage so that j p 1 stays in its original position. Lemma 6. j 1 rotates counterclockwise about j p 1 .

Proof. Consider the relative movement of j 1 and j p about j p 1 . Joint j p is rotating counterclockwise about j p 1 and the angle 6 j 1 j p 1 j p is increasing by Lemma 5. Hence, j 1 must also be rotating counterclockwise about j p 1 .

2

We are now in the position to prove that the polygon remains simple and monotone throughout the motion.

Proof (Theorem 1). The only way that simplicity or monotonicity can be violated is that either a link intersects another link, or a vertical link rotates in the \wrong" direction. The wrong direction for link (j i ; j i+1 ) on the lower upper] chain is when j i+1 becomes left right] of j i . Consider the rst time at which a link intersects another, or a vertical link rotates in the wrong direction.

Suppose rst that a vertical link (j i ; j i+1 ) rotates in the wrong direction. Because only joints j 1 ; : : : ; j p 1 move, we must have 0 i p 1. We distinguish three cases: Case 1: Link (j 0 ; j 1 ) is vertical Because j 1 is re ex and j 2 is nonstrictly right of j 1 , j 1 must be above j 0 . But j 1 rotates clockwise about j 0 , so monotonicity is preserved.

Case 2: Link (j 1 ; j 2 ) is vertical Because j 1 is re ex, j 1 is above j 2 . By Lemma 6, j 1 rotates counterclockwise about j p 1 . Hence, the rigid triangle j p 1 j 1 j 2 rotates counterclockwise about j p 1 . Thus because the link (j 1 ; j 2 ) is vertical, j 1 is above j 2 , and j p 1 is (nonstrictly) right of j 1 , j 1 moves left of j 2 . Thus, monotonicity is preserved.

Case 3: Link (j i ; j i+1 ) is vertical, 2 i p 1 We show that joints j i and j i+1 are both convex. First, if i p 2, then this follows by Lemma 3. Second, if i = p 1, then j p 1 and j p must be right of j 1 in order for them to be on opposite sides of ray(j 0 ; j 1 ). Hence, j p 1 and j p must be convex because they are right of j 1 which is a rightmost re ex vertex.

Thus, joints j i 1 and j i+2 are both left of the link (j i ; j i+1 ); that is, (j i 1 ; j i ) belongs to the lower chain and (j i+1 ; j i+2 ) belongs to the upper chain. This means that link (j i ; j i+1 ) joins the top chain to the bottom chain (like link BC in Fig. 1). The polygon remains monotone no matter which way the link moves. Now suppose that two links intersect each other, but the polygon remained simple and monotone before this time. By Lemma 5, the joint angles 1 and p 1 approach , and hence the chain of moving links (j 0 ; : : : ; j p ) cannot selfintersect. Hence, the only concern is whether any of these links could intersect the rest of the polygon.

In the following, refer to Fig. 4. Let u denote the original position of ray(j 0 ; j 1 ), and v denote the downward vertical ray emanating from j 0 . Let W be the wedge right of ray u and left of ray v.

Joint j 1 starts on the boundary of W; because it rotates clockwise about j 0 , it enters region W at the start of the move. By the choice of p, joints j 2 ; : : : ; j p 1 all lie to the right of u. These joints must also lie to the left of v, because otherwise the polygon would not be monotone. Thus, after the move starts, the chain j 1 ; : : : ; j p 1 lies inside W.

We now argue that the only joints that can be inside W are j 1 ; : : : ; j p 1 . We know that j 0 and j p are not interior to W. If some other joint lies inside W, the chain must cross one of the boundaries of W. The chain cannot cross ray v, because that would violate monotonicity. Nor can the chain cross ray u, because that would require a re ex vertex to the right of j 1 or a violation of monotonicity. Because none of j p ; : : : ; j n 1 ; j 0 are moving, this chain remains outside W during the motion.

To establish that the polygon remains simple, we claim further that the joints j 1 , . . . , j p 1 never leave W. Suppose to the contrary that one does. Let j i be the rst such joint to leave W. It must reach either ray u or ray v. Consider each possibility in turn. j i crosses v: Because j 1 stays re ex (unless it straightens which stops the move), it cannot be the rst to cross v. If j i crosses v for 1 < i < p, then we have both j 0 and j i left of j 1 , so the chain is not monotone, a contradiction. (Right) When (jp; jp+1) is on the lower chain. j i crosses u: Because j 1 rotates clockwise about j 0 , it never crosses u. If j 2 crosses, j 1 cannot be re ex, a contradiction. If j p 1 crosses, the move must have already stopped from j 0 , j 1 , and j p 1 becoming collinear because j 1 rotates clockwise about j 0 . Finally, if j i crosses u for 2 < i < p 1, j i must be re ex because j i 1 and j i+1 are both right of u, contradicting Lemma 3. Hence, the links of the chain j 0 ; : : : ; j p 1 always remain inside W, so they cannot intersect links outside of W.

This leaves just one moving link, (j p 1 ; j p ). By Lemma 5, j p 1 rotates counterclockwise about j p . De ne v 0 to be the vertical ray emanating from j p that points away from the interior of the polygon, preferring upward if both directions are possible. Thus, v 0 points downward upward] when the link (j p ; j p+1 ) is not] on the lower chain.

Let P be the pie wedge bounded by the link (j p 1 ; j p ), the ray v 0 , and the counterclockwise circular arc, centered at j p , starting at j p 1 and ending on v 0 (at distance kj p j p 1 k from j p ). Because monotonicity is preserved up to this point, P is empty of nonmoving links. P also contains the entire sweep of (j p 1 ; j p ): if v 0 points upward, j p 1 cannot cross v 0 without rst becoming collinear with j 0 and j 1 ; if v 0 points downward, it cannot cross without rst straightening j p . [START_REF] Biedl | On recon guring tree linkages: Trees can lock[END_REF]

Time and Move Bounds

Finally we establish the time and move bounds on the algorithm. Our model of computation is a real random-access machine supporting comparisons, basic arithmetic, and square roots. In order to compute the halting event, we de ne the following (refer to Fig. 5). Here x denotes that x changes during the move. a = kj 0 j 1 k; b = kj 1 j p 1 k; c = kj p 1 j p k; d = kj p j 0 k; m = kj 1 j p k;

' 0 = 6 j p j 0 j 1 ; ' 1 = 6 j 0 j 1 j p 1 ; ' p 1 = 6 j 1 j p 1 j p ; ' p = 6 j p 1 j p j 0 : Note that m increases during the move, because j 1 rotates clockwise about j 0 , increasing ' 0 and thus (by law of cosines) m . Hence, we parameterize the move by the diagonal distance m . More precisely, we determine the halting event by computing the value of (m ) 2 for each of the ve candidate events, and choosing the event with smallest (m ) 2 . Now the event that j i straightens happens when its angle i is , and the event that j 0 , j 1 , and j p 1 become collinear happens when ' 1 = . Note however that j 1 can only straighten after j 0 , j 1 , and j p 1 become collinear (because 6 j 0 ; j 1 ; j p 1 is initially re ex), and hence we do not need to consider this event.

Using the law of cosines, we obtain the following solutions to these event equations: j 0 straightens: (m ) 2 = a 2 + d 2 + 2ad cos( 6 j n 1 j 0 j p ) and 6 j n 1 j 0 j p < . j p 1 straightens: (m ) 2 = b 2 + c 2 + 2bc cos( 6 j p 2 j p 1 j 1 ). j p straightens: Provided 6 j 0 j p j p+1 < (which is necessary for this event), (m ) 2 is the solution of a quadratic polynomial involving a, b, c, d, and cos( 6 j 0 j p j p+1 ). This reduces to an arithmetic expression involving square roots. j 0 ; j 1 ; j p 1 collinear: (m ) 2 = (ac 2 + bd 2 ab(a + b))=(a + b), because cos 1 = cos 1 . The new joint coordinates can be computed as follows: Suppose that we know the new coordinates of joints j i 1 and j i (initially i = 0). Let v be the vector from j i to j i 1 , rescaled to have the known length kj i j i+1 k. Rotate this vector clockwise by the new i , which only involves cosines and sines of this angle, and then add it to the point j i . The result is the new position of joint j i+1 . We can similarly compute the new coordinates of j p 1 from the coordinates of j p and j p+1 . Thus, each update of j 1 , j p 1 (Step 2b), and possibly j p 2 (Step 2c) takes constant time as desired. Our result adds to the class of polygons that are known to be convexiable; previously, the only nontrivial classes were star-shaped polygons 5] and monotone-separable polygons 3]. A natural area of research is to explore more general classes of polygons. Is there a convexi able class containing both monotone and star-shaped polygons (other than trivial classes like the union)?

Fig. 2 .

 2 Fig. 2. The movement of joints j 1 and j p 1 . The thick dashed lines represent \virtual links" whose lengths are preserved.

  Fig. 3. Illustration of Lemma 4.

Fig. 4 .

 4 Fig. 4. De nition of v, v 0 , W , and P . (Left) When (jp; jp+1) is not on the lower chain.

Lemma 7 .

 7 Each iteration of Step 2 takes constant time. Proof. The computations in this step are computing which of the ve candidate events for stopping the motion occurs rst (Step 2a), and updating O(1) coordinate positions (Steps 2b and 2c).

Fig. 5 .

 5 Fig. 5. Illustration of the proof of Lemma 7.

2 Theorem 2 . 6

 226 Algorithm Convexify computes O(n 2 ) moves in O(n 2 ) time. Proof. By Lemma 7, any one move takes O(1) time to compute. Any execution of Step 2 therefore takes O(n) time, because initially p n 1, and p decreases with every move, until a joint straightens and Step 2 terminates. All other steps can also be implemented in O(n) time. One iteration of the main loop thus takes O(n) time. Because each iteration straightens a joint, the polygon becomes convex after O(n) iterations. Hence, there are O(n 2 ) moves, which are computed in O(n 2 ) time. 2 Conclusion We have presented an O(n 2 )-time algorithm to compute a sequence of O(n 2 ) moves, each rotating the minimum possible number of four joints at once, that recon gures a given monotone polygon into a convex polygon with the same link lengths. By running the algorithm twice we can nd a motion between any two monotone polygons with the same clockwise sequence of link lengths. Several interesting open problems remain. Can our algorithm be improved to use o(n 2 ) moves each rotating o(n) joints? More generally, what is the tradeo between the number of simultaneously rotated joints and the number of moves?

All straight (angle-) vertices are removed, so there is no possibility of two adjacent vertical edges.

Acknowledgments. We thank William Lenhart, Anna Lubiw, Godfried Toussaint, and Sue Whitesides for helpful discussions. This work was partially supported by FCAR and NSERC.


M Bonneau

S Gaba

N Peyrard

R Sabbadin

Weeds Sampling for Map Reconstruction: a Markov Random Field Approach

Introduction

In the past 15 years, there has been a growing interest for the study of the spatial repartition of weeds in crops, mainly because this is a prerequisite to herbicides use reduction. There has been a large variety of statistical methods developped for this problem ( [START_REF] Dale | Conceptual and mathematical relationships among methods for spatial analysis[END_REF], [START_REF] Dille | How good is your weed map ? a comparaison of spatial interpolators[END_REF], [START_REF] Perry | Illustrations and guidelines for selecting statistical methods for quatifying spatial pattern in ecological data[END_REF]). However, one common point of all of these methods is that they are based on in situ collection of data about weeds spatial repartition. A crucial problem is then to choose where, in the field, data should be collected. Since exhaustive sampling of a field is too costly, a lot of attention has been paid to the development of spatial sampling methods ( [START_REF] Wiles | Sampling to make maps for site specific weed management[END_REF], [START_REF] Cousens | Sampling strategy is important for producing weed maps : a case study using kriging[END_REF], [6] [9]). Classical spatial stochastic model of weeds counts are based on Cox processes [START_REF] Bourgeois | Inferring weed spatial distribution from multi-type data[END_REF] or kriging [START_REF] Dille | How good is your weed map ? a comparaison of spatial interpolators[END_REF]. In this work we propose to deal with abundance classes and to adopt a Markov Random Field (MRF) framework.

In a companion paper [START_REF] Bonneau | A reinforcement-learning algorithm for sampling design in markov random fields[END_REF], we present an approach for spatial sampling which is based on MRF. This approach relies on an a priori model of the repartition of weeds in crops. It also relies on a model of sampling costs (time spent to sample), in order to mimic field constraints. The goal of this talk is to present the modelling choices that we have made in order to apply the approach [START_REF] Bonneau | A reinforcement-learning algorithm for sampling design in markov random fields[END_REF] to the sampling and reconstruction problem for a real case study with a large data set of partial samples, in various conditions (weeds, crop, date...). In section 2 we present the model selection study that we have performed in order to build the a priori MRF model of weeds repartition. Then, in section 2, we present the sampling (time) cost model that we have built. Finally, in section 4 we discuss the use of the sampling approach [START_REF] Bonneau | A reinforcement-learning algorithm for sampling design in markov random fields[END_REF] for weeds sampling in crop fields.

A MRF model of the abundance repartition of a weed species 2.1 Candidates pairwise MRF models

Let us recall briefly the definition of a pairwise MRF distribution. Let X = (X 1 , . . . , X n ) be discrete random variables taking values in Ω n = {0, . . . , K} n . V = {1, . . . , n} is the set of indices of the vector X and an element i ∈ V will be called a site.

If G = (V, E) is the graph associated 1 with the MRF, then ∀(x 1 , . . . , x n ) ∈ Ω n , P x 1 , . . . , x n ∝ i∈V e ψi(xi) (i,j)∈E e ψij (xi,xj ) .
For modeling the map distribution of a particular weed species, we define G as a regular rectangular grid representing a decomposition of the field into quadrats (which are also the sampling units). We considered a first order neighbourhood (2 closest neighbours in each field direction). The variable X i is the abundance class on quadrat i. For example using Barralis classes [START_REF] Barralis | Méthode d'étude des groupements adventices des cultures annuelles[END_REF] : Ω = {0, . . . , 6} with 0 corresponding to the absence of the species. The choice of an appropriate MRF model for mapping weed abundance classes distribution amounts to the choice of adapted potential functions ψ i and ψ ij . We considered several options : Potts model with or without external field and with or without anisotropy. The more complex is the Potts model with external field and with aniisotropy :

∀(i, j) ∈ E, ∀k, l ∈ Ω      ψ i (k) = α k , ψ ij (k, l) = β s 1 {k=l} if edge (i, j) is along tillage direction ψ ij (k, l) = β o 1 {k=l} if edge (i, j) is orthogonal to tillage direction
where α k , β s and β o are real valued parameters. The three other models are derived by setting all the αs equal and/or β s = β o . We also considered an alternative to the Potts model, where we impose a smooth spatial variation of the abundance classes : the order-2 potentials are modified as follows

∀(i, j) ∈ E, ∀k, l ∈ Ω ψ ij (k, l) = β s (1 -|k-l| K ) if edge (i, j) is along tillage direction ψ ij (k, l) = β o (1 -|k-l| K ) if edge (i, j) is orthogonal to tillage direction

Model selection

The analysis was performed on 6 species, sampled in different cropping systems, at different periods of the year. For each situation, the data available consist of samples of abundance classes of the weed species within a crop field. We used variational versions of the EM algorithm and the BIC criterion [START_REF] Forbes | Hidden markov random field model selection criteria based on mean field-like approximations[END_REF] to estimate the parameters of each of the eight candidate models and estimate their BIC score. We obtained the following conclusions : i) for a large majority of situations, the isotropic Potts model without external field is the best candidate to represent abudance maps distribution, and ii) the MRF model with smooth variation is clearly not adapted. The latter conclusion is in coherence with results from the litterature which claim that variations of weeds abundances are often abrupt within a crop field.

Cost of sampling

Sampling is adaptive and divided into H steps. One quadrat is sampled at each step. The cost incured to sampling plan A defines the effort necessary for executing this sampling plan. From discussions with experts, we defined this cost based on the time spent to execute A. If A = {a 1 , . . . , a H } are the indices of observed quadrats, we suppose that the overall time cost, denoted c(A), is the sum of times spent for observing each quadrat. That is c

(A) = H i=1 c(a i ).
We propose a linear model which expresses the time spent for observing a quadrat as a function of variables (Z 1 , . . . , Z 5 ), representing respectively : the period of observation, the number of weed individuals, the number of species, crop and farming practices. Period of observation is a binary variable with value {favorable, unfavorable} depending of the recovery stage of the crop. We consider five different farming practices, depending on the quantity of pesticide used. For fitting the parameters of this model we use a 18300 length dataset which is a result of a nine-years experiment in Dijon-Epoisses. Eight different crops have been tested. Coefficients of the linear model were fitted using a linear regression with the software R.

Applying LSDP to weeds sampling

Once a model of the abundance repartition of a weed species is established, it can be used for finding new sampling policies which realise a trade-off beetween quality of the reconstructed map and cost of sampling. One way to compute this policy is based on the LSDP algorithm described in [START_REF] Bonneau | A reinforcement-learning algorithm for sampling design in markov random fields[END_REF]. The main constraint for applying LSDP to weeds sampling problems is the large number of quadrats within a field. For now the LSDP algorithm gives interesting results for problems with 100 quadrats which is much less than the possible number of quadrats within a field. For exemple [START_REF] Rew | Spatial distribution of weeds in arable crops : are current sampling and analytical methods appropriate[END_REF] report that the size of experimental fields usually varies between 0.019 and 173ha. The same authors report that a quadrat size varies usually between 0.025 and 1.46m 2 .

For solving this problem one solution is to divide the overall field into subfields and solve the sampling problem into each subfield. Another possibility is to combine heuristic(s) strategy(ies) and the LSDP algorithm for solving the sampling problem. This two approaches are currently investigated.

Discussion

In this work, we propose an alternative to classical kriging approaches or point processes models for representing the spatial distribution of weeds abundance. This seems to be more adapted to the observed non smooth spatial variation of weeds abundance. We are currently testing this hypothesis by extending our model selection work to a new candidate : the log normal Cox process [START_REF] Bourgeois | Inferring weed spatial distribution from multi-type data[END_REF]. It could also be worth investigating the adaptation of our Reinforcement-Learning approach [START_REF] Bonneau | A reinforcement-learning algorithm for sampling design in markov random fields[END_REF] to propose sampling strategies relying on this latter model.

Then, the combination of simple heuristic strategies and more complex ones (like the LSDP one) should lead to a promising avenue for designing spatial sampling strategies for weeds with a satisfying trade-off between evaluation complexity and map reconstruction quality.