Yves Aubry

Jean-Christophe Godin

Olivier Togni

Every triangle-free induced subgraph of the triangular lattice is (5m, 2m)-choosable

Keywords: Radio channel assignment, triangular lattice, choosability, weighted graph. 2010 MSC: 05C15, 05C38

A graph G is (a, b)-choosable if for any color list of size a associated with each vertex, one can choose a subset of b colors such that adjacent vertices are colored with disjoint color sets. This paper proves that for any integer m ≥ 1, every finite triangle-free induced subgraph of the triangular lattice is (5m, 2m)-choosable.

Introduction

Let G = (V (G), E(G)) be a graph where V (G) is the set of vertices and E(G) is the set of edges, and let a, b, n and e be integers.

Given a list assignment (called simply a list) L of G i.e. a map L : V (G) → P(N) and a weight function w of G i.e. a map w : V (G) → N, an (L, w)-coloring c of G is a list of the weighted graph G such that for all v ∈ V (G), c(v) ⊂ L(v) and |c(v)| = w(v), and for all vv

′ ∈ E(G), c(v) ∩ c(v ′ ) = ∅.
We say that G is (L, w)-colorable if there exists an (L, w)-coloring c of G. An (L, b)-coloring c of G is an (L, w)-coloring such that for all v ∈ V (G),

Email addresses: yves.aubry@univ-tln.fr (Yves Aubry), godinjeanchri@yahoo.fr (Jean-Christophe Godin), olivier.togni@u-bourgogne.fr (Olivier Togni)

we have w(v) = b. A a-list L of G is a list of G such that for all v ∈ V (G), we have |L(v)| = a. The graph G is said to be (a, b)-choosable if for any a-list L of G, there exists an (L, b)-coloring c of G. If the graph is (a, b)choosable for the a-list L such that L(v) = L(v ′ ) for all vertices v, v ′ , then G is (a, b)-colorable.

The concept of choosability of a graph, also called list coloring, has been introduced by Vizing [START_REF] Vizing | Coloring the vertices of a graph in prescribed colors (in Russian), Diskret. Analiz. No. 29, Metody Diskret[END_REF], and independently by Erdős, Rubin and Taylor [START_REF] Erdős | Choosability in graphs[END_REF]. It contains of course the colorability as a particular case. Since its introduction, choosability has been extensively studied (see for example [START_REF] Alon | Choosability and fractional chromatic number[END_REF][START_REF] Borodin | List edge and list colourings of multigraph[END_REF][START_REF] Thomassen | The chromatic number of a graph of girth 5 on a fixed surface[END_REF][START_REF] Zs | Every 2-choosable graph is (2m,m)-choosable[END_REF][START_REF] Gravier | A Hajós-like theorem for list coloring[END_REF] and more recently [START_REF] Gutner | Some results on (a:b)-choosability[END_REF][START_REF] Havet | Choosability of the square of planar subcubic graphs with large girth[END_REF]). Even for the original (unweighted) version, the problem proves to be difficult, and is NP-complete for very restricted graph classes.

Every graph that is (a, b)-colorable is also trivially (am, bm)-colorable for any integer m ≥ 1. For list coloring, Erdős, Rubin and Taylor [START_REF] Erdős | Choosability in graphs[END_REF] conjectured the following:

Conjecture 1 ([4]). The (a, b)-choosability of a graph G implies (am, bm)- choosability for all m ∈ N, m ≥ 1.
In relation with this question, Gutner and Tarsi [START_REF] Gutner | Some results on (a:b)-choosability[END_REF] have recently exhibited graphs G that are (a, b)-choosable but not (c, d)-choosable, with c d > a b ≥ 3. List multicoloring problems on graphs can be used to model channel assignment problems in wireless systems. Sets of radio frequencies are to be assigned to transmitters such that adjacent transmitters are assigned disjoint sets of frequencies. Often these transmitters are laid out like vertices of a triangular lattice in a plane. This problem corresponds to the problem of multicoloring an induced subgraph of a triangular lattice with integer demands associated with each vertex. Since more than a decade, multicoloring of subgraphs of the triangular lattice has been the subject of many papers (see e.g. [START_REF] Mcdiarmid | Channel assignement and weighted coloring[END_REF][START_REF] Havet | Channel assignement and multicolouring of the induced subgraphs of the triangular lattice[END_REF][START_REF] Havet | Finding a five bicolouring of a triangle-free subgraph of the triangular lattice[END_REF][START_REF] Kchikech | Approximation algorithms for multicoloring powers of square and triangular meshes[END_REF]). Mc Diarmid and Reed [START_REF] Mcdiarmid | Channel assignement and weighted coloring[END_REF] have made the following conjecture when the subgraph is induced and contains no triangle: Conjecture 2 ( [START_REF] Mcdiarmid | Channel assignement and weighted coloring[END_REF]). Every triangle-free induced subgraph of the triangular lattice is (⌈ 9b 4 ⌉, b)-colorable.

Some progress have been made regarding this conjecture with Havet [9] proving the (5, 2)-colorability and (7, 3)-colorability and Sudeep and Vishwanathan [START_REF] Sudeep | A technique for multicoloring triangle-free hexagonal graphs[END_REF] (with a simpler proof) the (14, 6)-colorability of any trianglefree induced subgraph of the triangular lattice.

The main result is Theorem 12 of Section 3 which shows the (5m, 2m)choosability of triangle-free induced subgraphs of the triangular lattice. The method is similar with that of Havet [START_REF] Havet | Channel assignement and multicolouring of the induced subgraphs of the triangular lattice[END_REF], that uses precoloring extensions and decomposition into induced path (called handles). However, we need here specific results on the choosability of a weighted path. We find convinient to work on a type of list of the path that we call waterfall list. This is the subject of the next section.

Waterfall lists on the path

We first define the similarity of two lists with respect to a weighted graph: Definition 1. Let (G, w) be a weighted graph. Two lists L and L ′ are said to be similar if this assertion is true:

G is (L, w)-colorable ⇔ G is (L ′ , w)-colorable.
The path P n+1 of length n is the graph with vertex set V = {v 0 , v 1 , . . . , v n } and edge set E = n-1 i=0 {v i v i+1 }. To simplify the notation, L(i) denotes L(v i ), c(i) denotes c(v i ) and w(i) denotes w(v i ).

By analogy with the flow of water in waterfalls, we define a waterfall list as follows: Definition 2. A waterfall list L of a path P n+1 of length n is a list L such that for all i, j ∈ {0, . . . , n} with |i -j| ≥ 2, we have L(i) ∩ L(j) = ∅.

Notice that another similar definition of a waterfall list is that any color is present only on one list or on two lists of consecutive vertices. Figure 1 shows a list L of the path P 5 (on the left), together with a similar waterfall list L c (on the right). Definition 3. For a weighted path (P n+1 , w), We first show that any good list can be transformed into a similar waterfall list.

• A list L is good if |L(i)| ≥ w(i) + w(i + 1) for any i, 1 ≤ i ≤ n -1. • The amplitude A(i, j)(L) (or A(i, j)) of a list L is A(i, j)(L) = ∪ j k=i L(k). L() v 0 v 1 v 2 v 3 v 4 t t t t t
v 0 v 1 v 2 v 3 v t t t t t
Proposition 4. For any good list L of P n+1 , there exists a similar waterfall list

L c with |L c (i)| = |L(i)| for all i ∈ {0, . . . , n}.
Proof. We are going to transform a good list L of P n+1 into a waterfall list L c and we will prove that L c is similar with L.

First, remark that if a color x ∈ L(i -1) but x ∈ L(i) for some i with 1 ≤ i ≤ n -1, then for any j > i, one can change the color x by a new color y ∈ A(0, n)(L) in the list L(j), without changing the choosability of the list. With this remark in hand, we can assume that L is such that any color x appears on the lists of consecutive vertices i x , . . . , j x . Now, by permuting the colors if necessary, we can assume that if x < y then i x < i y or i x = i y and j x ≤ j y .

Repeat the following transformation: 1. Take the minimum color x for which j x ≥ i x + 2 i.e. the color x is present on at least three vertices i x , i x + 1, i x + 2, . . . , j x ; 2. Replace color x by a new color y in lists L(i x + 2), . . . , L(j x ); until the obtained list is a waterfall list (obviously, the number of iterations is always finite). Now, we show that this transformation preserves the choosability of the list. Let L ′ be the list obtained from the list L by the above transformation.

If c is an (L, w)-coloring of P n+1 then the coloring c ′ obtained from c by changing the color x by the color y in the color set c(k) of each vertex

k ≥ i x + 2 (containing x) is an (L ′ , w)-coloring since y is a new color.
Conversely, if c ′ is an (L ′ , w)-coloring of P n+1 , we consider two cases:

Case 1: x ∈ c ′ (i x + 1) or y ∈ c ′ (i x + 2).
In this case, the coloring c obtained from c ′ by changing the color y by the color x in the color set c ′ (k) of each vertex k ≥ i x + 2 (containing y) is an (L, w)-coloring.

Case 2: x ∈ c ′ (i x + 1) and y ∈ c ′ (i x + 2). We have to consider two subcases:

• Subcase 1: L ′ (i x + 1) ⊂ (c ′ (i x ) ∪ c ′ (i x + 1) ∪ c ′ (i x + 2)). There exists z ∈ L ′ (i x + 1) \ (c ′ (i x ) ∪ c ′ (i x + 1) ∪ c ′ (i x + 2)
) and the coloring c obtained from c ′ by changing the color x by the color z in c ′ (i x + 1) and replacing the color y by the color x in the color set c ′ (k) of each vertex k ≥ i x + 2 (containing y) is an (L, w)-coloring.

• Subcase 2:

L ′ (i x + 1) ⊂ (c ′ (i x ) ∪ c ′ (i x + 1) ∪ c ′ (i x + 2)
). We have

|L ′ (i x + 1)| = (c ′ (i x ) ∪ c ′ (i x + 1) ∪ c ′ (i x + 2) ∩ L ′ (i x + 1) .
As c ′ is an (L ′ , w)-coloring of P n+1 , we have

|L ′ (i x +1)| = |c ′ (i x +2)∩L ′ (i x +1)|+|c ′ (i x +1)∩L ′ (i x +1)|+ c ′ (i x )\c ′ (i x +2) ∩L ′ (i x +1) , |L ′ (i x +1)|-w(i x +1)-|c ′ (i x +2)∩L ′ (i x +1)| = c ′ (i x )\c ′ (i x +2) ∩L ′ (i x +1) .
Since y ∈ c ′ (i x + 2) and y / ∈ L ′ (i x + 1), we obtain that

|c ′ (i x + 2) ∩ L ′ (i x + 1)| ≤ w(i x + 2) -1, hence |L ′ (i x +1)|-w(i x +1)-w(i x +2) +1 ≤ c ′ (i x )\c ′ (i x +2) ∩L ′ (i x +1) .
But, by hypothesis, L is a good list. Thus

|L(i x + 1)| = |L ′ (i x + 1)| ≥ w(i x + 1) + w(i x + 2) and 1 ≤ c ′ (i x )\c ′ (i x + 2) ∩ L ′ (i x + 1) . Consequently, there exists z ∈ c ′ (i x )\c ′ (i x + 2) ∩ L ′ (i x + 1)
. The coloring c is then constructed from c ′ by changing the color x by the color z in c ′ (i x + 1), the color z by the color x in c ′ (i x ) and the color y by the color x in the set c ′ (k) of each vertex k ≥ i x + 2.

Cropper et al. [START_REF] Cropper | Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs[END_REF] consider Philip Hall's theorem on systems of distinct representatives and its improvement by Halmos and Vaughan as statements about the existence of proper list colorings or list multicolorings of complete graphs. The necessary and sufficient condition in these theorems is generalized in the new setting as "Hall's condition" :

∀H ⊂ G, k∈C α(H, L, k) ≥ v∈V (H) w(v),
where C = v∈V (H) L(v) and α(H, L, k) is the independence number 1 of the subgraph of H induced by the vertices containing k in their color list. Notice that H can be restricted to be a connected induced subgraph of G.

It is easily seen that Hall's condition is necessary for a graph to be (L, w)colorable. Cropper et al. [START_REF] Cropper | Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs[END_REF] showed that the condition is also sufficient for some graphs, including paths: Theorem 5 ( [START_REF] Cropper | Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs[END_REF]). For the following graphs, Hall's condition is sufficient to ensure an (L, w)-coloring: (e) a triangle with an edge added at two of its three vertices.

This result is very nice, however, it is often hard to compute the left part of Hall's condition, even for paths. However, as the next result shows, Hall's condition is very easy to check when restricted to waterfall lists. Theorem 6. Let L c be a waterfall list of a weighted path (P n+1 , w). Then P n+1 is (L c , w)-colorable if and only if:

∀i, j ∈ {0, . . . , n}, | j k=i L c (k)| ≥ j k=i w(k).
1 the independence number of a graph is the size of the largest set of isolated vertices Proof. "if" part: Recall that A(i, j) = ∪ j k=i L c (k). For i, j ∈ {0, . . . , n}, let P i,j be the subpath of P n+1 induced by the vertices i, . . . , j. By Theorem 5, it is sufficient to show that ∀i, j ∈ {0, . . . , n},

x∈A(i,j) α(P i,j , L c , x) ≥ j k=i w(k).
Since the list is a waterfall list, then for each color x ∈ A(i, j), α(P i,j , L c , x) = 1 and thus x∈A(i,j)

α(P i,j , L c , x) = |A(i, j)| = | j k=i L c (k)|. "only if" part: If c is an (L c , w)-coloring of P n+1 then ∀i, j ∈ {0, . . . , n} : j k=i L c (k) ⊃ j k=i c(k).
Since L c is a waterfall list, it is easily seen that | j k=i c(k)| = j k=i w(k). Therefore, ∀i, j ∈ {0, . . . , n} :

| j k=i L c (k)| ≥ j k=i w(k).
Theorem 6 has the following corollary when the list is a good waterfall list and |L(n)| ≥ w(n).

Corollary 7. Let L c be a waterfall list of a weighted path (P n+1 , w) such that for any i,

1 ≤ i ≤ n -1, |L c (i)| ≥ w(i) + w(i + 1) and |L c (n)| ≥ w(n). Then P n+1 is (L c , w)-colorable if and only if ∀j ∈ {0, . . . , n}, | j k=0 L c (k)| ≥ j k=0 w(k).
Proof. Under the hypothesis, if P n+1 is (L c , w)-colorable, then Theorem 6 proves in particular the result.

Conversely, since L c is a waterfall list of P n+1 , we have:

∀i, j ∈ {1, . . . , n}, |A(i, j)| = |∪ j k=i L c (k)| ≥ |∪ j k=i k-i even L c (k)| = j k=i k-i even |L c (k)|.
Since L c is a good list of P n+1 (for simplicity, we set w(n + 1) = 0): ∀i, j ∈ {1, . . . , n},

j k=i k-i even |L c (k)| ≥ j k=i k-i even (w(k) + w(k + 1)) ≥ j k=i w(k),
and then we obtain for all i, j ∈ {1, . . . , n}, |A(i, j)| ≥ j k=i w(k). Since for all j ∈ {0, . . . , n}, |A(0, j)| ≥ j k=0 w(k), Theorem 6 concludes the proof.

Another interesting corollary holds for lists L such that |L(0)| = |L(n)| = b, and for all i ∈ {1, . . . , n -1}, |L(i)| = a. The function Even is defined for any real x by: Even(x) is the smallest even integer p such that p ≥ x. Proof. The hypothesis implies that L is a good list of P n+1 , hence by Proposition 4, there exists a waterfall list L c similar to L. So we get: Case 2: j ∈ {1, . . . , n -1}. Since L c is a waterfall list of P n+1 we obtain that: if j is even

∀i ∈ {1, . . . , n -1}, |L c (i)| ≥ 2b = w(i) + w(i + 1) and |L c (n)| ≥ b = w(n).
|A(0, j)| ≥ j k=0 k even |L c (k)| = b + j k=2 k even 2b = b + j 2 2b = (j + 1)b,
and if j is odd

|A(0, j)| ≥ j k=0 k odd |L c (k)| = j k=1 k odd 2b = j + 1 2 2b = (j + 1)b.
Hence for all j ∈ {0, . . . , n -1}, |A(0, j)| ≥ (j + 1)b.

Case 3: j = n. Since n ≥ Even 2b e by hypothesis, and

| A(0, n) |≥ n k=0 k odd |L c (k)| = a n 2 , if n is even; b + a n-1 2 , otherwise;
we deduce that |A(0, n)| ≥ (n + 1)b, which concludes the proof.

Also, we will need the following result with more restrictions on the lists of colors on the two last vertices of the path. Theorem 9. Let n, a, b, e be four integers such that a = 2b + e. Let L be a list of a path P n+1 such that |L(0)| = b, and for any i ∈ {1, . . . , n -2} :

|L(i)| = a, |L(n -1)| = |L(n)| = b + e, and |A(n -1, n)(L)| ≥ 2b. If n = Even( 2b e ) then P n+1 is (L, b)-colorable. Proof. Since |A(n -1, n)| = |L(n -1)| + |L(n)\L(n -1)| = (b + e) + |L(n)\L(n -1)| ≥ 2b, we obtain that |L(n)\L(n -1)| ≥ b -e. Let D be a set such that D ⊂ L(n)\L(n -1) and |D| = b -e.
Let L ′ be the new list constructed with L such that L ′ (i) = L(i) if i ∈ {0, . . . , n -1} and L ′ (n) = L(n)\D and let w ′ be a new weight function defined by w

′ (i) = b if i ∈ {0, . . . , n -1}and w ′ (n) = e.
We are going to prove that if P n+1 is (L ′ , w ′ )-colorable then P n+1 is (L, b)colorable. Indeed, if c ′ is an (L ′ , w ′ )-coloring of P n+1 , then we construct c such that:

c(i) = c ′ (i), if i ∈ {0, . . . , n -1}; c ′ (n) ∪ D, otherwise. Since D ∩ L(n -1) = ∅, we have c(n -1) ∩ c(n) = ∅ and then c is an (L, b)- coloring of P n+1 . Now, this new list L ′ is a good list of P n+1 and |L ′ (n)| ≥ w ′ (n). Proposition 4 shows that there exists a waterfall list L c similar to L ′ such that for all k we have |L c (k)| = |L ′ (k)|.
Thanks to Corollary 7, it remains to check that:

∀j ∈ {0, . . . , n} : |A(0, j)(L c )| ≥ j k=0 w ′ (k).
Case 1: j ∈ {0, . . . , n -2}. Since the list is a waterfall list, we have:

|A(0, j)(L c )| ≥    j k=0 k even |L c (k)| = b + a j 2 , if j is even; j k=0 k odd |L c (k)| = a j+1 2 , otherwise;
and the weight function satisfies j k=0 w ′ (k) = (j + 1)b. Hence, we deduce that

|A(0, j)(L c )| ≥ j k=0 w ′ (k).
Case 2: j = n -1. Since the list is a waterfall list, we have:

|A(0, n -1)(L c )| ≥ n-1 k=0 k odd |L c (k)| = (b + e) + a n -2 2 ,
and n-1 k=0 w ′ (k) = nb. Then b + e + a n-2 2 ≥ nb if and only if en 2 ≥ b, which is true by hypothesis since n = Even( 2b e ), thus

|A(0, n -1)(L c )| ≥ n-1 k=0 w ′ (k).
Case 3: j = n. Since the list is a waterfall list, we have:

|A(0, n)(L c )| ≥ n k=0 k even |L c (k)| = b + 2e + a n -2 2 ,
and n k=0 w ′ (k) = nb + e. Then b + 2e + a n-2 2 ≥ nb + e if and only if en 2 ≥ b, which is true by hypothesis since n = Even( 2b e ), thus

|A(0, n)(L c )| ≥ n k=0
w ′ (k).

Choosability of the triangular lattice

Let R be a finite triangle-free induced subgraph of the triangular lattice. Recall that the triangular lattice is embedded in an Euclidian space and that any vertex (x, y) of R has at most six neighbors: its neighbor on the left (x -1, y), its neighbor on the right (x + 1, y), its neighbor on the top left (x -1, y + 1), its neighbor on the top right (x, y + 1), its neighbor on the bottom left (x, y-1) and its neighbor on the bottom right (x+1, y-1).

Follwing the terminology used in [START_REF] Havet | Channel assignement and multicolouring of the induced subgraphs of the triangular lattice[END_REF], we define nodes and handles of R. Definition 11. A cutting node of R is a left node (x, y) such that for any node (x ′ , y ′ ), we have y ≥ y ′ , and for any left node (x ′ , y), we have x ′ ≤ x.

A handle H of R is a subpath of R such that its extremal vertices are nodes and its internal vertices have degree 2. The set of the internal vertices of a handle H is denoted by Ḣ.

A cutting handle of R is a handle such that one of its extremal vertices is the cutting node (x, y) and one of its internal vertices is (x, y + 1).

One can view the cutting node as the left node the most on the top on the right.

We have the following claim:

Claim 1. Let H be a cutting handle of R such that V (H) = {v 0 , . . . , v n }.

If the length n of H is less than or equal to 3, then n = 3 and v 3 has a neighbor v 4 = v 2 of degree less than or equal to 2.

u u u u u u u u J J J J J J v 0 v 1 v 2 v 3 v 4
Fig. 3. Cutting handle of length 3.

Theorem 12. For any integer m ≥ 1, every finite triangle-free induced subgraph of the triangular lattice is (5m, 2m)-choosable.

Proof. Set a = 5m, b = 2m and e = m. Any graph with only vertices of degree 0 or 1 is (2m, m)-choosable. Also, a graph having only vertices of degree 2 is a union of cycles. Cycles of even length are (2m, m)-choosable and cycles of odd length ℓ > 3 are (5m, 2m)-choosable [START_REF] Voigt | On list Colourings and Choosability of Graphs[END_REF].

Let G be a minimal (with respect to the number of vertices) counterexample. Since G is a triangle-free induced subgraph of the triangular lattice, its girth2 is at least 6 and hence it has at least two nodes. Therefore, by symmetry, G has a cutting handle H (otherwise, consider its mirror graph) and for any 5m-list L of G, there exists an (L, 2m)-coloring c of G -Ḣ. Notice that the above proof can be easily translated to show the more general result that for any integers a, b such that a/b ≥ 5/2, every finite triangle-free induced subgraph of the triangular lattice is (a, b)-choosable.

Also, using similar arguments with some additional results on the listcolorability of the path [START_REF] Godin | Coloration et choisissabilité des graphes et applications[END_REF], allows us to show that triangle-free induced subgraphs of the triangular lattice are (7, 3)-colorable, thus giving another proof of Havet's result.

Moreover, the method defined in this paper can serve as a starting tool in order to prove Conjecture 2. Proceeding as in the proof of Theorem 12 but with a = 9 and b = 4 (and e = a-2b = 1), allows us to prove that a minimal counter-example to the conjecture does not contain handles of length n ≥ 8. By using more complex structures than handles, some additional properties of a minimal counter-example were found by Godin [START_REF] Godin | Coloration et choisissabilité des graphes et applications[END_REF]. However, many configurations remain to be investigated in order to prove the conjecture.

Fig. 1 .

 1 Fig. 1. Example of a list L which is similar to a waterfall list L c .

  two cliques joined by a cut-vertex; (c) paths;(d) a triangle with a path of length two added at one of its vertices;

Corollary 8 .

 8 Let L be a list of P n+1 such that |L(0)| = |L(n)| = b, and |L(i)| = a = 2b + e for all i ∈ {1, . . . , n -1} (with e = 0). If n ≥ Even 2b e then P n+1 is (L, b)-colorable.

  By Corollary 7 it remains to prove that: ∀j ∈ {0, . . . , n}, |A(0, j)| ≥ j k=0 w(k) = (j + 1)b.

Case 1 :

 1 j = 0. By hypothesis, we have |A(0, 0)| = |L c (0)| ≥ b.

Definition 10 .

 10 The nodes of R are the vertices of degree 3. There are two kinds of nodes: the left nodes whose neighbors are the neighbors on the left, on the top right, and on the bottom right; and the right nodes whose neighbors are the neighbors on the right, on the top left and on the bottom left.

Fig. 2 .

 2 Fig. 2. Left node and right node.

  IfH is of length n ≥ 4 = Even 4m m , by Corollary 8, c can be extended to an (L, 2m)-coloring of G, contradicting the hypothesis. Otherwise, by Claim 1, H has length 3 and v 3 has a neighbor v 4 = v 2 of degree two (let v 5 be the other neighbor of v 4 ). Hence we have|L(v 4 )\c(v 5 )| ≥ 5m-2m = 3m = b+e, |L(v 3 )| = 5m ≥ b + e and |L(v 3 ) ∪ L(v 4 ) \ c(v 5 )| ≥ |c(v 3 ) ∪ c(v 4 )| = 4m = 2b.Then, H satisfies the conditions of Theorem 9 and the coloring c restricted to G-( Ḣ ∪{v 3 , v 4 }) can be extended to an (L, 2m)-coloring of G, contradicting the hypothesis.

the length of a shortest (simple) cycle in the graph


C Chandre
email: chandre@cpt.univ-mrs.fr

P J Morrison
email: morrison@physics.utexas.edu

E Tassi
email: tassi@cpt.univ-mrs.fr

On the Hamiltonian formulation of incompressible ideal fluids and magnetohydrodynamics via Dirac's theory of constraints

The Hamiltonian structures of the incompressible ideal fluid, including entropy advection, and magnetohydrodynamics are investigated by making use of Dirac's theory of constrained Hamiltonian systems. A Dirac bracket for these systems is constructed by assuming a primary constraint of constant density. The resulting bracket is seen to naturally project onto solenoidal velocity fields.

Introduction

From the early work of Lagrange [START_REF] Lagrange | Mécanique Analytique, English Title: Analytical Mechanics[END_REF] it became clear that ideal fluid systems possess the canonical Hamiltonian form when one adopts a fluid element description, the so-called Lagrangian variable description. Because the Lagrangian description is particle-like in nature, it is amenable to action functional and Hamiltonian formulations. However, when Eulerian variables are incorporated the canonical Hamiltonian structure for all ideal kinetic and fluid theories is altered because the transformation from Lagrangian to Eulerian variables is not canonical. This results in a Hamiltonian theory in terms of noncanonical Poisson brackets (see, e.g., [START_REF] Morrison | Mathematical Methods in Hydrodynamics and Integrability in Related Dynamical Systems[END_REF][START_REF] Salmon | [END_REF]4,[START_REF] Marsden | Introduction to Mechanics and Symmetry[END_REF][START_REF] Morrison | [END_REF][START_REF] Morrison | Hamiltonian Fluid Mechanics[END_REF] for review).

The present paper concerns the proper treatment of the incompressibility constraint of fluid mechanics in the context of the Eulerian Hamiltonian theory in terms of noncanonical Poisson brackets. We do this by applying Dirac's method for incorporating constraints in Hamiltonian theories, a central element of which is a Dirac bracket. In the past, researchers have used Dirac brackets for various reasons in fluid mechanics [8,9,10,11,[START_REF] Morrison | [END_REF]12], but the first works to use it to explicitly enforce the incompressibility constraint for Euler's equation in three dimensions appear to be Refs. [13,14,15]. Here we first extend the work of these authors by constructing the Dirac bracket for the ideal fluid with the inclusion of entropy advection, which allows for the inclusion of any advected quantity like salt concentration in the ocean. This generalization reveals that Dirac brackets of the kind considered in Refs. [13,14,15], as well as our generalization, can be written in a considerably simplified and perspicuous form in terms of the projection operator that takes a general vector field to a solenoidal one. With this realization we then construct the Dirac bracket for incompressible magnetohydrodynamics (MHD), thereby making clear its Hamiltonian structure. We present these results together by starting from the full compressible ideal MHD

equations, v = -v • ∇v -ρ -1 ∇ ρ 2 ∂U ∂ρ + ρ -1 (∇ × B) × B , (1) ρ
= -∇ • (ρv) , (2)
Ḃ = ∇ × (v × B) , (3) ṡ
= -v • ∇s , (4)
where v(x, t) is the velocity field, ρ(x, t) is the mass density, B(x, t) is the magnetic field, and s(x, t) is the entropy per unit mass. All of these dynamical variables are functions of x ∈ U ⊂ R 3 as well as time. We suppose boundary conditions are such that no surface terms appear in subsequent calculations which, e.g., would be the case on a periodic box or all space. The observables of the MHD system are functionals of these fields, denoted generically by

F [ρ, v, B, s].
In terms of these variables, this system has the following Hamiltonian (energy):

H[ρ, v, B, s] = d 3 x 1 2 ρv 2 + ρU (ρ, s) + B 2 2 , (5)
where

v 2 =
{F, G} = -d 3 x F ρ ∇ • G v + F v • ∇G ρ -ρ -1 (∇ × v) • (F v × G v ) +ρ -1 ∇s • (F s G v -F v G s ) + ρ -1 F v • [∇G B ] -ρ -1 G v • [∇F B ] • B +B • [∇ ρ -1 F v ] • G B -[∇ ρ -1 G v ] • F B , (6)
where F v denotes the functional derivative of F with respect to v, i.e. F v = δF/δv, and the same holds for F s , F B and F ρ . Here the notation a Here we impose a primary constraint that is a constant and uniform density and the rest follows from Dirac's algorithm. In particular, it is seen that the corresponding secondary constraint is that the velocity field be solenoidal. We verify that Poisson-Dirac bracket indeed produces the correct equations of motion. This is followed in Sec. 4 by a detailed comparison to previous attempts at incorporating incompressibility in Hamiltonian formulations of incompressible ideal fluids. Finally, in Sec. 5, we summarize and conclude. The paper also has several appendices that address various issues that arise in the text.

• [M ] • b = b•(a•[M ]) is

Dirac brackets

As stated above, Dirac's theory is used for the derivation of the Hamiltonian structure of Hamiltonian systems subjected to constraints. Dirac constructed his theory in terms of canonical Poisson brackets and detailed expositions of his theory can be found in Refs. [17,[START_REF] Sudarshan | Classical Dynamics: A Modern Perspective[END_REF][START_REF] Hanson | Constrained Hamiltonian Systems[END_REF][START_REF] Sundermeyer | Constrained Dynamics[END_REF][START_REF] Marsden | Introduction to Mechanics and Symmetry[END_REF]. However, it is not difficult to show that his procedure also works for noncanonical Poisson brackets (cf., e.g., an Appendix of Ref. [10]). In this section, we recall a few basic facts about Dirac

C αβ (x, x ′ ) = {Φ α (x), Φ β (x ′ )} ,
where we note that C αβ (x, x ′ ) = -C βα (x ′ , x). If C has an inverse, then the Dirac bracket is defined as follows:

{F, G} * = {F, G} -d 3 x d 3 x ′ {F, Φ α (x)}C -1 αβ (x, x ′ ){Φ β (x ′ ), G}, (7)
where the coefficients C -1 αβ (x, x ′ ) satisfy

d 3 x ′ C -1 αβ (x, x ′ )C βγ (x ′ , x ′′ ) = d 3 x ′ C αβ (x, x ′ )C -1 βγ (x ′ , x ′′ ) = δ αγ δ(x -x ′′ ), which implies C -1 αβ (x, x ′ ) = -C -1 βα (x ′ , x
). This procedure is effective only when the coefficients C -1 αβ (x, x ′ ) can be found. If C is not invertible, then one needs, in general, secondary constraints to determine the Dirac bracket. The secondary constraint is given by the consistency equation which states that Φ1 (x) = 0 for the Hamiltonian H + d 3 x u(x)Φ 1 (x). This translates into

d 3 x {Φ 1 (x), H}µ(x) ≈ 0, (8)
for all functions µ such that

d 3 x µ(x)C(x, x ′ ) = 0.
Here the weak equality ≈ stands for an equality on the manifold defined by Φ 1 (x) = 0. Equation (8) gives the expression which has to be satisfied by the secondary constraint.

Dirac bracket for ideal incompressible MHD

To construct the Hamiltonian theory of ideal incompressible MHD, the first (primary) constraint is chosen to be a constant and uniform density ρ 0 , i.e.

Φ 1 (x) = ρ(x) -ρ 0 .

However, the Dirac procedure can be performed for the case of a nonuniform background density (see Appendix A). Given that C 11 (x, x ′ ) = 0, at least one secondary constraint is needed. This secondary constraint, denoted Φ 2 (x), is

given by {Φ 1 (x), H} = 0 which leads us naturally to

Φ 2 (x) = ∇ • v .
From the Poisson bracket (6), we compute the elements C αβ (x, x ′ ) as

C 11 (x, x ′ ) = 0, C 12 (x, x ′ ) = ∆δ(x -x ′ ), C 21 (x, x ′ ) = -∆δ(x -x ′ ), C 22 (x, x ′ ) = ∇ • ρ -1 (∇ × v) × ∇δ(x -x ′ ) .
From these expressions, we obtain the coefficients C -1 αβ (x, x ′ ) as

C -1 11 (x, x ′ ) = ∆ -1 ∇ • ρ -1 (∇ × v) × ∇∆ -1 δ(x -x ′ ) , C -1 12 (x, x ′ ) = -∆ -1 δ(x -x ′ ), C -1 21 (x, x ′ ) = ∆ -1 δ(x -x ′ ), C -1 22 (x, x ′ ) = 0, where ∆ -1 acts on a function f as ∆ -1 f (x) = -(4π) -1 d 3 x ′ f (x ′ )/|x -x ′ |.
Given the following expressions

{Φ 1 (x), G} = -∇ • G v , {Φ 2 (x), G} = -∆G ρ -∇ • ρ -1 (∇ × v) × G v + ∇ • ρ -1 ∇sG s -∇ • ρ -1 [∇G B ] • B + ∇ • ρ -1 ∇ • [BG B ] ,
we deduce various contributions to the Dirac bracket (7):

d 3 xd 3 x ′ {F, Φ 1 (x)}C -1 11 (x, x ′ ){Φ 1 (x ′ ), G} = -d 3 x∇ • F v ∆ -1 ∇ • (ρ -1 (∇ × v) × ∇∆ -1 ∇ • G v ) , d 3 xd 3 x ′ {F, Φ 1 (x)}C -1 12 (x, x ′ ){Φ 2 (x ′ ), G} = d 3 x∇ • F v G ρ + ∆ -1 ∇ • (ρ -1 (∇ × v) × G v ) -∆ -1 ∇ • (ρ -1 ∇sG s ) + ∆ -1 ∇ • (ρ -1 [∇G B ] • B) -∆ -1 ∇ • ρ -1 ∇ • [BG B ] , d 3 xd 3 x ′ {F, Φ 2 (x)}C -1 21 (x, x ′ ){Φ 1 (x ′ ), G} = -d 3 x F ρ + ∆ -1 ∇ • (ρ -1 (∇ × v) × F v ) -∆ -1 ∇ • (ρ -1 ∇sF s ) + ∆ -1 ∇ • (ρ -1 [∇F B ] • B) -∆ -1 ∇ • ρ -1 ∇ • [BF B ] ∇ • G v .
From the contributions associated with C -1 12 and C -1 21 , we notice that the part 6) vanishes. We also notice that the terms in the Dirac bracket only involve

-d 3 x(F ρ ∇•G v +F v •∇G ρ ) of the Poisson bracket (
Ḡv := G v -∇∆ -1 ∇ • G v =: P • G v . (9)
Two equivalent expressions for P acting on a vector a are

P • a = a -∇∆ -1 ∇ • a = -∇ × (∇ × ∆ -1 a).
The linear projection operator P acting on vectors is symmetrical, in the sense that

d 3 x a • P • b = d 3 x b • P • a,
for any vector fields a(x) and b(x). In addition, it satisfies the following properties:

P 2 = P , P • ∇ = 0 , P • ∇× = ∇× , ∇ × P = ∇× , ∇ • P = 0 .
As a consequence, we notice that the functional derivatives Ḡv are divergencefree, i.e. ∇• Ḡv = 0. In terms of Ḡv given by Eq. ( 9) the Dirac bracket is written in the following compact form:

{F, G} * = d 3 x ρ -1 (∇ × v) • Fv × Ḡv -ρ -1 ∇s • F s Ḡv -Fv G s -ρ -1 Fv • [∇G B ] -ρ -1 Ḡv • [∇F B ] • B -B • [∇ ρ -1 Fv ] • G B -[∇ ρ -1 Ḡv ] • F B . (10)
Upon comparison with bracket (6), we see that this bracket is precisely that of Refs. [16,[START_REF] Morrison | Mathematical Methods in Hydrodynamics and Integrability in Related Dynamical Systems[END_REF] with the functional derivatives F v and G v replaced by the divergence-free functional derivatives Fv and Ḡv according to Eq. ( 9). In this procedure, the terms of the bracket [START_REF] Morrison | [END_REF] in

F ρ or G ρ disappear because ∇• Ḡv = 0.
We also note that if we drop all terms but the first in Eq. ( 10), then with some manipulations one can show this bracket is equivalent to the one obtained in

Ref. [13], albeit in a significantly simplified and perspicuous form, and that this term corresponds to the bracket of Ref. [START_REF] Zakharov | [END_REF].

Because the Poisson bracket ( 10) is exactly the bracket of Ref. [16] with the replacement of the functional derivatives by projected functional derivatives, one wonders if one can always construct Dirac brackets by this procedure. In Appendix B it is shown that not all projections produce good brackets, only those that define Hamiltonian vector fields (see also Appendix C).

Given that ∇ • Fv = 0 for all observables F , we obtain the following family of Casimir invariants of the Poisson bracket (10): Dirac brackets built on brackets with Casimir invariants retain those invariants (cf. Ref. [10]). As a consequence, the term d 3 x ρU (ρ, s) in the Hamiltonian is now a Casimir invariant, so that it can be dropped from the Hamiltonian because it will not give any contribution to the equations of motion (contrary to the compressible fluid or compressible MHD cases). Upon setting ρ 0 = 1, the Hamiltonian becomes

C[s] = d 3 x f (s),
H = 1 2 d 3 x v 2 + B 2 . ( 11
)
Therefore, the Hamiltonian theory for ideal Eulerian incompressible MHD is given by the bracket (10) with the Hamiltonian (11). The equations of motion follow: For the entropy s, this yields

ṡ = {s, H} * = -v • ∇s,
where, as before, we use the 'bar' shorthand for solenoidal quantities, i.e. v = P • v, and evidently ∇ • v = 0. Note s can be any advected quantity such as the concentration of salt.

Similarly, the dynamical equation for B is obtained

Ḃ = {B, H} * = -v • ∇B + B • ∇v = ∇ × (v × B) .
The equation for v is slightly more complicated, viz.

v = {v, H} * = -P • [(∇ × v) × v] + P • [(∇ × B) × B]. (12)
In particular, the property that ∇ • P = 0 implies that ∇ • v = 0, which is consistent with the constraint Φ 2 . We notice that the first term in Eq. ( 12) was obtained in Ref. [13]. Since v ≈ v (weak equality with the constraint Φ 2 ), the equations for v and

B becomes v = -v • ∇v -∇P c + (∇ × B) × B, Ḃ = ∇ × (v × B),
where the pressure-like term P c is given by

P c := - v 2 2 -∆ -1 ∇ • (∇ × v) × v + ∆ -1 ∇ • (∇ × B) × B .
Given the equation for the pressure, P c is not necessarily positive. Lastly, we point out that there is no equation for the mass density ρ, since it has been eliminated altogether from the theory.

The equations obtained above correspond to the traditional equations for incompressible MHD. It should be noted that ∇ • v = 0 is no longer a constraint on the flow since it is a conserved quantity. Actually, it is more than a conserved quantity since it is a Casimir invariant. If one choses an initial condition satisfying ∇•v = 0, then this quantity will remain constant under the dynamics.

Comparisons between brackets for incompressible fluids

We focus now on ordinary fluids and in particular we consider different for- A formal description of this was introduced in Refs. [22,23] for the Euler equations of an incompressible fluid. It was based on the fact that diffeomorphisms form an infinite parameter Lie group with a Lie algebra given by the commutator of vector fields. If D denotes vector fields of R 3 , then the commutator (Lie bracket)

[V, W] L = (W • ∇)V -(V • ∇)W, (13)
{F, G} L = d 3 x v • [F v , G v ] L , (14)
which indeed satisfies the Jacobi identity for all functionals of v, it being of the Lie-Poisson form. However, combined with the Hamiltonian H = d 3 x v 2 /2, it does not yield the correct equations of motion for incompressible fluid mechanics since ∇ • v is not conserved by the flow.

Another bracket for incompressible fluids was proposed in Ref. [24]:

{F, G} 0 = d 3 x ω • [(∇ × F ω ) × (∇ × G ω )] .
With this bracket and the Hamiltonian

H = d 3 x v 2 /2 where ω = ∇ × v, the equation ∇ × H ω = v = H v leads to ∂ω ∂t = ∇ × (v × ω),
which is the correct equation of motion for the vorticity in both compressible and incompressible barotropic fluids. However, two issues should be noted: (i) this bracket does not satisfy the Jacobi identity for functionals defined on arbitrary vector fields ω. This is easily seen by the following counter example:

F 1 = 1 2 d 3 x ω • x y 2 , F 2 = 1 2 d 3 x ω • ŷ z 2 , , F 3 = d 3 x ω • ẑ x , which yields, {F 1 , {F 2 , F 3 } 0 } 0 + = -d 3 x ω • ∇(yz) = 0 , (15)
and (ii) it is not stated how the constraint ∇ • v = 0 is to be applied, and indeed the procedure of this paper also gives the correct equation of motion for compressible barotropic fluids.

With regards to (i), if one considers vector fields that satisfy ω = ∇ × v, then Eq. ( 15) gives zero (see Appendix D). Thus, one might attempt to restrict the space of functionals on which this bracket is defined in order to get a Lie algebra realization on such functionals. Yet, since ω = ∇ × v, it seems natural just to use v as a variable to enforce the constraint ∇ • ω = 0. This leads to a bracket similar to Eq. ( 14), namely {F,

G} • = d 3 x v • [F v , G v ] • , where [V, W] • := ∇ × (V × W) = [V, W] L + V(∇ • W) -W(∇ • V).

This bracket is not of Lie-Poisson type since [•, •]

• does not satisfy the Jacobi identity, as can be seen from the counterexample (

V 1 , V 2 , V 3 ) = (xyx, y ŷ, ẑ), giving [[V 1 , V 2 ] • , V 3 ] • + = yẑ.
Thus {F, G} • has to be discarded even though it has the interesting property {∇ • v, F } • = 0 for all observables F . This returns us to issue (ii) above about enforcing ∇ • v = 0. The failure of Eq. ( 14) to give the correct equations of motion can be traced to the use of

∇ × F ω = F v , which cannot be true for all functionals because 0 = ∇ • ∇ × F ω = ∇ • F v = 0. Note, even if F [v]
is defined on divergence-free vector fields, it does not follow that ∇ • F v = 0. This suggests introducing

∇ × F ω = F v + Υ ,
where Υ is chosen to enforce the constraint, i.e.

∇ × F ω = F v -∇∆ -1 ∇ • F v = P • F v . ( 16
)
Now, inserting Eq. ( 16) into Eq. ( 14), we obtain the Dirac bracket of Sec. 3.

So the correct Poisson bracket for incompressible fluids can be constructed as a

Lie-Poisson bracket, from a projection of the Lie bracket [•, •] L as follows:

[V, W] P := [P • V, P • W] L ,
where we notice an important property for verifying the Jacobi identity is P •

[P • V, P • W] L = [P • V, P • W] L (cf. Appendix C).
Previously the need for the projection for the incompressible fluid was observed in Refs. [START_REF] Marsden | Introduction to Mechanics and Symmetry[END_REF][START_REF] Zakharov | [END_REF]. However, in light of our work, when projection is handled appropriately, this amounts to the Dirac bracket construction of Ref. [13], which we here generalized.

In closing this section we make a few more remarks. In the two-dimensional formulations of Refs. [START_REF] Morrison | Hamiltonian field description of two-dimensional vortex fluids an guiding center plasmas[END_REF][START_REF] Morrison | Mathematical Methods in Hydrodynamics and Integrability in Related Dynamical Systems[END_REF][START_REF] Olver | [END_REF] there is no issue with projection: unlike {•, •} 0 and {•, •} • , the bracket given there satisfies the Jacobi identity for all functionals of the scalar vorticity. Also, in the compressible formulation the density is added as a dynamical variable (cf. the first term of Eq. ( 9) of Ref. [16]) and the variations with respect to density in the Jacobi identity compensate the failure of Jacobi for the second term alone (see footnotes 10 and 12 of Ref. [16]). Lastly we point out that care must be taken when inserting projections on functional derivatives into Poisson brackets, for the resulting Poisson bracket may not satisfy the Jacobi identity (cf. Appendix B and Appendix C).

Conclusions

Here we have generalized the Dirac bracket approach of Ref. [13] by including entropy advection. This produces a Hamiltonian description of an important missing piece of the dynamics of incompressible fluids, viz. that of density advection. Recall, ∇ • v = 0 does not imply constant ρ, but that ρ be advected. If one chooses ∇ • v as the primary constraint then one does not obtain a bracket for an advected density. Thus, it would appear that density advection cannot be produced by the Dirac bracket construction. However, having done the calculation with entropy advection we observe that ρ drops out of the picture and we obtain a bracket that describes advection of a quantity s by a solenoidal velocity field. Thus, if one just reinterprets s as ρ we obtain the missing dynamics of density advection.

Performing the Dirac construction for MHD with density advection showed us that this approach is equivalent to direct projection of the MHD bracket of Refs. [16,[START_REF] Morrison | Mathematical Methods in Hydrodynamics and Integrability in Related Dynamical Systems[END_REF] to solenoidal vector fields. It is now evident how to construct brackets for a variety of incompressible models. If it is Lie-Poisson, then one can proceed as in Appendix C and if is not, then one can step through the Dirac bracket construction. In fact, the Dirac construction is more general and can be used to enforce any compatible constraints, as seen, e.g., in Appendix A. Evidently, Dirac brackets provide a powerful tool that extends well beyond the results of this paper.

Joseph Biello. The authors also acknowledge fruitful discussions with the Équipe de Dynamique Nonlinéaire of the Centre de Physique Théorique of Marseille.

Appendix A. Generalization to ideal MHD with nonuniform background density Suppose the density is constant but nonuniform, which might, e.g., be an imposed stratification caused by gravity. It is interesting to see where such

an assumption leads when one follows the Dirac construction. To this end we assume Φ 1 (x) = ρ -ρ 0 (x) = 0, where ρ 0 is the time-independent background density. Proceeding as in Sec. 3, because {Φ 1 (x), Φ 1 (x ′ )} = 0 we obtain the secondary constraint that has the form

Φ 2 (x) = ∇ • (ρ 0 (x)v) = 0 . (A.1)
Although Eq. (A.1) is valid for compressible equilibria, to justify such a constraint on physical grounds would require a mechanism for maintaining the constraint or a time scale argument of some sort. We will not pursue this here.

From the Poisson bracket (6), we compute the elements C αβ (x, x ′ ) as

C 11 (x, x ′ ) = 0, C 12 (x, x ′ ) = Aδ(x -x ′ ), C 21 (x, x ′ ) = -Aδ(x -x ′ ), C 22 (x, x ′ ) = ∇ • ρ 2 0 ρ -1 (∇ × v) × ∇δ(x -x ′ ) ,
where A is the symmetric operator Af = ∇ • (ρ 0 ∇f ). Provided A is invertible, we obtain the coefficients C -1 αβ (x, x ′ ) as

C -1 11 (x, x ′ ) = A -1 ∇ • ρ 2 0 ρ -1 (∇ × v) × ∇A -1 δ(x -x ′ ) , C -1 12 (x, x ′ ) = -A -1 δ(x -x ′ ), C -1 21 (x, x ′ ) = A -1 δ(x -x ′ ), C -1 22 (x, x ′ ) = 0.
Given the following expressions

{Φ 1 (x), G} = -∇ • G v , {Φ 2 (x), G} = -AG ρ -∇ • ρ 0 ρ -1 (∇ × v) × G v + ∇ • ρ 0 ρ -1 ∇sG s -∇ • ρ 0 ρ -1 [∇G B ] • B + ∇ • ρ 0 ρ -1 ∇ • [BG B ] ,
we deduce various contributions to the Dirac bracket (7):

d 3 xd 3 x ′ {F, Φ 1 (x)}C -1 11 (x, x ′ ){Φ 1 (x ′ ), G} = -d 3 x∇ • F v A -1 ∇ • (ρ 2 0 ρ -1 (∇ × v) × ∇A -1 ∇ • G v ), d 3 xd 3 x ′ {F, Φ 1 (x)}C -1 12 (x, x ′ ){Φ 2 (x ′ ), G} = d 3 x∇ • F v G ρ + A -1 ∇ • (ρ 0 ρ -1 (∇ × v) × G v ) -A -1 ∇ • (ρ 0 ρ -1 ∇sG s ) + A -1 ∇ • (ρ 0 ρ -1 [∇G B ] • B) -A -1 ∇ • ρ 0 ρ -1 ∇ • [BG B ] , d 3 xd 3 x ′ {F, Φ 2 (x)}C -1 21 (x, x ′ ){Φ 1 (x ′ ), G} = -d 3 x F ρ + A -1 ∇ • (ρ 0 ρ -1 (∇ × v) × F v ) -A -1 ∇ • (ρ 0 ρ -1 ∇sF s ) + A -1 ∇ • (ρ 0 ρ -1 [∇F B ] • B) -A -1 ∇ • ρ 0 ρ -1 ∇ • [BF B ] ∇
The Dirac bracket now reads

{F, G} * = d 3 x ρ -1 (∇ × v) • Fv × Ĝv -ρ -1 ∇s • F s Ĝv -Fv G s -ρ -1 Fv • [∇G B ] -ρ -1 Ĝv • [∇F B ] • B -B • [∇ ρ -1 Fv ] • G B -[∇ ρ -1 Ĝv ] • F B , (A.2)
where Fv =

P A • F v = F v -ρ 0 ∇ A -1 ∇ • F v .
Observe that ∇ • Fv = 0 for these equations, as was the case for the incompressible MHD. We also notice that the Dirac bracket has the same form as that for incompressible MHD, with the only difference being divergence-free functional derivatives Fv replacing Fv .

In the same way as in Sec. 3, one term in the Hamiltonian corresponds to a Casimir invariant. More precisely, from the property that ∇ • Fv = 0 for any observable F , it is shown that

C[s] = d 3 x ρf (ρ, s),
is a family of Casimir invariants, where f is any function of s and ρ. Therefore the Hamiltonian is

H = 1 2 d 3 x ρ 0 v 2 + B 2 ,
and the internal energy U plays no role in the dynamics, just as was the case for ideal incompressible MHD.

We impose an even number of constraints Φ α ∈ C ∞ (Z), α = 1, . . . , 2m, and wish to project Hamiltonian vector fields on Z, elements of X (Z), to Hamiltonian vector fields that are tangent to a submanifold M := ∩ α Φ α , X (M).

As is well-known elements of X (Z) are linear operators, in particular, the element generated by f ∈ C ∞ (Z) has the form

L f = -{f, • } = J ab ∂f ∂z b ∂ ∂z a ,
and the commutator of two such elements satisfies [L f , L g ] = -L {f,g} . Thus there an isomorphism between the Lie algebra of such linear operators and Poisson brackets. We wish to maintain this structure for Hamiltonian vector fields projected onto X (M).

To project a Cartesian vector into a surface defined by φ =constant, one uses the normal ∇φ to construct the following projection operator:

P := I - ∇φ∇φ |∇φ| 2 (B.1)
where I is the identity. Evidently P • ∇φ ≡ 0. Essentially this same idea occurs in infinite dimensions in the context of Hilbert spaces and is efficacious for application in quantum mechanics. However, the problem at hand differs from these cases in that we are interested in Hamiltonian vector fields (finite or infinite) and our manifold is symplectic with no intrinsic notion of metric. Thus, if we are to proceed without adding additional structure, we must construct a projection operator using only the functions Φ α and cosymplectic form, J. With Eq. (B.1) as a guide we write

P a b = δ a b -K αβ ∂Φ α ∂z b ∂Φ β ∂z c J ac
where K αβ is chosen so that Hamiltonian vector fields generated by any of the Φ α are projected out, i.e. P • L Φα ≡ 0 for all α. Now it is desired to find such a K αβ in terms of the {Φ α } and J alone. Fortunately, a direct calculation reveals that the desired quantity is given by K αβ = {Φ α , Φ β } -1 . Thus we have achieved our goal if this inverse exists. Assuming this is the case we obtain the following Hamiltonian projection operator:

P a b = δ a b -{Φ α , Φ β } -1 ∂Φ α ∂z b ∂Φ β ∂z c J ac . Evidently Λ a f := P a b L b f = P a b J bd ∂f ∂z d = J ad ∂f ∂z d -{Φ α , Φ β } -1 ∂Φ α ∂z b ∂Φ β ∂z c J ac J bd ∂f ∂z d , (B.2)
and Λ Φα ≡ 0 for all α. Also, an elementary calculation reveals the P 2 = P, as expected for a projection operator.

It remains to show that the set of projected vector fields of the form Λ f = P • L f are Hamiltonian on the constraint submanifold:

[Λ f , Λ g ] = -Λ {f,
L f , L g ] = L f L g -L g L f = J bc ∂ c f ∂ b (J rs ∂ s g∂ r ) -(f ↔ g) = [J bc ∂ b J rs ∂ c f ∂ s g + J bc J rs ∂ c f ∂ b ∂ s g]∂ r -(f ↔ g) = -[J rb ∂ b J cs ∂ c f ∂ s g + J sc J rb ∂ b (∂ c f ∂ s g) = -L {f,
∇ × [f × (h • ∇)g] = f ∇ • [(h • ∇)g] + [(h • ∇)g • ∇]f -(f • ∇)[(h • ∇)g].
Since ∇ • f = 0 (for all observable F ), the divergence terms in Eq. (D.2) vanish, gives the same value for ω. For instance, if we choose ∇ • v = 0, we obtain

∇ × F ω = F v -∇∆ -1 ∇ • F v .
Thus, we end up with the Poisson bracket obtained with Dirac's procedure for constrained Hamiltonian systems.

  a scalar explicitly given by a i M ij b j (with repeated indices summed) for any vectors a and b and any matrix (or dyad) [M ]. The bracket (6) with Hamiltonian (5) gives the MHD equations (1)-(4) in the form Ḟ = {F, H}. (Assuming ∇ • B = 0.) The paper is organized as follows: In Sec. 2 we review Dirac's formalism for constrained Hamiltonian systems. Then, in Sec. 3 this theory is used to obtain the noncanonical Poisson-Dirac bracket for the incompressible ideal MHD equations including entropy advection.

  brackets in infinite dimensions in the context of noncanonical Poisson brackets. If we impose K local constraints Φ α (x) = 0 for α = 1, . . . , K on a Hamiltonian system with a Hamiltonian H and a Poisson bracket {•, •}, the Dirac bracket is obtained from the matrix C defined by the Poisson brackets between the constraints,

  where f (s) is any function of the entropy, i.e. it commutes with all the observables, {C[s], G} * = 0 for all G. This family originates from the family of Casimir invariants of the original Poisson bracket[START_REF] Morrison | [END_REF] given by d 3 x ρf (s), and the fact that the Dirac constraints are also Casimir invariants. This follows since

  mulations for describing the motion of an ideal incompressible fluid. In his famous treatise Lagrange[START_REF] Lagrange | Mécanique Analytique, English Title: Analytical Mechanics[END_REF] provides descriptions of both incompressible and compressible ideal fluids. Lagrange uses what is now generally called the Lagrangian variable description, whereby the dynamics of fluid elements, points, are treated in a spatial domain, and he constructs the Lagrangian for this infinite-dimensional system. If we let q denote the position of a fluid element labeled by a, that lies in a domain U ⊂ R 3 occupied by the fluid, then q : U → U at each time, or q(a, t). To describe incompressible fluids, Lagrange adds the constraint det |∂q/∂a| = 1. It naturally leads to what is now referred to as the volume preserving diffeomorphism description of the incompressible fluid.

  is again a vector field for any V, W ∈ D, and it is an elementary exercise in vector calculus to show the Jacobi identity, [U, [V, W] L ] L + = 0 for all U, V, W ∈ D, where denotes the two other terms obtained by cyclic permutation of (U, V, W). If one restricts D to contain only divergence-free vector fields, D := {V ∈ D|∇ • V = 0}, then D ⊂ D is a Lie subalgebra, as seen by another elementary vector calculation that assures closure: ∇ • [V, W] L = 0 if V, W ∈ D. From the Lie bracket (13) one can construct the Lie-Poisson bracket (cf., e.g., Refs.[4, 5])

  g} , where ∂ b := ∂/∂z b and ∂ b operates only on the term immediately to its right unless parenthesis are included. In obtaining the second equality, second derivative terms canceled in the usual way, and in obtaining the third equality, antisymmetry, the Jacobi identity, and relabeling were used.All of the above can be formally extended to infinite dimensions (see, e.g., Ref.[START_REF] Morrison | Mathematical Methods in Hydrodynamics and Integrability in Related Dynamical Systems[END_REF]) by replacing partial derivatives by functional derivatives, sums by integrals, and matrix multiplication by operator action. derivative δ{F, G}/δω. In what follows, we let f := ∇ × F ω . The functional derivative of {F, G} with respect to ω contains three terms: one that comes from the explicit dependence of the bracket on ω and two other terms that are the second order functional derivatives of F and G. It has been shown in Ref.[START_REF] Morrison | Mathematical Methods in Hydrodynamics and Integrability in Related Dynamical Systems[END_REF] that the only important term comes from the explicit dependence on the variables, i.e. on ω. So from {F, G} ω = f × g, we get{F, {G, H}} = d 3 x ω • (f × ∇ × (g × h)). Since ∇ • f = 0, this becomes {F, {G, H}} = d 3 x ω • [f × (h • ∇)gf × (g • ∇)h]. (D.2) If ∇ • ω = 0,there exists a vector v such that ω = ∇ × v. By symmetry of the operator ∇×, we obtain terms like ∇ × [f × (h • ∇)gf × (g • ∇)h], which are transformed by the identity

  i.e. ∇ • [(h • ∇)g] = ∇ • [(g • ∇)h].In addition, from the following identity(f • ∇)[(h • ∇)g] = [(f • ∇)h • ∇]g + f i h j ∂ i ∂ j g, we have ∇×[f ×(h•∇)g-f ×(g•∇)h] = (h, g, f )-(f , h, g)-(g, h, f )+(f , g, h)-f i h j ∂ i ∂ j g+f i g j ∂ i ∂ j h,where (f , g, h) := [(f • ∇)g • ∇]h. By adding the cyclic permutations of F , G and H, we obtain∇ × [f × (h • ∇)gf × (g • ∇)h]+ = 0.As a consequence, the bracket (D.1) satisfies the Jacobi identity if ∇ • ω = 0.From the bracket (D.1) with ∇ • ω = 0, we perform the following change of variables: ω = ∇ × v. This change of variables depends on a gauge since v + ∇φ

  |v| 2 and B 2 = |B| 2 . With the MHD noncanonical Poisson bracket

	of Refs. [16, 2]

  . Because Eq. (B.3) is satisfied for a generic Poisson bracket, then it must be true for the Dirac bracket as well. To see that it is true for a generic Poisson bracket we write [

g} * , (B.3) for some well-defined Poisson bracket {f, g} * . As the notation suggests this turns out to be the Dirac bracket. It is evident from Eq. (B.2) that Λ a f = -{f, • } *

Acknowledgments

We acknowledge financial support from the Agence Nationale de la Recherche (ANR GYPSI). This work was also supported by the European Community under the contract of Association between EURATOM, CEA, and the French Research Federation for fusion study. The views and opinions expressed herein do not necessarily reflect those of the European Commission. Also, PJM was supported by U.S. Dept. of Energy Contract # DE-FG05-80ET-53088 and he would like to acknowledge several helpful conversations with Norm Lebovitz and

The two dynamical equations for s and B are similar than the ones for incompressible MHD, and are given by ṡ = -v • ∇s and Ḃ = ∇ × (v × B) ,

where the Bernoulli-like term W c is given by

Again we notice that ∇ • (ρ 0 v) is conserved by the flow since it is a Casimir invariant.

It should be noted that the second constraint Φ 2 above had a constant background density. Another choice would be to use the constraint Φ 2 with ρ replacing ρ 0 , i.e. use the following set of constraints:

Proceeding as above, the definition of the operator A naturally becomes Af = ∇ • (ρ∇f ), and the expression for the Dirac bracket obtained is identical to Eq. (A.2) with Fv :

Appendix B. Hamiltonian-Dirac Vector Fields

Let Z denote a phase space manifold that is a symplectic or Poisson manifold, and is thus equipped with a bracket operation {

We suppose the bracket satisfies the usual Lie enveloping algebra properties and can thus be written in coordinates as The bracket (C.1) does not in general satisfy the Jacobi identity. However, if P is independent of χ it may.

If the bracket is Lie-Poisson, then projection onto subalgebras always produces brackets that satisfy the Jacobi identity. Consider the Lie-Poisson bracket

In this construction F χ ∈ g where g is a Lie algebra and hence F χ is a vector.

Suppose P : g → k, where k is a vector subspace of g. Then, (i) the bracket

is defined, and (ii) it satisfies the Jacobi identity for arbitrary functionals of χ,

, which is the case if k is a subalgebra of g. This follows from the general Jacobi identity theorem proven in Ref. [START_REF] Morrison | Mathematical Methods in Hydrodynamics and Integrability in Related Dynamical Systems[END_REF] or more immediately from the fact that Eq. (C.2) is a Lie-Poisson bracket for k.

Appendix D. Direct proof of Jacobi identity

We consider the bracket

In order to prove the Jacobi identity for this kind of bracket, one only needs to consider the explicit dependence of the bracket on ω when taking the functional