Matjaž Krnc
email: matjaz.krnc@upr.si

Tomaž Pisanski
email: tomaz.pisanski@upr.si

Generalized Petersen Graphs and Kronecker Covers *

Keywords: generalised Petersen graphs, Kronecker cover MSC: 57M10, 05C10, 05C25

, is a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. The Kronecker cover KC (G) of a simple undirected graph G is a special type of bipartite covering graph of G, isomorphic to the direct (tensor) product of G and K2. We characterize all generalised Petersen graphs that are Kronecker covers, and describe the structure of their respective quotients. We observe that some of such quotients are again generalised Petersen graphs, and describe all such pairs. The results of this paper have been presented at EUROCOMB 2019 and an extended abstract has been published elsewhere.

Introduction

The generalised Petersen graphs, introduced by Coxeter et al. [START_REF] Coxeter | Self-dual configurations and regular graphs[END_REF] and named by Watkins [START_REF] Watkins | A theorem on Tait colorings with an application to the generalized Petersen graphs[END_REF], form a very interesting family of trivalent graphs that can be described by only two integer parameters. They include Hamiltonian and non-Hamiltonian graphs, bipartite and non-bipartite graphs, vertex-transitive and non-vertex-transitive graphs, Cayley and non-Cayley graphs, arc-transitive graphs and non-arc-transitive graphs, graphs of girth 3, 4, 5, 6, 7 or 8. Their generalization to I-graphs does not introduce any new vertex-transitive graphs but it contains also non-connected graphs and has in special cases unexpected symmetries [START_REF] Boben | I-graphs and the corresponding configurations[END_REF]. For further properties of I-graphs also see [START_REF] Horvat | Isomorphism checking of I-graphs[END_REF][START_REF] Petkovšek | Enumeration of I-graphs: Burnside does it again[END_REF].

Following the notation of Watkins [START_REF] Watkins | A theorem on Tait colorings with an application to the generalized Petersen graphs[END_REF], for given integers n and k < n 2 , we can define a generalised Petersen graph G (n, k) as a graph on vertex-set {u 0 , . . . , u n-1 , v 0 , . . . , v n-1 }. The edge-set may be naturally partitioned into three equal parts (note that all subscripts are assumed modulo n): the edges

E O (n, k) = {u i u i+1 } n-1
i=0 form the outer rim, inducing a cycle of length n; the edges E I (n, k) = {v i v i+k } n-1 i=0 form the inner rims, inducing gcd(n, k) cycles of length n gcd(n,k) ; and the edges E S (n, k) = {u i v i } n-1 i=0 , also called spokes, which induce a perfect matching in G (n, k). Hence the edge-set may be defined as

E (G (n, k)) = E O (n, k) ∪ E I (n, k) ∪ E S (n, k).
Various structural aspects of the mentioned family have been pointed out. Examples include identifying generalised Petersen graphs that are Hamiltonian [START_REF] Alspach | The classification of hamiltonian generalized Petersen graphs[END_REF] or Cayley [START_REF] Nedela | Which generalized Petersen graphs are Cayley graphs?[END_REF][START_REF] Saražin | A note on the generalized Petersen graphs that are also Cayley graphs[END_REF], or isomorphic [START_REF] Horvat | Isomorphism checking of I-graphs[END_REF][START_REF] Petkovšek | Enumeration of I-graphs: Burnside does it again[END_REF][START_REF] Steimle | The isomorphism classes of the generalized Petersen graphs[END_REF], or finding their automorphism group [START_REF] Frucht | The groups of the generalized Petersen graphs[END_REF]. Also, a related generalization to I-graphs has been introduced in the Foster census [START_REF] Bouwer | The Foster Census[END_REF], and further studied by Boben et al. [START_REF] Boben | I-graphs and the corresponding configurations[END_REF].

The theory of covering graphs became one of the most important and successful tools of algebraic graph theory. It is a discrete analog of the well known theory of covering spaces in algebraic topology. In general, covers depend on the values called voltages assigned to the edges of the graphs. Only in some cases the covering is determined by the graph itself. One of such cases is the recently studied clone cover [START_REF] Malnič | The clone cover[END_REF]. The other, more widely known case is the Kronecker cover.

The Kronecker cover KC (G) (also called bipartite or canonical double cover) of a simple undirected graph G is a bipartite covering graph with twice as many vertices as G. Formally, KC (G) is defined as a tensor product G × K 2 , i.e. a graph on a vertex-set V (KC (G)) = {v , v } v∈V (G) , and the edge-set

E (KC (G)) = {u v , u v } uv∈E(G)
. For H = KC (G), we also say that G is a quotient of H. Some recent work on Kronecker covers includes Gévay and Pisanski [START_REF] Gévay | Kronecker covers, V-construction, unit-distance graphs and isometric point-circle configurations[END_REF] and Imrich and Pisanski [START_REF] Imrich | Multiple Kronecker covering graphs[END_REF].

In this paper, we study the family of generalised Petersen graphs in conjunction with the Kronecker cover operation. Namely, in the next section we state our main theorem characterizing all generalised Petersen graphs that are Kronecker covers, and describing the structure of their corresponding quotient graphs. In Section 3 we focus on the necessary and sufficient conditions for a generalised Petersen graph to be a Kronecker cover while in Section 4 we complement the existence results with the description of the structure of the corresponding quotient graphs. We conclude the paper with some remarks and directions for possible future research.

Main result

In order to state the main result we need to introduce the graph H and two 2-parametric families of cubic, connected graphs.

Let H be the graph defined by the following procedure: Take the Cartesian product K 3 P 3 , remove the edges of the triangle connecting the three vertices of degree 4, add a new vertex and connect it to the same three vertices. Note that the graph H is mentioned in [START_REF] Imrich | Multiple Kronecker covering graphs[END_REF] and is depicted in Figure 1.

As shown in [START_REF] Imrich | Multiple Kronecker covering graphs[END_REF], the Desargues graph G (10, 3) is the Kronecker cover of both G (5, 2) and H. Note that in Figure 1 the edge-colored subgraphs of H lift to the corresponding edge-colored subgraphs of G [START_REF] Krnc | Characterization of generalised petersen graphs that are kronecker covers[END_REF][START_REF] Bouwer | The Foster Census[END_REF].

To describe the quotients of generalised Petersen graphs, we use the LCF notation, named by developers Lederberg, Coxeter and Frucht, for the representation of cubic hamiltonian graphs (for extended description see [START_REF] Pisanski | Configurations from a graphical viewpoint[END_REF]).

In a Hamiltonian cubic graph, the vertices can be arranged in a cycle, which accounts for two edges per vertex. The third edge from each vertex can then be described by how many positions clockwise (positive) or counter-clockwise (negative) it leads. The basic form of the LCF notation is just the sequence [a 0 , a 1 , . . . , a n-1 ] of numbers of positions, starting from an arbitrarily chosen vertex and written in square brackets. To state our results, we only use a special type of such LCF-representable graphs, namely C + (n, k) and C -(n, k), which we define below. Definition 1. Let n be a positive even integer and let k < n/2 be a positive integer such that k 2 ≡ 1 (mod n). Assuming all numbers are modulo n, define graphs

C + (n, k) = n 2 , n 2 + (k -1), n 2 + 2(k -1), . . . , n 2 + (n -1)(k -1) ,
and similarly

C -(n, k) = n 2 , n 2
-(k + 1), n 2 -2(k + 1), . . . , n 2 -(n -1)(k + 1) .
It is easy to show that, under the mentioned restrictions on k from above, both graphs C + (n, k) and C -(n, k) are well defined. For the case of C + (n, k), pick an i-th chord, and (from its LCF-representation) look at the values on its endpoints a i and a i+ai -namely n/2+i(k-1) and n/2+(i+n/2+i(k-1))(k-1). The claim follows from the fact that their sum is divisible by n.

In [START_REF] Imrich | Multiple Kronecker covering graphs[END_REF] it was proven that G (10, 3) is the Kronecker cover of two non-isomorphic graphs. Here we prove among other things that this is the only generalised Petersen graph that is a multiple Kronecker cover. Every other generalised Petersen graph is either a Kronecker cover of a single graph or it is not a Kronecker cover at all. More precisely; Theorem 1. Among the members of the family of generalised Petersen graphs, G (10, 3) is the only graph that is the Kronecker cover of two non-isomorphic graphs, the Petersen graph and the graph H. For any other G G (n, k), the following holds: a) If n ≡ 2 (mod 4) and k is odd, G is a Kronecker cover. In particular

a 1 ) if 4k < n, the corresponding quotient graph is G n 2 , k , and a 2 ) if n < 4k < 2n the quotient graph is G n 2 , n 2 -k . b) If n ≡ 0 (mod 4) and k is odd, G is a Kronecker cover if and only if n | k 2 -1 2 . Moreover, b 1 ) if k ≡ 1 (mod 4) the corresponding quotient is C + (n, k) while b 2 ) if k ≡ 3 (mod 4) the quotient is C -(n, k).
c) Any other generalised Petersen graph is not a Kronecker cover.

For k = 1 and even n each G(n, 1) is a Kronecker cover. If n = 4t case b 1 ) applies and the quotient graph is the Möbius ladder M n (see [START_REF] Guy | On the möbius ladders[END_REF]). For G(4, 1) the quotient is K 4 = M 4 . Similarly, the 8-sided prism G(8, 1) is the Kronecker cover of M 8 . In case n = 4t + 2 the case a 1 ) applies and the quotient is G(n/2, 1). For instance, the 6-sided prism is the Kronecker cover of the 3-sided prism. For k > 1 the smallest cases stated in Theorem 1 are presented in Table 1.

It is well-known that any automorphism of a connected bipartite graph either preserves the two sets of bipartition or interchanges the two sets of bipartition. In the former case we call the automorphism colour preserving and in the latter case colour-reversing. Clearly, the product of two color-reversing automorphisms is a color preserving automorphism and the collection of all color preserving automorphisms determines a subgroup of the full automorphism group that is of index at most 2.

Identifying the Kronecker involutions

Before we state an important condition that classifies Kronecker covers we give the following definition. Definition 2. A color-reversing involution ω from the automorphism group of a bipartite graph is called a Kronecker involution, if the vertices v and ω(v) are non-adjacent for every vertex v.

We proceed by a well-known proposition from [START_REF] Imrich | Multiple Kronecker covering graphs[END_REF], regarding the existence of Kronecker covers.

Theorem 2. For a bipartite graph G, there exists G such that KC (G ) G, if and only if Aut(G) admits a Kronecker involution. Furthermore, the corresponding quotient graph may be obtained by contracting all pairs of vertices, naturally coupled by a given Kronecker involution.

The following result is well-known. One can find it, for instance in [START_REF] Horvat | Isomorphism checking of I-graphs[END_REF]. Theorem 3. A generalised Petersen graph G(n, k) is bipartite if and only if n is even and k is odd.

We also include the classification concerning symmetries of generalised Petersen graphs, which follows from the work of Frucht et al. [START_REF] Frucht | The groups of the generalized Petersen graphs[END_REF], Nedela and Škoviera [START_REF] Nedela | Which generalized Petersen graphs are Cayley graphs?[END_REF], and Lovrečič-Saražin [START_REF] Saražin | A note on the generalized Petersen graphs that are also Cayley graphs[END_REF]. Theorem 4 ([5,[START_REF] Nedela | Which generalized Petersen graphs are Cayley graphs?[END_REF][START_REF] Saražin | A note on the generalized Petersen graphs that are also Cayley graphs[END_REF]). Let G (n, k) be a generalised Petersen graph. Then a) it is symmetric if and only if

(n, k) ∈ {(4, 1) , (5, 2) , (8, 3) , (10, 2) , (10, 3) , (12, 5) , (24, 5)} , b) it is vertex-transitive if and only if k 2 ≡ ±1 (mod n) or if n = 10 and k = 2, c) it is a Cayley graph if and only if k 2 ≡ 1 (mod n).
In general the word symmetric means arc-transitive. For cubic graphs this is equivalent to saying vertextransitive and edge-transitive. For a generalised Petersen graph symmetric is equivalent to edge-transitive.

In order to understand which generalised Petersen graphs are Kronecker covers we have to identify all Kronecker involutions for each G(n, k). In what follows, for a given pair (n, k), our arguments rely on the structure of the automorphism group A(n, k) of G (n, k). We define three types of permutations on the vertex set of a generalised Petersen graph which are useful for describing elements of its automorphism group.

Definition 3. For i ∈ [0, n -1], define the permutations α, β and γ on V (G (n, k)) by α (u i ) = u i+1 , α (v i ) = v i+1 , β (u i ) = u -i , β (v i ) = v -i , γ (u i ) = v ki , γ (v i ) = u ki .
Let us paraphrase Theorem 5 of Loverčič-Saražin [START_REF] Saražin | A note on the generalized Petersen graphs that are also Cayley graphs[END_REF] that follows from Frucht et al. [START_REF] Frucht | The groups of the generalized Petersen graphs[END_REF] Theorem 5. If (n, k) is not one of (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), [START_REF] Nedela | Which generalized Petersen graphs are Cayley graphs?[END_REF][START_REF] Frucht | The groups of the generalized Petersen graphs[END_REF], or (24, 5), then the following holds:

• if k 2 ≡ 1 mod n, then A(n, k) = α, β, γ|α n = β 2 = γ 2 = 1, αβ = βα -1 , αγ = γα k , βγ = γβ • if k 2 ≡ -1 mod n, then A(n, k) = α, β, γ|α n = β 2 = γ 4 = 1, αβ = βα -1 , αγ = γα k , βγ = γβ In this case β = γ 2 .
• In all other cases the graph G(n, k) is not vertex-transitive and

A(n, k) = α, β|α n = β 2 = 1, αβ = βα -1
Since all of α, β and γ preserve the set of spokes, it is clear that the automorphism group of a symmetric graph is not generated by α, β and γ. As there is only five symmetric bipartite generalised Petersen graphs, we simply checked their automorphism group by using SageMath software [START_REF]The Sage Developers[END_REF], identified the Kronecker involutions, and the corresponding quotient graphs. It turns out that the quotients of generalised Petersen graphs may be obtained by Kronecker involutions from α, β, γ , except in the case n = 10 and k = 3 by another involution which we call ∆, and corresponds to the quotient graph H.

However, for the non-symmetric members of generalised Petersen graphs, Theorem 5 implies that any element of the automorphism group (including any Kronecker involution) may be expressed in terms of α, β and γ. In fact, in the next lemma we show that any such element may be expressed in a canonical way. Lemma 6. Let n ≥ 3 and 1 ≤ k < n/2 be integers such that (n, k) is not one of the pairs (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), [START_REF] Nedela | Which generalized Petersen graphs are Cayley graphs?[END_REF][START_REF] Frucht | The groups of the generalized Petersen graphs[END_REF], or (24, 5). Then any automorphism ω from A(n, k) may associated unique triple Proof: Let G (n, k) be a generalised Petersen graph and let a, b, c be arbitrary integers. Then, by definition of the three generators α, β, γ (or the three permutations) it clearly holds

(a, b, c) ∈ Z n × Z 2 × Z 2 such that ω = α a β b γ c . n k case involution quotient 4 1 b 1 α 2 γ C + (4, 1) 6 1 a 1 α 3 G(3, 1) 8 1 b 1 α 4 γ C + (8, 1) 10 1 a 1 α 5 G(5, 1) 10 3 • α 5 , ∆ G(5, 2), H 12 1 b 1 α 6 γ C + (12, 1) 12 5 b 1 α 6 γ C + (12, 5) 14 1 a 1 α 7 G(7, 1) 14 3 a 1 α 7 G(7, 3) 16 1 b 1 α 8 γ C + (16, 1) 18 1 a 1 α 9 G(9, 1) 18 3 a 1 α 9 G(9, 3) 18 5 a 2 α 9 G(9, 4) 20 1 b 1 α 10 γ C + (20, 1) 20 9 b 1 α 10 γ C + (20, 9) 22 1 a 1 α 11 G(
1. βα a = α -a β, 2. γα a = α ak γ. If k 2 ≡ 1 mod n.
3. γα a = α -ak γ. If k 2 ≡ -1 mod n.

γβ = βγ,

We omit the arguments for ( 1) and ( 4) as they are repeated from the definition. Property (2) follows from the facts αγ = γα k and k 2 ≡ 1 mod n. Since α a γ = γα ak for any a, take a = k and we get α k γ = γα k 2 = γα and the result follows. In a similar way we prove [START_REF] Bouwer | The Foster Census[END_REF]. By using the commuting rules (1-4) above we may transform any product of permutations α, β, γ to a form α a β b γ c with 0 ≤ b, c ≤ 1. In non-vertex-transitive case we have c = 0 while in vertex-transitive non-Cayley case, one could have γ, γ 2 , γ 3 . However, we may always use the fact that γ 2 = β and the result follows readily.

A shorter proof was suggested by a referee: Namely, from Theorem 5 it clearly follows that both β and γ normalize α, and so the fact that the intersection of α and β, γ (which is clearly isomorphic to one of

Z 2 , Z 2 × Z 2 and Z 4 ) is trivial implies that A(n, k) is a semidirect product of Z n by Z 2 , Z 2 × Z 2 or Z 4 .
Note that in a bipartite G (n, k) automorphisms α and γ are color-reversing, while β is color preserving.

Proposition 7. For a bipartite generalised Petersen graph G (n, k), the following statements hold:

1. α a is a Kronecker involution if and only if a = n/2 and n ≡ 2 (mod 4); 2. α a β is not a Kronecker involution; 3. if k 2 ≡ -1 (mod n), then neither α a γ nor α a βγ is a Kronecker involution, for any admissible a.

Proof: We prove the claims separately.

(1) Let ω = α a be a Kronecker involution. It is clear that ω does not fix any edge, and since ω is an involution we trivially have a = n 2 . But since ω must be color-reversing, a must at the same time be odd, hence the conclusion.

(2) Let ω = α a β be a Kronecker involution. Since ω is color-reversing, a must be odd. Letting i = a-1 2 , it is enough to observe that an edge u i u i+1 is fixed by ω. (3) In both cases, the resulting squared permutation can be written in form α a β, which contradicts the fact that the original permutation is an involution.

In every generalised Petersen graph G(n, k) the permutations α and β are automorphisms. Moreover, they generate the dihedral group D n of order 2n of automorphisms which is, in general, a subgroup of the full automorphism group A(n, k). The two vertex orbits under D n are exactly the outer rim and the union of the inner rims. The three edge orbits are outer-rim, inner-rim and the spokes. Clearly, Proposition 7 deals with Kronecker involutions from D n and in particular implies the condition for G (n, k) being Kronecker cover described in a) of Theorem 1. But additional Kronecker involutions may exist by the fact that the automorphism group of a generalised Petersen graph may be larger then D n . In the next subsection we describe these additional Kronecker involutions, which may (see (3) of Proposition 7) only happen when k 2 ≡ 1 (mod n).

Additional Kronecker involutions with k 2 ≡ 1 (mod n)

In what follows, we assume k 2 ≡ 1 (mod n) and define Q, such that k 2 -1 = Qn. The only two permissible types of involutions are α a γ and α a βγ.

For an integer i let b(i) be the maximal integer such that 2 b(i) divides i. In particular, we have

b(n) = b(k + 1) + b(k -1) -b(Q). (1)
In the following two subsections, we prove the condition for a generalised Petersen graph being a Kronecker cover, described in (b 1 ) and (b 2 ) of Theorem 1, respectively.

Involutions of type α a γ

We have ω a = α a γ such that ω a (v i ) = u ki+a and ω a (u i ) = v ki+a , so let us for easier notation define a function Ω a : Z n → Z n such that Ω a (i) = ki + a. By these definitions, Theorem 2 translates to the following properties:

P1 Permutation ω a is color-reversing if and only if Ω a (i) ≡ i (mod 2), in other words if a is even. P2 Permutation ω a is an involution if and only if Ω a (Ω a (i)) ≡ i (mod n), i.e. if a(k + 1) ≡ 0 (mod n).
P3 Permutation ω a may not fix any spoke. In particular, ω a fixes some edge if and only if there exists an integer i, such that Ω a (i) ≡ i (mod n). In other words, a is not allowed to be any multiple of (k -1) in Z n .

We now describe an alternative reformulation of the property P3. Proof: First observe that gcd(k -1, k + 1) = 2, while n | (k + 1)(k -1). But, by P2 also n | (k + 1)a holds, hence every odd divisor of gcd(n, k -1) must also divide gcd(n, a). To conclude the proof it is enough to observe that whenever a is some multiple of (k -1) in Z n (i.e. the negation of P3), it must also hold that b(gcd(n, a)) ≥ b(gcd(n, k -1)).

It is now easy to derive the existence version of our main theorem, for the involutitons of type α a γ.

Corollary 9. Let G = G(n, k) with k 2 ≡ 1 (mod n),

Involutions of type α a βγ

In this section we focus on Kronecker involutions that also include the reflection β. While this fact requires some adjustments by the fact that we are now considering involutions of type α a βγ, the subsection is mostly a compact transcript of the previous one.

Define ω a = α a βγ i.e. ω a (v i ) = u a-ki and ω a (u i ) = v a-ki , and let Ω a : Z n → Z n be a function defined as Ω a (i) = a -ki. In this case, the requirements for the ω a being Kronecker involution are by Theorem 2 equivalent to:

P1 Permutation ω a is color-reversing if and only if a is even.

P2 Permutation ω a is an involution if and only if a -ak ≡ 0 (mod n).

P3 Permutation ω a may only fix an i-th spoke if and only if there exists an integer i, such that Ω a (i) ≡ i (mod n). As before, this is equivalent to saying that a is not allowed to be any multiple of (k + 1) in Z n .

We now describe an alternative reformulation of the property P3 . Proof: First observe that gcd(k -1, k + 1) = 2, while n | (k + 1)(k -1). But, by P2 also n | (k -1)a holds, hence every odd divisor of gcd(n, k + 1) must also divide gcd(n, a). To conclude the proof it is enough to observe that whenever a is some multiple of (k + 1) in Z n (i.e. the negation of P3), it must also hold that b(gcd(n, a)) ≥ b(gcd(n, k + 1)).

It is now easy to derive the existence version of our main theorem, for the involutitons of type α a βγ.

Corollary 11. Let G = G(n, k) with k 2 ≡ 1 (mod n),
(Q) = 1, i.e. 2n | k 2 -1. Conversely, assume that b(Q) = 0. Then (1) implies b(k + 1) ≤ b(n) -1, while Lemma 10 implies b(a) ≤ b(n) -2, for otherwise P3 is violated. But b(a) ≤ b(n) -2 then violates Property P2 .
In the next section we prove that for any generalised Petersen graph except G (10, 3), all quotients are isomorphic.

Finally, for edges of type b i , b i+k , we now observe that

f (b i b i+k ) = v i v i+k if i is even, v i v i+k if i is odd. (2)
Indeed, if k is odd or even, we have

b i+k → v i+k if i + k is even, v i+k if i + k is odd. and b i-k+n → v i+n-k if i -k + n is even, v i+n-k if i -k + n is odd,
respectively. Keep in mind that all subscripts on the right hand side are modulo n. By (2) we conclude that edges of type b i b i+k correspond to the edges of type (E3) in G . Since both G and H are by definition cubic and of the same cardinality, the isomorphism follows.

It remains to describe the behavior of the rest of Kronecker involutions satisfying the conditions n ≡ 0 (mod 4) and n | k 2 -1 2 , while k < n 2 . In the next subsection we describe their equivalence (for fixed n, k), and also the corresponding quotient structure.

The rim-switching Kronecker involutions

Let us now turn to the Kronecker involutions containing permutation α, which are described by item b) in Theorem 1, so we assume that k 2 ≡ 1 (mod n) and Q = k 2 -1 n is even. In addition, we assume that our involution is of type α i γ (or α i βγ), whenever k ≡ 1 (mod n) (or k ≡ 3 (mod n)), respectively. We will say that a positive integer a is nice whenever α a γ or α a βγ, is a Kronecker involution.

In contrast with involutions from D n , whenever G (n, k) admits a rim-switching Kronecker involution, there may exist several different such involutions, so we will first enumerate all such involutions. These involutions could potentially give rise to several non-isomorphic quotients. In order to show that this is not the case, we will need the following extension of the LCF notion. It is easy to see that both graphs C + (n, k) and C -(n, k) from Definition 1 correspond to [ n 2 + (k -1)x] and [ n 2 -(k + 1)x], respectively. In order to complete the proof of the main theorem, it remains to show that for all possible Kronecker involutions, the corresponding quotient is unique. We split the further analysis into two cases, depending on the value of k (mod 4).

Case 1: k ≡ 1 (mod 4)

Define a min = n/gcd(n, k + 1). The next lemma describes all nice values and hence enumerates the Kronecker involutions for this case.

Lemma 13. The value a min is the smallest nice value. Furthermore, a is nice whenever a ≡ sa min (mod n) for some odd integer s.

Proof: From P2 it follows that a(k + 1) is a multiple of n. In other words, there exists a positive integer C, such that a = Cn k+1 . It is clear that a is minimized whenever Cn = lcm(k + 1, n), i.e.

a min = lcm(k + 1, n) k + 1 = n gcd(n, k + 1)
.

Note that in general C may be some s-th multiple of lcm(k + 1, n)/n, however, by Lemma 8, such value of s corresponds to a nice value if and only if s is positive and odd.

After showing that any positive odd s defines a = sa min and subseqently a Kronecker involution of the form α a γ, with Ω a (i) = a + ki, let us look at the corresponding quotient graph G . By Definition 1 and Theorem 2 the graph G is isomorphic to an outer-rim, augmented by a matching edges of type

i ∼ Ω -1 a (i), which implies G [f a ],
where

f a (i) = Ω -1 a (i) -i = ik + a -i.
To show that for any odd s, all instances of corresponding Kronecker involutions are equivalent, we first prove the following lemma.

Lemma 14. Let a = a + gcd(k -1, Q) • a min . Then [f a ] [f a ]. Proof: First notice a min = Qn gcd(Qn,Q(k+1)) = k-1 gcd(Q,k-1) .
To prove the claim it is enough to observe that the LCF sequence of graph [f a ] is equivalent to the LCF sequence of [f a ], cyclically shifted by one, i.e. f a (i) = f a (i + 1). Indeed, this is clear as

f a (i) = a + gcd(k -1, Q)a min + i(k -1) = a + (i + 1)(k -1) = f a (i + 1).
We are now ready to show item b 1 ) of Theorem 1.

Proposition 15. Let k 2 ≡ 1 (mod n) with n | k 2 -1 2 and k ≡ 1 (mod 4). Then G (n, k) have unique quotient [f ].
Proof Proof of b 1 ) of Theorem 1: Let S be the set of all gcd(n, k + 1)/2 Kronecker involutions. Lemma 14 partitions S into equivalence classes with respect to the relation of having the corresponding quotients isomorphic. We show that all elements of S are members of the same equivalence class.

In other words, this is equivalent to being in an additive group of order gcd(n,k+1) 2 and calculating the order of the element gcd(Q,k-1)

2

. Clearly, all classes of such partition of S have the same cardinality, while the number of these classes is equal to

gcd gcd(n, k + 1) 2 , gcd(Q, k -1) 2 = gcd n 2 , k + 1 2 , k -1 2 , Q 2
≤ gcd k + 1 2 , k -1 2 = 1.
But then any Kronecker involution corresponds to the unique quotient C + (n, k). For this case of k ≡ 1 (mod 4), an easy example of such an involution is α n/2 γ.

Case 2: k ≡ 3 (mod 4)

Define a min = n/gcd(n, k + 1). We will say that a positive integer a is nice whenever ω a = α a βγ is a Kronecker involution. We proceed by enumerating the Kronecker involutions for this case.

Lemma 16. The value a min is the smallest nice value. Furthermore, a is nice whenever a ≡ sa min (mod n) for some odd integer s.

Proof: From P2 it follows that a(k -1) is a multiple of n. In other words, there exists a positive integer C, such that a = Cn k-1 . It is clear that a is minimized whenever Cn = lcm(k -1, n), i.e.

a min = lcm(k -1, n) k -1 = n gcd(n, k -1)
.

Note that in general C may be some s-th multiple of lcm(k -1, n)/n, however, by Lemma 10, such value of s corresponds to a nice value if and only if s is positive and odd.

After showing that any odd s defines a = sa min and subseqently a Kronecker involution of the form ω a = α a βγ, with Ω a (i) = a -ki. By Definition 1 and Theorem 2 the corresponding quotient graph G is isomorphic to an outer-rim, augmented by matching edges of type

i ∼ Ω -1 a (i), which implies G [f a ], where f a (i) = Ω -1 a (i) -i = a -ik -i.
Before we can show the item b 2 ) of Theorem 1, we need tp prove the following lemma.

Lemma 17. Let a = a + gcd(k + 1, Q) • a min . Then [f a ] [f a ].
Proof: Again notice a min = Qn gcd(Qn,Q(k-1)) = k+1 gcd(Q,k+1) . We similarly prove the claim by observing f a (i) = f a (i -1). Indeed, we have f a (i) = a + gcd(k + 1, Q)a min -i(k + 1) = a -(i -1)(k + 1) = f a (i -1).

The following proposition is equivalent to the item b 2 ) of Theorem 1. Proof Proof of b 2 ) of Theorem 1: Let S be the set of all gcd(n,k-1) 2 Kronecker involutions. Again, we show that Lemma 17 eventually covers the whole set S.

In this case one may consider an additive group of order gcd(n,k-1) 2 and calculate the order of the element gcd(k+1,Q) We finally conclude that also in this case of k ≡ 3 (mod 4), any Kronecker involution corresponds to the unique quotient C -(n, k).

Since we described the quotients of all existing Kronecker involutions, this concludes the proof of Theorem 1. We conclude with an observation about an easy example of rim-switching Kronecker involutions whenever they exist, by simply setting a = n/2.

Corollary 19. Let G (n, k) admit a rim-switching Kronecker involution. Then either α n/2 γ or α n/2 βγ is such a Kronecker involution.

Proof: Assume k ≡ 1 (mod 4) and observe that setting a = n/2 immediately satisfies P1 and P2. To conclude the proof it is hence enough to observe that b(n/2) = b(n) -1, which is by Lemma 8 equivalent to P3. We omit the case of k ≡ 3 (mod 4) as it is the same.

Concluding remarks and future work

In this paper, we classified parameters (n, k) such that G (n, k) is a Kronecker cover of some graph, and described the corresponding quotients. From our main result it easily follows:

Corollary 20. KC (G (n, k)) is itself a generalised Petersen graph if and only if n is odd.

We analyzed the problem of Kronecker covers of the family of generalised Petersen graphs. It would be interesting to transfer this problem to the family of I-graphs [START_REF] Boben | I-graphs and the corresponding configurations[END_REF][START_REF] Bouwer | The Foster Census[END_REF][START_REF] Petkovšek | Enumeration of I-graphs: Burnside does it again[END_REF][START_REF] Horvat | Isomorphism checking of I-graphs[END_REF] or Rose-Window graphs [START_REF] Wilson | Rose window graphs[END_REF], or some other families of cubic or quartic graphs.

Graphs KC (G (n, k)) that are not generalised Petersen graphs, in other words if n is even, fall into two known classes, depending on the parity of k. If k is odd, we have KC (G (n, k)) = 2G (n, k). It would be interesting to investigate the family of graphs KC (G (n, k)) with both n and k even. The smallest case is depicted in Figure 2. This is the Kronecker cover of the Dürer graph G (6, 2).

Fig. 1 :

 1 Fig. 1: The Desargues graph and both its quotients; H and the Petersen graph.

Lemma 8 .

 8 Assume that properties P1 and P2 hold. Then the property P3 is equivalent to b(gcd(n, a)) < b(gcd(n, k -1)).

1 2and k ≡ 1 ( 1 2and k ≡ 1 (

 1111 and let a be an integer. Then G admits a Kronecker involution of type α a γ if and only if n | k 2 -mod 4).Proof: By Theorem 2 and Lemma 8, a permutation α a γ is a rim-switching Kronecker involution if and only if b(gcd(n, a)) < b(gcd(n, k -1)), in addition to the properties P1 and P2.It is easy to see that in the case when these properties hold for α a γ, we also have n | k 2 -mod 4). Indeed, as n and a are both even, it follows that 4 | gcd(n, k -1), in particular 4 | n, and k ≡ 1 (mod 4), and hence trivially b(k + 1) = 1. Now observe that by Lemma 8 the only possible values for b(k -1) and b(a) are b(n) and b(n) -1, respectively. But then (1) implies b(Q) = 1, i.e. 2n | k 2 -1. Conversely, assume that b(Q) = 0. Then (1) implies b(k -1) ≤ b(n) -1, while Lemma 8 in turn implies b(a) ≤ b(n) -2, for otherwise P3 is violated. But b(a) ≤ b(n) -2 then violates Property P2.

Lemma 10 .

 10 Assume that properties P1 and P2 hold. Then the property P3 is equivalent to b(gcd(n, a)) < b(gcd(n, k + 1)).

1 2 1 2and k ≡ 3 (

 113 and let a be an integer. Then G admits a Kronecker involution of type α a βγ if and only if n | k 2 -and k ≡ 3 (mod 4).Proof: By Theorem 2 and Lemma 10, a permutation α a βγ is a rim-switching Kronecker involution if and only if b(gcd(n, a)) < b(gcd(n, k + 1)), in addition to the properties P1 and P2 .It is easy to see that in the case when these properties hold for α a βγ, we also have n | k 2 -mod 4). Indeed, as n and a are both even, it follows that 4 | gcd(n, k + 1), in particular 4 | n, and k ≡ 3 (mod 4), and hence trivially b(k -1) = 1. Now observe that by Lemma 10 the only possible values for b(k + 1) and b(a) are b(n) and b(n) -1, respectively. But then (1) implies b

Definition 4 .

 4 For an involution g without fixed points of type [n] → [n], we define f (i) = g(i) -i and write, for short, [f ] instead of [f (0), f (1), . . . , f (n -1)].

Proposition 18 . 1 2

 181 Let k 2 ≡ 1 (mod n) with n | k 2 -and k ≡ 3 (mod 4). Then G (n, k) have the unique quotient C -(n, k).

2 .

 2 The number of such orbits is equal to gcd gcd(n, n -k + 1

Fig. 2 :

 2 Fig. 2: The Dürer graph G (6, 2) and its Kronecker cover KC(G (6, 2)) with proper vertex two-coloring.

Acknowledgements

We would like to thank A. Hujdurović and A. Žitnik for helpful comments and discussions and Gábor Gévay for the drawing of KC(G (6, 2)). In particular, we would like to thank to the anonymous referee for useful comments which resulted in shortening some parts of this exposition. The authors gratefully acknowledge the European Commission for funding the InnoRenew CoE project (Grant Agreement #739574) under the Horizon2020 Widespread-Teaming program and the Republic of Slovenia (Investment funding of the Republic of Slovenia and the European Union of the European regional Development Fund). The second author gratefully acknowledges financial support of the Slovenian Research Agency, ARRS, research program no. P1-0294. The first author gratefully acknowledges financial support of the same agency, research project J1-1692 and research program P1-0383. The results of this paper have been presented at EUROCOMB 2019 and an extended abstract has been published in [10].

The quotients of generalised Petersen graphs

For a given generalised Petersen graph, so far we identified all its Kronecker involutions. In this section we determine the structure of the corresponding quotient graphs, for each of these involutions. Namely, the next two subsections deal with the structural part of the statements a) and b) of Theorem 1, respectively.

Involutions of D n

We already know that the only Kronecker involution in the Dihedral group is the rotation α n/2 , which is realized whenever n ≡ 2 (mod 4) and k is odd. In order to prove a) of Theorem 1, it is enough to show the following proposition, which describes the corresponding quotient graph explicitly.

Proposition 12. For an odd n and an integer k < n 2 , we have

Proof Proof of a) from Theorem 1: Let G G(n, k) and G KC (G), for an odd integer n and k < n 2 . The edges of KC (G) are naturally partitioned into the following three groups:

For easier notation, define k to be equal to k or n-k, depending on whether k is odd or even, respectively. Furthermore, let H := G (2n, k ) and denote its vertex set with V (H) = {a 0 , . . . , a 2n-1 , b 0 , . . . , b 2n-1 } , while its edge set consists of edges of the form a i a i+1 , a i b i and b i , b i+k . To show the left implication of Proposition 12, it is enough to show that G H. Throughout the proof all subscripts for vertices of H (on the left-hand side) are assumed to be modulo 2n, while all subscripts for vertices of G (on the right-hand side) are assumed to be modulo n. To show an equivalence, we introduce a bijection f : V (H) → V (G ), such that

for any 0 ≤ i < 2n. Since n is odd, f is clearly a bijection and it is enough to show that f is a homomorphism between H and G . We now check that all edges of H map to edges in G . First observe that in H, edges of types a i a i+1 and a i b i map to these in (E2) and (E1), respectively. Indeed, by definition we have


Toufik Bakir
email: toufik.bakir@u-bourgogne.fr

Bernard Bonnard
email: bernard.bonnard@u-bourgogne.fr

Jérémy Rouot
email: jeremy.rouot@grenoble-inp.org

Connection between singular arcs in optimal control using bridges. Physical occurence and Mathematical model

Keywords: Pontryagin maximum principle, Singularity theory, Geometric control

Connection between singular arcs in optimal control using bridges. Physical occurence and Mathematical model

I. INTRODUCTION

In this article we consider a real analytic single input control system in R n-1 of the form: dc dt = f (c, T ), c ∈ R n-1 , T ∈ R which is extended using the Goh transformation u = dT dt onto the control affine system dx dt = F (x) + u G(x), x = (c, T ) ∈ R n and the set U of admissible controls is the set of bounded measurable mappings defined on [0, t f (u)], and valued into [-1, 1] (such model being motivated by the control of chemical reaction networks where c is the vector representing the concentrations of the chemical species and T is the temperature).

We consider the time-minimal control problem where x(0) = x 0 is fixed and x(t f ) ∈ N where N is the (analytic) terminal manifold. According to the Maximum Principle [START_REF] Pontryagin | The mathematical theory of optimal processes[END_REF] an optimal solution has to be found among the extremal triplets (x(•), p(•), u(•)), p ∈ R n \ 0 solutions for a.e. t ∈ [0, t f ] of the pseudo-Hamiltonian system:

ẋ(t) = ∂H ∂p (x(t), p(t), u(t)), ṗ(t) = - ∂H ∂x (x(t), p(t), u(t)), (1)
H(x(t), p(t), u(t)) = M (x(t), p(t))

where H(x, p, u) = p • (F (x) + u G(x)) is the pseudo Hamiltonian, • stands for the scalar product and M (x, p) = max |u|≤1 H(x, p, u) is the maximized Hamiltonian. Moreover M (x(t), p(t)) is a non-negative constant along an extremal solution and one has p(t f ) ⊥ T x(t f ) N (transversality equation).

p(t) • G(x(t)) = 0 a.e. on [0, t f ]. (3)
Note that a general extremal is a concatenation of such subcases.

In the second case, the singular control u s (t) can be obtained differentiating twice the equation (3) as follows.

Introducing the Lie bracket of two vector fields Z 1 , Z 2 :

[Z 1 , Z 2 ](x) = ∂Z1 ∂x (x)Z 2 (x) -∂Z2 ∂x (x)Z 1 (x) one gets: p(t) • G(x(t)) = p(t) • [G, F ](x(t)) = 0 (4) p(t) • ([[G, F ], F ] + u(t) [[G, F ], G])(x(t)) = 0 (5) From (5) if p(t) • [[G, F ], G](x(t)
) is non zero, the singular control u s (t) can be defined as

u s (t) = - p(t) • [[G, F ], F ](x(t)) p(t) • [[G, F ], G](x(t)) . (6)
Moreover from the high order Maximum Principle [START_REF] Krener | The high order maximal principle and its application to singular extremals[END_REF], the so-called Legendre-Clebsch condition:

∂ ∂u d 2 dt 2 ∂H ∂u = p(t) • [[G, F ], G](x(t)) ≥ 0
is a necessary time optimality condition. Connection between singular arcs and regular arcs are authorized to compute the optimal solutions and such connection occur when meeting the switching surface: Σ : p • G(x) = 0. Such a phenomenon was analyzed in the generic case in the seminal article [START_REF] Kupka | Geometric theory of extremals in optimal control problems. I. The fold and Maxwell case[END_REF] and it can be used in many case to compute the so-called turnpike optimal solution of the form σ ± σ s σ ± where σ ± is a bang arc and σ s is a singular arc (the arc σ 1 σ 2 represents an arc σ 1 followed by σ 2 ). The objective of this article is to analyze the connection between singular arcs using a bridge that is a bang arc which is tangent to Σ at both extremities, which leads to optimal solutions of the form σ ± σ s σ ± σ s σ ± . . . This phenomenon was obtained in many cases in the problem of multisaturation of spin particles see [START_REF] Bonnard | Time minimal saturation of a pair of spins and application in Magnetic Resonance Imaging[END_REF] or [START_REF] Lapert | Singular extremals for the time-optimal control of dissipative spin 1/2 particles[END_REF] for a single spin, that is to drive the magnetization vector from the North pole to the center of the Bloch ball, where the system is of the form:

ẋ = -Γx -uy, ẏ = -γ(y -1) + ux, |u| ≤ 1 (7)
with 0 < γ ≤ 2Γ, Γ, γ being the relaxation parameters.

The main contribution of this article is to present this important physical example to derive a mathematical model in dimension two. In particular it can be used to complete our programs of optimizing the yield of batch chemical reactors by controlling the temperature [START_REF] Bonnard | Classification générique de synthèses temps minimales avec cible de codimension un et applications[END_REF], [START_REF] Bonnard | Time minimal control of batch reactors[END_REF].

The organization of this article is the following. In section II, we present a recap of the classification of extremals near the switching surface in the so-called fold case [START_REF] Kupka | Geometric theory of extremals in optimal control problems. I. The fold and Maxwell case[END_REF] which is the basis of the geometric construction of bridges. In section III, the saturation of the spin case is described in details based on [START_REF] Bonnard | Time minimal saturation of a pair of spins and application in Magnetic Resonance Imaging[END_REF]. This leads to construct in section IV a planar mathematical model. Occurrence of bridges for chemical networks are computed in the final section.

II. CONCEPT AND RECAP ABOUT THE CLASSIFICATION OF EXTREMALS [8]

A. Notations

We denote by σ + (resp. σ -) a bang arc which constant control +1 (resp. -1) and σ s is a singular arc. We note σ 1 σ 2 an arc σ 1 followed by σ 2 . The surface

Σ : p • G(x) = 0 is called the switching surface. If z(•) = (x(•), p(•)) is an extremal curve on [0, t f ], we note Φ(t) = p(t) • G(x(t))
the switching function (which codes the switching times). Differentiating twice with respect to time one gets:

Φ(t) = p(t) • [G, F ](x(t)), (8)
Φ(t) = p(t) • ([[G, F ], F ]](x(t)) + u(t) [[G, F ], G]](x(t))) . (9)
From this calculus we deduce: Ordinary switching time. t ∈ [0, t f ] is called an ordinary switching time and z(t) an ordinary switching point if Φ(t) = 0 and Φ(t) = 0. From that we deduce: Lemma 1. In the ordinary case, near z(t) every extremal solution is of the form σ + σ -if Φ(t) < 0 and σ -σ + if Φ(t) > 0.

The Fold case. If Φ ε (t) = Φε (t) = 0 and Φε (t) = p(t) • ([[G, F ], F ]](x(t)) + ε [[G, F ], G]]) (x(t)) = 0, ε = ±1, the point z(t) = (x(t), p(t)) is called a fold point. If moreover p • G(x) = p • [G, F ](x)
is regular, we have three cases:

• Case 1. parabolic case: Φ+ (t) Φ-(t) > 0. • Case 2. hyperbolic case: Φ+ (t) > 0 and Φ-(t) < 0. • Case 3. elliptic case: Φ+ (t) < 0 and Φ-(t) > 0.
Moreover denotes by u s (t) the singular control defined by

p(t) • ([[G, F ], F ]](x(t)) + u s (t) [[G, F ], G]]) (x(t)) = 0 one has Theorem 1.
In a neighborhood of z(t) every extremal solution is of the form:

• Parabolic case: σ + σ -σ + or σ -σ + σ - • Hyperbolic case: σ ± σ s σ ± • Elliptic case: each extremal is bang-bang, i.e. of the form σ + σ -σ + σ -.
. . but the number of switches is not uniformly bounded.

The concept of bridge. From the previous analysis, a bridge is a bang arc (σ b + or σ b -) connecting two different hyperbolic points so that σ ± σ s σ b ± σ s σ ± is an authorized extremal curve.

III. THE OCCURRENCE OF (OPTIMAL) BRIDGES IN MAGNETIC RESONANCE IMAGING [2]

We consider the problem of transferring the system from the North pole N = (0, 1) to the center O = (0, 0) of the Bloch ball so that the system takes the form

F = -Γx ∂ ∂x + γ(1 -y) ∂ ∂y , G = -y ∂ ∂x + x ∂ ∂y .
where Γ, γ are the relaxation parameters and 0 < γ ≤ 2Γ.

Note that F is affine with a single stable node equilibrium at the North pole and integral curves of G are circles.

To make the analysis denoting δ = γ -Γ, we need the following Lie brackets

[G, F ] = (-γ + δy) ∂ ∂x + δx ∂ ∂y , [[G, F ], F ] = (γ(γ -2Γ) -δ 2 y) ∂ ∂x + δ 2 x ∂ ∂y , [[G, F ], G] = 2δx ∂ ∂x + (γ -δy) ∂ ∂y .
Singular arcs. They are located on the set S : det(G, [G, F ]) = 0 which is given by x(γ -2δy) = 0. Hence, they are two lines: the y-axis of symmetry and the horizontal line L : y 0 = γ/(2δ). These lines intersect the Bloch ball x 2 + y 2 < 1 whenever 2Γ > 3γ and moreover with y 0 < 0.

Along the vertical line, the singular control is zero and along L it is given by: D

(x) + u s D(x) = 0 where D = det(G, [[G, F ], G]) and D = det(G, [[G, F ], F ]). Computing we have u s = γ(2Γ -γ)/(2δ)x and u s → ∞ when x → 0.
The strict Legendre-Clebsch condition from [START_REF] Krener | The high order maximal principle and its application to singular extremals[END_REF] is used to distinguish between fast and slow displacement direction. Introducing D = det(G, F ) we have: fast if DD > 0 and slow if DD < 0.

Computing we have:

• The horizontal line is fast • The vertical line is fast if 1 > y > y 0 = γ/(2δ) and slow if y 0 = γ/(2δ) > y > -1. We represent in Fig. 1 the optimal policy to drive the North pole to the center O computed for parameters such that 0 < 3γ < 2Γ. By symmetry we represent the policy in the domain x < 0. Note that the bridge occurs at S 2 before the saturating point S 3 where |u s | = 1. The optimal policy is σ + σ h s σ b + σ v s where σ h s , σ v s are respectively the horizontal and vertical singular arc, σ b + is the bridge. This policy can be compared to the standard inversion sequence σ + σ v s used in practice.

From the previous analysis one use the following in terms of Lie brackets at (0, y 0 ) which is the intersection of the singular lines:

p • [[G, F ], G](0, y 0 ) = 0. Moreover p • [[G, F ],
G](0, y 0 ) > 0 for y > y 0 and < 0 if y < y 0 and p can be seen on the picture thanks to the relation p • G(x) = 0. Conditions on the parameters to have a bridge can be obtained computing Lie brackets up to order 4 at (0, y 0 ).

x y L ® σ + ® σ v s ® σ + ® σ h s ® σ + ® σ v s N • O • • y 0 • S 2 • • S 3 •

IV. CONSTRUCTION OF A PLANAR (SYMMETRIC) MODEL

From the previous example we shall construct a local model (near (0, y 0 ) in the previous example) which exhibits the previous behaviors.

A. Birth of the model.

We start with the following planar model:

ẋ = u ẏ = 1 -εx 2
where the singular arc σ s is identified to t → (0, t) and corresponds to u s (t) = 0. Such a line is fast if ε > 0 and slow if ε < 0.

Let us consider now

ẋ = u ẏ = 1 -x 2 y. Computing we have [G, F ] = 2xy ∂ ∂y and [[G, F ], G] = 2y ∂ ∂y .
Hence singular trajectories are the two lines: x = 0 and y = 0. By construction the vertical line can be followed by u = 0 and the horizontal line can be followed by "u = ∞" so it cannot be tracked in practice. To construct the model one must bend this line and we get the following.

B. The model

We consider the system

ẋ = F (x) + u G(x), t f ← min |u|≤1 , x = (x, y) (10)
where F = (1x 2 y) ∂ ∂y and G = -(y -1) ∂ ∂x + x ∂ ∂y . Note that integrating G led to circles centered at x = 0, y = 1.

Computations. We have

• [G, F ](x) = (-1 + x 2 y) ∂ ∂x + (2xy(1 -y) + x 3 ) ∂ ∂y , • [[G, F ], G](x) = 2x(x 2 -2(y -1)y) ∂ ∂x +(x 2 (5-8y)+ 2y 3 -4y 2 + 2y + 1) ∂ ∂y , • [[G, F ], F ](x) = (x 2 -x 4 y) ∂ ∂x + x(x 4 + 4x 2 y 2 -6y + 2) ∂ ∂y , • det(G, [G, F ])(x) = x(x 2 (1-2y)+2y 3 -4y 2 +2y+1), • D(x, y) = det(G, [[G, F ], G])(x) = -2x 4 + x 2 (12y 2 - 17y + 5) -2y 4 + 6y 3 -6y 2 + y + 1, • D (x) = det(G, [[G, F ], F ])(x) = x(x 4 + x 2 (-4y 3 + 4y 2 -1) + 6y 2 -8y + 2), • Collinearity set: D (x) = 0 with D (x) = det(G, F )(x) = (y -1)(x 2 y -1).
Singular trajectories. The singular set is defined by Σ s = {q, det(G, [G, F ])(q) = 0} and we have Lemma 2. The singular trajectories corresponds to the union of the vertical line (Oy) and the algebraic curve defined by l(x, y) := x 2 (1 -2y) + 2y 3 -4y 2 + 2y + 1 = 0.

Remark 1. The equation l(x, y) = 0 is equivalent to x = ± 2y 3 -4y 2 +2y+1 2y-1

. We denote by L the horizontal component and by L the vertical component (see Fig. 2).

Moreover Σ s ∩ (Oy) = {(0, y 0 )} where y 0 -0.297157 is the unique real root of l(0, y) = 0.

Bridge bang arc. Consider the problem of minimizing the time to reach the origin starting from the point (x(0), y(0)) = (-1, -1) and under the dynamics defined by [START_REF] Lapert | Singular extremals for the time-optimal control of dissipative spin 1/2 particles[END_REF]. A time minimal solution is of the form σ -σ s σ b + σ s where σ -is a bang arc associated to u = -1, σ s is a singular arc and σ b + is a bridge that is a bang arc connecting two points of the singular line (see Fig. 3). From the following computations

• along (Oy), D • D = (y -1) 2 2y 3 -4y 2 + 2y + 1 , • along L, D•D = 2 79y 2
0 -120y 0 + 74 (y 0 -y)/(1-2y 0 ) 4 + o(yy 0 ), we have Proposition 1. The vertical singular line (Oy) is hyperbolic for y > y 0 , elliptic for y < y 0 . The singular set L is hyperbolic.

The singular control along (Oy) is zero and the expression of the singular control along L ∩ {x ≤ 0} is u s = -D D = -8y 7 +30y 6 -44y 5 +38y 4 -27y 3 +15y 2 -6y+2 √ (2y-1)(2y 3 -4y 2 +2y+1)(8y 3 -15y 2 +9y-3)

and there is two saturated points. By rescaling one can make y 0 → 0 and this leads to a complicated synthesis near 0. Remark 3. Interaction between two singular lines is coded by the singularities of the flow: ẋ = F (x) -D (x) D(x) G(x) since D + u s D = 0. It can be analyzed using time reparameterization to lead to ẋ = D(x)F (x) -D (x)G(x). This geometric remark is crucial for the extension to the non planar case that we present next.

V. EXTENSION TO THE n-DIMENSIONAL CASE AND AN APPLICATION TO CHEMICAL NETWORKS

A. Extension

Due to the space restriction we shall consider the situation n = 3, which already contains all the technical difficulties. In this case, we introduce the following determinants:

D = det(G, [G, F ], [[G, F ], G]), D = det(G, [G, F ], [[G, F ], F ]), D = det(G, [G, F ], F )
and from ( 4)-( 5)-( 6) the singular control is given by

u s (x) = - D (x) D(x) .
We have three types of singular trajectories coming from the fold case classification:

• hyperbolic: D D > 0 • elliptic: D D < 0 and the so-called exceptional case corresponds to singular trajectories such that H = p • F (x) = 0. Eliminating p leads to

• exceptional: D = 0.
Note that in this case the adjoint vector is either p or -p.

Moreover using [START_REF] Bonnard | Théorie des singularités et optimalité des trajectoires singulières dans le problème temps minimal[END_REF] the small time optimality status is: time minimizing in the hyperbolic and exceptional case, time maximizing in the elliptic case.

Again, since the singular trajectories are solutions of: ẋ = F (x) -D (x) D(x) G(x) connections between singular arcs are related to the behaviors of the solution of the reparameterized equation:

ẋ = D(x)F (x) -D (x)G(x)
and in particular near the non isolated equilibria contained in D = D = 0. This is the main issue for n ≥ 3 to analyze connections between singular arcs using a bridge in relation with the occurrence of p(t)

• [[G, F ], G](x(t)) = 0.

B. Application to chemical networks

We shall outline the discussion of the occurrence of bridges for chemical networks, extending results from [START_REF] Bonnard | Classification générique de synthèses temps minimales avec cible de codimension un et applications[END_REF], [START_REF] Bonnard | Time minimal control of batch reactors[END_REF]. The problem of maximizing the yield of one species [X] is converted into a minimizing the time to produce a fixed [X] = d ([X] denoting the concentration of the species X).

One consider two reactions schemes:

Case 1: A B C k1 k2
: sequence of two irreversible reactions k i = A i exp(-E i /(RT )), i = 1, 2, A i , E i are parameters, R is the gas constant and T is the temperature.

We

introduce v = k 1 , x = log[A], y = [B], α = E 2 /E 1 , β = A 2 /A α
1 so that the dynamics takes the form:

F = -vx ∂ ∂x +(vx-βv α y) ∂ ∂y , G = ∂ ∂v and the terminal manifold is N = {[B] = y = d}. Computing one has • [G, F ] = x ∂ ∂x + (-x + αβv α-1 y) ∂ ∂y , E S v = A 1 O v x α < 1 O x v = A 1 S E v α > 1.
[[G, F ], G] = (α(α -1)βv α-2 y ∂ ∂y , • [[G, F ], F ] = ((α -1)βv α x ∂ ∂y , • D = det(G, [G, F ], [[G, F ], G]) = α(α -1)βxyv α-2 , • D = det(G, [G, F ], [[G, F ], F ]) = (α -1)βx 2 v α , • D = det(G, [G, F ], F ) = (α -1)βxyv α .
One wants to detect the existence of bridges near the terminal manifold. In the discussion we introduce the following stratification of N .

• E : exceptional set: n • F = 0 with n = (0, 1, 0) normal to N and we get E : vxβyv α = 0,

• S : singular arcs so that n

• G = n • [G, F ] = 0, that is -x + αβyv α-1 = 0.
We represent E and S on Fig. 5 in the two cases α > 1 and α < 1.

Note that E forms the boundary of the terminal manifold which can be reached from y(0) < d. In case α > 1, there exists no admissible singular arcs and the optimal policy is u = +1. In the case α < 1, there exists hyperbolic singular arcs. where

k i = A i exp(-E i /(RT )), i = 1, 2, 3. Denote v = k 1 , α = E 2 /E 1 , α = E 3 /E 1 , β = A 2 /A α 1 , β = A 3 /A α 1 , x x = [A], [y] = [B]
so that the dynamics is defined by

F = (-vx + β v α y) ∂ ∂x + (vx -β v α y -βv α y) ∂ ∂y and G = ∂ ∂v . One has • [G, F ] = (x -α β v α -1 y) ∂ ∂x + (-x + α β v α -1 y + αβv α-1 ) ∂ ∂y , • [[G, F ], G] = (-α (α -1)β v α -2 y) ∂ ∂x + (α (α - 1)β v α -2 y + α(α -1)βv α-2 ) ∂ ∂y , • D = det(G, [G, F ], [[G, F ], G]) = α(α -1)βxyv α-2 + α β αβ(α -α)v α+α -3 y 2 • D = det(G, [G, F ], [[G, F ], F ]) = y 2 αβ 2 β (α - α )v 2α+α -2 -α ββ 2 (α -α)v α+2α -2 + β(αα β - αβ )v a+α -1 + βxy(2α β -2αβ )v a+α -1 + (α - 1)βx 2 v α • D = det(G, [G, F ], F ) = -βv α xy + (α - α)ββ v α +α-1 y 2 .
Computing E and S with y = d leads to

• exceptional case: E : n•F = vx-v α d βv α-α +β = 0. • singular case: S : n • [G, F ] = dv α -1 αβv α-α + α β -x = 0.
From which we deduce that E ∩ S is defined by

x = dβ v α -1 α -α α -1 v α-α = - β (α -1) β(α -1) .
We represent on Fig. 6, E and S for specific values of the parameters such that

• E ∩ S = ∅ • A "semi-
ẋ = 1 + a y -3c yz + c z 3 ẏ = z ż = u, |u| ≤ 1. (11)
Writing the dynamics as q = F (q)+u G(q), q = (x, y, z), we have the following computations

• F = (1 + a y -3c yz + c z 3 ) ∂ ∂x + z ∂ ∂y , • G = ∂ ∂z • [G, F ] = 3c(y -z 2 ) ∂ ∂x -∂ ∂y , • [[G, F ] , G] = -6cz ∂ ∂x , • [[G, F ] , F ] = a ∂ ∂x , • D = det(G, [G, F ], [[G, F ], G]) = -6cz, • D = det(G, [G, F ], [[G, F ], F ]) = a.
Proposition 2. The system (11) satisfies the following properties :

• N : x = 0 is the terminal manifold, • G = ∂ ∂z , • S : n • [G, F ] (q) = 0, x = 0 is y = z 2 , • n • [[G, F ] , G] (0) = 0 and n • [[G, F ], F ](0) = 0,
• the trajectory associated to u = 0 defined on [t f , 0] with σ(0) = 0 is γ → (t, 0, 0).

Figure 7 represents the stratification of the terminal manifold for the system [START_REF] Pontryagin | The mathematical theory of optimal processes[END_REF].

Singular flow: Next we present the main properties of the singular flow. Proposition 3. The singular control is given by u s (q) = -D (q)/D(q) = a/(6c z) and the singular trajectories can be integrated by quadratures. This allows to compute the singular leaf passing through q(0) ∈ S : {y(0) = z(0) 2 , x(0) = 0}. We proceed as follows. Parameterizing by z, the singular trajectories are solutions of dy dz = 6c z 2 /a dx dz = (1 + a y -3c yz + c z 3 ) 6c z/a. From the first equation we deduce, with y(z(0), z(0)) = z(0) 2 , y(z, z(0)) = 2c (z 3 -z(0) 3 )/a+z(0) 2 . Plugging such y into the second equation, one gets, with x(z(0), z(0)) = 0, x(z, z(0)) = g(z, z(0))g(z(0), z(0)) where g(z, z(0)) = 3cz 2 5a 2 2a(2c + 1) z 3 + 30cz(0) 2 (a -2cz(0)) z + 30c 2 z 4 + 5a(az(0) 2 -2cz(0) 3 + 1) .

VI. CONCLUSION

In view of applications to optimize the yield of chemical batch reactors we have analyzed the so-called bridge phenomenon in optimal control that is a connection between two singular arcs using a bang arc. Based on the occurrence of this phenomenon in Magnetic Resonance Imaging we have constructed a planar mathematical model to analyze this phenomenon. This is extended in dimension 3 to describe cases where bridges can occur for chemical networks, in relation with reversibility. Note that in this example the singular set is only folded and more complicated chemical schemes have to be used to get ramifications.

Fig. 1 .

 1 Fig. 1. (left) Time optimal policy with a bridge compared with (right) inversion sequence.

Fig. 2 .

 2 Fig. 2. (Oy) and L are two singular trajectories for the system (10) represented by two continuous lines. The filled regions are the points where D • D > 0.

Fig. 3 .

 3 Fig. 3. σ b+ is a bridge connecting two switching points of the singular set and the singular control saturates at the point Ssat.

Remark 2 .LD • D < 0 D • D < 0 D

 200 Adding a parameter λ in the model (10) by replacing the vector field G by G ← -(yλ) ∂ ∂x + x ∂ ∂y affects the position of y 0 (see Fig.4): as λ → +∞, y 0 → 0. det(Y, X) = 0 det(Y, [Y, X]) = 0 • D > 0

Fig. 4 .

 4 Fig. 4. (Oy) and L corresponding singular trajectories for the system (10) where G is replaced by G = -(y -λ) ∂ ∂x + x ∂ ∂y and λ = 200. The dash-dotted curve corresponds to the collinearity set. The filled regions are the points where D • D > 0.

Fig. 5 .

 5 Fig. 5. Stratification of the manifold N .

•

Case 2 :

 2 Consider now the following network where the first reaction is reversible: A B C k1 k2 k3

  bridge" occurs and corresponds to a vertical tangent to S at the point (x, v) where n • [[G, F ], G](x, v) = 0.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Stratification of N : y= d for d = 1, α = 1.5, β = β = 1, α = 0.5. S = {n • G = n • [G, F ] = 0}, E = {n • F = 0}.

  nomenon


Vincent Laudet
email: vincent.laudet@obs-banyuls.fr

Pauline Salis

Thibault Lorin

Bruno Frédérich
email: bruno.frederich@uliege.be

Magic Traits in Magic Fish: Understanding Color Patterns using Reef Fish

Keywords: Pigmentation pattern, Ecology, Evolution, Development, Chromatophores, Modularity Pigmentation pattern, Ecology, Evolution, Development, Chromatophores, 18 Modularity

Color patterns provide an easy access to phenotypic diversity and allow the questioning of the adaptive value of traits or the constraints acting on phenotypic evolution. Reef fish offer a unique opportunity to address such questions because they are ecologically and phylogenetically diverse and have the largest variety of pigment cell types known in vertebrates. In addition to recent development of their genetic resources, reef fish also constitute experimental models that allow the discrimination of ecological, developmental and evolutionary processes at work. Here, we emphasize how the study of color patterns in reef fish can be integrated in an Eco/Evo/Devo perspective and we illustrate that such an approach can bring new insights on the evolution of complex phenotypes.

Diversity and function of color patterns in reef fish

Reef fish harbor a myriad of colors and associated patterns. Some display uniform body color 73 such as the blue-green damselfish Chromis viridis (Fig. 1A) whereas others show complex 74 patterns as seen in the clown triggerfish Balistoides conspicillum (Fig. 1B). The latter combines 75 a series of large ventral white spots, with a dorsal yellow shield punctuated with small brown 76 spots. Strikingly, some reef fish species share ornamental similarities whereas others have the 77 exact same color pattern (Fig. 1).

78

The functionality of these patterns can be diverse however. It has often been assumed 79 to be related to camouflage and/or communication [10] and the "prey-predator" relationship 80 probably led to a large variety of color patterns. Caudo-rostral stripes have been shown, for example, to have a role in inducing a confusion effect during shoaling behavior of snappers 82 (Lutjanus spp) (Fig. 1C) [15] or serving as cues for intra-school orientation [16]. On the other 83 hand, a comparative study in butterflyfishes provided evidence that the number of diagonal 84 body stripes are associated with social behavior and dietary complexity: social species, living 85 in groups, have fewer diagonal stripes while species with greater dietary diversity have more 86 of these markings [17]. Another frequently observed ornaments in reef fish, eye stripes, have 87 been attributed as serving to camouflage the eyes from predators, hence hiding a primary target 88 [18]. Eyespots have also been linked to various antipredatory functions such as deterring 89 hunting predators to initiate an attack (intimidation hypothesis) or diverting their attacks toward 90 less vital body parts (deflective hypothesis) [19]. For example, it was largely assumed that the 91 large eyespot of the comet fish Calloplesiops altivelis has such an antipredatory function (Fig. 92 1D). However, the roles of eyespots might also be plural. In the juveniles of the ambon 93 damselfish Pomacentrus amboinensis, these markings serve as a signal of subordinance from 94 juveniles to reduce aggression by mature males [20]. Moreover, the function of eyespots in P. 95 amboinensis changes over ontogeny. Indeed, some mature males of P. amboinensis retain 96 eyespots, when others do not (i.e. the mature dominant males), and adopt a deceptive 97 appearance [21]. These studies from P. amboinensis reveal that markings may have multiple 98 roles and beautifully illustrates the (sometimes conflicting) effects of natural and sexual section. well as laterally at the level of the myoseptum on a subtle yellowish background caused by 130 scattered xanthophores (Fig. 3A). At the onset of metamorphosis, the adult pattern starts 131 developing. It is composed of longitudinal dark stripes of melanophores and iridophores 132 contrasting with light inter-stripe regions containing xanthophores and iridophores (Fig. 3A).

133

The generation of the adult color pattern is complex due to the variation in adult pigment cell 134 origin. Experimental genetic analyses revealed that the largest number of melanophores and 135 iridophores found in adults (often called metamorphic chromatophores) differentiate during 136 metamorphosis and later [26][START_REF] Singh | Proliferation, dispersal and patterned aggregation of 387 iridophores in the skin prefigure striped colouration of zebrafish[END_REF][START_REF] Van Eeden | Genetic analysis of fin formation in the zebrafish, Danio 390 rerio[END_REF], whereas almost all adult xanthophores differentiate earlier, 137 during the larval stage [START_REF] Mahalwar | Local reorganization of xanthophores fine-tunes and colors 392 the striped pattern of zebrafish[END_REF]. Additionally, the melanophores found in adults have a dual origin: 138 the largest number of melanophores differentiates at the adult stage whereas a minority 139 corresponds to persisting embryonic melanophores [START_REF] Johnson | Mitfa is required at multiple stages of melanocyte 394 differentiation but not to establish the melanocyte stem cell[END_REF]. These results demonstrated that the 140 underlying genetic architectures of the larval and adult patterns are only partially overlapping.

141

An important feature of this two steps-process that corresponds to a metamorphosis, is 142 the role of thyroid hormones (TH). As in other teleosts, these hormones trigger and coordinate 143 this elaborate transformation [START_REF] Laudet | The Origins and evolution of vertebrate metamorphosis[END_REF]. Interestingly, the different types of chromatophores are 144 differentially sensitive to alterations of TH levels. For example, treatment with TH leads to a 145 marked xanthophores excess and deficiency in melanophores in adults [START_REF] Mcmenamin | Thyroid hormone-dependent adult pigment cell lineage 398 and pattern in zebrafish[END_REF]. The role of TH is 146 therefore central for controlling the differentiation and the ultimate presence of the three types 147 of chromatophores, generating the observed adult pattern. Genetic studies in zebrafish have revealed the major role of the interactions among the three 151 types of chromatophores in the development of the color pattern. For example, in some 152 xanthophore-deficient mutants (pfeffer mutants), the melanophore stripes are reorganized into 153 spots [START_REF] Frohnhöfer | Iridophores and their interactions with other 400 chromatophores are required for stripe formation in zebrafish[END_REF]. Mutants in which two chromatophores types have been deleted (e.g. shady:pfeffer 154 having neither iridophores nor xanthophores) reveal that the single remaining chromatophore 155 type (melanophores) is not able to form the precise pattern [START_REF] Frohnhöfer | Iridophores and their interactions with other 400 chromatophores are required for stripe formation in zebrafish[END_REF]. Moreover, such interdependency is also important for sustaining formation and/or survival of chromatophores.

157 For example, it was shown that iridophores promote and sustain melanophore differentiation 158 [26,[START_REF] Frohnhöfer | Iridophores and their interactions with other 400 chromatophores are required for stripe formation in zebrafish[END_REF], whereas depletion of xanthophores leads to a reduction in melanophore number [START_REF] Nakamasu | Interactions between zebrafish pigment cells responsible 403 for the generation of Turing patterns[END_REF]. stripes [START_REF] Patterson | Pigment cell interactions and differential xanthophore 412 recruitment underlying zebrafish stripe reiteration and Danio pattern evolution[END_REF]. It was shown experimentally that increased expression of csf1 in zebrafish results

205

in similar cascading effects giving rise ultimately to a similar intermingling of all three pigment 206 cell types and stripe loss [START_REF] Patterson | Pigment cell interactions and differential xanthophore 412 recruitment underlying zebrafish stripe reiteration and Danio pattern evolution[END_REF]. Recently, the secreted peptide Endothelin-3, a known 207 melanogenic factor, was shown to contribute to the reduced iridophore proliferation and fewer 208 stripes observed in another species, D. nigrofasciatus [START_REF] Spiewak | Evolution of Endothelin signaling and diversification of 415 adult pigment pattern in Danio fishes[END_REF]. These data illustrate how changes pattern, has driven incipient speciation in this fish [START_REF] Puebla | Colour pattern as a single trait driving speciation in 427 (Hypoplectrus spp., Serranidae)[END_REF]. It is often considered that, as a predatory 254 fish, Hypoplectrus mimics harmless fish in order to increase their predation success on their 255 preys ( [START_REF] Puebla | Colour pattern as a single trait driving speciation in 427 (Hypoplectrus spp., Serranidae)[END_REF] but see [45]). Genetic analysis allowed to identify divergent loci among color morphs [46][47][START_REF] Picq | Population genomics of local adaptation versus speciation in coral 436 reef fishes (Hypoplectrus spp, Serranidae)[END_REF]. Among them, an analysis using SNPs identify the HoxC cluster as being 257 associated with color variation [47]. Hox genes have never been associated with pigmentation 258 defect in teleosts but they have been linked to body pigmentation and eyespot formation in 259 insects [START_REF] Jeong | Regulation of body pigmentation by the Abdominal-B Hox 438 protein and its gain and loss in Drosophila evolution[END_REF]. Developmental studies are much needed to better understand the role, if any, that 260 these genes could play in the divergence of color patterns.

261

Clownfish offers a third case in which the mechanisms controlling pattern formation 262 can be deciphered. These fishes are forming a tribe composed of 30 species within the 263 damselfishes and displays a relatively simple color pattern made of zero to three white stripes 264 containing iridophores well visible on a darker body background [START_REF] Salis | Ontogenetic and phylogenetic simplification during white stripe 440 evolution in clownfishes[END_REF][START_REF] Salis | Developmental and comparative transcriptomic identification of 442 iridophore contribution to white barring in clownfish[END_REF]. Vertical white stripes 265 likely play a role in species recognition [START_REF] Salis | Ontogenetic and phylogenetic simplification during white stripe 440 evolution in clownfishes[END_REF] but it was also suggested that this varied striped 266 pattern might serve for camouflage or use as an aposematic signal [START_REF] Merilaita | Scary clowns: adaptive function of anemonefish 444 coloration[END_REF]. Recently, we mapped 267 the occurrence of these stripes on the clownfish phylogeny to reconstruct the ancestral state in 268 terms of white stripes presence/absence [START_REF] Salis | Ontogenetic and phylogenetic simplification during white stripe 440 evolution in clownfishes[END_REF]. Through this analysis, we provide evidence that

307

-Eye stripes: a dark bar that runs through the eye, matching the eye color and therefore hiding 308 the eye.

309

-Proximal causation: explanation of a trait when considering direct mechanistical aspects 310 (for instance, a change in the levels of a given hormone explain a particular color change).

311

See [START_REF] Laland | Cause and effect in biology revisited: Is Mayr's proximate-448 ultimate dichotomy still useful?[END_REF].

312

-Ultimate causation: explanation of a trait when considering long-term evolutionary forces 313 (for instance, prey-predator interactions can lead to better background matching in preys).

314

See [START_REF] Laland | Cause and effect in biology revisited: Is Mayr's proximate-448 ultimate dichotomy still useful?[END_REF].

315

-Eco/Evo/Devo: the interactions between an organism's environment, genes and 316 development, and their consequences on evolution.

317

-Melanosome: in melanophores, organelles that effectively contain the dark pigment, 318 melanin. This pigment is synthesized by enzymes through a process called melanogenesis.

319

-Color pattern polymorphism: consequence of developmental plasticity, in which the 320 trajectories of developing organisms diverge under the influence of ultimate cues 321 -Magic trait: a trait subject to divergent selection and a trait contributing to non-random 322 mating that are pleiotropic expressions of the same gene(s). Often these two traits will be 323 one and the same. Thus, pleiotropy in the context of magic trait refers to the phenotypic 324 effects on both selection and mating, rather than necessarily to two distinguishable 325 phenotypic traits. See [START_REF] Servedio | Magic traits in speciation: "magic" but not rare?[END_REF]. distinguished [START_REF] Bennett | The color loci of mice -A genetic century[END_REF]. The situation is even more complex in other vertebrates, and in particular in 541 teleosts, that have more chromatophore types (see Box 2) [8]. Studies in zebrafish and medaka 542 have identified genes involved in specific teleost chromatophore differentiation [START_REF] Nüsslein-Volhard | How fish color their skin: A paradigm for 452 development and evolution of adult patterns[END_REF]. To date, 543 this makes a total of ca. 200 genes known to be involved in pigmentation [9]. Some genes, such 544 as mitf (important for melanocyte development) and agouti (controls dorso-ventral patterning), 545 have conserved mechanisms of action throughout vertebrates [START_REF] Cal | BAC recombineering of the agouti loci from spotted gar and 454 zebrafish reveals the evolutionary ancestry of dorsal-ventral pigment asymmetry in 455 fish[END_REF]. Others are specifically 546 involved in teleosts: for example, both ltk and sox5 are known to be required for iridophores 547 and xanthophores development [START_REF] Nagao | Sox5 functions as a fate switch in medaka pigment cell 457 development[END_REF][START_REF] Fadeev | Zebrafish leucocyte tyrosine kinase controls iridophore 459 establishment, proliferation and survival[END_REF]. Recent work has shown that the same gene can be 548 involved in the development of the same pigment cell type but in different ways in various fish 549 species. For instance, xanthophore differentiation requires the expression of sox5 in medaka 550 whereas the repression of this gene is needed in zebrafish [START_REF] Nagao | Distinct interactions of Sox5 and Sox10 in fate specification of 461 pigment cells in medaka and zebrafish[END_REF].

551

During vertebrates' evolution, the pigmentation gene repertoire has been shaped by 552 several whole-genome duplications (WGDs). After a WGD event, genes are either retained or 553 lost. The retention pattern greatly varies with the function of the encoded protein, and genes 554 that are retained in two copies often provide the raw material for the acquisition of new 555 functions [START_REF] Mcgrath | Differential retention and divergent resolution of duplicate 463 genes following whole-genome duplication[END_REF]. Interestingly, it was recently demonstrated that pigmentation genes have been 556 globally more frequently retained as duplicates than other genes after teleosts-specific WGDs [9,[START_REF] Braasch | Pigmentation pathway evolution after whole-genome 465 duplication in fish[END_REF]. This high pigmentation gene repertoire is thus expected to be linked to the highest 558 pigment cell diversity and the great diversity of pigmentation patterns observed in teleosts. 564 Some of the extra pigment cells present in reef fish appear to be variants of the three 565 main types. This may be the case of leucophores responsible for the white coloration in medaka 566 that have been recently described as similar to xanthophores [START_REF] Kimura | Leucophores are similar to xanthophores in their specification 467 and differentiation processes in medaka[END_REF]. White hue is also present in 567 clownfish and has been shown to be based on iridophores [START_REF] Salis | Ontogenetic and phylogenetic simplification during white stripe 440 evolution in clownfishes[END_REF][START_REF] Salis | Developmental and comparative transcriptomic identification of 442 iridophore contribution to white barring in clownfish[END_REF].

568

However, new chromatophore types have also been recently described. For example, 569 the blue color observed in the mandarin fish Synchiropus splendidus is linked to a specialized 570 cell type, the cyanophores [START_REF] Goda | Blue chromatophores in two species of Callionymid fish[END_REF]. The molecular nature of the pigment present in their specialized 571 organelles has not been identified to date. Another fascinating case is provided by the red 572 fluorescent system observed in the pigmy reef goby Eviota pellucida [START_REF] Stieb | Why UV vision and red vision are important for damselfish 471 (Pomacentridae): structural and expression variation in opsin genes[END_REF]. Reef fish are also 573 providing the only known case of dichromatic pigment cells. The erythro-iridophores, found in 574 the diadem dottyback Pseudochromis diadema, contain both a reddish carotenoid pigment and 575 reflecting platelets similar to those found in iridophores [START_REF] Goda | Integumental reddish-violet coloration owing to novel 474 dichromatic chromatophores in the teleost fish, Pseudochromis diadema[END_REF]. The mandarin fish S. splendidus 576 also possesses dichromatic cells, the cyano-erythrophores [START_REF] Goda | Novel dichromatic chromatophores in the integument of the 488 visual pigments in erythrophores of Nile tilapia[END_REF]. to explain in a detailed manner the dynamic of stripes formation [START_REF] Painter | Stripe formation in juvenile Pomacanthus explained by a 422 generalized turing mechanism with chemotaxis[END_REF]. Recently, the arrangement 608 the zebrafish stripes was also shown to be consistent with a RD [START_REF] Yamaguchi | Pattern regulation in the stripe of zebrafish suggests an 407 underlying dynamic and autonomous mechanism[END_REF][START_REF] Kondo | Reaction-Diffusion model as a framework for 496 understanding biological pattern formation[END_REF].

609

RD has also been applied in a variety of other biological systems. As it is particularly 610 easy to implement in a simple two dimensional space they have been used to better understand 611 the formation of several ectodermal appendages such as hair follicle spacing in mouse [START_REF] Sick | WNT and DKK determine hair follicle spacing through a 498 reaction-diffusion mechanism[END_REF], or 612 feathers patterning in birds [2]. More complex systems such as branching morphogenesis in the 613 lung, or teeth patterning have also been explored [START_REF] Miura | Depletion of FGF acts as a lateral inhibitory factor in 500 lung branching morphogenesis in vitro[END_REF]. By changing the parameters and initial 614 conditions of the systems, RD can generate a virtually unlimited variety of spatial pattern [START_REF] Kondo | Reaction-Diffusion model as a framework for 496 understanding biological pattern formation[END_REF].

615

We thus expect that a large proportion of pigmentation patterns observed in reef fish could be 616 explained through RD.

99 123 124

 123 The taxonomic diversity of reef fish[22] facilitates the identification of cases of parallel 100 evolution (See examples on Fig. 1) and this might help to identify ecological and molecular 101 mechanisms underlying convergence in color patterns. Methods for the quantification of color 102 pattern become available [23] but, often, even the most complex patterns can be interpreted by 103 the combination of several simpler elements/markings. Usually, we can reduce this complexity 104 by fragmenting them into well-characterized modular sub-patterns defined by their nature (e.g. 105 lines, spots, borders) and associated body regions. This property offers a unique opportunity to explore the evolution of color patterns through the biological concepts of integration and 107 modularity [24]. The above-mentioned comparative study of butterflyfishes provided a first 108 demonstration that some markings evolved differently: eyespots are evolutionary labile 109 whereas eye stripes are more phylogenetically conserved [17]. Correlated evolution of some 110 specific markings, such as "spots and eye stripes" or "eyespot and adjacent eye stripe" in 111 butterflyfishes [17], allows the suggestion of ultimate and proximate mechanisms driving the 112 pigmentation patterns. Fragmenting complex patterns and isolating markings with extensive 113 comparative studies across various reef fish families will help for delineating repeated modes 114 of trait evolution (Fig. 2). 115 116 Understanding the ontogeny of color patterns using fish models 117 Developmental studies are needed to provide additional information on proximate mechanisms 118 allowing the emergence of various color patterns during development and evolution. Up to now, 119 cellular and molecular studies have mainly been carried out using zebrafish (Danio rerio), a 120 widely used model. Thanks to the genetic and live imaging tools developed in this species, it 121 has been possible to investigate the mechanisms underlying color pattern formation and 122 evolution. The cellular context of adult pigmentation 125 In zebrafish, three distinct types of chromatophores are present: black melanophores, yellow 126 xanthophores and iridescent iridophores [25]. As in most teleosts, the zebrafish shows two very 127 different pigmentation patterns during ontogeny: a larval pattern and an adult one. The larval 128 pattern consists of loose longitudinal stripes of melanophores, in the dorsal and ventral apex as

  129

  interactions are instrumental for patterning 150

159

  These interactions go beyond pigment cells as it was shown in an elegant study that 160 macrophages participate, via long distance cytoplasmic projections reaching xanthophores, to 161 the network of cell interactions that govern the stripe patterning .162 These dynamics of cell interactions are predicted by Turing models (also known as 163 reaction-diffusion models), which is a standard for the modelling of complex pattern formation 164 (Box 3). The Turing model effectively explains the formation of color pattern observed in 165 zebrafish. Interestingly, artificial disturbance of the striped pattern by using laser irradiation 166 (which ablates chromatophores) induces changes that can effectively be predicted by the model 167 (Fig.3B)[START_REF] Yamaguchi | Pattern regulation in the stripe of zebrafish suggests an 407 underlying dynamic and autonomous mechanism[END_REF]. Moreover, ablation experiments of chromatophore types in different regions 168 leads to the disruption of various short-range and long-range interactions that are essential in 169 the Turing model. For example, when part of a xanthophores stripe is ablated, only 170 xanthophores will arise in the cleared area (Fig. 3C -upper panel). Conversely, when the two 171 adjacent black stripes are also ablated in addition to the same part of the xanthophore stripe (Fig 172 3C-middle panel), melanophores will emerge in the former xanthophores domain suggesting 173 that melanophores in the neighboring stripes had a repressive effect on the development of 174 melanophores at a distant place [34]. Together, this puts forward that long-range interactions 175 (e.g. xanthophores promoting melanophores emergence and melanophores inhibiting other 176 melanophores) as well as short-range interactions are important in setting up final width of the 177 stripes. Altogether, this reveals that this network of interactions possesses the properties 178 necessary to form the Turing pattern (Fig. 3D) [34]. Another fundamental characteristic of 179 Turing model is that the number of repeated stripes or spots is intimately connected to body 180 size, and therefore to the growth of the organism. Such characteristics were observed in long-181 fin zebrafish mutant (for which the fins never stop growing) which continues to form perfectly 182 new stripes as the fins grow [28]. 183 If cell interdependency shapes the width of the stripes, the global directionality of the 184 pattern has to be established. Some biological indicators must specify the direction of stripe 185 formation. Accordingly, the pigmentation pattern of zebrafish body trunk needs initial 186 information and this is provided by the horizontal myoseptum in which iridophores precursors 187 migrate to form the first horizontal stripe. The melanophores and xanthophores that will 188 subsequently develop are then influenced by the position of iridophores. The crucial role of the 189 horizontal myoseptum in providing directionality information was illustrated by the choker 190 mutants in which the myoseptum is lost. In adult mutants, the pigmentation develops into a 191 labyrinth-like pattern because of the loss of the initial positional indicator [33,37].192 193 Evolution of color patterns 194 The study of cellular and molecular mechanisms of color pattern generation in D. rerio and 195 their closely related species showing different pigmentation patterns allowed deciphering some 196 evolutionary mechanisms controlling the evolution of color patterns. For example, an 197 interesting case is provided by Danio albolineatus, a non-striped Danio species characterized 198 by the presence of intermingled populations of the three pigment cells. In this species, 199 differentiation of xanthophores occurs earlier than in D. rerio because of an increased 200 expression of csf1 (due to a change in its gene regulatory region), a growth factor supplied by 201 iridophores and other cells in the skin [38]. This earlier differentiated population of 202 xanthophores in D. albolineatus modifies the positioning information provided to 203 melanophores compared to D. rerio. Consequently, D. albolineatus individuals do not form 204

209

  of expression of key molecular factors coupled with changes in cell-cell interactions can lead 210 to the evolution of a new color pattern. 211 212 Integrating ecology with Evo/Devo to understand the color patterns of reef 213 fish 214 Integrating ecology with evolution and development allows addressing how developmental 215 mechanisms modified during evolutionary changes are selected. If zebrafish with its unique 216 toolkit is an excellent model to understand the development of reiterated striped pattern, their 217 ecological diversity is limited and thus how the developmental mechanisms at the origin of 218 variation in the pigmentation patterns have been selected remains unknown. This is why reef 219 fish, with their diversity of pigment cell types (Box 2), combined with the vast knowledge 220 gathered on their ecology and the new development of genomic resources [40,41] are becoming 221 attractive models to reach a full understanding of the diversity and the evolution of color 222 patterns. Moreover, amongst those advantages, most of color patterns observed in reef fish are 223 not reiterated patterns but rather results from the combination of simpler elements that cannot 224 be explained by the Turing mechanisms. Thus, whereas Turing model have been successfully 225 applied to angelfishes (Pomacanthus spp) [42], it is clear that it will only explain a subset of 226 the patterns observed in reef fish and that other mechanisms must be at work. 227 To exemplify analyses that beautifully illustrate the potential of incorporating the 228 ecological and developmental approaches in the evolution of complex color patterns, we have 229 chosen three recent studies. The first concerns phenotypic plasticity, a major tenet of 230 Eco/Evo/Devo. It is well exemplified by the dusky dottyback Pseudochromis fuscus, a small 231 predatory fish [11,12]. This species can exhibit numerous uniform color morphs from orange 232 to brown, yellow, pink or gray. At the Great Barrier Reef, the yellow morph inhabits living 233 coral heads with yellow damselfishes (e.g. Pomacentrus amboiensis) whereas the brown one is 234 associated with brown damselfish species (e.g. Pomacentrus chrysurus) on coral rubbles. 235 Experiments revealed that yellow morphs can transform into brown morphs within 2 weeks if 236 translocated from living corals to coral rubbles [43]. Strikingly, however, the dottyback does 237 not change color because of the environment but because of the presence of colored 238 damselfishes. The advantages of this strategy are double for P. fuscus. First, by mimicking 239 adults of a damselfish species, it increases its predation success on their juveniles. Second, the 240 color change helps the dottyback to escape its own predator by providing a habitat-associated 241 crypsis. The study of associated cellular mechanisms revealed that this change in color is 242 explained by a change in the respective proportions of xanthophores and melanophores [12]. In 243 a fascinating follow-up study, this color change has been placed upon an ontogenetic trajectory 244 and it has been shown that, in fact, dottybacks change color twice during development: once 245 during metamorphosis, when a pelagic translucid larvae is transformed into a grey juvenile, and 246 then when the large-enough juvenile starts its mimicry strategy and select either yellow or 247 brown victims [11]. This study therefore addresses how developmental plasticity can promote 248 ecological adaptation. 249 The two other cases incorporate this time, evolution together with development and 250 ecology. One concerns the radiation of the Caribbean hamlets (Hypoplectrus spp) and shows 251 how color polymorphisms allow the understanding of the ecological and developmental basis 252 of phenotypic adaptation. Detailed analysis of their radiation revealed that a single trait, color 253

269

  the diversification of clownfish color pattern results from successive caudal to rostral losses of 270 stripes during evolution. Interestingly, the juveniles of some species have supplementary stripes 271 that disappear caudo-rostrally later on. The reduction of stripes number over ontogeny totally 272 matches the sequences of stripe losses across evolution, demonstrating that the diversification 273 in color pattern among clownfish lineages results from changes in developmental processes. 274 This analysis illustrates that the clownfish model is very different from the zebrafish since the 275 number of stripes is independent to body size [50]. Thus, Turing like mechanism cannot explain 276 the disappearance of stripes during clownfish ontogeny and other mechanisms are obviously 277 involved in white stripes formation. Genetic analyses are now required to understand the 278 molecular mechanism at the origin of such color pattern evolution within clownfish.

281 (-

 281 France), ENS Lyon (France) and the FNRS (Belgium). We thank Germain Boussarie, Franck 300 Merlier, Philippe Bourjon, Alan Sutton, Guido Poppe and Philippe Poppe for the pictures used 301 in the Figures. We also thank Natacha Roux, Laurence Besseau and Mathieu Denoël for critical 302 reading of the manuscript. Color pattern: distribution of color across the body 306 -Eyespots (or ocelli): concentric markings that contrast with the surrounding area.

Figure 1 .

 1 Figure Legends

Figure 2 .Figure 3 .

 23 Figure 2. Evolution of some markings in two groups of reef fish. Example from the

  diversity of pigment cells in reef fish 561Reef fish contains many chromatophores in addition to the three types observed in zebrafish 562 (i.e. melanophores, xanthophores, and iridophores)[8]. Reef fish are therefore of particular 563 importance to fully grasp the range of possible pigmentation systems in vertebrates.

577

  Lastly, the mechanism allowing color change of some species have started to be 578 analyzed. The chameleon sand tilefish Hoplolatilus chlupatyi can exhibit color change from 579 blue to red in a matter of few seconds and this very fast color change is linked to a novel type 580 of iridophores in which the reflecting platelets are concentrated in the periphery of the cell. 581 Box Figure, panel B). By incorporating cell growth and movement in the models, it is possible 607

617Figure Box 3 :

 3 Figure Box 3: Stripes formation is predicted by Turing model in fishes

Acknowledgments

298

Works from our laboratories are funded by the CNRS (France), the Sorbonne Université

Color patterns in reef fish, with their extreme divergence and plasticity, can indeed be 282 considered as a "magic trait" that may easily lead to speciation [START_REF] Servedio | Magic traits in speciation: "magic" but not rare?[END_REF]. Thanks to works on the 283 zebrafish model, we have more knowledge about the developmental mechanisms generating 284 color patterns. The combination of ecological analysis with genomic and/or developmental 285 analysis using reef "magic" fish as model systems (in addition to other valuable models such as 286 cichlids and guppies) will help to provide an integrated understanding of the evolution of such 287 complex phenotypes. We have identified several concrete directions in which the study of reef 288 fish could have specific advantages. The first is the study of the numerous color polymorphisms 289 existing in these fish (e.g. dottybacks, melanic clownfish, etc.) as well as the link between 290 behaviour and color. In both cases, the vast ecological knowledge accumulated can be 291 advantageously combined with the transcriptomic and functional approaches to understand how 292 ecological and developmental constraints intermingle to generate novel phenotypes. Another

293

promising aspect is to study the developmental and evolutionary rules governing the assembly 294 of various patterns. For all these questions, it will be critical to bring together proximate and 295 ultimate causations to understand the "Magic traits". As discussed during our exchanges of e-mails this review presents an eco/evo/devo interdisciplinary perspective to understand the origin of pigmentation pattern diversification using reef fish as an example. We made all possible efforts to link the field discussed to broader, underlying questions of developmental biology and evolution. Our aim is effectively to attract a broad readership and to convince them that they should consider these fishes as interesting models. The first part focuses on the diversity and functions of color patterns in reef fishes. Then we reviewed the molecular, cellular and developmental basis for color pattern formation studied mainly in zebrafish. Finally, the last section explains how integrating ecology together with evo/devo allows uncovering the mechanisms promoting pigmentation diversity in these fishes. As this review brings in information from a number of scientific disciplines in the service of a question of basic science we hope you will find it appropriate for the wide audience of Trends in Genetics.

Observatoire

Hoping that our manuscript will be regarded favourable, we look forward to hearing from you.

We would like to thank you in advance for taking care of our manuscript.

Yours sincerely, Vincent Laudet