F Chapoton

On some varieties associated with trees

This article considers some affine algebraic varieties attached to finite trees and closely related to cluster algebras. Their definition involves a canonical coloring of vertices of trees into three colors. These varieties are proved to be smooth and to admit sometimes free actions of algebraic tori. Some results are obtained on their number of points over finite fields and on their cohomology.

Introduction

The theory of cluster algebras, introduced by S. Fomin and A. Zelevinsky around 2000 [START_REF] Fomin | Cluster algebras. I. Foundations[END_REF][START_REF] Fomin | Cluster algebras. II. Finite type classification[END_REF], was motivated initially by the study of total positivity in Lie groups and canonical bases in quantum groups. It has since then developed rapidly in many directions, among which one can cite (for example) triangulated categories [BMR + 06], triangulations of surfaces [START_REF] Fomin | Cluster algebras and triangulated surfaces. I. Cluster complexes[END_REF] and Poisson geometry [START_REF] Michael Gekhtman | Cluster algebras and Poisson geometry[END_REF][START_REF] Michael Gekhtman | Cluster algebras and Poisson geometry[END_REF].

Because cluster algebras are commutative algebras endowed with more structure, it is natural to study them from the point of view of algebraic geometry. The geometric study of cluster algebras has nevertheless been mostly concentrated on aspects related to Poisson geometry or symplectic geometry. The appearance of the known cluster structure on coordinate rings of grassmannians in a physical context [ABC + 12] has raised recently the interest in the computation of integrals on the varieties associated with cluster algebras. The natural context for this is of course the cohomology ring.

The present article aims to study some varieties closely related to the spectrum of cluster algebras, and their cohomology rings. General cluster algebras are defined using a quiver or a skew-symmetric matrix. For our purposes, one needs as a starting point a presentation by generators and relations of the cluster algebras. This is available for cluster algebras with an acyclic quiver [START_REF] Berenstein | Cluster algebras. III. Upper bounds and double Bruhat cells[END_REF] and in a few other cases (see for example [START_REF] Muller | Locally acyclic cluster algebras[END_REF]). The choice has been made here to restrict to a still smaller class, namely cluster algebras with a quiver which is a tree, in the hope that the answers may be simpler in that case, and also because all finite Dynkin diagrams are trees.

Cluster algebras come with a subalgebra generated by so-called frozen (or coefficient) variables, which are invertible elements. This corresponds to a morphism from the spectrum of the cluster algebra to an algebraic torus. At the start of this work, our intention was to study both the fibers of this map and the spectrum in full. Later it turned out that it is possible (for cluster algebras associated with trees) to define more general varieties.

Cohomology and number of points on similar varieties have been considered in some previous works [START_REF] Michael Gekhtman | Cluster algebras and Weil-Petersson forms[END_REF][START_REF] Muller | The Weil-Petersson form on an acyclic cluster variety[END_REF][START_REF] Chapoton | On the number of points over finite fields on varieties related to cluster algebras[END_REF]. Some results of these articles will be recalled when necessary.

The article is organized as follows. In the first section, one recalls a canonical tri-coloring of the vertices of trees, originally defined in [START_REF] Coulomb | On vertex covers, matchings and random trees[END_REF][START_REF] Coulomb | Minimal vertex covers of random trees[END_REF][START_REF] Zito | The structure and maximum number of maximum independent sets in trees[END_REF] and not so well-known. This coloring is closely connected to matchings and independent sets in the trees. It will be used in an intensive way in the rest of the article, as it enters in the very definition of the varieties under study. One introduces the notion of red-green components of a tree, and defines an important integer invariant, the dimension of a tree.

The second section is devoted to the definition of the varieties. This is rather involved, and the definition itself only appears after a long preparation. One first considers a very general family of varieties, depending one many invertible parameters. By considering these varieties as objects in a groupoid, one can reduce this family to a much smaller one, with less parameters. One proves that every variety in the big family is isomorphic to a variety in the small family. One also introduces an explicit condition of genericity. Then everything is ready for the definition, which involves making an independent choice for every red-green component of the tree.

The third section is devoted to some geometric properties of these varieties. One proves by induction that all these varieties are smooth, by finding explicit coverings by products of varieties of the same type and algebraic tori. One next shows that some of these varieties are endowed with a free torus action, which turns them into principal torus bundles.

The fourth section turns to the study of the number of points over finite fields. One shows by induction that the number of points is a polynomial in the cardinality q of the finite field. This is done by finding an appropriate decomposition into pieces isomorphic to products of varieties of the same type and algebraic tori. One then gives formulas for some classical trees, including Dynkin diagrams. One also obtains (Prop. 4.16) a general decomposition as a disjoint union of products of tori and affine spaces (indexed by independent sets), which allows to compute the Euler characteristic.

The three next sections (5,6 and 7) deal with some computations regarding the cohomology rings. Section 5 is a very short reminder about known results about differential forms on varieties associated with cluster algebras, and about the general theory of (mixed) Hodge structure on the cohomology ring of algebraic varieties. Section 6 deals with some examples of trees, namely linear trees (the case of which forms a useful building stone) and some trees of shape H with no parameters. Section 7 is about varieties where parameters have been given a generic value. Our results about cohomology are rather partial, restricted to special cases, but there does not seem to be any simple general answer. The prominent missing case is in type A with an odd number of vertices, where one proposes a conjecture.

The appendix A presents a simple algorithm for the computation of the canonical coloring of trees. This algorithm is not needed in the rest of the article.

Let us finish this introduction by a few side remarks. Another interesting question which has not been considered here is the study of the real points of the same varieties, and their cohomology. This is probably also rather complicated, but certainly worth looking at.

There seems to be some kind of vague analogy between the counting-points polynomials considered here and the characteristic polynomials of bipartite Coxeter elements (cf [START_REF] Curtis | Coxeter groups, Salem numbers and the Hilbert metric[END_REF] and [START_REF] Stekolshchik | Notes on Coxeter transformations and the McKay correspondence[END_REF]), namely the general look and feel of these two families of polynomials are similar in various points (including some rela-tions to Pisot and Salem numbers).

At the end of section 1.2 of [START_REF] Dragoš | Spectra of graphs[END_REF], one can find some speculations about the idea of "quadratic spectra" for graphs, that would be an analog of the usual spectrum but related to quadratic equations instead of linear equations. Maybe one can argue that the cluster varieties considered here and their counting-point polynomials are a good candidate for such a quadratic spectrum (even if they involve polynomial relations of arbitrary degree).

This work has been supported by the ANR program CARMA (ANR-12-BS01-0017-02).

Combinatorics of trees

In this article, a tree is a finite connected and simply-connected graph. A leaf is a vertex with at most one neighbor. A forest is a disjoint union of trees.

Canonical red-orange-green coloring of trees

In this section, one recalls a canonical coloring of the vertices of all trees, using the colors red, orange and green. This coloring has first appeared in an article by J. Zito [START_REF] Zito | The structure and maximum number of maximum independent sets in trees[END_REF] and has been studied independently later by S. Coulomb and M. Bauer in [START_REF] Coulomb | Minimal vertex covers of random trees[END_REF][START_REF] Coulomb | On vertex covers, matchings and random trees[END_REF]. Let us consider a tree T . A vertex cover of T is a subset S of the vertices of T such that every edge of T has at least one end in S. A minimum vertex cover of T is a vertex cover of minimal cardinality among all vertex covers of T .

Let us use this notion to color the vertices of T according to the following rule: a vertex v is

• green if v is present in all minimum vertex covers,
• orange if v is present in some but not all minimum vertex covers,

• red if v is present in no minimum vertex covers.

The colors have been chosen to match this definition with traffic lights colors.

For the tree of figure 1, the minimum vertex covers are made of the two green vertices {4, 6} and one of the two orange vertices {1, 2}.

Remark 1.1 By taking the complementary subset, there is a bijection between minimum vertex covers, and sets of non-adjacent vertices of maximal cardinality (maximum independent sets, also called maximum stable sets).

This coloring is also related to maximum matchings of T . A matching of T is a set D of edges of T , such that every vertex belongs to at most one element of D. The elements of D will be called dominoes. A maximum matching is a matching of maximal cardinality among all matchings of T .

Then, a vertex v is

• green if v is present in all maximum matchings, in several different dominoes.

• orange if v is present in all maximum matchings, always in the same domino.

• red if v is absent in some maximum matchings.

The proof of the equivalence of these two descriptions of the coloring can be found in [START_REF] Coulomb | On vertex covers, matchings and random trees[END_REF].

For the tree of figure 1, the maximum matchings are made of three dominoes, one of them being the edge between the two orange vertices {1, 2}.

Proposition 1.2 The orange vertices are matched in pairs by the unique domino in which they are contained in any maximum matching. In maximum matchings, green vertices are matched with red vertices in several different ways.

Proof. This is proved in [START_REF] Coulomb | On vertex covers, matchings and random trees[END_REF].

This coloring has a third equivalent description, also given in [START_REF] Coulomb | On vertex covers, matchings and random trees[END_REF]. It is the unique coloring of the vertices such that

• the induced forest on orange vertices has a perfect matching,

• every green vertex has at least two red neighbors,

• every red vertex has only green neighbors.

It follows from this description that the coloring is stable by any of the following operations:

• taking the induced forest on orange vertices,

• taking the induced forest on the union of red and green vertices,

• removing a matched pair of orange vertices,

• removing a green vertex.

An algorithm to compute the coloring is presented in appendix A.

Further properties of the coloring

Let us first state a corollary of the third description of the coloring.

Lemma 1.3 A tree admits a perfect matching if and only if all vertices are orange.

Figure 2: A typical example

Proof. If all vertices are orange, there is a perfect matching by the first condition in the third description. If the tree has a perfect matching, letting all the vertices be orange gives a coloring which satisfies all the required conditions, and therefore is the correct one by uniqueness.

Note that the maximum matching is unique for these trees. We will call them orange trees. They are also known as perfect trees or matched trees [START_REF] Simion | Trees with 1-factors and oriented trees[END_REF].

Let T be a tree. The red-green components of T are the connected components of the graph defined by keeping only the edges of T with one red end and one green end. Every red-green component is a tree, which is moreover bipartite with only red leaves. In these trees, every green vertex has valency at least two. This kind of trees has been considered under the name of bc-trees in the study of blocks and cut-vertices of graphs, see for example [START_REF] Harary | Graph theory[END_REF]Chap. 4].

Even trees with no orange vertex can have several such components, because there can be edges with two green ends, and these edges are not kept in the red-green components.

By the third description of the coloring, the coloring is stable by taking a red-green component.

A tree which is equal to its only red-green component will be called a redgreen tree.

Lemma 1.4 The set of maximum matchings of a tree is in bijection with the product of the sets of maximum matchings of its red-green components.

Proof. The dominoes are fixed on the set of orange vertices, and cannot connect two distinct red-green components by proposition 1.2. Therefore, one can choose a maximum matching independently on every red-green component.

Let us denote by r(T ), o(T ) and g(T ) the number of red, orange and green vertices in the coloring of T . Let us call dimension of a tree T the quantity dim(T ) = r(T ) -g(T ).

(1)

Remark 1.5 The dimension of T is also the dimension of the kernel of the adjacency matrix of T , see [START_REF] Coulomb | On vertex covers, matchings and random trees[END_REF].

Lemma 1.6 The dimension of T is the number of vertices not covered by dominoes in any maximum matching.

Proof. By the precise description of maximum matchings given in proposition 1.2, the number of dominoes in a maximum matching is g(T ) + o(T )/2. The number of covered vertices is therefore 2g(T ) + o(T ). The statement follows.

Lemma 1.7 The dimension of T is the sum of the dimensions of the red-green components of T . Every red-green component has dimension at least 1.

Proof. The formula (1) for the dimension does not depend on orange vertices, and is clearly additive on red-green components.

Let T be a red-green tree. The Euler characteristic is given by

χ(T ) = 1 = r(T ) + g(T ) -e(T ),
where e(T ) is the number of edges of T . On the other hand, e(T ) ≥ 2g(T ), because every green vertex has at least two red neighbors.

Lemma 1.8 Let T be a red-green tree. Let F be the forest obtained by removing one red vertex of T . Then dim(F ) = dim(T ) -1.

Proof. Removing the vertex makes a big difference in the colorings of F and T . The coloring of F can be obtained from the restriction of the coloring of T by some avalanche of orange vertices, as follows.

At start, the restriction of the coloring of T gives a bad coloring of F , where some green vertices v may have exactly one red neighbor. If not, then the coloring is the canonical one. Otherwise, one can turn every such vertex v and its unique red neighbor into an orange domino. Doing that may create a certain number of green vertices with exactly one red neighbor. For each of them, replace it and its unique red neighbor by a domino. Repeat this as long as there is some green vertex with exactly one red neighbor. This must stop at some point, because we work in a finite union of trees. At the end of this avalanche of orange dominoes, one has obtained a canonical coloring of F . This construction implies that the dimension of F is the dimension of T minus 1, because it only involves turning pairs (green vertex, red vertex) into orange dominoes.

Lemma 1.9 Let T be a red-green tree and u -v be any edge of T . Let F be the forest induced from T by removing the vertices u and v. Then the dimension of T is the sum of the dimensions of the trees in F .

Proof. Assume that u is green and v is red. Let S 1 , . . . , S k be the trees in F attached to u and let T 1 , . . . , T ℓ be the trees in F attached to v.

Then the coloring of every S i is just obtained by restriction, because it still satisfies the third description of the canonical coloring.

On the other hand, let us denote by T j the tree obtained from T j by adding back the red vertex v. Then the coloring of every T j is just obtained by restriction, because it still satisfies the third description of the canonical coloring.

By the definition (1) of the dimension, one therefore finds that

dim(T ) = i dim(S i ) + j (dim( T j ) -1).
By lemma 1.8, this is equal to the expected result.

Lemma 1.10 Let T be a tree. Let u -v be a red-green edge of T . There exists a maximum matching of T containing u -v.

Proof. One can assume that T is a red-green component, as maximum matchings of different red-green components are independent.

One can take maximum matchings of the connected components of the forest F induced from T by removing u and v. From lemma 1.9 and lemma 1.6, the number of vertices not covered on F is the dimension of T . Therefore, adding the domino u -v gives a maximum matching of T .

Lemma 1.11 Let T be a red-green tree and let v be a leaf of T . There exists a maximum matching of T where the vertices which are not covered are leaves. Moreover, unless T is reduced to the single vertex v, one can find such a matching where v is in a domino.

Proof. By induction on the size of the tree T . This is true for the tree with 1 vertex.

Let us call u the green neighbor of the red leaf v. The induced forest F defined as T \ {u, v} is made of red-green trees, whose sum of dimensions is the dimension of T by lemma 1.9. By induction, one can find a maximum matching of F such that vertices which are not covered are leaves of F . Moreover, one can choose this matching such that the vertices which are not covered are in fact leaves of T .

One then obtains by adding the domino u -v a maximum matching of T with all the required properties.

Lemma 1.12 Let T be a tree and let v be a red vertex of T . There exists a maximum matching of T not containing v.

Proof. Otherwise, one would get a contradiction with the characterization of the canonical coloring.

Lemma 1.13 The trees obtained by removing a leaf in an orange tree are exactly the trees of dimension 1. They have exactly one red-green component.

Proof. Let us pick an orange tree T and a leaf v with adjacent vertex w. Removing the leaf v gives a tree T \ {v} with a matching covering all vertices but w. This is clearly a maximum matching, hence T \ {v} has dimension 1 by lemma 1.6.

Conversely, consider a tree T ′ of dimension 1. It has exactly one red-green component, as every red-green component contributes at least 1 to the dimension by lemma 1.7. This red-green component has dimension 1. By lemma 1.11, one can find a maximum matching of T ′ missing only one leaf w. Adding a vertex v attached to w gives a tree with a perfect matching, i.e. an orange tree.

We will call the trees of dimension 1 unimodal trees.

Remark 1.14 The classical Dynkin diagrams are simple examples of trees:

• Type A n : orange for even n, unimodal for odd n,

• Type D n : unimodal for odd n,

• Type E n : orange for n = 6, 8, unimodal for n = 7.

The type D n with n even has dimension 2.

Affine algebraic varieties

Using the coloring of the previous section, one can define several affine algebraic varieties attached to a tree T and some auxiliary choices. These varieties are closely related to cluster algebras.

First, let us consider the system of equations

x i x ′ i = 1 + α i i-j x j (2)
for all vertices i of T , where the product runs over vertices j adjacent to i. Here x i and x ′ i are called cluster variables, and α i are called coefficient variables. By a special case of [BFZ05, Corollary 1.17], this system is a presentation of the cluster algebra associated with the quiver given by a bipartite orientation of T , with one frozen vertex attached to every vertex of T (in such a way that all vertices of T remain sources or sinks). In the context of cluster algebras, the equations (2) are called exchange relations.

We will be interested here in considering the α i as parameters, and letting them either vary in some well-chosen families or take fixed generic values (and even a mix of these two possibilities), so that the resulting space is smooth.

Jumping around a groupoid

Let us denote by X T (α) the algebraic scheme defined by fixing some invertible values for all coefficient variables α i .

Recall the following lemma ([Cha11, Lemma 2.2]).

Lemma 2.1 Let u -v be an edge of T . Let β be defined by

β w = α w /α u if w is a neighbor of v (in particular β u = 1) and β w = α w otherwise. Then X T (α) and X T (β) are isomorphic, by the change of variables x v = α u x v and x ′ v = x ′ v /α u .
One may say that the coefficient α u has jumped away from u over v and its inverse has got spread over all other neighbors of v. When v has u as only neighbor, the coefficient α u just disappears from the equations.

From now on, we will only admit the following kinds of jumps:

• a red vertex over one of its green neighbors,

• a green vertex over one of its red neighbors,

• an orange vertex over its matched orange neighbor.

Let us now define a groupoid G T with objects the schemes X T (α) indexed by invertible values of the parameters α, and isomorphisms

X T (α) ≃ X T (ᾱ) of the shape xi → λ i x i , x′ i → x ′ i /λ i , (3)
where λ i are some invertible elements. The parameters are then related by

α i = ᾱi i-j λ j . (4)
Note that every jump corresponds to an isomorphism in the groupoid G T .

Proposition 2.2 For every maximum matching M and given parameters α, there exists unique parameters β (given by monic Laurent monomials in α) such that

• the function β is 1 except on the set of red vertices not covered by M .

• X T (α) is isomorphic to X T (β)
u → w in G if u -v is a domino in M and v -w is another edge in T .
With this notation, if there are edges starting from u in G, one can use lemma 2.1 (by jumping over v) to turn the coefficient β u into 1 and replace the coefficients β w by β w /β u , for all vertices at the end of an arrow u → w.

One can see that the graph G has no oriented cycle, otherwise there would be a cycle in T made of concatenated dominoes. Moreover, edges in the graph G can only go from green to green, from orange to orange or green, or start from red.

Then one can do these jumps starting from the sources in G and then proceeding along any linear extension of the partial order defined by G.

At the end of this process, all vertices covered by dominoes have coefficient 1. There only remains coefficients on the red vertices not covered by the maximum matching M . This proves the existence of the required parameters β.

The fact that the coefficients β j are products of coefficients α i and their inverses is immediate from the definition of jumping.

Let us now prove uniqueness. Assume there are two such sets of parameters β and β. Let x and x be the coordinates on the isomorphic X T (β) and X T ( β).

Let us first prove that any isomorphism in the groupoid G T from X T (β) to X T ( β) maps xj to x j for every green vertex j. This is done by induction using the auxiliary graph G, starting with the green vertices that do not have any outgoing edge in G. For every green vertex, one just has to consider the equation (2) for the unique red vertex that is in the same domino in M .

Using then the equation (2) for all red vertices i not covered by M , one obtains that β i = βi . This proves uniqueness.

For the statement (a), consider what happens to the coefficient attached to an orange or a green vertex u. By proposition 1.2, the domino containing u must be orange or green-red. The coefficient can therefore only jump to green or orange vertices. So they must disappear at some point, because only red vertices bear coefficients at the end of the process.

Similarly for the statement (b), consider the coefficient attached to a red vertex u. Again by proposition 1.2, the domino containing u must be red-green. The coefficient can only jump to red vertices in the same red-green component, or to orange and green vertices. As the coefficients on orange or green vertices will disappear by the previous point, coefficients can only stay within a given red-green component.

Recall that the dimension dim(T ) of T is (by lemma 1.6) the number of red vertices that are not covered in any maximum matching of T . Proposition 2.2 justifies this terminology, as this gives the number of independent parameters for the varieties X T (α) (inside the groupoid G T ).

Remark 2.3 In the particular case when the tree T is orange, all X T (α) are isomorphic.

By proposition 2.2, in order to study all isomorphism classes of such varieties, one can restrict oneself to attach parameters only to red vertices not covered by a maximum matching M .

For a maximum matching M of T , let us define a scheme X M T (α) by the set of equations (2), where α i are invertible fixed parameters, equal to 1 if i is covered by M .

Given two matchings M and M ′ , one can always find by Proposition 2.2 a sequence of jumps that provides an isomorphism in G T between X M T (α) and X M ′ T (β), where the parameters β are uniquely determined Laurent monomials in α.

Let us consider now the automorphism group Aut(X M T (α)) of the object

X M T (α) in the groupoid G T . Proposition 2.4 The automorphism group Aut(X M T (α)) is an algebraic torus isomorphic to G dim(T ) m . If (λ i ) i∈T is an element of Aut(X M T (α))
, then λ i = 1 on green and orange vertices of T .

Proof. Let us consider an automorphism in G T given by invertible elements λ i .

The condition that the equation (2) for the vertex i is preserved is

j-i λ j = 1. ( 5
)
This just means that the λ i belongs to the kernel of the adjacency matrix of T (seen as an endomorphism of G T m ). Looking at the induced linear equations on the tangent space at one, one can deduce from remark 1.5 that the dimension of Aut(X M T (α)) is dim(T ). By the same argument (using induction on the auxiliary graph G) as in the uniqueness step of the proof of Prop. 2.2, every automorphism fixes x j for every green vertex j.

By a similar argument (starting with orange vertices attached to green vertices in the auxiliary graph G), one can then prove that every automorphism fixes x j for every orange vertex j.

There remains to show that Aut(X M T (α)) is connected. Let us prove that, given any choice for the values of λ i for i ∈ M , there is a unique element of Aut(X M T (α)) extending this choice. This is once again done by induction using the auxiliary graph G. Let us consider a red vertex j that is pointing in G only toward vertices with known λ. Then there is a unique way to fix the value λ j such that (5) holds for the green vertex i in the domino of j.

This proves that the kernel is isomorphic to

G dim(T ) m .
Note that the torus Aut(X M T (α)) and its action on X M T (α) do not depend on α. This action therefore extends to varieties defined as the union of X M T (α) over some family of parameters α.

The torus Aut(X M T (α)) can be written as a product of several tori, indexed by the red-green components. Every factor acts only on the red vertices inside a fixed red-green component. This factorization will be useful later to describe free actions on some varieties.

Genericity

A non-empty set S of red vertices in a red-green component C is called an admissible set if every green vertex in C has either 0 or 2 neighbors in S.

Lemma 2.5 Given a red vertex u in C, there is an admissible set containing u.

Proof. One can build an admissible set S starting from {u} by repeated addition of red vertices. If there is a green vertex v with exactly one red neighbor in S, then add to S one of the other red neighbors of v. Repeat until the set S is admissible.

Let us now introduce an explicit genericity condition on the parameters attached to a given red-green component C.

For every admissible set S of red vertices of C, the alternating product

i∈S α ± i = (-1) #S , (6)
where any two red vertices sharing a common green neighbor have opposite powers in the left hand side.

Lemma 2.6 The genericity condition is preserved under jumping moves.

Proof. Indeed, consider the jumping move from a red vertex u over a green vertex v. The coefficients of all red neighbors of v are divided by α u . Let S be an admissible set. If the vertex v has no neighbor in S, nothing is changed in the genericity condition for S. Otherwise, the vertex v has two neighbors in S.

Then two terms are changed in the left-hand side of (6), both being divided by α u . But they appear with opposite powers, hence the product is not changed.

The two other kinds of jumping moves (green over red and orange over orange) do not change the parameters of red vertices.

Definition of the varieties

Let us now carefully define the varieties that will be studied in the rest of the article.

Let us fix a tree T , a choice function ϕ from the set of red-green components of T to the set {generic, versal} and a maximum matching M of T .

For every red-green component C such that ϕ(C) is generic, let us fix for every vertex u of C not covered by the maximum matching M , an invertible value α u .

To this data, one associates a scheme X ϕ,M T,α as follows. The variables are

• x i and x ′
i for all vertices of T , • α i for all vertices not covered by the matching M in the red-green components C of T such that ϕ(C) is versal.

The equations are

• the system of equations (2),

• all variables α i are invertible.

In fact, there is no true dependency on the matching M . Let us consider two maximum matchings M and M ′ . Using proposition 2.2, one can find an isomorphism between X ϕ,M T,α for arbitrary invertible parameters α and X ϕ,M ′ T,β for parameters β depending on the parameters α.

One will therefore forget the matching and use the notation X ϕ T from now on, keeping the parameters α implicit as well.

Moreover, by lemma 2.6, if the genericity condition (6) holds for the parameters α with respect to one matching M , they will also hold for the corresponding parameters β for another matching M ′ .

One can therefore impose that the genericity condition (6) holds for all generic red-green components of T . This will always be assumed from now on.

Let us summarize this lengthy definition. Once the tree T is chosen, one picks a maximum matching M of T . Any choice of matching will lead to isomorphic varieties. One then decides for every red-green component of T either to take the union over all invertible parameters or to fix some generic parameters.

One will use the simplified notation X T for orange trees, as there is then no choice to be made for the function ϕ. One will also use the notations X generic T and X versal T when the function ϕ is constant.

Remark 2.7 One can as well consider forests instead of trees in the definition of the varieties X ϕ T , but then everything factors according to the connected components. This possibility will be used implicitly in the rest of the article. Proof. This follows from the exchange relation

x a x ′ a = 1 + α a x b y,
where y is some product of other cluster variables.

Remark 2.9 When removing red vertices or green vertices in a tree T , some red-green components may split into several red-green components. One can then define a function ϕ on the new set of red-green components, whose value on a red green component C is the value of ϕ in the unique red-green component of T containing C. Abusing notation, one will denote this induced function ϕ simply by ϕ.

3 Smoothness and free actions Theorem 3.1 For every choice of ϕ, the variety X ϕ T is smooth.

Proof. The proof is by induction on the size of the tree T . For the tree with only one vertex, the only equation is

xx ′ = 1 + α. (7)
In the generic case when α is considered to have a fixed value, different from -1 by the genericity condition (6), the variety is isomorphic to the punctured affine line G m and is therefore smooth.

In the versal case when α is considered to be a variable and assumed to be invertible, the variety is an open set in the variety defined by (7) where α is not assumed to be invertible. This last variety is isomorphic to the affine plane A 2 , hence smooth.

The rest of the proof by induction is organized as follows. One first considers the case when the tree has at least one red-green component, and treat separately the case when there is a red-green component which is generic and the case when there is one which is versal. Otherwise, the tree is orange. These three cases are done in the next three subsections.

Let us first state a few useful lemmas. Lemma 3.2 If one variable x i is assumed to be non-zero, then one can get rid of the associated variable x ′ i and of the equation (2) of index i.

Proof. Indeed, one can just use the equation to eliminate x ′ i .

Lemma 3.3 If one variable x i is assumed to be zero, then x ′ i becomes a free variable and the equation (2) of index i reduces to

-1 = α i i-j x j .
Let us now introduce a useful variant of the varieties X ϕ T . Let v be a vertex of T . Let X ϕ T [v] be defined just as X ϕ T , but with one more invertible variable γ v attached to the vertex v as a coefficient (playing the same role as α v in the equations). This variable defines a morphism

γ v from X ϕ T [v] to G m . Lemma 3.4 If v is an orange or green vertex, then X ϕ T [v] is isomorphic as a variety over G m to X ϕ
T × G m endowed with the projection to the second factor.

Proof. By proposition 2.2 and its proof, one can find an isomorphism in the groupoid G T between X ϕ T and X ϕ T [v] that only changes the coordinates x i for orange and green vertices. More precisely, using the auxiliary oriented graph G, one can find a sequence of jumps (corresponding to edges in G starting with a green or orange vertex) that makes the coefficient γ v disappear from the equations.

The isomorphism associated with this sequence of jumps is multiplying the variables x i by monic Laurent monomials in the parameter γ v , hence defines an isomorphism over G m .

Lemma 3.5 If v is a red vertex in a versal red-green component C, then X ϕ T [v] is isomorphic as a variety over G m to X ϕ
T × G m endowed with the projection to the second factor.

Proof. If the red vertex v is not covered by the matching M chosen to define X ϕ T , then one has two coefficient variables α v and γ v attached to the vertex v. By the simple change of coordinates α v := α v γ v and γ v := γ v , one gets the expected isomorphism.

Assume now that that red vertex v is covered by the matching M . By proposition 2.2 and its proof, one can find an isomorphism in the groupoid G T between X ϕ T [v] and a variety X ϕ,M T,β that only changes the coordinates x i for orange and green vertices and for red vertices in the red-green component C. More precisely, using the auxiliary oriented graph G, one can find a sequence of jumps that moves the coefficient γ v towards the red vertices in C not covered by the matching. At the end, every new coefficient β i is the product of α i by a Laurent monomial in γ v .

The isomorphism associated with this sequence of jumps is multiplying the variables x i by monic Laurent monomials in the parameter γ v , hence defines an isomorphism over G m . One can then compose this isomorphism with a relabeling of the coefficients α i := β i in order to get the expected isomorphism, still defined over G m , between

X ϕ T [v] and X ϕ T × G m .
One could say that the coefficient γ v can be detached from T in these cases. This will be used frequently in the rest of the article.

Trees with a generic component

One assumes now that T has at least two vertices and a generic component C.

Let us pick an admissible set S of red vertices in C, as defined in §2.2.

Lemma 3.6

The open sets U (x i ) for i ∈ S form a covering of X ϕ T .

Proof. Indeed, the complement of their union is the set where all variables x i for i ∈ S vanish. This implies that

α i j-i x j = -1 (8)
for every i in S. Taking the alternating product of these equalities gives

i∈S α ± i = (-1) #S , (9)
because for every green vertex j attached by an edge to some element of S, the cluster variable x j appears exactly twice by definition of admissible sets, hence disappears in the alternating product. But the equation ( 9) is incompatible with the genericity condition (6).

Let us now show that the open sets U (x i ) are smooth.

Let F be the forest T \ {i}. In the forest F , the coloring is changed only on the red-green component containing i, where an avalanche of orange dominoes can take place when removing i. The red-green component C is therefore split into a number of red-green components. Let us moreover introduce a function ϕ on F , which is generic on every red-green component coming from C, and unchanged on all other red-green components.

Lemma 3.7 The open set U (x i ) is isomorphic to G m × X ϕ F .
Proof. The condition that x i is not zero allows one to get rid of the variable x ′ i by using the equation (2) of index i. What remains are the equations for the forest F = T \ {i}, where now x i is treated as a parameter attached to all neighbors of i in T .

Because all neighbors of i in T are green, they become either green or orange in F . It follows from lemma 3.4 that one can, without changing the variety, consider instead that the parameter x i is not attached to any vertex of F .

Let us check that the genericity condition still holds on all generic red-green components. If the component D does not come from the splitting of C, then the genericity conditions are unchanged on this red-green component. Otherwise, let us choose an admissible set in D. It was then already an admissible set in C, by inspection of what happens during the avalanche of orange dominoes. Therefore the genericity condition for D is inherited from that for C.

One has therefore obtained an isomorphism

U (x i ) ≃ G m × X ϕ F , (10)
which is smooth by induction. Therefore X ϕ T is also smooth.

Trees with a versal component

One assumes now that T has at least two vertices, and has a versal component C. Let us choose a red leaf v in this component. By proposition 1.12, one can find a maximum matching M not containing v. Therefore there is a coefficient variable α v . Let u be the green vertex adjacent to v. By lemma 2.8, the two open sets U (x u ) and U (x v ) cover X ϕ T . Let us first prove that U (x v ) is smooth. Let T ′ be the tree T \ {v}. The coloring of T ′ is obtained from T by an avalanche of orange dominoes. The dimension of T ′ is dim(T ) -1.

The avalanche may split the red-green component of T containing v into several components. Let ϕ be the function which maps all these new components to the versal condition, and unchanged condition on all the other red-green components.

Lemma 3.8 The open set U (x v ) is isomorphic to G 2 m × X ϕ T ′ .
Proof. Assuming that x v is not zero allows one to get rid of the variable x ′ v by using (2) with index v. The coefficient variable α v also disappears from the equations: this gives one factor G m . Then the variable x v is seen as a coefficient attached to the vertex u in T ′ , which is either green or orange. The coefficient can therefore be detached by lemma 3.4, and one obtains a factor isomorphic to G m × X ϕ T ′ .

Therefore U (x v ) is smooth by induction.

Let us now prove that U (x u ) is smooth. Let us choose instead a matching M containing the domino u-v, thanks to lemma 1.11. This amounts to go through an isomorphism in the groupoid G T , hence preserves the open set U (x u ).

Let F be the forest T \ {u}. Because u is green, the coloring of F is obtained from that of T by restriction and the dimension of F is dim(T ) + 1. Let v, T 1 , . . . , T k be the connected components of the forest F . By removing the domino u -v, one can restrict the matching M to a matching of the forest F .

The red-green component of T containing u splits into several red-green components in F , one of them being the vertex v. One takes the versal condition on all of these red-green components of F , and unchanged condition on all the other red-green components.

Lemma 3.9

The open set U (x u ) is isomorphic to

X versal {v} × k j=1 X ϕ Tj , (11)
where the first component is the vertex v with coefficient variable x u .

Proof. Setting x u = 0 in the equations allows to get rid of the variable x ′ u . The result can be described as a fiber product over G m , where the same coefficient variable x u is attached to every connected component of F at a red vertex in a versal red-green component. By repeated use of lemma 3.5 on all connected components (but not on the isolated vertex v), one finds that the open set U (x u ) is isomorphic to the product

X versal v × k j=1 X ϕ Tj , (12)
where the first component is the vertex v with coefficient x u .

Therefore U (X u ) is smooth by induction, and hence X ϕ T is also smooth.

Orange trees

Let us now assume that T is an orange tree and let us choose one domino u -v in the perfect matching of T . By lemma 2.8, the two open sets U (x u ) and U (x v ) cover the variety X T . By symmetry between u and v, it is enough to prove that U (x u ) is smooth.

Let T 1 , . . . , T k be the trees attached to u in T \{v}. The T i are clearly orange trees.

Let R be the connected component of v in T \{u}. The tree R is obtained by removing a leaf in an orange tree, hence (by lemma 1.13) has dimension 1 and a unique red-green component. Moreover, R has a maximum matching avoiding only v and the vertex v is red in the coloring of R.

Lemma 3.10

The open set U (x u ) is isomorphic to the product of the varieties X Ti and the variety X versal R .

Proof. Assuming that x u is not zero allows to eliminate the variable x ′ u and the equation (2) of index u.

There remains the equations for the union of R and the T i , with x u considered as a parameter attached to all of them at the former neighbors of u.

Because the trees T i are orange, one can consider instead (by lemma 3.4) that the parameter x u is only attached to the vertex v of R.

This proves that the open set U (x u ) is isomorphic to the product of the varieties X Ti and the variety X versal R . By induction, this proves that U (x u ) is smooth. Therefore X T is smooth too.

Torus actions

Let T be a tree and let ϕ be a choice in {generic, versal} for every red-green component of T . Let us also choose a maximum matching M of T .

One can deduce from proposition 2.4 and the remarks following it that there is an action of an algebraic torus of dimension dim(T ) on X ϕ T , and that this torus (and its action) can be written as a product over red-green components C of tori Λ C T . Let us define a smaller torus Λ ϕ T acting on X ϕ T as the product of Λ C T over all generic red-green components of T . Let us call the rank of (T, ϕ) and denote by rk(T, ϕ) the sum of the dimensions of the generic red-green components of T . This is the dimension of Λ ϕ T .

Proposition 3.11 If ϕ(C) is generic, the action of Λ C T on X ϕ T is free.

Proof. Let us assume that there is a non-trivial element λ = (λ i ) i of Λ C T that fixes a point (x i ) i in X ϕ T . Let i be a red vertex in C such that λ i = 1. For every green neighbor j of i, one can find another red vertex k incident to j such that λ k = 1, because of (5). Iterating this process, one can build an admissible set S (as defined in §2.2), such that λ s = 1 for every s ∈ S.

Because λ fixes the given point, one then has x s = 0 for every s ∈ S. But this is impossible by Lemma 3.6. Corollary 3.12 There is on X ϕ T a free action by a torus Λ ϕ T of dimension the rank rk(T, ϕ).

This gives X ϕ

T the structure of a principal bundle with structure group Λ ϕ T . As one will see later, this bundle is not trivial in general (i.e. not a product), as can be seen from our results for the cohomology already in type A 3 .

Number of points over finite fields and Euler characteristic

Let us denote by N ϕ T (q) the number of points on X ϕ T over the finite field F q . When the tree is orange, one will use the shorthand notation N T . When the function ϕ is constant, one will use the notations N versal T and N generic T . Proposition 4.1 The numbers N ϕ T (q) are monic polynomials in q of degree dim X ϕ T .

Proof. The proof is by induction on the size of the tree.

For the tree with one vertex, the number of points is q -1 in the generic case and q 2 -q + 1 in the versal case, by the description given at the beginning of the proof of theorem 3.1.

Then either the tree has a red-green component, which can be generic or versal, or it is an orange tree. The proof is decomposed into the three following geometric decomposition lemmas, or rather into their obvious corollaries on the number of points over finite fields.

Let T be a tree and v be a red leaf in a red-green component C of T . Let u be the neighbor of v. Removing the vertex v creates an orange avalanche and may separate the red-green component C into several ones. Let ϕ be the induced genericity condition (as defined in Remark 2.9). Let F be the forest T \ {u, v}. The component C may also split into several red-green components in F . Let ϕ be the induced genericity condition.

Let us consider now the case of a generic red-green component C. Lemma 4.2 In this situation, the variety X ϕ T can be decomposed as

X ϕ T = G m X ϕ T \{v} ⊔ A 1 X ϕ F . ( 13
)
Proof. Either x v is not zero or x v is zero. This will give the required disjoint union. In the case where x v = 0, one uses lemma 3.7. This gives the first term of the right hand side.

Let us pick a maximum matching M of T containing v. This is possible by lemma 1.11. This does not change the open set U (x v ) and its complement, up to isomorphism.

Assume now that x v is zero. Then x ′ v is a free variable, and x u is equal to -1, because there are no coefficients on v. One then gets rid of x ′ u . The coloring of the forest F is by restriction of the coloring of T . Therefore the parameter x u = -1 is attached to some red vertices of F , as a coefficient.

One has to check that the genericity condition still holds on every connected component of F . Let S be an admissible set in one of these components. Either S was already an admissible set in T , and then the genericity condition still holds, or it contains exactly one of the neighbors of u in T . In this case, one can extend S by adding v to form an admissible set in T . The genericity condition for S ⊔ {v} in T implies the condition for S, because of the additional -1 coefficient attached to S in F .

Keeping the same notations, let us consider now the case of a versal red-green component C.

Lemma 4.3 In this situation, the variety X ϕ

T can be decomposed as

X ϕ T = G 2 m X ϕ T \{v} ⊔ A 1 X ϕ F . (14)
Proof. Either x v is not zero or x v is zero. This will give the required disjoint union. If x v = 0, using lemma 3.8 gives the first term of the right hand side.

Let us pick a maximum matching M of T containing v. This is possible by lemma 1.11. This does not change the open set U (x v ) and its complement, up to isomorphism.

Assume now that x v is zero. Then x ′ v is a free variable, and x u is equal to -1, because there are no coefficients on v. One then gets rid of x ′ u . The coloring of the forest F is by restriction of the coloring of T . Therefore the parameter x u = -1 is attached to red vertices of F . By lemma 3.5, it can be detached, and this just gives the expected second term.

Let T be an orange tree and u -v be a domino in T . Let (T u,i ) i (resp. (T v,j ) j ) be the connected components of T \ {u, v} that were attached to u (resp. to v). All these trees are orange. Let us denote by S u,i and S v,j the forests obtained from them by removing the vertex that was linked to u or v. These forests are unimodal, in the sense that they have one unimodal connected component, all the other connected components being orange.

Lemma 4.4 In this situation, one has

X T = G 2 m i X Tu,i j X Tv,j ⊔ A 1 i X versal Su,i j X Tv,j ⊔ A 1 i X Tu,i j X versal Sv,j .
Proof. Because the open sets U (x u ) and U (x v ) are a covering by lemma 2.8, one can cut the variety X T into three pieces: either both x u and x v are not zero, or exactly one of them is zero.

If both are not zero, then one obtains the product of G 2 m (with coordinates x u and x v ) with the product of the varieties attached to the T u,i and the T v,j . Indeed, one first get that x u becomes a parameter attached to all trees T u,i and x v becomes a parameter attached to all trees T v,j . But these trees are orange, so x u and x v can be detached by lemma 3.4. This gives the first term.

If x u is zero and x v is not zero, then there is a free variable x ′ u and the variable x v is determined by the variables attached to the vertices of the trees T u,i linked to u, which must be non-zero. One obtains therefore a versal condition on each forest S u,i . For the trees T v,j , the coefficient x v is attached to all of them, but because they are orange it can be detached. This gives the second term.

The third term is the same after exchanging u and v.

Reciprocal property

Recall from §3.4 that the rank rk(T, ϕ) of the pair (T, ϕ) formed by a tree T and a choice function ϕ is the sum of the dimensions of the generic red-green components of T .

Proposition 4.5 The polynomial N ϕ T (q) is divisible par (q -1) rk(T,ϕ) .

Proof. This follows from the existence of the free action obtained in corollary 3.12.

Let us refine this slightly.

Proposition 4.6 The polynomial N ϕ T can be written as (q -1) rk(T,ϕ) times a reciprocal polynomial.

Proof. By induction. This is true for the tree with one vertex.

One just has to look carefully at the decompositions given in the three lemmas that were used to prove polynomiality by induction.

For lemma 4.2, let D be the rank for T . Then the rank is D -1 for T \ {v} and D for F . Using the additional factor q -1 coming from G m , there is a common factor (q -1) D to all terms involved. The factor A 1 in the codimension 1 piece ensures that the reciprocal property holds.

For lemma 4.3, the rank D is the same in all terms involved. One uses that (q -1) 2 is reciprocal. The factor A 1 in the codimension 1 piece ensures that the reciprocal property holds.

For lemma 4.4, the rank D is 0 in all terms involved, as there is no generic red-green component. One uses again that (q -1) 2 is reciprocal. The factor A 1 in the codimension 1 pieces ensures that the reciprocal property holds.

Enumeration and coincidences

In the following remarks, one will describe trees by their numbers in the tables at the end of [START_REF] Dragoš | Spectra of graphs[END_REF] and by their graph6 string (which is a standard format for graphs).

Remark 4.7 One can find distinct orange trees with the same enumerating polynomial. This happens first for trees with 8 vertices. The trees 2.188 (graph6 'IhGGOC@?G') and 2.189 (graph6 'IhC_GCA?G') have the same polynomial, as One can check that D n is unimodal if n is odd and has dimension 2 if n is even.

Proposition 4.11 The number of points on varieties attached to D n is given by

N versal Dn = q n+3 -q n+2 + q n + q 3 -q + 1 q + 1 and N generic Dn = (q n/2 -1) 2 (17)
if n is even and by

N versal Dn = q n+3 -q n+2 + q n -q 3 + q -1 q 2 -1 and N generic Dn = q n -1 (18)
if n is odd.

Proof. This is easily deduced from the type A case, using 4.2, 4.3 applied to a red leaf on a short branch.

Trees of type E

Let us consider now a family of trees containing the Dynkin diagrams of type E. The tree E n is the tree with one triple point and branches of size 1, 2 and n -4. One can check that E n is orange if n is even and unimodal if n is odd.

Proposition 4.12 The number of points on varieties attached to E n is given by

N En = (q 2 -q + 1) q n-1 -1 q -1 ( 19
)
if n is even and by N versal En = (q 2 -q + 1)(1 + q n-1 ) and

N generic En = q n+1 -q n + q n-1 -q (n+3)/2 -q (n-1)/2 + q 2 -q + 1 q -1 ( 20
)
if n is odd.

Proof. In the even case, one uses lemma 4.4 applied to the domino on the short branch, and the known type A cases. In the odd case, one uses lemmas 4.3 and 4.2 applied to the red leaf on the short branch, and the known type A cases.

Orange trees and unimodal trees

Let us now describe a recursion involving only the polynomials for orange trees and versal unimodal trees.

Let T be an orange tree and v be a leaf of T . Let T ′ be the unimodal tree T \ {v} and let F be the orange forest obtained from T by removing the domino u -v containing v. Lemma 4.13 There is a decomposition

X T = X versal T ′ ⊔ A 1 X F . (21)
Proof. This decomposition is made according to the value of x v . If x v = 0, then one has a free parameter x ′ v , which gives the factor A 1 . One also has x u = -1 and one can get rid of x ′ u . The value -1 is attached as a coefficient to some orange vertices of F , but one can detach this coefficient by lemma 3.4. There remains the equations for X F .

If x v = 0, one can use lemma 3.10. In the special case of a leaf, this gives an isomorphism with X versal T ′ . One can use lemma 4.13 to compute the enumerating polynomials for orange trees and versal unimodal trees only, by the following algorithm.

Step 0: if the tree T is of type A n with n even, use the known value from (15) in proposition 4.10.

Step 1: if the tree T is orange, find a leaf v whose branch has minimal length. Here the branch is the longest sequence of vertices of valency 2 starting at the unique neighbor of the leaf (it could be empty). Then use lemma 4.13 applied to the leaf v to compute N T .

Step 2: if the tree T is unimodal, find a red leaf w whose branch has maximal length. Adding a vertex v at the end of this branch gives an orange tree T ′ . Then use lemma 4.13 (backwards) applied to the tree T ′ and its leaf v to compute N T .

This will work because each step either shorten the shortest branch or add some vertex to the longest branch. This makes sure that the tree become more and more linear, and that at some point one is reduced to the initial step. This is a decreasing induction on the number of points of valency at least 3 and the length of the longest branch.

Remark 4.14 For orange trees, one can use instead in this algorithm the lemma 4.4, maybe choosing a domino close to the center of the tree for a better complexity.

Euler characteristic and independent sets

Let us denote by vc(T ) the number of minimum vertex covers of T . This is also the number of maximum independent sets.

Let us now describe a decomposition of the versal varieties according to independent sets (not necessarily maximal).

If S is a subset of the vertices of T , one can define W T (S) as the set of points in X versal T where

x u = 0 if u ∈ S, (22)
x u = 0 if u ∈ S. (23) 24
The sets W T (S) are obviously disjoint in X versal T .

Lemma 4.15 If the set W T (S) is not empty, then S is an independent set in T .

Proof. This follows from lemma 2.8.

Proposition 4.16 Let S be an independent set in T . There is an isomorphism

W T (S) ≃ (G m ) t+dim(T )-2s × (A 1 ) s ,
where t is the size of T and s the size of S.

Proof. Let us fix a maximum matching M of T . For every u not in S, one can use the hypothesis x u = 0 to get rid of x ′ u and of the equation of index u. There remains only the equations of index v for v ∈ S. Because x v = 0 when v ∈ S, the variables x ′ v for v ∈ S do no longer appear in the equations, hence they are free. This gives the factor (A 1 ) s .

Then there remains s equations of the general shape

-1 = α i j-i x j , (E i )
involving the t -s invertible variables x u and the dim(T ) coefficient variables α i . The factor α i is present in this equation only if the vertex i is not covered by the chosen maximum matching M . One will use the following auxiliary graph T . The vertices are the vertices of T and new vertices Z i indexed by coefficient variables α i for i ∈ M . The edges of T are edges of T and new edges between the vertex Z i and the vertex i for every i ∈ M . Clearly, this graph is still a tree and admits a perfect matching M , by adding dominoes i -Z i to the matching M .

Because S is an independent set in T , there is at most one element of S in every edge of T . Let us orient every edge containing an element of S towards this element if the edge is a domino and in the other way otherwise. This defines a partial order on the vertices of T , decreasing along the chosen orientation of edges.

Consider now the equation E i associated with a vertex i ∈ S. There is a unique domino i-j in T containing i. The equation can then be used to express the variable x j in terms of variables of lower index in the partial order.

One can therefore eliminate one variable for every equation. At the end, one obtains an algebraic torus whose dimension is the difference between the number t -s + dim(T ) of initial variables and the number s of equations.

Corollary 4.17 The Euler characteristic of X versal T is vc(T ).

Proof. Every set W T (S) contributes either 0 or 1 to the Euler characteristic. It contributes by 1 if and only if the exponent t + dim(T ) -2s is zero.

This exponent can be expressed as (r(T ) + o(T ) + g(T )) + (r(T ) -g(T )) -2s.

It is therefore zero if and only if s = r(T ) + o(T )/2, which is the size of the maximum independent sets in T .

Of course, one can also use Proposition 4.16 to give a formula for the number of points N versal T as a sum over independent sets. Corollary 4.18 The value at q = 1 of the polynomial N versal T is the number vc(T ) of maximum independent sets of T .

Cohomology: general setting and results

This section first describes some differential forms that are always present in the varieties under study, and then very briefly recalls the results one needs about (mixed) Hodge structures. For a general reference about mixed Hodge structures, see for example [START_REF] Chris | Mixed Hodge structures[END_REF].

Weil-Petersson two-form

Let T be a tree and let S be a subset of T . Consider the augmented tree T + S obtained by adding a new edge out of every vertex in S, and endow this tree with a bipartite orientation, where every vertex is either a sink or a source.

As a variant of the definition of the variety X ϕ T , one can define a variety X(T + S) attached to this data, with invertible variables associated to the new vertices, playing the role of coefficients in the equations (as the α do).

Let ω i denote d log(x i ). The following lemma has been proved by Greg Muller in [START_REF] Muller | The Weil-Petersson form on an acyclic cluster variety[END_REF] in a more general context.

Lemma 5.1 The differential form

WP = i→j ω i ω j , (24)
where the sum is running over edges of T + S, is an algebraic differential form on the variety X(T + S).

Proof. Let us prove that it has no pole. Let us fix i. To study the possible pole along x i = 0, it is enough to look at the sum j↔i ω i ω j restricted to edges containing i.

By the relation x i x ′ i = 1 + j↔i x j , one has

x i dx ′ i + x ′ i dx i = j↔i   k =j k↔i x k   dx j , (25)
and therefore

x i dx ′ i dx i = j↔i   k =j k↔i x k   dx j dx i . (26)
This implies

dx ′ i dx i / k↔i x k = j↔i ω j ω i , (27)
where the left-hand side has clearly no pole at x i .

Note that WP stands here for Weil-Petersson. Abusing notations, one will use the same symbol WP to denote these differential forms on different varieties. The ambient variety should be clear from the context.

Hodge structures

We will use the notation Q(-i) to denote a one dimensional vector space over Q endowed with a pure Hodge structure of Tate type, of weight 2i and type (i, i). The tensor product of Q(-i) and Q(-j) is Q(-i -j).

Recall that the cohomology of G m has an Hodge structure described by

H k (G m ) = Q(-k) (28) for 0 ≤ k ≤ 1.
There is no morphism between pure Hodge structures of distinct weights. The Künneth isomorphism is compatible with the Hodge structures. The Mayer-Vietoris long exact sequence is an exact sequence of Hodge structures.

Cohomology: orange and versal cases

This section deals with the cohomology, in several cases where either varieties do not depend on parameters, or versal conditions are assumed on all parameters. The first part is devoted to linear trees; the results there can then be used as building blocks.

Linear trees A

Let A n be the linear tree with n vertices numbered from 1 to n. As seen in §4.3, this is an orange tree if n is even, and an unimodal tree otherwise. Some of the results of this section were already obtained in [START_REF] Chapoton | On the number of points over finite fields on varieties related to cluster algebras[END_REF] using instead the cohomology with compact supports.

Cohomology of some auxiliary varieties for A

Let us introduce three varieties X n , Y n and Z n with dimensions n, n + 1 and n + 1. The variety Z n is defined by variables x 1 , . . . , x n , x ′ 1 , . . . , x ′ n and α such that

x 1 x ′ 1 = 1 + αx 2 , ( 29
)
x i x ′ i = 1 + x i-1 x i+1 , (30) x n x ′ n = 1 + x n-1 . (31)
The variety Y n is the open set in Z n where α is invertible.

The variety X n is the closed set in Y n where α is fixed to a generic invertible value (where generic means distinct from (-1) (n+1)/2 if n is odd).

In our general notations, Y n is X versal An and X n is X generic An . Let us first describe the variety Z n . Proposition 6.1 There exists an isomorphism between Z n and the affine space A n+1 .

Proof. This follows from the known cohomology of Y n and the Künneth theorem applied to the isomorphism Y n ≃ X n G m given by lemma 3.4. The Künneth theorem gives immediately the Hodge structure.

For the basis, it is enough to recall that the G m factor is given by the value of α, and to check that fixing the value α = 1 maps WP (for Y n ) to WP (for X n ). Let us denote by H k,ℓ,m,n the tree described as two chains joined by an edge, such that by removing the joining edge and its extremities a and b, one gets two chains of lengths k and ℓ on the a side (top) and two chains of lengths m and n on the b side (bottom).

We assume now that H k,ℓ,m,n is an orange tree. It implies that either k, ℓ, m and n are even if the middle edge is an orange domino, or that (without loss of generality) k and m are odd and l and n are even otherwise.

Then one can compute the cohomology of H k,ℓ,m,n using the Mayer-Vietoris long exact sequence for the open covering by U (x a ) and U (x b ).

When the middle edge is an orange domino, one has

U (x a ) ≃ X k X ℓ Y m+n+1 , U (x b ) ≃ Y k+ℓ+1 X m X n , U (x a ) ∩ U (x b ) ≃ (G m ) 2 X k X ℓ X m X n . (35)
When the middle edge is not an orange domino, one finds instead

U (x a ) ≃ Y k X ℓ X m+n+1 , U (x b ) ≃ X k+ℓ+1 Y m X n , U (x a ) ∩ U (x b ) ≃ Y k X ℓ Y m X n . (36)
Let us introduce some notations: call K, L, M, N the subsets of vertices corresponding to the four branches of H (i.e. the connected components of H \{a, b}).

Let us denote by W S the Weil-Petersson 2-form associated with a subset S of the vertices of H. For conciseness, one will use shortcuts such as W KaL or W M abN . Note that there holds ω a W aL = ω a W L and other similar simplifications, by the definition (24) of these forms.

Let us now describe generators and bases of the cohomology of the open sets U (x a ), U (x b ) and U (x b )∩U (x b ). This can be computed using the isomorphisms (35), (36) and the known cohomology of varieties X and Y . It turns out that the result does not depend on whether or not the middle edge a -b is an orange domino.

The cohomology of U (x a ) is generated by ω a , W Ka , W aL and W M abN . A basis is given by

W κ Ka W λ aL W B M abN and ω a W κ K W λ L W B M bN , (37)
where 0

≤ κ ≤ k/2, 0 ≤ λ ≤ l/2 and 0 ≤ B ≤ (m + n + 2)/2 (left) or 0 ≤ B ≤ (m + n)/2 (right).
Similarly, the cohomology of U (x b ) is generated by ω b , W M b , W bN and W KabL . A basis is given by

W µ M b W ν bN W A KabL and ω b W µ M W ν N W A KaL , (38)
where 0

≤ µ ≤ m/2, 0 ≤ ν ≤ n/2 and 0 ≤ A ≤ (k + l + 2)/2 (left) or 0 ≤ A ≤ (k + l)/2 (right). The cohomology of U (x b ) ∩ U (x b ) is generated by ω a , ω b , W M b , W bN , W Ka and W aL . A basis is given by W κ Ka W λ aL W µ M b W ν bN , ω a W κ K W λ L W µ M b W ν bN , ω a ω b W κ K W λ L W µ M W ν N and ω b W κ Ka W λ aL W µ M W ν N , (39)
with the same conditions as above on κ, λ, µ and ν.

There is a bigrading corresponding to the top and bottom parts of the H shape. Every differential form involved in the bases just described is a sum of products of ω i . The bidegree of a monomial in the ω i is the pair (number of ω i where i is in the top row, number of ω i where i is in the bottom row). Among the various Weil-Petersson forms involved, only the differential forms W KabL and W M abN are not homogeneous for the bidegree, but have terms in bidegrees (2, 0) and (1, 1) (resp. (0, 2) and (1, 1)).

One needs now to compute explicitly the following maps in the Mayer-Vietoris long exact sequence:

H i (U (x a )) ⊕ H i (U (x b )) fi -→ H i (U (x a ) ∩ U (x b )).
Because one has bases of all these spaces, this is a matter of matrices.

For odd degree i, let us show that the differential is injective. Because in this case all basis elements (given by right columns of (37), (38) and (39)) are homogeneous for the bigrading, one can separate the cases of bidegree congruent to (0, 1) and to (1, 0) modulo (2, 2). Let us give details only for the first possibility, the other case being similar after exchanging top and bottom of H. The basis of the corresponding bihomogeneous subspace of

H i (U (x b )) is given by ω b W A KaL W µ M W ν N with i = 1 + 2A + 2µ + 2ν. The corresponding bihomogeneous subspace of H i (U (x a )) is zero. The basis of the corresponding bihomogeneous subspace of H i (U (x a ) ∩ U (x b )) is given by ω b W κ Ka W λ aL W µ M W ν N with i = 1+2κ+2λ+2µ+2ν. But W A
KaL can be written as a linear combination of W κ Ka W λ aL with κ + λ = A. Therefore the basis elements are mapped to linear combinations with disjoint supports. It follows that the map f i is injective.

Let us now turn to even degrees. Proposition 6.4 For even degree 2i, the kernel of the differential f 2i has dimension 1, spanned by the i th power of the form WP.

Proof. First note that one can define an injective map ∆ from the space H 2i (U (x a ) ∩ U (x b )) to the space D i spanned by all products of i 2-forms of the shape ω s ω t for s -t an edge of the tree (always written in the order given by a fixed alternating orientation of the tree). Indeed, both terms in the left column of (39) can be written as linear combinations of such products. The injectivity holds because distinct elements in this part of the basis are mapped to linear combinations with disjoint supports. To recover a basis element B from any monomial in its image by ∆, first count in ∆(B) if the number of ω k in the top row is odd or even. This tells if the basis elements B contains ω a ω b or not. Then it is easy to recover the exponents (κ, λ, µ, ν) defining B by counting in ∆(B) how many ω k there are in the different parts of the tree.

To prove the statement of the proposition, it is therefore enough to compute the kernel of the composite map ∆ • f 2i .

It turns out that the matrix of this composite map has a nice description. First, every monomial d made of i 2-forms ω s ω t as above appears in exactly two images, the image of a form W κ Ka W λ aL W B M abN and the image of a form W µ M b W ν bN W A KabL (with opposite signs). Let us denote these two forms by F a (d) and F b (d). On the other hand, the image of every basis element is the sum of several monomials (at least one), with constant sign.

Let us pick an element z of the kernel of f 2i . Then for every monomial d in D i , the coefficients of F a (d) and F b (d) in z must be the same. One can make a graph with vertices given by all forms in the basis, and edges corresponding to the relations F a (d) -F b (d) for all monomials d.

By a combinatorial argument, one can check that this graph is connected. For this, one just has to show that one can go from any monomial d to any monomial d ′ , using two kinds of moves: replace d by another monomial appearing in the same F a (d), or replace d by another monomial appearing in the same F b (d). This is not difficult once translated in terms of dominoes, and details are left to the reader.

From the connectedness of this graph, one deduces that the kernel is spanned by the sum of all basis elements of H 2i (U (x a )) ⊕ H 2i (U (x b )), which is just (WP i , WP i ).

This proposition and the injectivity in the case of odd degree allow to give a description of the weights of the Hodge structure on the cohomology. This can easily be made explicit, but one will not do that here.

There would remain to find explicit expressions for the cohomology classes coming from the co-image of the differentials f i .

In the case of the Dynkin diagrams E 6 and E 8 , one can go further and compute explicit representatives of the cohomology classes.

By the general proof, the cohomology for E 6 is described by

Q(0) | 0 | Q(-2) | 0 | Q(-3) ⊕ Q(-4) | 0 | Q(-6),
where the Q(-i) with i even correspond to the powers of WP.

Using the connection homomorphism in the long exact sequence, one finds that the form dx 2 dx 3 dx 5 ω 4 (40)

corresponds to Q(-3).

Similarly, the cohomology for E 8 is described by

Q(0) | 0 | Q(-2) | 0 | Q(-3) ⊕ Q(-4) | 0 | Q(-5) ⊕ Q(-6) | 0 | Q(-8),
where the even Q(-i) are the powers of WP. One finds that the form dx 2 dx 3 dx 5 ω 4 (41) corresponds to Q(-3), and its product by WP corresponds to Q(-5). This section contains one conjecture and one result in some specific cases about the cohomology of generic fibers.

Cohomology for A odd and generic

Let us now consider the linear tree A n for odd n, which is unimodal. In this section, one proposes a conjectural description for the cohomology of the variety X generic An (which is also denoted X n in §6.1.1).

Conjecture 7.1 The Hodge structure on the cohomology of X n is given by

H k (X n ) = Q(-k) (42)
for even k in 0 ≤ k ≤ (n -1), and

H n (X n ) = ⊕ n i=(n+1)/2 Q(-i). ( 43
)
The cohomology ring has a basis given by all powers WP i for 0 ≤ i ≤ (n -1)/2 and by a basis of H n (X n ). The cohomology ring is generated by WP in degree 2 and by the elements of H n (X n ) in degree n.

One approach for this computation would be using the covering of X n by the (n + 1)/2 open sets U (x i ) (i odd) given by Lemma 3.6. One can then consider the spectral sequence for this covering (where d 1 is the deRham differential and d 2 is the Cech differential).

The intersection of open sets in this covering have a simple description: they are products G m times two varieties of the type X k with k even, times some varieties of type Y k with k odd. Lemma 7.2 This spectral sequence degenerates at E 2 .

Proof. This follows from the purity of the Hodge structure on the cohomology of the open sets in the covering.

It would therefore be enough to understand the behavior of the Cech differential acting on the cohomology groups of the open sets. This is still a rather intricate question. The conjecture has been checked by computer for n ≤ 11. Maybe one should look for a better approach.

Remark 7.3 To give an explicit description of the generators of the top cohomology group seems to be an interesting problem.

Cohomology for D odd and generic

Let us now consider the tree D n for odd n, which is unimodal. Our aim is to compute the cohomology of the variety X generic Dn . One will assume that the generic parameter α is attached to the vertex 1, where 1 and 2 are the two red vertices on the short branches. By Lemma 3.6, one has a covering by U (x 1 ) and U (x 2 ). One will use the Mayer-Vietoris long exact sequence for this covering. One has

U (x 1 ) ≃ G m X n-1 , U (x 2 ) ≃ G m X n-1 , U (x 1 ) ∩ U (x 2 ) ≃ G m Y n-2 .
Given the known explicit description of the cohomology rings of X n-1 and Y n-2 , one can write very explicitly the long exact sequence.

First note that the Hodge structure of H k (U (x 1 )) ⊕ H k (U (x 2 )) is 2 Q(-k) for 0 ≤ k ≤ n. Similarly, the Hodge structure of H k (U (x 1 ) ∩ U (x 2 )) is 2 Q(-k), unless k = 0 or n where it is Q(-k).

Using the known basis of the cohomology, one can describe the map ρ k from H k (U (x 1 )) ⊕ H k (U (x 2 )) to H k (U (x 1 ) ∩ U (x 2 )). One can see that this map has rank 1 if k is even. One can also check that it is an isomorphism if k is odd, unless k = n where it has rank 1.

It follows that the Hodge structure on H k (X generic

Dn

) is given by

     Q(-k) if k ≡ 0 (mod 2), Q(-k + 1) if k ≡ 1 (mod 2), k ∈ {1, n} Q(-n + 1) ⊕ Q(-n) if k = n. (44)
Moreover, it also follows from the explicit knowledge of the long exact sequence that the classes in even cohomological degree are just the powers of the 2-form WP.

One can also see that the Hodge structure Q(-n) in cohomological degree n is given by the differential form Λ n i=1 ω i . There remains to understand the even Hodge structures present in odd cohomological degrees.

By a small diagram chase, and using the formula

1 -α x 1 x 2 = x ′ 1 x 2 -α x ′ 2 x 1 , (45)
one finds that a basis of the Q(-2) part of H 3 (X generic

Dn

) is given by the differential form

dx 3 ω 1 ω 2 . ( 46
)
Moreover, a similar computation shows that products of this form by powers of WP give a basis for the even Hodge structures in odd cohomological degrees. The cohomology ring is therefore generated by one generator in each degree 2, 3 and n (of Hodge type Q(-2), Q(-2) and Q(-n)).

Let us go back to this previous step of this algorithm, where u and v are red, w is green with v as only red neighbor. u -v -w So w must have another neighbor z, such that w has turned green as the last red neighbor of z.

u -v -w -z

One can assume, by changing maybe the order in which the algorithm has been performed, that z has turned green before w. This is because trees are bipartite, and the algorithm can be run independently on the two parts of the bipartition.

Therefore, w has turned green as the last red neighbor of the green vertex z, and hence belongs to a domino w -z. Hence one has found a configuration v -w -z similar to the initial one:

v -w -z .
This can be iterated to provide an infinite sequence of vertices. This is absurd.

It follows from the lemma that once a domino is created, its vertices do not have any red neighbors. Therefore they will be orange at the end.

This also implies that the dominoes are disjoint, because the creation of a domino takes a red vertex with only green neighbors and a green vertex with exactly one red neighbor, and produces a pair of green vertices with only green neighbors. Therefore a vertex can only enter once in a domino.

Moreover, every orange vertex v is in a domino. This is because green vertices surrounded only by green vertices can only be introduced during the creation of a domino.

Remark A.3 From the previous proof, one can see that one can modify the algorithm as follows: when creating a new domino, color in orange its two vertices, and forget step 4.

Figure 1 :

 1 Figure 1: Canonical coloring: {1,2} are orange, {4,6} green and {3,5,7} red

  by a sequence of jumps. Moreover, (a) the function β only depends on the values of α on the red vertices of T , (b) the values of β on a red-green component are Laurent monomials in the values of α on the same red-green component. Proof. Let us first prove the existence of such parameters β. The main idea is to iterate lemma 2.1 by jumping over dominoes of M . Let us define an auxiliary oriented graph G as follows: the vertices of G are the vertices of T , and there is an edge

  Let us introduce the notation U (x) for the open set defined by x = 0. Lemma 2.8 If a -b is an edge in a tree T , then the two open sets U (x a ) and U (x b ) cover the variety X ϕ T .

4. 4

 4 Trees of type D Let us denote by D n the tree with n vertices associated with the Dynkin diagram of type D.

6. 2

 2 Cohomology for orange trees of shape H

well as the trees 2.172 (graph6 'IhGGOCA?G') and 2.174 (graph6 'IhGH?C@?G'). The number of different polynomials for orange trees with 2n vertices is the sequence 1, 1, 2, 5, 13, 41, 138, . . .

Linear trees

Let us denote by A n the linear tree with n vertices.

if n is even and by

if n is odd.

Proof. This follows easily by induction from lemmas 4.2, 4.3 and 4.4.

Proof. This has been proved in [START_REF] Chapoton | On the number of points over finite fields on varieties related to cluster algebras[END_REF]Prop. 3.6].

Therefore, the cohomology of Z n is known for all n:

The Hodge structure on

Let us now compute the cohomology of Y n by induction. This uses the Mayer-Vietoris long exact sequence for the covering of Z n by the two open sets U (x 1 ) and U (α).

First, let us note that U (α) ≃ Y n by definition. Next, one finds that U (x 1 ) ≃ A 1 Y n-1 . Indeed one can eliminate x ′ 1 using the first equation. Then α becomes a free variable, and there remains the equations for Y n-1 , with x 1 now playing the role of α. Last, the intersection

Let us write ω α for d log(α).

Proposition 6.2 The cohomology ring of Y n has the following description:

for 0 ≤ k ≤ n + 1. It has a basis given by powers of WP in even degrees and by powers of WP times ω α in odd degrees. It is generated by the 1-form ω α and the 2-form WP.

Proof. Because of the vanishing of H k (Z n ) for k > 0, the Mayer-Vietoris long exact sequence gives short exact sequences

for every k > 0. This determines by induction the Hodge structure of the cohomology of Y n .

Let us now proceed to the expected basis. One already knows that WP and ω α are indeed algebraic differential forms on Y n .

By the short exact sequences above, one can check that for k > 0 the union of the expected basis of H k (Y n ) with the known basis of H k (U (x 1 )) is mapped to a basis of H k (U (α) ∩ U (x 1 )). This implies the statement.

Cohomology for A n with even n

Let us now consider the linear tree A n for even n, and compute the cohomology of X n . Proposition 6.3 The Hodge structure of the cohomology of X n is

for all even k between 0 and n, and 0 otherwise. A basis is given by powers of WP. The cohomology ring is generated by WP.

A Algorithm for the canonical coloring of trees

Let us now describe an algorithm to find the red-orange-green coloring. Let T be a tree.

1. At start, all vertices are considered to be red.

2. Then, one changes the colors according to the following rule:

If a vertex v has exactly one red neighbor w, this red neighbor becomes green.

If moreover v is green, then one puts a domino on the edge v -w.

3. One repeats the previous step until no color can change.

4. Then one colors in orange the green vertices that do not have a red neighbor.

One gets in that way a coloring of the tree with green, orange and red vertices, together with a collection of dominoes.

Proposition A.1 This algorithm defines the same coloring as in section 1. Moreover the dominoes obtained are those that are present in all maximum matchings.

Proof. At the end of step 3, one has obtained a tree with red and green vertices, with the property that every vertex has either no red neighbor or at least two red neighbors.

Let us prove that a red vertex can not have at least two red neighbors. Assume that there is such a vertex v 1 . Let v 2 be one of its red neighbors. Then v 2 must also have at least two red neighbors. Hence one can find another red neighbor v 3 of v 2 . Going on in this way, and because T is a tree, one can build an infinite sequence of red vertices, which is absurd.

So, after step 3, one has three kinds of vertices: red vertices (they have only green neighbors), green vertices with no red neighbors and green vertices with at least two red neighbors.

It follows that after step 4, one has the following situation: red vertices with only green neighbors, green vertices with at least two red neighbors, and orange vertices with no red neighbors.

Using the third characterization of the coloring, it just remains to prove that the induced forest on orange vertices has a perfect matching. This matching is provided by the set of dominoes computed by the algorithm. When a domino is introduced, both its vertices are green. We need a lemma. Lemma A.2 During the algorithm, the configuration u -v -w where u is red and v -w is a domino, does not appear.

Proof. Let us assume the contrary, and let u -v -w be such a configuration.

Because v still has a red neighbor, the domino v -w must have been created by turning green the vertex v as the last red neighbor of the green vertex w.