Vincent Pilaud

COMPATIBILITY FANS FOR GRAPHICAL NESTED COMPLEXES

Keywords: Graph associahedra, finite type cluster algebras, compatibility degrees, compatibility fans. MSC classes. 52B11, 52B12, 05E45

Introduction

Associahedra. The n-dimensional associahedron is a simple polytope whose 1 n+2 2n+2 n+1 vertices correspond to Catalan objects (triangulations of an (n+3)-gon, binary trees on n+1 nodes, ...) and whose edges correspond to mutations between them (diagonal flips, edge rotations, ...). Its combinatorial structure appeared in early works of D. Tamari [START_REF] Tamari | Monoïdes préordonnés et chaînes de Malcev[END_REF] and J. Stasheff [START_REF] Stasheff | Homotopy associativity of H-spaces I[END_REF], and was first realized as a convex polytope by M. Haiman [START_REF] Haiman | Constructing the associahedron[END_REF] and C. Lee [START_REF] Lee | The associahedron and triangulations of the n-gon[END_REF]. Since then, the associahedron has motivated a flourishing research trend with rich connections to combinatorics, geometry and algebra: polytopal constructions [Lod04, HL07, CSZ15, LP13], Tamari and Cambrian lattices [START_REF]Associahedra, Tamari Lattices and Related Structures[END_REF][START_REF] Reading | Lattice congruences of the weak order[END_REF][START_REF] Reading | Cambrian lattices[END_REF], diameter and Hamiltonicity [STT88, Deh10, Pou14, HN99], geometric properties [START_REF] Bergeron | Isometry classes of generalized associahedra[END_REF][START_REF] Hohlweg | The centers of gravity of the associahedron and of the permutahedron are the same[END_REF][START_REF] Pilaud | Vertex barycenter of generalized associahedra[END_REF], combinatorial Hopf algebras [LR98, HNT05, Cha00, CP14], to cite a few. The associahedron was also generalized in several directions, in particular to secondary and fiber polytopes [START_REF] Gelfand | Discriminants, resultants and multidimensional determinants[END_REF][START_REF] Billera | Constructions and complexity of secondary polytopes[END_REF], graph associahedra and nestohedra [CD06, Dev09, Pos09, FS05, Zel06, Pil13], pseudotriangulation polytopes [START_REF] Rote | Expansive motions and the polytope of pointed pseudo-triangulations[END_REF], cluster complexes and generalized associahedra [START_REF] Fomin | Y -systems and generalized associahedra[END_REF][START_REF] Chapoton | Polytopal realizations of generalized associahedra[END_REF][START_REF] Hohlweg | Permutahedra and generalized associahedra[END_REF][START_REF] Stella | Polyhedral models for generalized associahedra via Coxeter elements[END_REF][START_REF] Hohlweg | Permutahedra and associahedra[END_REF], and brick polytopes [START_REF] Pilaud | The brick polytope of a sorting network[END_REF][START_REF] Pilaud | Brick polytopes of spherical subword complexes and generalized associahedra[END_REF].

Graph associahedra. This paper deals with graph associahedra, which were defined by M. Carr and S. Devadoss [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF] in connection to C. De Concini and C. Procesi's wonderful arrangements [START_REF] De | Wonderful models of subspace arrangements[END_REF]. Given a simple graph G with κ connected components and n + κ vertices, the G-associahedron Asso(G) is an n-dimensional simple polytope whose combinatorial structure encodes the connected subgraphs of G and their nested structure. More precisely, the face lattice of the polar of the G-associahedron is isomorphic to the nested complex Nest(G) on G, defined as the simplicial complex of all collections of tubes (connected induced subgraphs) of G which are pairwise compatible (either nested, or disjoint and non-adjacent). As illustrated in Figures 1, 2 and3, the graph associahedra of certain special families of graphs happen to coincide with well-known families of polytopes: classical associahedra are path associahedra, cyclohedra are cycle associahedra, and permutahedra are complete graph associahedra. The graph associahedra were extended to the nestohedra, which are simple polytopes realizing the nested complex of arbitrary building sets [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF][START_REF] Eva | Matroid polytopes, nested sets and Bergman fans[END_REF]. Graph associahedra and nestohedra have been geometrically realized in different ways: by successive truncations of faces of the standard simplex [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF], as Minkowski sums of faces of the standard simplex [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF][START_REF] Eva | Matroid polytopes, nested sets and Bergman fans[END_REF], or from their normal fans by exhibiting explicit inequality descriptions [START_REF] Satyan | A realization of graph associahedra[END_REF][START_REF] Zelevinsky | Nested complexes and their polyhedral realizations[END_REF]. For a given graph G, the resulting polytopes all have the same normal fan which coarsens the type A Coxeter arrangement: its rays are the characteristic vectors of the tubes, and its cones are generated by characteristic vectors of compatible tubes. Alternative realizations of graph associahedra with different normal fans are obtained by successive truncations of faces of the cube in [START_REF] Volodin | Cubical realizations of flag nestohedra and a proof of Gal's conjecture for them[END_REF][START_REF] Satyan | Convex polytopes from nested posets[END_REF]. The objective of this paper is to provide a new unrelated family of complete simplicial fans realizing the graphical nested complex Nest(G) for any graph G.

Cluster algebras and cluster fans. Our construction is directly inspired from combinatorial and geometric properties of finite type cluster algebras and generalized associahedra introduced by S. Fomin and A. Zelevinsky in [START_REF] Fomin | Cluster algebras. I. Foundations[END_REF][START_REF] Fomin | Cluster algebras. II. Finite type classification[END_REF][START_REF] Fomin | Y -systems and generalized associahedra[END_REF]. Note that A. Zelevinsky [START_REF] Zelevinsky | Nested complexes and their polyhedral realizations[END_REF] already underlined the closed connection between nested complexes, nested fans, and nestohedra on one hand and cluster complexes, cluster fans and generalized associahedra on the other hand. More recently, T. Lam and P. Pylyavskyy established an even deeper connection with linear Laurent Phenomenon algebras [START_REF] Lam | Laurent phenomenon algebras[END_REF][START_REF] Lam | Linear Laurent phenomenon algebras[END_REF], see the discussion in Section 5.5. In this paper, we use ideas from cluster algebras to obtain results on graphical nested complexes, which in turn translate to relevant properties of the geometry of finite type cluster algebras.

Cluster algebras are commutative rings generated by a set of cluster variables grouped into overlapping clusters. The clusters are obtained from an initial cluster X • by a mutation process. Each mutation exchanges a single variable in a cluster according to a formula controlled by a combinatorial object. We refer to [START_REF] Fomin | Cluster algebras. I. Foundations[END_REF] since precise details on this mutation are not needed here. Two cluster variables are compatible if they belong to a same cluster and exchangeable if they are not compatible and belong to two clusters connected by a mutation. The cluster complex of a cluster algebra A is the pure simplicial complex whose vertices are cluster variables of A and whose facets are the clusters of A. A cluster algebra is of finite type if it has finitely many cluster variables, and thus if its cluster complex is finite. Finite type cluster algebras were classified in [START_REF] Fomin | Cluster algebras. II. Finite type classification[END_REF]: up to isomorphism, there is one finite type (coefficient-free) cluster algebra for each finite crystallographic root system.

The Laurent Phenomenon [START_REF] Fomin | Cluster algebras. I. Foundations[END_REF] asserts that each cluster variable x can be expressed as a Laurent polynomial in terms of the cluster variables x • 1 , . . . , x • n of the initial cluster X • . The d-vector of x with respect to X • is the vector d(X • , x) whose ith coordinate is the exponent of the initial variable x • i in the denominator of x. In finite type, this exponent was also interpreted in [START_REF] Fomin | Y -systems and generalized associahedra[END_REF][START_REF] Ceballos | Denominator vectors and compatibility degrees in cluster algebras of finite types[END_REF] as the compatibility degree (x • i x) between the cluster variables x • i and x. The compatiblity degree (• •) has the following properties: for any distinct cluster variables x and x , we have (x x ) ≥ 0 with equality if and only if x and x are compatible, and (x x ) = 1 = (x x) if and only if x and x are exchangeable. The d-vectors can be used to construct a simplicial fan realization of the cluster complex, called d-vector fan: it is known for certain initial clusters in finite type cluster algebras, that the cones generated by the d-vectors of all collections of compatible cluster variables form a complete simplicial fan realizing the cluster complex. This is proved by S. Fomin and A. Zelevinsky [START_REF] Fomin | Cluster algebras. II. Finite type classification[END_REF] for the bipartite initial cluster, by S. Stella [START_REF] Stella | Polyhedral models for generalized associahedra via Coxeter elements[END_REF] for all acyclic initial clusters, and by F. Santos [CSZ15, Section 5] for any initial cluster in type A. In fact, we expect this property to hold for any initial cluster, acyclic or not, of any finite type cluster algebra: this paper proves it for types A, B, and C (our general proof provides as a particular case a new proof in type A, similar to that of [CSZ15, Section 5]), and the other finite types are investigated in a current project of the authors in collaboration with C. Ceballos.

There is another complete simplicial fan realizing the cluster complex, whose rays are now given by the g-vectors of the cluster variables, defined as the multi-degrees of the cluster variables in the cluster algebra with principal coefficients [START_REF] Fomin | Cluster algebras[END_REF]. The fact that the cones generated by the g-vectors of all collections of compatible cluster variables form a complete simplicial fan is a consequence of [START_REF] Reading | Universal geometric cluster algebras[END_REF]. When the initial cluster is acyclic, the resulting g-vector fan is the Cambrian fan of N. Reading and D. Speyer [START_REF] Reading | Cambrian fans[END_REF] and it coarsens the Coxeter fan. Compatibility fans for graphical nested complexes. Motivated by the combinatorial and geometric richness of the dand g-vector fans described above for finite type cluster algebras, we want to construct various simplicial fan realizations of the nested complex. As it coarsens the Coxeter fan, the normal fan of the graph-associahedra and nestohedra of [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF][START_REF] Satyan | A realization of graph associahedra[END_REF][START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF][START_REF] Eva | Matroid polytopes, nested sets and Bergman fans[END_REF][START_REF] Zelevinsky | Nested complexes and their polyhedral realizations[END_REF] should be considered as an analogue of the g-vector fan. A tentative approach to construct alternative g-vector fans for tree associahedra can be found in [START_REF] Pilaud | Signed tree associahedra[END_REF].

In this paper, we construct an analogue of the d-vector fan for graphical nested complexes. For two tubes t, t of a graph G, we define the compatibility degree (t t ) of t with t to be (t t ) = -1 if t = t , (t t ) = 0 if t = t are compatible, and (t t ) = |{neighbors of t in t t}| otherwise. Similar to the compatibility degree for cluster algebras, it satisfies (t t ) ≥ 0 for any distinct tubes t, t of G, with equality if and only if t and t are compatible, and (t t ) = 1 = (t t) if and only if t and t are exchangeable. We define the compatibility vector d(T • , t) := [(t • 1 t), . . . , (t • n t)] of a tube t with respect to an initial maximal tubing T • := {t • 1 , . . . , t • n }, and the compatibility matrix

d(T • , T) := [(t • i t j )] i∈[n],j∈[m]
of a tubing T := {t 1 , . . . , t m } of G with respect to the initial tubing T • . We write R ≥0 d(T • , T) to denote the polyhedral cone generated by the compatibility vectors of the tubes of T with respect to T • .

Notice that our degree is asymmetric, which yields a natural notion of duality. We define the dual compatibility vector d * (t, T • ) := [(t t • 1 ), . . . , (t t • n )] of t with respect to T • and the dual compatibility matrix d * (T, T

• ) := [(t j t • i )] i∈[n],j∈[m] .
To make the distinction clear from the dual compatibility vector, we often call d(T • , t) the primal compatibility vector.

Although there is no denominators involved anymore, we still use the letter d to stand for compatibility degree vector, and to match with the cluster algebra notations. Indeed, our compatibility degrees for paths and cycles coincide with the compatibility degree of [START_REF] Fomin | Y -systems and generalized associahedra[END_REF] in types A, B, and C. Compatibility degrees on type A cluster variables correspond to compatibility (and dual compatibility) degrees on tubes of paths while compatibility degrees in type C (resp. B) cluster variables correspond to compatibility (resp. dual compatibility) degrees on tubes of cycles.

Our main result is the following analogue of the compatibility fan for path associahedra constructed by F. Santos in [CSZ15, Section 5].

Theorem 1. For any graph G, the compatibility vectors (resp. dual compatibility vectors) of all tubes of G with respect to any initial maximal tubing T • on G support a complete simplicial fan realizing the nested complex on G. More precisely, both collections of cones We then study the number of distinct compatibility fans. As in [START_REF] Ceballos | Many non-equivalent realizations of the associahedron[END_REF], we consider that two compatibility fans D(G, T • ) and D(G , T • ) are equivalent if they differ by a linear isomorphism. Such a linear isomorphism induces an isomorphism between the nested complexes N (G) and N (G ). Besides those induced by graph isomorphisms between G and G , there are non-trivial nested complex isomorphisms: for example, the complementation t → V t on the complete graph, or the map on tubes of the path corresponding to the rotation of diagonals in the polygon. Extending these two examples, we exhibit a non-trivial nested complex isomorphism on any spider (a set of paths attached by one endpoint to a clique). Our next statement shows that these are essentially the only non-trivial nested complex isomorphisms. Theorem 2. All nested complex isomorphisms N (G) → N (G ) are induced by graph isomorphisms G → G , except if one of the connected components of G is a spider. Corollary 3. Except if one of the connected components of G is a path, the number of linear isomorphism classes of compatibility fans of G is the number of orbits of maximal tubings on G under graph automorphisms of G.

The next step would be to realize all these complete simplicial fans as normal fans of convex polytopes. This question remains open, except for some particular graphs: besides all graphs with at most 4 vertices, we settle the case of paths and cycles following a similar proof as [START_REF] Ceballos | Many non-equivalent realizations of the associahedron[END_REF].

Theorem 4. All compatibility and dual compatibility fans of paths and cycles are polytopal.

Overview. The paper is organized as follows. We first recall in Section 2 definitions and basic notions on polyhedral fans and graphical nested complexes. In particular, we state in Proposition 5 a crucial sufficient condition for a set of vectors indexed by a set X to support a simplicial fan realization of a simplicial complex on X. We also briefly survey the classical constructions of graph associahedra of [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF][START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF][START_REF] Zelevinsky | Nested complexes and their polyhedral realizations[END_REF].

In Section 3, we define the compatibility degree between two tubes of a graph, review its combinatorial properties, and state our geometric results on compatibility and dual compatibility fans.

We study various examples in Section 4. After an exhaustive description of the compatibility fans of all graphs with at most 4 vertices, we study four families of graphs: paths, cycles, complete graphs, and stars. The first two families connect our construction to S. Fomin and A. Zelevinsky's d-vector fans for type A, B, and C cluster complexes.

Section 5 discusses various further topics. We first study the behavior of the compatibility fans with respect to products and links. We then describe all nested complex isomorphisms in order to show that most compatibility fans are not linearly isomorphic. We also discuss the question of the realization of our compatibility fans as normal fans of convex polytopes. We extend our construction to design nested complexes [START_REF] Satyan | Deformations of bordered surfaces and convex polytopes[END_REF]. Finally, we discuss the connection of this paper to Laurent Phenomenon algebras [START_REF] Lam | Laurent phenomenon algebras[END_REF][START_REF] Lam | Linear Laurent phenomenon algebras[END_REF].

Finally, we have chosen to gather all proofs of our results in Section 6 with the hope that the properties and examples of compatibility fans treated in Sections 4 and 5 help the reader's intuition.

Preliminaries

In this section, we briefly review classical material to recall basic definitions and fix notations. The reader familiar with polyhedral geometry and graph associahedra can skip these preliminaries and proceed directly to Section 3. A closed polyhedral cone is a subset of R n defined equivalently as the positive span of finitely many vectors or as the intersection of finitely many closed linear halfspaces. The dimension of a cone is the dimension of its linear span. The faces of a cone C are the intersections of C with the supporting hyperplanes of C. Faces of polyhedral cones are polyhedral cones. The faces of dimension 1 (resp. codimension 1) are called rays (resp. facets). We will only consider pointed cones, which contain no entire line of R n . Therefore, C is the positive span of its rays and the intersection of the halfspaces defined by its facets and containing it. We say that C is simplicial if its rays form a linear basis of its linear span.

A polyhedral fan is a collection F of polyhedral cones of R n closed under faces and which intersect properly, i.e.

(1) if C ∈ F and F is a face of C, then F ∈ F;

(2) the intersection of any two cones of F is a face of both. A polyhedral fan is simplicial if all its cones are, and complete if the union of its cones covers the entire space R n . We will use the following characterization of complete simplicial fans, whose formal proof can be found e.g. in [DRS10, Corollary 4.5.20].

Proposition 5. For a simplicial sphere ∆ with vertex set X and a set of vectors

V := (v x ) x∈X of R n , the collection of cones R ≥0 V | ∈ ∆
, where R ≥0 V denotes the positive span of V := {v x | x ∈ }, forms a complete simplicial fan if and only if

(1) there exists a facet of ∆ such that V is a basis of R n and such that the open cones R >0 V and R >0 V are disjoint for any facet of ∆ distinct from ; (2) for two adjacent facets , of ∆ with {x} = {x }, there is a linear dependence

α v x + α v x + y∈ ∩ β y v y = 0
on V ∪ in which the coefficients α and α have the same sign (different from 0). Note that when these conditions hold, this linear dependence is unique up to rescaling.

a b c d e f g h i j k l m n o a b c d e f g h i j k l m n o Figure 4. A tube t • ex of G • ex (left) and a maximal tubing T • ex on G • ex (right).
A polytope is a subset P in R n defined equivalently as the convex hull of finitely many points in R n or as a bounded intersection of finitely many closed half-spaces of R n . The faces of P are the intersections of P with its supporting hyperplanes. The (outer) normal cone of a face F of P is the cone generated by the outer normal vectors of the facets (codimension 1 faces) of P containing F . Finally, the (outer) normal fan of P is the collection of the (outer) normal cones of all its faces. 2.2. Graphical nested complexes. We review the definitions and basic properties of graphical nested complexes. We refer to [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF][START_REF] Satyan | A realization of graph associahedra[END_REF] for the original construction of graph associahedra. This construction extends to nested complexes on arbitrary building sets, see [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF][START_REF] Eva | Matroid polytopes, nested sets and Bergman fans[END_REF][START_REF] Zelevinsky | Nested complexes and their polyhedral realizations[END_REF]. Although we remain in the graphical situation, our presentation borrows results from these papers.

Fix a graph G with vertex set V. Let κ(G) denote the set of connected components of G and define n

:= |V| -|κ(G)|. A tube of G is a non-empty subset t of vertices of G inducing a connected subgraph G[t] of G.
The inclusion maximal tubes of G are its connected components κ(G); all other tubes are called proper. Two tubes t, t of G are compatible if they are either nested (i.e. t ⊆ t or t ⊆ t), or disjoint and non-adjacent (i.e. t ∪ t is not a tube of G). A tubing on G is a set T of pairwise compatible proper tubes of G. The collection of all tubings on G is a simplicial complex, called nested complex of G and denoted by N (G).

Example 6. To illustrate the content of the paper, we will follow a toy example, presented in Figure 4. We have represented a graph G • ex on the left with a tube t • ex := {a, b, d, f, g, h, i, k, l}, and a maximal tubing T • ex on G • ex on the right. For a tubing T on G and a tube t of T ∪ κ(G), we define λ(t, T) := t t ∈T,t t t . The sets λ(t, T) for t ∈ T ∪ κ(G) form a partition of the vertex set of G. When T is a maximal tubing, each set λ(t, T) contains a unique vertex of G that we call the root of t in T.

The nested complex N (G) is an (n -1)-dimensional simplicial sphere. The dual graph of this complex is the graph whose vertices are maximal tubings on G and whose edges are flips between them. A flip is a pair of distinct maximal tubings T, T on G such that T {t} = T {t } for some tubes t ∈ T and t ∈ T . Since N (G) is a sphere, any tube of any maximal tubing can be flipped, and the resulting tube is described in the following proposition, whose proof is left to the reader. Remember that we denote by G[U ] the subgraph of G induced by a subset U ⊆ V.

Proposition 7. Let t be a tube in a maximal tubing T on G, and let t be the inclusion minimal tube of T ∪ κ(G) which strictly contains t. Then the unique tube t such that T = T {t, t } is again a maximal tubing on G is the connected component of G[t λ(t, T)] containing λ(t, T).

We say that two distinct tubes t, t of G are exchangeable if there exists two adjacent maximal tubings T, T on G such that T {t} = T {t }. Note that several such pairs {T, T } are possible, but they all contain certain tubes. We call forced tubes of the exchangeable pair {t, t } any tube which belongs to any adjacent maximal tubings T, T such that T {t} = T {t }. These tubes are easy to describe: they are precisely the tube t := t ∪ t and the connected components of t (λ(t, T) ∪ λ(t , T )). Let (e v ) v∈V be the canonical basis of R V , let H := x ∈ R V | w∈W x w = 0 for all W ∈ κ(G) and π : R V → H denote the orthogonal projection on H. Let g(t) := π v∈t e v denote the projection of the characteristic vector of a tube t of G, and define g(T) := {g(t) | t ∈ T} for a tubing T on G. These vectors support a complete simplicial fan realization of the nested complex:

Theorem 9 ([CD06, Pos09, FS05, Zel06]). For any graph G, the collection of cones G(G) := {R ≥0 g(T) | T tubing on G} is a complete simplicial fan of H, called nested fan of G, which realizes the nested complex N (G).

Remark 10. The cones of this fan can be encoded as follows. Fix a tubing T on G. The spine of T is the directed forest S given by the Hasse diagram of the inclusion poset on T ∪ κ(G) where the vertex corresponding to a tube t is labeled by λ(t, T) and the edges are directed in inclusion order. Then the cone R ≥0 g(T) is the braid cone of S and is polar to the incidence cone of S:

R ≥0 g(T) = {x ∈ H | x v ≤ x w for all v → w ∈ S} = R ≥0 {e v -e w | v → w ∈ S}
where v → w ∈ S means that there is a directed path in S from the node containing v to the node of S containing w. Spines are called B-trees in [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF].

It is proved in [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF][START_REF] Satyan | A realization of graph associahedra[END_REF][START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF][START_REF] Eva | Matroid polytopes, nested sets and Bergman fans[END_REF][START_REF] Zelevinsky | Nested complexes and their polyhedral realizations[END_REF] that the nested fan comes from a polytope.

Theorem 11 ([CD06, Dev09, Pos09, FS05, Zel06]). For any graph G, the nested fan G(G) is the normal fan of the graph associahedron Asso(G).

In fact, these different papers define different constructions and realizations for the graph associahedron Asso(G). Originally, M. Carr and S. Devadoss constructed Asso(G) by iterative truncations of faces of the standard simplex. S. Devadoss then gave explicit integer coordinates for the facets in [START_REF] Satyan | A realization of graph associahedra[END_REF]. In a different context, A. Postnikov [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF] and independently E. M. Feichtner and B. Sturmfels [START_REF] Eva | Matroid polytopes, nested sets and Bergman fans[END_REF] constructed graph associahedra (more generally nestohedra) by Minkowski sums of faces of the standard simplex. Finally, A. Zelevinsky [START_REF] Zelevinsky | Nested complexes and their polyhedral realizations[END_REF] discussed which polytopes can realize the nested fan using a characterization of all possible facet inequality descriptions.

Compatibility degrees, vectors, and fans

In this section, we define our compatibility degree on tubes and state our main results. To go straight to results and examples, the proofs are delayed to Section 6. We refer to Section 4 for examples of compatibility fans of relevant graphs in connection to the geometry of type A, B and C cluster complexes, and to Section 5 for further properties of compatibility fans.

3.1. Compatibility degree. Motivated by the compatibility degrees in finite type cluster algebras, we introduce an analogous notion on tubes of graphical nested complexes.

Definition 12. For two tubes t, t of G, the compatibility degree of t with t is

(t t ) =      -1 if t = t , |{neighbors of t in t t}| if t ⊆ t , 0 otherwise.
Example 13. On the graph G

(t • ex t • ex ) = |{i}| = 1, (t ex t • ex ) = |{g}| = 1, (t ex t • ex ) = 0, (t • ex t • ex ) = |{c, m}| = 2, (t • ex t ex ) = |{c, e, m}| = 3, (t • ex t ex ) = 0.
Note that the last 0 is forced by the last line of the definition since t • ex t ex .

We will see in Sections 4.2 and 4.3 that our compatibility degree on tubes of paths (resp. cycles) corresponds to the compatibility degree on cluster variables in type A (resp. B/C) cluster algebras defined in [START_REF] Fomin | Y -systems and generalized associahedra[END_REF]. The compatibility degree in cluster algebras encodes compatibility and exchangeability between cluster variables. The analogous result for the graphical compatibility degree is given by the following proposition, proved in Section 6.1. Proposition 14. For any two tubes t, t of G,

• (t t ) < 0 ⇐⇒ (t t) < 0 ⇐⇒ t = t ,
• (t t ) = 0 ⇐⇒ (t t) = 0 ⇐⇒ t and t are compatible, and • (t t ) = 1 = (t t) ⇐⇒ t and t are exchangeable.

Remark 15. It can happen that (t t ) = 1 while (t t) = 1, in which case t and t are not exchangeable. This situation appears as soon as G contains a cycle or a trivalent vertex. See e.g. Example 13. Proposition 14 should be understood informally as follows: the compatibility degree between two tubes measures how much they are incompatible. It is natural to use this measure to construct fan realizations of the nested complex: intuitively, pairs of tubes with low compatibility degrees should correspond to rays close to each other. We make this idea precise in the next section.

3.2. Compatibility fans. Similar to the d-vector fan defined by S. Fomin and A. Zelevinsky [START_REF] Fomin | Cluster algebras. II. Finite type classification[END_REF], we consider the compatibility vectors with respect to an arbitrary initial maximal tubing T • . Remember that any maximal tubing on G has precisely n := |V| -|κ(G)| tubes.

Definition 16. Let T • := {t • 1 , . . . , t • n } be an arbitrary initial maximal tubing on G. The compatibility vector of a tube t of G with respect to T • is the integer vector d(T • , t) := [(t • 1 t), . . . , (t • n t)]. The compatibility matrix of a tubing T := {t 1 , . . . , t m } on G with respect to T • is the matrix

d(T • , T) := [(t • i t j )] i∈[n],j∈[m]
. Remember that we denote by R ≥0 M the polyhedral cone generated by the column vectors of a matrix M. Note that the compatibility vectors of the initial tubes are given by the negative of the basis vectors, while all other compatibility vectors lie in the positive orthant:

d(T • , T • ) = -I n and d(T • , t) ∈ R ≥0 I n for t / ∈ T • .
Our main result asserts that these compatibility vectors support a complete simplicial fan realization of the graphical nested complex.

Theorem 17. For any graph G and any maximal tubing T • on G, the collection of cones D(G, T • ) := {R ≥0 d(T • , T) | T tubing on G} is a complete simplicial fan which realizes the nested complex N (G). We call it the compatibility fan of G with respect to T • .

We prove this statement in Section 6.3. The proof relies on the characterization of complete simplicial fans presented in Proposition 5. Unfortunately, we are not able to compute the linear dependence between the compatibility vectors involved in an arbitrary flip. To illustrate the difficulty, we show in the following example that these linear dependences may be complicated. In particular, they do not always involve only the forced tubes of the flip.

• ex ∪ T ex with respect to T • ex is 2 d(T • ex , t • ex ) + d(T • ex , t ex ) -d(T • ex , {d}) -d(T • ex , {e}) -3 d(T • ex , {m}) + 4 d(T • ex , {k, l}) -3 d(T • ex , {c, d, h}) = 0.
Observe that the tube {d} is involved in this linear dependence although it is not a forced tube of the exchangeable pair {t • ex , t ex }. Theorem 17 has the following consequences, whose direct proof would require some work.

Corollary 19. For any initial tubing T • on G,

• the compatibility vector map

t -→ d(T • , t) is injective: d(T • , t) = d(T • , t ) =⇒ t = t .
• the compatibility matrix d(T

) := [(t j t • i )] i∈[n],j∈[m]
. The following statement is the analogue of Theorem 17.

Theorem 21. For any graph G and any maximal tubing T • on G, the collection of cones

D * (G, T • ) := {R ≥0 d * (T, T • ) | T tubing
on G} is a complete simplicial fan which realizes the nested complex N (G). We call it the dual compatibility fan of G with respect to T • .

The proof of this statement appears in Section 6.4. It is a direct application of Theorem 17 using duality between compatibility and dual compatibility matrices.

• ex ∪ T ex with respect to T • ex is 2 d * (t • ex , T • ex ) + d * (t ex , T • ex ) -d * ({e}, T • ex ) -d * ({c, d, h}, T • ex ) = 0.

Examples for specific graphs

In this section, we provide examples of compatibility fans for particular families of graphs. We start with graphs with few vertices to illustrate the variety of compatibility fans. We then describe compatibility fans for paths, cycles, complete graphs and stars using alternative combinatorial models (triangulations, lattice paths, ...). For paths and cycles, we give an explicit connection to the compatibility degree in cluster algebras of types A, B, and C. The examples of this section shall help the intuition for further properties studied in Section 5 and for the proofs gathered in Section 6. 4.1. Graphs with few vertices. In view of Proposition 38 below, we restrict to connected graphs. The only connected graphs with 3 vertices are the 3-path and the triangle, whose compatibility fans are represented in Figure 6. The other possible choices for the initial tubing in these pictures would produce the same fans: it is clear for the triangle as all maximal tubings are obtained from one another by graph isomorphisms; for the path, it is an illustration of the non-trivial isomorphisms between compatibility fans studied in Section 5.2.

The first interesting compatibility fans appear in dimension 3 for connected graphs on 4 vertices. All possibilities up to linear transformations are represented in Figure 8. Instead of representing cones in the 3-dimensional space, we intersect the compatibility vectors with the unit sphere, make a stereographic projection of the resulting points on the sphere (the pole of the projection is the point of the sphere in direction -e 1 -e 2 -e 3 ), and draw the cones on the resulting planar points. Under this projection, the three external vertices correspond to the tubes of the initial tubing, and the external face corresponds to the initial tubing. For the sake of readability, we do not label the remaining vertices of the projection. Their labels can be reconstructed from the initial tubes by flips. For example, the tubes corresponding to the vertices of the top pictures of Figure 8 are given in Figure 7.

The pictures become more complicated in dimension 4. To illustrate them, we have represented in Figure 9 the stereographic projection of the compatibility fan for an arbitrary initial maximal tubing on the path, cycle, complete graph, and star on 5 vertices. Figure 8. All possible compatibility fans up to linear isomorphism, for all connected graphs on 4 vertices (see also the end of the picture on page 12 for the two remaining graphs). Instead of representing the cones in the 3-dimensional space, we intersect the compatibility vectors with the unit sphere, make a stereographic projection of the resulting points on the sphere (the pole of the projection is the point of the sphere in direction -e 1 -e 2 -e 3 ), and draw the cones on the resulting planar points.

Complete graph minus one edge

Complete graph minus two incident edges Figure 9. Stereographic projection of the compatibility fan for particular initial maximal tubings on the path, cycle, complete graph, and star on 5 vertices. 4.2. Paths. We now consider the nested complex N (P n+1 ) and the compatibility fan D(P n+1 , T • ) for the path P n+1 on n + 1 vertices. As already mentioned in the introduction, the nested complex N (P n+1 ) is isomorphic to the n-dimensional simplicial associahedron, i.e. the simplicial complex of sets of pairwise non-crossing diagonals of an (n + 3)-gon. It is convenient to present the correspondence as follows. Consider an (n + 3)-gon Q n+3 with vertices labeled from left to right by 0, 1, . . . , n + 2 and such that all vertices 1, . . . , n + 1 are located strictly below the boundary edge [0, n+2]. We can therefore identify the path P n+1 with the path 1, . . . , n+1 on the boundary of Q n+3 . We then associate to a diagonal δ of Q n+3 the tube t δ of P n+1 whose vertices are located strictly below δ, see Figures 10 and1. Finally, we associate to a set ∆ of pairwise non-crossing internal diagonals of Q n+3 the set of tubes T ∆ := {t δ | δ ∈ ∆}, see Figure 1. The reader can check that the map ∆ → T ∆ defines an isomorphism between the simplicial associahedron and the nested complex N (P n+1 ): two diagonals δ, δ of Q n+3 are non-crossing if and only if the corresponding tubes t δ , t δ of P n+1 are compatible.

It follows by classical results on the associahedron that the path P n+1 has:

• n(n + 3) 2 proper tubes [OEI10, A000096] (internal diagonals of the (n + 3)-gon),

• 1 n + 2 2n + 2 n + 1
maximal tubings [OEI10, A000108] (triangulations of the (n + 3)-gon),

• 1 k + 1 n k n + k + 2
k tubings with k tubes [OEI10, A033282] (dissections of the (n + 3)gon into k parts). The following statement, whose proof is left to the reader, describes the behavior of the map δ → t δ with respect to compatibility degrees.

Proposition 23. For any two diagonals δ, δ of Q n+3 , the compatibility degree of the corresponding tubes t δ and t δ of P n+1 is given by

(t δ t δ ) =      -1 if δ = δ , 0 if δ = δ do not cross, 1 if δ = δ cross.
In other words, our compatibility degree between tubes of P n+1 coincides with the compatibility degree between type A cluster variables defined by S. Fomin and A. Zelevinsky in [START_REF] Fomin | Y -systems and generalized associahedra[END_REF], and our graphical compatibility fan coincides with the type A compatibility fan defined for the bipartite initial cluster in [START_REF] Fomin | Cluster algebras. II. Finite type classification[END_REF] and for any initial cluster in [CSZ15, Section 5]. We thus obtain an alternative proof of F. Santos' result [CSZ15, Section 5].

Corollary 24. For type A cluster algebras, the denominator vectors (or compatibility vectors) of all cluster variables with respect to any initial cluster support a complete simplicial fan which realizes the cluster complex.

Remark 25 (Dual compatibility fan). The compatibility fan D(P n+1 , T • ) and the dual compatibility fan D * (P n+1 , T • ) coincide since the compatibility degree is symmetric for tubes of P n+1 .

Remark 26 (Linear dependences). In the case of the path P n+1 , the linear dependences are explicity described in [START_REF] Ceballos | Many non-equivalent realizations of the associahedron[END_REF]. They are derived from the case of the octagon by edge contraction in the interpretation in terms of triangulations. They can only involve the two flipped tubes and the forced tubes, and the coefficients are either 1 or 2 for the flipped tubes and -1 or 0 for the forced tubes. See Section 6.6 for more details.

Remark 27. The compatibility degree for tubes of a path takes values in {-1, 0, 1}. It is tempting to construct compatibility fans for graphical nestohedra using the naive compatibility degree defined by (t t ) = -1 if t = t , (t t ) = 0 if t = t are compatible, and (t t ) = 1 if t = t are incompatible. This naive approach works for the paths but fails for any other connected graph since two distinct tubes would get the same compatibility vectors. See Figure 11 for examples on the triangle and on the tripod.

Figure 11.

Counter-examples to the naive definition of compatibility degrees: both on the triangle and on the tripod, all tubes of the initial maximal tubing on the left are incompatible with the two distinct tubes on the right. 4.3. Cycles. We now consider the nested complex N (O n+1 ) and the compatibility fan D(O n+1 , T • ) for the cycle O n+1 on n + 1 vertices. As already mentioned in the introduction, the nested complex N (O n+1 ) is isomorphic to the n-dimensional simplicial cyclohedron, i.e. the simplicial complex of sets of pairwise non-crossings pairs of centrally symmetric internal diagonals (including duplicated long diagonals) of a regular (2n + 2)-gon R 2n+2 . The explicit correspondence works as follows. We label the vertices of R 2n+2 cyclically with two copies of [n + 1]. We then associate

• to a duplicated long diagonal δ with vertices labeled by i the tube

t δ := [n+1] {i} of O n+1 ,
• to a pair of centrally symmetric diagonals {δ, δ} the tube t δ of O n+1 which consists of the labels of the vertices of R 2n+2 separated from the center of R 2n+2 by δ and δ. Finally, we associate to a set ∆ of pairwise non-crossing pairs of centrally symmetric internal diagonals of R 2n+2 the set of tubes T ∆ := {t δ | δ ∈ ∆}. See Figures 12 and2. The reader can check that the map ∆ → T ∆ defines an isomorphism between the simplicial cyclohedron and the nested complex N (O n+1 ): two pairs of centrally symmetric diagonals (or duplicated long diagonals) {δ, δ} and {δ , δ } of R 2n+2 are non-crossing if and only if the corresponding tubes t δ and t δ of O n+1 are compatible. It follows by classical results on the cyclohedron that the cycle O n+1 has:

• n(n + 1) proper tubes [OEI10, A002378] (centrally symmetric pairs of diagonals),

• 2n n maximal tubings [OEI10, A000984] (centrally symmetric triangulations),

• n k n + k k tubings with k tubes [OEI10, A063007] (centrally symmetric dissections).
The following statement, whose proof is left to the reader, describes the behavior of the map {δ, δ} → t δ with respect to compatibility degrees.

Proposition 28. For any two pairs of centrally symmetric diagonals (or duplicated long diagonals) {δ, δ} and {δ , δ } of R 2n+2 , the compatibility degree (t δ t δ ) of the corresponding tubes t δ and t δ of O n+1 is the number of crossings between the two diagonals δ and δ and the diagonal δ .

In other words, our compatibility degree (resp. dual compatibility degree) between tubes of O n+1 coincides with the compatibility degree between type C (resp. type B) cluster variables defined by S. Fomin and A. Zelevinsky in [START_REF] Fomin | Y -systems and generalized associahedra[END_REF]. Moreover, our graphical compatibility fan (resp. dual compatibility fan) coincides with the type C (resp. type B) compatibility fan defined for an acyclic initial cluster in [START_REF] Fomin | Cluster algebras. II. Finite type classification[END_REF]. This extends for any arbitrary initial cluster to the following corollary.

Corollary 29. For type B and C cluster algebras, the denominator vectors (or compatibility vectors) of all cluster variables with respect to any initial cluster support a complete simplicial fan which realizes the cluster complex. Remark 31 (Linear dependences). As for paths, only finitely many linear dependences occur for all cycles O n+1 , both on compatibility vectors as on dual compatibility vectors. Indeed, with the interpretation of the maximal tubings in terms of centrally symmetric triangulations, the same kind of arguments as in [START_REF] Ceballos | Many non-equivalent realizations of the associahedron[END_REF] ensure that all these dependences can be inferred by checking the cycle O 8 on 8 vertices. As for the path, these linear dependences only involve flipped and forced tubes, and the coefficients of the flipped tubes may only be 1 or 2 and these of the forces tubes may only be 0, -1 or -2. See Section 6.6 for more details.

It is easy to find an example of a maximal tubing on the tripod such that one of the linear dependences obtained with respect to this maximal tubing does not only involve forced tubes. It implies in particular that the paths and cycles are the only graphs that have this property. It is then tempting to ask whether it is a coincidence that these graphs also are the only ones whose corresponding associahedra also are generalized associahedra. 4.4. Complete graphs. We now consider the nested complex N (K n+1 ) and the compatibility fan D(K n+1 , T • ) for the complete graph K n+1 on n + 1 vertices. As already mentioned in the introduction, the nested complex N (K n+1 ) is isomorphic to the n-dimensional simplicial permutahedron, i.e. the simplicial complex of collections of pairwise nested subsets of [n + 1]. See Figure 3.

It follows by classical results on the permutahedron that the complete graph K n+1 has:

• 2 n -2 proper tubes [OEI10, A000918] (proper subsets of [n]), • n! maximal tubings [OEI10, A000142] (permutations of [n]),
• k! S(n, k) tubings with k tubes, where S(n, k) is the Stirling number of second kind (i.e. the number of ways to partition a set of n elements into k non-empty subsets) [OEI10, A008277]. For two tubes t, t of K n+1 , the compatibility degree of t with t is (t t ) = -1 if t = t , (t t ) = 0 if t and t are distinct and nested, and (t t ) = |t t| otherwise. This connects the compatibility vector d(T • , t) to an alternative combinatorial model for the permutahedron in terms of lattice paths. Since all maximal tubings are equivalent, we can assume that T

• = {[i] | i ∈ [n]}.
For any tube t of K n+1 , we consider the lattice paths φ(t) and ψ(t) whose horizontal steps above abscissa [i, i + 1] lie at height |t [i]| and ([i] t) respectively. These lattice paths are illustrated in Figure 15, where φ(t) is the plain path while ψ(t) is dotted until it meets φ(t). The proof of the following statement is left to the reader.

Proposition 32. (i) For any tube t of K n+1 , the lattice path φ(t) is decreasing from (0, |t|) to (n + 1, 0) with vertical steps of height 0 or 1. (ii) φ is surjective on the decreasing paths ending at (n + 1, 0) with vertical steps of height 0 or 1. (iii) For any tubes t, t of K n+1 , we have t ⊆ t if and only if φ(t ) decreases when φ(t) decreases.

In particular, the paths φ(t) and φ(t ) are then non-crossing. (iv) For a tubing T on K n+1 , the map σ(T)

: i -→ | {t ∈ T | φ(t) has a descent at abscissa i} |+1 is a surjection from [n + 1] to [|T| + 1],
and therefore π(T)

:= j∈[|T|+1] σ -1 (j) is an ordered partition of [n + 1] into |T| + 1 parts.
The map T → π(T) defines an isomorphism form the nested complex N (K n+1 ) to the refinement poset of ordered partitions. (v) For a tube t of K n+1 not in T • , the path ψ(t) is obtained from the path φ(t) by replacing the initial down stairs by an horizontal path at height 0. See Figure 15, where ψ(t) is dotted until it meets φ(t).

Remark 33 (Dual compatibility fan). As discussed in Section 5.2 below, the complementation t → V t defines an automorphism of the nested complex N (K n+1 ), which dualizes the compatibility degree: (t t ) = (V t V t) for any tubes t, t of K n+1 . Therefore, the dual compatibility fans are compatibility fans: for any tubing

T • on K n+1 , D * (K n+1 , T • ) = D(K n+1 , {V t • | t • ∈ T • }).
Remark 34 (Linear dependences). For the complete graph, the linear dependences between compatibility vectors of tubes involved in a flip can already be complicated. However, the coefficients (α, α ) of the flipped tubes in these dependences can only take the following values:

(k, k) with k > 0, or (k, kp) with k, p > 0, or (kp + p, kp) with k, p > 0. 4.5. Stars. We finally consider the nested complex N (X n+1 ) and the compatibility fan D(X n+1 , T • ) for the star X n+1 with n + 1 vertices, i.e. the tree with n leaves 1 , . . . , n all connected to a central vertex denoted * . The graph associahedron Asso(X n+1 ) is called stellohedron. We have represented in Figure 16 two realizations of the 3-dimensional stellohedron.

One easily checks that the star X n+1 has:

• 2 n + n -1 proper tubes [OEI10, A052944] (distinguish tubes containing * or not), • n! n i=0 1 i! maximal tubings [OEI10, A000522] (consider the minimal tube containing * ), • i∈[k] n k -i (i -1)! i S(n -k + i, i) + S(n -k + i, i -
• 4 n! ni=n 1 n i -1 = i≥1 (i + 1
) n /2 i tubings in total (including the empty tubing). This is the number of chains in the boolean lattice on an n-element set [OEI10, A007047] (an immediate bijection is given by the spines of the tubings). We consider the initial maximal tubing T • := { 1 }, . . . , { n } whose tubes are the n leaves of X n+1 . The other 2 n -1 tubes of X n+1 are the tubes containing the central vertex * and some leaves (but not all). The compatibility degree of such a tube t containing * with a tube

{ i } is 0 if i ∈ t and 1 if i / ∈ t.
The compatibility vector d(T • , t) of t with respect to T • is thus given by the characteristic vector of the leaves of X n+1 not contained in t. Moreover, two tubes t, t / ∈ T • are compatible if and only if they are nested (since they both contain the vertex * ). Therefore, the compatibility fan D(X n+1 , T • ) is obtained from the coordinate hyperplan fan by a barycentric subdivision of the positive orthant. Examples in dimension 2, 3 and 4 are gathered in Figure 17.

Remark 35 (Dual compatibility fan). Observe that the compatibility degree of any tube of X n+1 with any leaf of X n+1 belongs to {-1, 0, 1}. Therefore, d(T • , t) = d * (t, T • ) for any tube t, so that the compatibility and dual compatibility fans with respect to the initial tubing T • coincide. This does not hold for arbitrary initial tubings on X n+1 , see Remark 27 and Figure 11 (right).

Remark 36 (Linear dependences). In the special case discussed in this section, all linear dependences between compatibility vectors of tubes involved in a flip are inclusion-exclusion dependences as in the beginning of the proof of Theorem 17 in Section 6.3. The coefficients of the flipped tubes thus always equal 1 while those of the forced tubes (not in the initial tubing T • ) always equal -1.

Remark 37. As pointed out by F. Santos, the stellohedron Asso(X n+1 ) coincides with the secondary polytope of two concentric copies of an (n -1)-dimensional simplex. See Figure 18.

Further topics

In this section, we discuss several further topics in connection to compatibility fans. Note that we only state the results for compatibility fans, but similar statements hold for dual compatibility fans. Section 5.1 studies the behavior of the compatibility fans with respect to products and links. In Section 5.2, we show that most compatibility fans are not linearly isomorphic, which requires a description of all nested complex isomorphisms. Section 5.3 discusses the question of the realization of our compatibility fans as normal fans of convex polytopes. In Section 5.4, we extend our construction to design nested complexes [START_REF] Satyan | Deformations of bordered surfaces and convex polytopes[END_REF]. Finally, we discuss in Section 5.5 the connection of this paper to Laurent Phenomenon algebras [START_REF] Lam | Laurent phenomenon algebras[END_REF][START_REF] Lam | Linear Laurent phenomenon algebras[END_REF].

Products and restrictions.

In all examples that we discussed earlier, we only considered connected graphs. Compatibility fans for disconnected graphs can be reconstructed from those for connected graphs by the following statement, whose proof is left to the reader.

Proposition 38. If G has connected components G 1 , . . . , G k , then the nested complex N (G) is the join of the nested complexes N (G 1 ), . . . , N (G k ). Moreover, for any maximal tubings T • 1 , . . . , T • k on G 1 , .
. . , G k respectively, the compatibility fan D(G, T • ) with respect to the maximal tubing As observed in [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF], all links of graphical nested complexes are joins of graphical nested complexes. The following statement asserts that the compatibility fans reflect this property on coordinate hyperplanes. To be more precise, for a tube t • of G, we denote by G[t • ] the restriction of G to t • and by G t • the reconnected complement of t • in G, i.e. the graph with vertex set V t • and edge set e

T • := T • 1 ∪ • • • ∪ T • k on G is the product of the compatibility fans D(G 1 , T • 1 ), . . . , D(G k , T • k ): D(G, T • ) = D(G 1 , T • 1 ) × • • • × D(G k , T • k ) = {C 1 × • • • × C k | C i ∈ D(G i , T • i ) for all i ∈ [k]} .
∈ V t • 2 | e or e ∪ t • is connected in G . A maximal tubing T • on G containing t • induces maximal tubings T • [t • ] := {t | t ∈ T • , t t • } on the restriction G[t • ] and T • t • := {t t • | t ∈ T • , t ⊂ t • } on the reconnected complement G t • . See Figure 20.
Proposition 39. The link of a tube t • in the nested complex N (G) is isomorphic to the join of the nested complexes N (G[t • ]) and N (G t • ). Moreover, for an initial maximal tubing T • containing t • , the intersection of the compatibility fan D(G, T • ) with the coordinate hyperplane orthogonal to e t • is the product of the compatibility fans

D(G[t • ], T • [t • ]) and D(G t • , T • t • ).
This statement follows from Lemmas 72 and 73 and Theorem 17, proved in Section 6.

• ex = {a, b, d, f, g, h, i, k, l} in the maximal tub- ing T • (left) yields a maximal tubing T • ex [t • ex ] on the restriction G • ex [t • ex ] (middle) and a maximal tubing T • ex t • ex on the reconnected complement G • ex t • ex (right).
5.2. Many compatibility fans. In this section, we show that we obtained many distinct compatibility fans. Following [START_REF] Ceballos | Many non-equivalent realizations of the associahedron[END_REF], we classify compatibility fans up to linear isomorphisms: two fans F, F of R n are linearly isomorphic if there exists an invertible linear map which sends the cones of F to the cones of F . Observe already that if two compatibility fans D(G, T • ) and D(G , T • ) are linearly isomorphic, then the two nested complexes N (G) and N (G ) are (combinatorially) isomorphic, meaning that there is a bijection Φ from the tubes of G to the tubes of G which preserves the compatibility. The converse does not always hold: a nested complex isomorphism can preserve compatibility without preserving the compatibility degree. However, we prove below that the nested complex isomorphisms are so constrained that they all either preserve the compatibility degree and thus induce linear isomorphisms between compatibility fans, or exchange the compatibility and dual compatibility degrees and thus induce linear isomorphisms between compatibility and dual compatibility fans.

In the sequel, we describe all nested complex isomorphisms. Observe first that an isomorphism φ between two graphs G and G automatically induces an isomorphism Φ between the nested complexes N (G) and N (G ) defined by Φ(t) := {φ(v) | v ∈ t} for all tubes t on G. We say that such a nested complex isomorphism Φ is trivial. Trivial isomorphisms clearly preserve compatibility degrees: (Φ(t) Φ(t )) = (t t ) for any tubes t, t on G. We are interested in non-trivial nested complex isomorphisms. We first want to underline two relevant examples.

Example 40. The reader can check that:

(i) The complementation t → V t is a non-trivial automorphism of the nested complex N (K n+1 ) of the complete graph K n+1 . It dualizes the compatibility degree: (V t V t ) = (t t) for any tubes t, t of K n+1 . (ii) The map defined for 1

≤ j ≤ k ≤ n + 1 by [j, k] := [k + 1, n + 1] if j = 1, [j -1, k -1] if j > 1,
is a non-trivial automorphism of the nested complex N (P n+1 ) of the path P n+1 . Indeed, up to conjugation by the bijection δ → t δ of Section 4.2, the map coincides with the (combinatorial) 1-vertex clockwise rotation of the (n + 3)-gon Q n+3 . See Figure 21.

Therefore, has order n + 3, and its iterated powers are explicitly described by

p [j, k] :=      [j -p, k -p] if 0 ≤ p < j, [k -p + 2, n + j -p + 1] if j ≤ p < k + 2, [n + p + j -2k -1, n + p -k -1] if k + 2 ≤ p < n + 3.
In fact, it is shown in [CSZ15, Lemma 2.2] that the automorphism group of the nested complex N (P n+1 ) is the dihedral group generated by the non-trivial automorphism (the

1 2 3 4 6 5 1 2 3 4 6 5 7 0 1 2 3 4 6 5 1 2 3 4 6 5 7 0 t [1] [2] [3] [4] [5] [6] [1, 2] [2, 3] [3, 4] [4, 5] [5, 6] [1, 3] [2, 4] [3, 5] [4, 6] [1, 4] [2, 5] [3, 6] [1, 5] [2, 6] t [2, 6] [1] [2] [3] [4] [5] [3, 6] [1, 2] [2, 3] [3, 4] [4, 5] [4, 6] [1, 3] [2, 4] [3, 5] [5, 6] [1, 4] [2, 5] [6] [1, 5]
Figure 21. The 1-vertex clockwise rotation of the (n + 3)-gon induces a nontrivial automorphism of the nested complex N (P n+1 ). rotation of the (n + 3)-gon Q n+3 ) and the automorphism ↔:

[j, k] → [n + 2 -k, n + 2 -j]
induced by the graph automorphism j → n + 2 -j of P n+1 (the vertical reflection of the (n + 3)-gon Q n+3 ). Note that since the compatibility degree on P n+1 is in {-1, 0, 1}, any nested complex automorphism preserves the compatibility degree (and also dualizes it since it is symmetric).

We now describe a generalization of both cases of Example 40. For

n := {n 1 , . . . , n } ∈ N with n+1 = i∈[ ] (n i +1), define the spider X n as the graph with vertices v i j i ∈ [ ], 0 ≤ j ≤ n i and edges v i j-1 , v i j | i ∈ [ ], j ∈ [n i ] ∪ v i 0 , v i 0 | i = i ∈ [ ] . For 0 ≤ j ≤ k ≤ n i , we denote by v i j , v i k the path between v i j and v i k in X n . Informally, the spider X n consists in paths [v i 1 , v i ni ]
called legs of the spider, each attached to a vertex v i 0 of a clique called body of the spider. See Figure 22. Note that spiders are sometimes called sunlike graphs in the literature.

We now define a non-trivial automorphism Ω of the nested complex N (X n ) of the spider X n . We distinguish two kinds of tubes of N (X n ):

Leg tubes: A tube t disjoint from the body is included in a leg. The map Ω sends t into its image by the transformation which cuts the leg containing t and glues it back to the body by its other endpoint. Formally, for i ∈ [ ] and 1

≤ j ≤ k ≤ n i , Ω v i j , v i k := v i ni+1-k , v i ni+1-j .
Note that Ω sends a leg tube t to a leg tube Ω(t) with |Ω(t)| = |t|. Body tubes: A tube t intersecting the body is the union of segments

v i 0 , v i ki , with -1 ≤ k i ≤ n i (with the convention that [v i 0 , v i -1 ] = ∅). We then define Ω i∈[ ] v i 0 , v i ki := i∈[ ] v i 0 , v i ni-1-ki .
Note that Ω sends a body tube t to a body tube Ω(t) with |Ω(t)| = |V| -|t|.

Figure 22 illustrates the map Ω on different tubes of the spider X {0,3,2,3,0,3,2,3} . Observe that Ω indeed generalizes both non-trivial nested complex automorphisms of Example 40:

(i) The complete graph K n+1 is the spider X {0} n+1 whose legs are all empty. The automorphism Ω of N (X {0} n+1 ) specializes to the complementation t → V t on N (K n+1 ). (ii) The path P n+1 is a degenerate spider whose body can be chosen at different places. Indeed, the path P n+1 coincides with the spider X 1 := X {n} with body {1} and the single leg [2, n + 1], and the automorphism Ω of N (X 1 ) is the composition of the rotation automorphism with the vertical reflection automorphism ↔. Similarly, for any 2 ≤ p ≤ n + 1, the path P n+1 coincides with the spider X p := X {p-2,n+1-p} with body {p-1, p} and legs [1, p -2]

v 0 5 v 0 4 v 0 3 v 0 6 v 0 7 v 0 8 v 0 2 v 1 3 v 1 2 v 2 2 v 1 4 v 2 4 v 3 4 v 2 3 v 3 2 v 1 6 v 2 6 v 3 6 v 1 7 v 2 7 v 1 8 v 2 8 v 3 8 v 0 1 v 0 5 v 0 4 v 0 3 v 0 6 v 0 7 v 0 8 v 0 2 v 1 3 v 1 2 v 2 2 v 1 4 v 2 4 v 3 4 v 2 3 v 3 2 v 1 6 v 2 6 v 3 6 v 1 7 v 2 7 v 1 8 v 2 8 v 3 8 v 0 1
Figure 22. The spider X {0,3,2,3,0,3,2,3} and examples of the action of the nontrivial nested complex isomorphism Ω: the tubing T on the left is sent to the tubing Ω(T) on the right.

and [p + 1, n + 1], and the automorphism Ω of N (X p ) is the composition of p with ↔. Finally, the path P n+1 coincides with the spider X n+2 := X {n} with body {n + 1} and the single leg [n], and the automorphism Ω of N (X n+2 ) is the composition of n+2 with ↔. This actually suggests an alternative description of Ω on arbitrary spiders X n . Namely, Ω is equivalently described by the following steps: shift all leg tubes towards the body, complement all body tubes, delete all edges

v i 0 , v i 0 | i = i ∈ [ ] of the body, replace them by the clique v i ni , v i n i | i = i ∈ [ ]
on the feets of the spider, and finally apply the trivial isomorphism from the resulting spider back to the initial spider. Our original presentation of Ω will nevertheless be easier to handle in the proofs. The following statement is proved in Section 6.5.

Proposition 41. The map Ω is a non-trivial involutive automorphism of the nested complex N (X n ) of the spider X n which dualizes the compatibility degree: (Ω(t) Ω(t )) = (t t).

Remark 42. It follows from Proposition 41 that all dual compatibility fans of a spider X n are also compatibility fans of X n : we have D * (X n , T • ) = D(X n , Ω(T • )) for any tubing T • on X n . Note that we already used this observation for complete graphs in Remark 33.

In fact, these non-trivial automorphisms of the nested complexes of the spiders are essentially the only non-trivial nested complex isomorphisms. The following statements are proved in Section 6.5. Proposition 43. A nested complex isomorphism Φ : N (G) → N (G ) restricts to nested complex isomorphisms N (H) → N (H ) between maximal connected subgraphs H of G and H of G .

Theorem 44. Let G and G be two connected graphs and Φ : N (G) → N (G ) be a non-trivial nested complex isomorphism. Then G and G are spiders and there exists a graph isomorphism ψ : G → G which induces a nested complex isomorphism Ψ :

N (G) → N (G ) (defined by Ψ(t) := {ψ(v) | v ∈ t}) such that the composition Ψ -1 • Φ coincides with the non-trivial nested complex automorphism Ω on N (G).
Corollary 45. For connected graphs G, G , any nested complex isomorphism Φ : N (G) → N (G ) either preserves or dualizes the compatibility degree: either (Φ(t) Φ(t )) = (t t ) for all t, t of G, or (Φ(t) Φ(t )) = (t t) for all t, t of G.

To finish our classification of primal and dual compatibility fans up to linear isomorphisms, it remains to understand when the primal and the dual compatibility fans of G with respect to the same initial maximal tubing are linearly isomorphic. For example, we already observed that (i)

D(P n+1 , T • ) = D * (P n+1 , T • ) for any initial tubing T • on a path P n+1 , see Remark 25, (ii) D(X n+1 , T • ) = D * (X n+1 , T • ) for the initial tubing T • := { 1 }, . . . , { n } of the star X n+1
whose tubes are the n leaves, see Remark 35. These examples extend to all subdivisions of stars. Namely, for n := {n 1 , . . . , n } ∈ N with n = i∈[ ] (n i + 1), define the octopus X n as the graph with vertices * ∪ v i j i ∈ [ ], 0 ≤ j ≤ n i and edges

v i j-1 , v i j | i ∈ [ ], j ∈ [n i ] ∪ * , v i 0 | i ∈ [ ] .
Informally, the octopus X n consists in paths [v i 0 , v i ni ] called legs, each attached to a head * . These graphs are often called starlike graphs in the literature, we use the term octopus to stay in the wildlife lexical field. Note that the path P n+1 is a degenerate octopus where the head can be chosen at any vertex. As for stars, a tube of an octopus X n that does not contain its head * is either compatible or exchangeable with any other tube of X n . Therefore, if T • is a maximal tubing on X n whose tubes do not contain the head * , then the compatibility fan D(X n , T • ) and the dual compatibility fan D * (X n , T • ) coincide. The following lemma states that this only happens in this situation.

Lemma 46. Let G be a connected graph and T • be an initial maximal tubing on G. If D(G, T • ) and D * (G, T • ) are linearly isomorphic, then G is an octopus whose head is contained in no tube of T • .

We finally obtain our classification of primal and dual compatibility fans, whose detailed proof is given in Section 6.5. We first focus on primal compatibility fans and then conclude with both primal and dual compatibility fans together.

Corollary 47. The number of linear isomorphism classes of compatibility fans of a connected graph G is:

(i) the number of triangulations of the regular (n + 3)-gon up to the action of the dihedral group if G = P n+1 is a path, (ii) the number of orbits of maximal tubings on G under graph automorphisms of G otherwise.

Corollary 48. The number of linear isomorphism classes of primal and dual compatibility fans of a connected graph G is:

(i) the number of triangulations of the regular (n + 3)-gon up to the action of the dihedral group if G = P n+1 is a path, (ii) the number of G-automorphism orbits of maximal tubings on G if G is a spider but not a path, (iii) the number of G-automorphism orbits of maximal tubings on G, counted twice if not rooted at * , if G is an octopus with head * but not a path, (iv) twice the number of G-automorphism orbits of maximal tubings on G otherwise.

Remark 49. Not only we obtain many non-isomorphic complete simplicial fan realizations for graphical nested complexes (as stated in Corollary 47), but these realizations cannot be derived from the existing geometric constructions for graph associahedra. Indeed, all previous polytopal realizations of graph associahedra can be obtained by successive face truncations of a simplex [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF] or of a cube [START_REF] Volodin | Cubical realizations of flag nestohedra and a proof of Gal's conjecture for them[END_REF][START_REF] Satyan | Convex polytopes from nested posets[END_REF]. Not all compatibility fans can be constructed in this way. For example, the leftmost compatibility fan of Figure 7 is not linearly isomorphic to the normal fan of a polytope obtained by face truncations of the 3-dimensional simplex or cube. 5.3. Polytopality. In this section, we briefly discuss the polytopality of our compatibility fans for graphical nested complexes. A complete polyhedral fan is said to be polytopal (or regular) if it is the normal fan of a polytope. It is well known that not all complete polyhedral fans (even simplicial) are polytopal. Examples are easily constructed from non-regular triangulations, see e.g. the discussion in [DRS10, Chapter 2].

Polytopality of cluster fans. The polytopality of cluster fans has been studied since the foundations of finite type cluster algebras. For compatibility fans, polytopality was shown for particular initial clusters by F. Chapoton, S. Fomin and A. Zelevinsky [START_REF] Chapoton | Polytopal realizations of generalized associahedra[END_REF] Theorem 51 ([HLT11, [START_REF] Stella | Polyhedral models for generalized associahedra via Coxeter elements[END_REF][START_REF] Pilaud | Brick polytopes of spherical subword complexes and generalized associahedra[END_REF]). The g-vector fan (or Cambrian fan) is polytopal for any acyclic initial cluster in any finite type cluster algebra.

To our knowledge, the polytopality of the dand g-vector fans remains open in all other cases. All these results rely on the following characterization of polytopality for complete simplicial fans, in connection to regular triangulations of vector configurations and to the theory of secondary polytopes [START_REF] Gelfand | Discriminants, resultants and multidimensional determinants[END_REF], see also [START_REF] Loera | Triangulations: Structures for Algorithms and Applications[END_REF]. Equivalent formulations of this characterization appear e.g. in [CFZ02, Lemma 2.1], [Zel06, Proposition 6.3], [HLT11, Theorem 4.1], or [START_REF] Ceballos | Many non-equivalent realizations of the associahedron[END_REF]Lemma 5.4]. Here, we follow the presentation of the first two which fits our previous notations.

Proposition 52. Let F be a complete simplicial fan in R n and let R denote a set of vectors generating its rays (1-dimensional cones). Then the following are equivalent:

(1) F is the normal fan of a simple polytope in (R n ) * ;

(2) There exists a map ω : R → R >0 such that for any two maximal adjacent cones R ≥0 S and R ≥0 S of F with S, S ⊆ R and S {s} = S {s }, we have

α ω(s) + α ω(s ) + r∈S∩S β r ω(r) > 0,
where

α s + α s + r∈S∩S β r r = 0
is the unique (up to rescaling) linear dependence with α, α > 0 between the rays of S ∪ S . Under these conditions, F is the normal fan of the polytope defined by To settle this conjecture, the hope would be to apply the characterization of polytopality for complete simplicial fans presented in Proposition 52. Besides finding an explicit function ω on the compatibility vectors of the tubes of a graph, our main issue is that we do not control the details of the linear dependence between the compatibility vectors of the tubes involved in a flip. See the proof of Theorem 17 in Section 6.3.

{φ ∈ (R n ) * | φ | r ≤ ω(r) for all r ∈ R} .
To support Conjecture 53, we have studied the polytopality of the compatibility fans of the specific families of graphs discussed in Section 4. We show in Section 6.6 that Conjecture 53 holds for paths and cycles.

Theorem 54. All compatibility and dual compatibility fans of paths and cycles are polytopal.

Note that the case of paths is covered by the results of [CSZ15, Section 5] presented in Theorem 50. For cycles, the result was unknown except for the bipartite initial tubing by the results of [START_REF] Chapoton | Polytopal realizations of generalized associahedra[END_REF] on type B and C cluster algebras. Via the correspondences given in Propositions 23 and 28, Theorem 54 translates to the following relevant property of d-vector fans.

Corollary 55. In types A, B and C cluster algebras, the d-vector fan with respect to any initial cluster (acyclic or not) is polytopal.

We were not able to settle Conjecture 53 for arbitrary graphs. We believe that this question is worth investigating. As already mentioned, it requires a better understanding of all linear dependences between the compatibility vectors of the tubes involved in a flip.

In another direction, we checked empirically that all 3-dimensional compatibility and dual compatibility fans of Section 4.1 and Figure 8 are polytopal. Using the characterization given in Proposition 52, it boils down to check the feasibility of (many) linear programs.

Finally, as a curiosity and to conclude this polytopality section on a recreative note, we provide a polytopal realization of the compatibility fan for the star X n+1 with respect to the initial tubing T • := { 1 }, . . . , { n } whose tubes are the n leaves of X n+1 . We first observe that this fan is linearly isomophic to the fan G(G) of Theorem 9. Therefore, it can be realized by an affine transformation of the graph associahedra constructed in Theorem 11. Here, we prefer to give a direct construction with integer coordinates. We provide both the vertex and the facet descriptions of this realization. On the one hand, for each maximal tubing T on X n+1 we define a point x(T) ∈ R n whose ith coordinate is the cardinality of the inclusion minimal tube of T ∪ {V} containing the leaf i minus 1. The set {x(T) | T maximal tubing on X n+1 } is the orbit under permutation coordinates of the set i>k i e i 0 ≤ k ≤ n . On the other hand, for a tube t of X n+1 containing the central vertex * , we observed earlier that the compatibility vector of t with respect to T • is the characteristic vector of the leaves of X n+1 not contained in t.

Let f (k) := n j=k j = 1 2 (n + k)(n + 1 -k) and define a half-space H ≥ (t) of R n by H ≥ (t) := x ∈ R n d(T • , t) | x ≤ f (|t|) = x ∈ R n i∈[n] i∈t x i ≤ f (|t|) .
Finally, for the tubes of the initial tubing T • , we define

H ≥ ({ i }) := {x ∈ R n | d(T • , { i }) | x ≤ 0} = {x ∈ R n | x i ≥ 0} .
Proposition 56. The compatibility fan D(X n+1 , T • ) for the initial tubing T • := { 1 }, . . . , { n } whose tubes are the n leaves of X n+1 is the normal fan of the n-dimensional simple polytope defined equivalently as

• the convex hull of the points x(T) for all maximal tubings T on X n+1 , or • the intersection of the half-spaces H ≥ (t) for all tubes t of X n+1 .

The proof of this statement is given in Section 6.6. As an illustration, the 3-dimensional stellohedron defined in Proposition 56 is represented in Figure 16 (right). Figure 23 represents two Schlegel diagrams (see [Zie95, Lecture 5] for definition) for the 4-dimensional stellohedron defined in Proposition 56. In both pictures, we have distinguished two particular facets:

• The red facet corresponds to all tubings containing the tube { * }. Since the reconnected complement of { * } in X 5 is the complete graph K 4 , it has the combinatorics of the permutahedron. In fact, by definition of our polytopal realization, this facet is the classical permutahedron, obtained as the convex hull of the orbit of i∈[4] i e i under permutation of the coordinates. • The blue facet corresponds to all tubings containing the tube { }, where is the bottom left leaf of X 5 . This facet contains the initial tubing T • at the back. Note that there are 4 isometric facets to this blue facet, corresponding to the four leaves of X 5 . This is visible in Figure 23 (right). The blue (resp. red) facet is the projection facet on the left (resp. right) picture.

Remark 57. To conclude, observe that we could have replaced the function f in the definition of the half-spaces H ≥ (t) by any concave function. This follows from Proposition 52 since the linear dependence between the compatibility vectors of the tubes of T ∪ T is given for any adjacent maximal tubings T, T on X n+1 distinct from T • such that T {t} = T {t } by

d(T • , t) + d(T • , t ) = d(T • , t) + d(T • , t)
where t := t ∩ t and t := t ∩ t (which are tubes of X n+1 ). Details are left to the reader.

5.4. Design nested complex. Generalizing graphical nested complexes, S. Devadoss, T. Heath and C. Vipismakul introduced design nested complexes in [DHV11, Section 5]. To define these complexes, one considers design tubes of G, which are of two types:

• the round tubes are usual tubes of G (including the connecting components of G),

• the square tubes are just single nodes of G. We denote by v the square tube containing v, and still denote round tubes as sets. Two design tubes are compatible if

• they are both round tubes and they are either nested, or disjoint and non-adjacent,

• or at least one of them is a square tube and they are not nested. The design nested complex of G is the simplicial complex N (G) of sets of pairwise compatible design tubes of G. Examples are given in Figure 24. By definition, the nested complex N (G) is (isomorphic to) the subcomplex of the design nested complex N (G) involving none of the square tubes, or equivalently containing all improper round tubes.

For a design tube t of G, set

g (t) := v∈t e v if t is a round tube, -e v
if t is the square tube {v}.

For a tubing T on G, define g (T) := {g (t) | t ∈ T}. These vectors again support a complete simplicial fan realization of the design nested complex N (G).

Theorem 58 ([DHV11]

). For any graph G, the collection of cones

G (G) := {R ≥0 g (T) | T tubing on G} is a complete simplicial fan of R V , called design nested fan of G, which realizes N (G).
By definition, the g vector of a round tube t is just the characteristic vector of t. Therefore, the non-negative part of the design nested fan G (G) projects to the nested fan G(G) defined in Section 2.3. Using ideas similar to the construction of the graph associahedra Asso(G) realizing G(G), S. Devadoss, T. Heath and C. Vipismakul prove that G (G) is as well polytopal.

Theorem 59 ([DHV11]

). The design nested fan is the normal fan of a polytope obtained from the cube by iterated face truncations.

We denote this polytope by Asso (G) and call it design graph associahedron (although it is called graph cubeahedron in [START_REF] Satyan | Deformations of bordered surfaces and convex polytopes[END_REF]). Observe that the face of Asso (G) corresponding to the tubing formed by the connected components of G coincides with the graph associahedron Asso(G). Figure 24 illustrates the design P 3 -associahedron and the design K 3 -associahedron. In this figure, the attentive reader should recognize different standard graph associahedra: on the one hand, the front 2-dimensional faces of Asso (P 3 ) and Asso (K 3 ) are respectively Asso(P 3 ) and Asso(K 3 ), and on the other hand, the design graph associahedra Asso (P 3 ) and Asso (K 3 ) themselves turn out to coincide respectively with Asso(P 4 ) and Asso(X 4 ) (see Example 62). Starting from dimension 4, most design graph associahedra are not standard graph associahedra (see Proposition 64). This section aims at showing that our compatibility fan construction extends to the design nested complex. That is, we produce a complete simplicial fan realizing the design nested complex from any initial maximal design tubing. Interestingly, we will see in Remark 69 that the compatibility fan associated to the specific maximal design tubing consisting of all square tubes coincides with the design nested fan. This provides a relevant connection between our construction and the classical constructions [CD06, FS05, Dev09, Zel06] for graph associahedra.

Observe that a square tube is compatible with all design tubes not containing it and exchangeable with all design tubes containing it. Definition 12 of compatibility degree thus naturally extends on all pairs of design tubes as follows.

Definition 60. For two design tubes t, t of G, the compatibility degree of t with t is By construction, this compatibility degree still satisfies the conclusions of Proposition 14 and thus measures the incompatibility between design tubes. We then define as usual the compatibility vector of a design tube t of G with respect to an initial maximal design tubing T

(t t ) =          -1 if t =
• := {t • 1 , . . . , t • n } as the integer vector d(T • , t) := [(t • 1 t), . . . , (t • n t)
] and the compatibility matrix of a design tubing T := {t 1 , . . . , t m } on G with respect to T • as the matrix d(T

• , T) := [(t • i t j )] i∈[n],j∈[m]
. We extend Theorem 17 in the following statement, whose proof is sketched in Section 6.7.

Theorem 61. For any graph G and any maximal design tubing T • on G, the collection of cones D (G, T • ) := {R ≥0 d(T • , T) | T design tubing on G} is a complete simplicial fan which realizes the design nested complex N (G). We call it the design compatibility fan of G with respect to T • .

Using the same duality trick as in the proof of Theorem 21, the reader can obtain as well dual design compatibility fans. Figure 27. An isomorphism from the design nested complex of a complete graph with 5 vertices (left) to the nested complex of a star with 6 vertices (right).

Figure 28. An isomorphism from the design nested complex of a path with 5 vertices (top) to the nested complex of a path with 6 vertices (bottom).

Concerning isomorphisms, we have similar results as in Section 5.2. Notice first that the conclusions of Proposition 43 still hold for design nested complexes. We can thus restrict our discussion to design nested complexes of connected graphs. We first compare design and standard nested complexes, starting with the following examples.

Example 62. The reader can check that:

(i) The design nested complex N (K n ) is isomorphic to the standard nested complex N (X n+1 ).

A natural isomorphism sends a square tube v of K n to the tube {v} of X n+1 , and a round tube t of K n to the tube { * } ∪ ([n] t) of X n+1 (where * is the central vertex). See Figure 27. (ii) The design nested complex N (P n ) is isomorphic to the standard nested complex N (P n+1 ).

A natural isomorphism sends a square tube v of P n to the tube {v + 1, . . . , n + 1} of P n+1 , and a round tube t of P n to the tube t of P n+1 . See Figure 28. We denote this isomorphism by Π : N (P n ) → N (P n+1 ).

We now describe a generalization of both cases of Example 62. We consider the spiders and octopuses defined in Section 5.2: for n := {n 1 , . . . , n } ∈ N with n = i∈[ ] (n i + 1),

• the spider X n has legs [v i 1 , v i ni ] attached to its body formed by a complete graph on {v i 0 } i∈[ ] ,

• the octopus X n has legs [v i 0 , v i ni ] attached to its head formed by a single vertex * . We now define an isomorphism Ω from the design nested complex N (X n ) of the spider X n to the nested complex N (X n ) of the octopus X n . We distinguish three kinds of tubes of N (X n ):

Square tubes: for i ∈ [ ] and j ∈ [0, n i ], Ω(v i j ) := v i 0 , v i ni-j , Leg tubes: for i ∈ [ ] and 1 ≤ j ≤ k ≤ n i , Ω v i j , v i k := v i ni+1-k , v i ni+1-j , Body tubes: for -1 ≤ k i ≤ n i (i ∈ [ ]), Ω i∈[ ] v i 0 , v i ki := { * } ∪ i∈[ ] v i 0 , v i ni-1-ki .
Figure 29 illustrates the map Ω on different tubes of the spider X {0,3,2,3,0,3,2,3} . Observe that Ω indeed generalizes both isomorphisms of Example 62:

(i) We have K n = X {0} n while X n+1 = X {0} n , and the isomorphism Ω : N (X {0} n ) → N (X {0} n ) coincides with the isomorphism of Example 62 (i). (ii) We have P n = X {n} while P n+1 = X {n} , and the isomorphism Ω : N (X {n} ) → N (X {n} ) coincides with the isomorphism Π of Example 62 (ii) up to the automorphisms and ↔ of the nested complex N (X {n} ) described in Example 40 (ii). More precisely if we consider the leftmost vertex of P n as the body of X {n} and the leftmost vertex of P n+1 as the head of X {n} , then one can check that • Ω = ↔ • Π. The following statement is left to the reader. The proof is similar to that of Proposition 41.

v 0 5 v 0 4 v 0 3 v 0 6 v 0 7 v 0 8 v 0 2 v 1 3 v 1 2 v 2 2 v 1 4 v 2 4 v 3 4 v 2 3 v 3 2 v 1 6 v 2 6 v 3 6 v 1 7 v 2 7 v 1 8 v 2 8 v 3 8 v 0 1 v 0 5 v 0 4 v 0 3 v 0 6 v 0 7 v 0 8 v 0 2 v 1 3 v 1 2 v 2 2 v 1 4 v 2 4 v 3 4 v 2 3 v 3 2 v 1 6 v 2 6 v 3 6 v 1 7 v 2 7 v 1 8 v 2 8 v 3 8 v 0 1 * Figure 29
. An isomorphism from the design nested complex of the spider X {0,3,2,3,0,3,2,3} (left) to the nested complex of the octopus X {0,3,2,3,0,3,2,3} (right).

Proposition 63. The map Ω is an isomorphism from the design nested complex N (X n ) of the spider X n to the nested complex N (X n ) of the octopus X n which dualizes the compatibility degree:

( Ω(t) Ω(t )) = (t t).

The following proposition, proved in Section 6.8, states that Ω is essentially the only isomorphism between design and standard nested complexes.

Proposition 64. Let Ḡ and G be two connected graphs and Φ : N ( Ḡ) → N (G) be a simplicial complex isomorphism. Then Ḡ is a spider X n while G is an octopus X n and Φ coincides with Ω up to composition with a nested complex automorphism of N (G) (described in Theorem 44).

We now classify combinatorial isomorphisms of design nested complexes. As for nested complexes, a graph isomorphism φ : G → G induces a trivial design nested complex isomorphism Φ : N (G) → N (G ), defined by Ψ(t) := {ψ(v) | v ∈ t} and Ψ(v ) := ψ(v) , which preserves compatibility degrees. We again focus on non-trivial design nested complex isomorphisms. We first underline two examples.

Example 65. The reader can check that:

(i) For the star X n with central vertex * , the map which preserves the square tube * , exchanges the square tube v with the round tube {v}, and exchanges any other round tube t with the round tube ([n] t) ∪ { * }, is a non-trivial design nested complex isomorphism of N (X n ). (ii) For p ∈ [n+3], the conjugation Π • p • Π -1 of the automorphism p : N (P n+1 ) → N (P n+1 ) of Example 40 (ii) by the isomorphism Π : N (P n ) → N (P n+1 ) of Example 62 (ii) is a nontrivial design nested complex isomorphism of N (P n ). Note that these two isomorphisms send some square tubes to round tubes and thus are non-trivial.

We now describe a generalization of both cases of Example 65. Namely, we define an automorphism Ω of the design nested complex N (X n ) of the octopus X n for any n := {n1, . . . , n } ∈ N with n = i∈[ ] (n i + 1) as follows:

Square tubes: for i ∈ [ ] and j ∈ [0, n i ], Ω (v i j ) := v i 0 , v i ni-j
and Ω ( * ) := * , Leg tubes:

for i ∈ [ ] and 0 ≤ k ≤ n i , Ω v i 0 , v i k := v i ni-k , for i ∈ [ ] and 1 ≤ j ≤ k ≤ n i , Ω v i j , v i k := v i ni+1-k , v i ni+1-j , Head tubes: for -1 ≤ k i ≤ n i (i ∈ [ ]), Ω { * }∪ i∈[ ] v i 0 , v i ki := { * }∪ i∈[ ] v i 0 , v i ni-1-ki .
Figure 30 illustrates the map Ω on different tubes of the octopus X {0,3,2,3,0,3,2,3} . The reader is invited to check that Ω indeed generalizes the non-trivial automorphisms of Example 65. The following statement is also left to the reader. The proof is similar to that of Proposition 41.

Proposition 66. The map Ω is a non-trivial involutive automorphism of the design nested complex N (X n ) of the octopus X n which dualizes the compatibility degree: (Ω (t) Ω (t )) = (t t).

The following theorem, proved in Section 6.8, states that Ω is essentially the only non-trivial design nested complex isomorphism.

v 0 5 v 0 4 v 0 3 v 0 6 v 0 7 v 0 8 v 0 2 v 1 3 v 1 2 v 2 2 v 1 4 v 2 4 v 3 4 v 2 3 v 3 2 v 1 6 v 2 6 v 3 6 v 1 7 v 2 7 v 1 8 v 2 8 v 3 8 v 0 1 * v 0 5 v 0 4 v 0 3 v 0 6 v 0 7 v 0 8 v 0 2 v 1 3 v 1 2 v 2 2 v 1 4 v 2 4 v 3 4 v 2 3 v 3 2 v 1 6 v 2 6 v 3 6 v 1 7 v 2 7 v 1 8 v 2 8 v 3 8 v 0 1 * Figure 30
. The octopus X {0,3,2,3,0,3,2,3} and examples of the action of the nontrivial design nested complex isomorphism Ω : the design tubing T on the left is sent to the design tubing Ω (T) on the right.

Theorem 67. Let G and G be two connected graphs and Φ : N (G) → N (G ) be a non-trivial design nested complex isomorphism. Then G and G are octopuses and there exists a graph isomorphism ψ : G → G which induces a design nested complex isomorphism Ψ :

N (G) → N (G ) (defined by Ψ(t) := {ψ(v) | v ∈ t} and Ψ(v ) := ψ(v)
) such that the composition Ψ -1 • Φ coincides with the non-trivial design nested complex automorphism Ω on N (G).

We conclude that we get many design compatibility fans (up to linear isomorphism).

Corollary 68. If a connected graph G is not an octopus, then the number of linear isomorphism classes of primal (resp. dual) design compatibility fans of G is the number of orbits of maximal design tubings on G under graph automorphisms of G.

Finally, as for the compatibility fan, we do not know in general whether the design compatibility fan is or not polytopal. Nevertheless, we know it for the following initial tubing.

Remark 69. Consider the maximal tubing T of a graph G consisting of all square tubes of G. By definition of the compatibility degree with square tubes, the compatibility vector of a square tube {v} is just -e v while the compatibility vector of a round tube t with respect to T is just the characteristic vector of t. Therefore, the design compatibility fan D (G, T ) coincides with the design nested fan G (G). It follows that D (G, T ) is the normal fan of the design graph associahedron Asso (G) for any graph G. In fact, as the linear dependencies among the compatibility vectors with respect to the initial tubing T are simply described, a direct computation shows that the map ω defined by ω(t) = 3 |V| |t| -3 |t| for a round tube and ω(v ) = C for a sufficiently large constant C provides a suitable weight function for Condition (2) of Proposition 52.

Laurent Phenomenon algebras.

To conclude, we discuss our construction with respect to the framework of Laurent Phenomenon algebras developed by T. Lam and P. Pylyavskyy in [START_REF] Lam | Laurent phenomenon algebras[END_REF][START_REF] Lam | Linear Laurent phenomenon algebras[END_REF]. The definition of these algebras is similar to that of cluster algebras but allows more flexibility for the variable mutation. Namely, the cluster variables of these algebras are still obtained by a mutation process from an initial cluster X • , but the mutated variable depends upon some mutation polynomials which are themselves updated along the mutations. We refer to [START_REF] Lam | Laurent phenomenon algebras[END_REF] for the precise rules directing these variable and polynomial mutations.

Since the construction is more flexible, it yields more general algebras and cluster complexes. To our knowledge, there is no classification of the finite type Laurent Phenomenon algebras, in contrast to the case of classical cluster algebras. However, an important subclass is the class of linear Laurent Phenomenon algebras discussed in [START_REF] Lam | Linear Laurent phenomenon algebras[END_REF], where the mutation polynomials of a given cluster are all linear. A striking fact is that all graphical nested complexes appear as cluster complexes for some linear Laurent Phenomenon algebras. Namely, T. Lam and P. Pylyavskyy associate to each graph G a Laurent Phenomenon algebra A(G) whose cluster complex is isomorphic to the design nested complex N (G) discussed in Section 5.4. The nested complex N (G) is thus isomorphic to the cluster complex of the linear Laurent Phenomenon algebra obtained by freezing in A(G) the variables corresponding to square tubes (see [LP12a, Section 3.5]).

As the name suggests, Laurent Phenomenon algebras still exhibits the Laurent Phenomenon. Each cluster variable x can be expressed as a Laurent polynomial in terms of the cluster variables x • 1 , . . . , x • n of the initial cluster X • . Define the d-vector of x with respect to X • as the vector d(X • , x) whose ith coordinate is the exponent of the initial variable x • i in the denominator of x. It is then tempting to extend the construction of the d-vector fan of S. Fomin and A. Zelevinsky [START_REF] Fomin | Cluster algebras. II. Finite type classification[END_REF] to all Laurent Phenomenon algebras: Question 70. Given a finite type Laurent Phenomenon algebra A and an initial cluster seed X • of A, do the cones generated by the d-vectors with respect to X • of all collections of compatible cluster variables in A always form a complete simplicial fan realizing the cluster complex of A?

When studying this question, we encountered several difficulties that we want to underline here:

• Although similar to the problem addressed in this paper, we have not been able to prove or disprove Question 70 even for the specific case of linear Laurent Phenomenon algebras arising from nested complexes of graphs. In contrast to our combinatorial definition of compatibility degree among tubes, it is difficult to track the denominator vectors along the mutation process. In particular, expressing explicitly the linear dependence among the denominator vectors of the cluster variables involved in a mutation seems out of reach at the moment. • One of the main difficulties is that, even in some finite cases, an entry of the denominator vector of a variable can depend on the whole initial cluster, not only on the variable corresponding to that entry. Namely, in certain linear Laurent Phenomenon algebras, one can find cluster variables x, x • and initial clusters X • , X • both containing x • such that the exponent of x • in the denominator of x is different when computed with respect to X • or with respect to X • . In this sense, the denominator vectors are not anymore compatibility vectors arising from a compatibility degree between cluster variables. • Even worst, given an initial cluster X • , an initial variable x • and a cluster variable x not in X • but compatible with x • , the exponent of x • in the denominator x, when expanded in the variables of X • can be nonzero. • In particular, the denominator vectors in the linear Laurent Phenomenon algebra A(G)

do not always coincide with our compatibility vectors on tubes of G. Despite all these difficulties, we hope that the study of the linear Laurent Phenomenon algebras arising from (design) nested complexes of graphs can help to answer Question 70. Since nonisomorphic Laurent Phenomenon algebra may have isomorphic cluster complexes (the cyclohedron is an example [LP12b, Section 6.2]), another simpler question would be to look for other Laurent Phenomenon algebras whose denominators interpret our compatibility degrees.

Question 71. For which graph G does there exist a Laurent Phenomenon algebra whose cluster complex is isomorphic to the nested complex Asso(G) (resp. to the design nested complex Asso (G)) and whose denominators are given by the (primal or dual) compatibility degrees defined in this paper?

Proofs

This section contains all proofs of our results. Some of them require additional technical steps, which motivated us to separate them from the rest of the paper. We also hope that the many examples treated in Section 4 help the reader's intuition throughout these proofs. 6.1. Compatibility degree (Proposition 14). We start with the proof that our graphical compatibility degree encodes compatibility and exchangeability between tubes. We show the three points of Proposition 14:

• (t t ) < 0 ⇐⇒ (t t) < 0 ⇐⇒ t = t .
This is immediate from the definition since the compatibility degree between two distinct tubes is either a cardinal or 0.

• (t t ) = 0 ⇐⇒ (t t) = 0 ⇐⇒ t and t are compatible. Consider two distinct tubes t, t of G. If they are compatible, then either t ⊆ t , or t ⊆ t, or t and t are non-adjacent. In the first case, (t t ) = 0 by the last line of Definition 12 of the compatibility degree. In the last two cases, (t t ) = |{neighbors of t in t t}| = |∅| = 0. Conversely, if (t t ) = 0, then either t has no neighbor in t , or t ⊆ t, or t ⊆ t , so that the two tubes are compatible.

• (t t ) = 1 = (t t) ⇐⇒ t and t are exchangeable. The ⇐ part follows from the explicit flip description in Proposition 7. Indeed, assume that t and t are exchangeable, let t := t ∪ t , and let T, T be two adjacent maximal tubings on G such that T {t} = T {t }. Since t is the connected component of G[t λ(t, T)] containing λ(t, T), the root λ(t, T) is the unique neighbor of t in t t. Therefore, (t t ) = 1, and (t t) = 1 by symmetry.

Assume conversely that (t t ) = 1 = (t t). Since (t t) = 1, there exists a unique neighbor r of t in t t . Similarly, there exists a unique neighbor r of t in t t. We want to find two adjacent maximal tubings T, T on G such that T {t} = T {t }. We start with the forced tubes (see the end of Section 2.2): we define t := t ∪ t and we let s 1 , . . . , s be the connected components of t {r, r }. We choose an arbitrary maximal tubing S i on G[s i ] for each i, and an arbitrary maximal tubing S on G containing t. The set of tubes

R := {t, s 1 , . . . , s } S 1 • • • S {s | s ∈ S, s ⊆ t} .
is clearly a tubing, and is compatible with both t and t . We now compute the cardinality of R.

Observe first that |S| = |V| -|κ(G)| so that | {s | s ∈ S, s ⊆ t} | = |V| -|κ(G)| -|t| since t is a tube of G. Moreover, |S i | = |s i | -1 since s i is a tube, and i |s i | = | i s i | = |t {r, r }| = |t| -2. We conclude that |R| = (1 + ) + (|t| -2 -) + (|V| -|κ(G)| -|t|) = |V| -|κ(G)| -1
Therefore, R is a ridge of the nested complex N (G), so that T := R ∪ {t} and T := R ∪ {t } are maximal tubings related by the flip of t into t .

Restriction on coordinate hyperplanes (Proposition 39)

. We now state two lemmas needed in the proofs of Theorem 17. They have essentially the same content as Proposition 39, except that they focus on compatibility vectors (rays) and not on the other cones of the compatibility fan since Theorem 17 is not proved yet. In particular, they will imply Proposition 39 once Theorem 17 will be established. Remember that for a tube t • of G, we denote by G[t • ] the restriction of G to t • and by G t • the reconnected complement of t • in G, defined as the graph with vertex set V t • and edge set e

∈ V t • 2 | e or e ∪ t • is connected in G .

Lemma 72 ([CD06]

). For a tube t • of G, the map

s -→ s := s if s t • s t • if s t • or s ∩ t • = ∅
between the tubes of G compatible with t • and the tubes of G := G[t • ] G t • defines an isomorphism between the link of t • in the nested complex N (G) and the nested complex N ( G).

We denote by T := t t ∈ T the image of a tubing T on G. This map actually preserves the compatibility degrees between tubes and the compatibility vectors.

Lemma 73. Let t • be a tube of G. The map s → s between the link of t • in the nested complex N (G) and the nested complex N ( G) of the graph G := G[t • ] G t • defined in Lemma 72 preserves the compatibility degree: (t t ) = ( t t ) for any tubes t, t of G compatible with t • . Therefore, for any maximal tubing T • on G containing t • and any tube t of G compatible with t • , the compatibility vector d( T • , t) is obtained from the compatibility vector d(T • , t) by deletion of its vanishing t • -coordinate.

Proof. If t and t are compatible, so are t and t by Lemma 72, thus the result follows from Proposition 14. We can therefore assume that t and t are incompatible, so as t and t . Therefore, the compatibility degrees (t t ) and ( t t ) actually count neighbors. However, it follows immediately from the definitions of the graph G and of the map s → s that the neighbors of t in t t are precisely the neighbors of t in t t. This proves the equality between the compatibility degrees. The equality between the compatibility vectors follows coordinate by coordinate.

Compatibility fan (Theorem 17).

In order to show that the cones of the compatibility matrices of all tubings on G form a complete simplicial fan, we need the following refinement.

Theorem 74. For any graph G and any maximal tubing T • on G, the compatibility vectors with respect to T • have the following properties.

Span Property: For any tube u of G, the span of {d(T • , s) | s ∈ T, s ⊆ u}, for a maximal tubing T on G containing u, is independent of T.

Flip Property: For any two adjacent maximal tubings T, T on G with T {t} = T {t }, there exists a linear dependence

α d(T • , t) + α d(T • , t ) + s∈T∩T β s d(T • , s) = 0
between the compatibility vectors of T ∪ T with respect to T • which is: Separating: the hyperplane spanned by {d(T Observe also that we do not need to prove that the linear dependence between the compatibility vectors of T ∪ T is unique: it is a consequence of Proposition 5 once we know the Separating Flip Property.

Before entering details, let us sketch the general idea of the proof of Theorem 74. We seek for a linear dependence between the compatibility vectors of the tubes of T ∪ T with respect to the initial tubing T • , that is, for a linear relation satisfied by their compatibility degrees with any tube of T • . There are simple combinatorial relations between the compatibility degrees of the tubes of T ∪ T with all tubes of T • not contained in t. Our strategy is to start from such a relation and adapt it iteratively such that it holds for the other tubes of T • as well. This transformation is done in two steps:

• We first deal with the tubes of T • contained in t and maximal for this property. They determine the coefficients of the linear dependence on the forced tubes • For the remaining tubes of T • , we need to make successive corrections to the linear dependence. We first get an explicit linear dependence assuming that T ∩ T contains certain suitable tubes included in t. We then use inductively the Span Property and the Local Flip Property to get an implicit linear dependence in general. The key of the proof is that our transformation increases the set of tubes of T • for which the relation between the compatibility degrees of the tubes of T ∪ T is valid.

We now start the formal proof. We proceed by induction on the dimension of the nested complex N (G). It is immediate when this dimension is 0. We now consider an arbitrary graph G and assume that we have shown Theorem 74 and thus Corollary 19 for any graph H such that dim(N (H)) < dim(N (G)). Given a exchangeable pair of tubes t, t of G, our first objective is to exhibit separating and local linear dependences for some adjacent maximal tubings T, T on G such that T {t} = T {t }. We will show later the Span Property and use it to prove that the linear dependence is separating and local for all adjacent maximal tubings T, T on G such that T {t} = T {t }.

Lemma 75. For any two exchangeable tubes t, t of G, there exists adjacent maximal tubings T, T on G such that T {t} = T {t } and a linear dependence between the compatibility vectors of the tubes of T ∪ T which is both separating and local.

Proof. We fix some notations for the forced tubes of the exchangeable pair {t, t }. First recall that since t and t are exchangeable, the tube t (resp. t ) has a single neighbor in t t (resp. in t t ) that we denote by r (resp. r ). We set t := t ∪ t , and we denote by t 1 , . . . , t k the connected components of G[t ∩ t ], by a 1 , . . . , a the connected components of G[t (t ∪ {r})], and by a 1 , . . . , a the connected components of G[t (t ∪ {r })]. Although it is not a tube, we set t := i∈[k] t i and we abuse notation to write (t • t) for i∈[k] (t • t i ) and similarly d(T • , t) for i∈[k] d(T • , t i ). We will use in the same way the notations a and a .

We need to distinguish different cases, for which the linear dependences are slightly different, while the proofs are essentially identical. To simplify the discussion, we assume in Cases (A), (B) and (C) below that t, t / ∈ T • and that no tube of T • is compatible with both t and t . At the end of the proof, Cases (D) and (E) show how to restrict to these hypotheses.

(A) A first relation. Consider a tube t • of T • not contained in t. We claim that (t • t) + (t • t ) = (t • t) + (t • t).
Indeed, since t • ⊆ t, these four compatibility degrees actually count neighbors of t • . The formula thus follows from inclusion-exclusion principle since t = t ∪ t and t = t ∩ t .

There are other tubes of T • satisfying this relation. Indeed, consider a tube t • in T • included in t which contains r but does not contain nor is adjacent to r . Then t • t t so that (t • t) = (t • t) = 0. Moreover, t • is incompatible with t and all t 1 , . . . , t k . Since r is not adjacent to t • , all neighbors of t • in t t • are in t t • . Therefore (t • t ) = (t • t). The relation follows. Similarly, the relation follows if t • contains r and does not contain nor is adjacent to r.

If all tubes of T • included in t satisfy the previous conditions, we have obtained a separating and local linear dependence:

(1)

d(T • , t) + d(T • , t ) = d(T • , t) + d(T • , t).
This linear dependence would be valid for any adjacent maximal tubings T, T on G such that T {t} = T {t } since the tube t and the tubes t are forced in any such pair. Unfortunately, these conditions do not always hold for all tubes of T • . In this case, we will therefore adapt the linear dependence (1) to cover all possible configurations for the tubes of T • .

(B) No tube of T • contained in t contains both r and r . Except if the linear dependence (1) is valid, there must exist w.l.o.g. a tube t • ∈ T • contained in t, containing r and adjacent to r . Choose t • maximal for these properties. Since we have assumed that no tube of T • is compatible with both t and t , all tubes of T • included in t • contain r. These tubes thus form a nested chain t

• = t • 0 t • 1 • • • t • p = {r}. For i ∈ [p], define t i to be the connected component of G[t • i-1 {r}] containing the singleton t • i-1 t • i . Set α := (t • a) + (t • t ) and α := (t • t) + (t • a)
, and define inductively β 1 , . . . , β p by

β i = α (t • i t ) -α (t • i t) -(α -α )(t • i a) - j∈[i-1] β j (t • i t j ).
We claim that

(2) α d(T • , t) + α d(T • , t ) = α d(T • , t) + α d(T • , t) + (α -α ) d(T • , a) + i∈[p] β i d(T • , t i ).
To prove it, we check this linear dependence coordinate by coordinate.

Observe first that (t

• i t) = (t • i t) = 0 for all 0 ≤ i ≤ p since t • i t ⊆ t.
Moreover, for all i < j, we have by definition t j t • i , so that (t • i t j ) = 0. Finally, we have (t

• i t i ) = 1 since t • i
and t i are incompatible and the only neighbor of t

• i in t i t • i is the singleton t • i-1 t • i .
Therefore, Relation (2) holds for t • by definition of α and α and for t • i by definition of β i . Consider now a tube s • of T • not included in t • . Suppose that s • is included in t. Then s • contains precisely one of r and r (it cannot contain both by assumption (B), and it cannot avoid both as it would be compatible with both t and t ). If s • contains r, it contains t • and therefore equals t • by maximality of the latter. Otherwise, s • contains r , thus is adjacent to t • , thus contains it (by compatibility), and thus contains r, a contradiction. We therefore obtained that s • is not included in t, so that all compatibility degrees (s • t), (s • t), (s • t) and (s • a) actually count neighbors of s • . Observe now that r cannot be adjacent to s • (except if it belongs to s • ), since r belongs to t • which is compatible with s • . Therefore, we have

(s • t) = (s • t) + (s • a) and (s • t ) = (s • t) -(s • a),
since t = t a {r} and t = t a {r}. Finally, since any t i is contained in t • , it is compatible with s • , so that (s • t i ) = 0 by Proposition 14. Combining these equalities, we obtain that Relation (2) holds for any s • ∈ T • . We found a linear dependence between the compatibility vectors of {t, t , t} ∪ t ∪ a ∪ {t i | i ∈ [p]} with respect to the initial tubing T • . Any two of these tubes except t, t are compatible:

• the forced tubes are pairwise compatible;

• each t i is a connected component of t • i
{r}, thus is contained in t {r, r }, and thus is compatible with the connected components of t {r, r } (i.e. all forced tubes);

• for t • i ⊇ t • j , any connected component of t • j {r} is contained in a connected component of t •
i {r} and thus is compatible with all connected components of t • i {r}. In particular t i and t j are compatible.

Therefore, there exists adjacent maximal tubings T, T on G such that T {t} = T {t } and

T ∪ T ⊇ {t, t , t} ∪ t ∪ a ∪ {t i | i ∈ [p]}.
For this choice of T, T , we thus obtained a separating and local linear dependence (2) between the compatibility vectors of the tubes of T ∪ T .

(C) A tube of T • contained in t contains both r and r . We distinguish again two cases.

(C.1) No tube of T • contained in t contains r and is adjacent to r or conversely. There must exist a tube t • ∈ T • included in t and containing r. Choose t • maximal for these properties. With the same arguments as in Case (B), the tubes of

T • included in t • form a nested chain t • = t • 0 t • 1 • • • t • p = {r}. For i ∈ [p], define t i to be the connected component of G[t • i-1 {r}] containing the singleton t • i-1 t • i . We define the tube t • , the chain t • = t • 0 t • 1 • • • t • p = {r } and the tubes t i for i ∈ [p ] similarly.
Consider now the inclusion minimal tube t • of T • contained in t and containing both r and r .

Since we assumed that no tube of T • is compatible with both t and t , we have t

• = t • t • {r} where r ∈ t. Let t be the connected component of G[t • {r, r }] containing r. Set α := (t • t) + (t • a ) and α := (t • t) + (t • a),
and define inductively β 1 , . . . , β p and β 1 , . . . , β p by

β i = α (t • i t ) -(α + α ) (t • i t) -α (t • i a) + αα (t • i t ) - j∈[i-1] β j (t • i t j ), β i = α (t • i t) -(α + α ) (t • i t) -α (t • i a ) + αα (t • i t ) - j∈[i-1] β j (t • i t j ).
We claim that

α d(T • , t) + α d(T • , t ) = (α + α ) d(T • , t) + α d(T • , a) + α d(T • , a ) -αα d(T • , t ) (3) + i∈[p] β i d(T • , t i ) + i∈[p ] β i d(T • , t i ).
To prove it, we check this linear dependence coordinate by coordinate.

We start with t • and t • . We have (t • t) = 0 since t • t. Moreover, (t • t ) = |{r}| = 1. Finally, we have by definition t j t • so that (t • t j ) = 0 for all j ∈ [p]. Combining these equalities, Relation (3) follows for t • from the definition of α and α . The argument is identical for t • .

We now consider the tubes t • i and t

• i . Observe first that (t • i t) = 0 for all 0 ≤ i ≤ p since t • i t.
Moreover, for all i < j, we have by definition t j t • i , so that (t • i t j ) = 0. In addition, we have (t • i t j ) = 0 for all i ∈ [p] and j ∈ [p ] since t • i and t j are compatible. Finally, we have (t • i t i ) = 1 since t • i and t i are incompatible and the only neighbor of t

• i in t i t • i is the singleton t • i-1 t • i .
Therefore, Relation (3) holds for t • i by definition of β i . The argument is identical for t • i . Finally, we consider a tube s • of T • not strictly contained in t

• . With similar arguments as in Case (B), the compatibility degrees (s • t), (s • t ), (s • t), (s • a) and (s • a ) actually count neighbors of s • , and (by assumption C) satisfy

(s • t) = (s • t) + (s • a) and (s • t ) = (s • t) + (s • a ).
Moreover, since all t i , t i and t are contained in t • , they are all compatible with s • , so that (s

• t i ) = (s • t i ) = (s • t ) =
∪ T ⊇ {t, t , t } ∪ t ∪ a ∪ a ∪ {t i | i ∈ [p]} ∪ {t i | i ∈ [p]}.
For this choice of T, T , we thus obtained a separating and local linear dependence (3) between the compatibility vectors of the tubes of T ∪ T .

(C.2) A tube of T • contained in t contains r and is adjacent to r or conversely. W.l.o.g., consider an inclusion maximal tube t • ∈ T • contained in t, containing r and adjacent to r . Since we have assumed that no tube of T • is compatible with both t and t , all tubes of T • included in t • contain r. These tubes thus form a nested chain t

• = t • 0 t • 1 • • • t • p = {r}. For i ∈ [p], define t i to be the connected component of G[t • i-1 {r}] containing the singleton t • i-1 t • i . Set α := (t • t ) -(t • t) = |{r }| = 1 and α := (t • t) + (t • a),
and define inductively β 1 , . . . , β p by

β i = α (t • i t ) -(1 + α ) (t • i t) -(t • i a) - j∈[i-1] β j (t • i t j ).
We claim that (4)

d(T • , t) + α d(T • , t ) = (1 + α ) d(T • , t) + d(T • , a) + α d(T • , a ) + i∈[p] β i d(T • , t i ).
To prove it, we check this linear dependence coordinate by coordinate.

Observe first that (t

• i t) = 0 for all 0 ≤ i ≤ p since t • i t.
Moreover, for all i < j, we have by definition t j t • i , so that (t • i t j ) = 0. Finally, we have (t • i t i ) = 1 since t • i and t i are incompatible and the only neighbor of t

• i in t i t • i is the singleton t • i-1 t • i .
Therefore, Relation (2) holds for t • by definition of α and α and for t • i by definition of β i . Consider now a tube s • of T • not strictly contained in t • . With similar arguments as in Case (B), the compatibility degrees (s • t), (s • t ), (s • t), (s • a) and (s • a ) actually count neighbors of s • , and (by assumption C) satisfy

(s • t) = (s • t) + (s • a) and (s • t ) = (s • t) + (s • a ).
Moreover, since all t i are contained in t • , they are all compatible with s • , so that (s • t i ) = 0 by Proposition 14. Combining these equalities, we obtain that Relation (3) holds for any s • ∈ T • . With the same arguments as in Case (B), there exists adjacent maximal tubings T, T on G such that T {t} = T {t } and

T ∪ T ⊇ {t, t } ∪ t ∪ a ∪ a ∪ {t i | i ∈ [p]}.
For this choice of T, T , we thus obtained a separating and local linear dependence (4) between the compatibility vectors of the tubes of T ∪ T .

We assumed in Cases (A), (B) and (C) above that t, t / ∈ T • and that no tube of T • is compatible with both t and t . The remaining two cases show how to force this assumption.

(D) A tube t • of T • is compatible with both t and t . We treat this case by induction on the number of tubes of T • compatible with both t and t . By Lemma 73, the compatibility vectors with respect to T • of the tubes of G compatible with t • correspond to the compatibility vectors of the tubes of G := G[t • ] G t • with respect to the maximal tubing T • . Since there are strictly less tubes of T • compatible with both t and t than tubes of T • compatible with both t and t , the induction hypothesis ensures that there exists adjacent maximal tubings T, T on G such that T { t} = T { t } and a separating and local linear dependence between the compatibility vectors of T ∪ T with respect to T • . By Lemma 72, the sets T := {t • } ∪ s | s ∈ T and T := {t • } ∪ s | s ∈ T are tubings on G (since t • is compatible with all preimages of tubes of G) and they are maximal by cardinality. Moreover, Lemma 73 ensures that the linear dependence between the compatibility vectors of the tubes of T ∪ T with respect to T • coincides with the linear dependence between the compatibility vectors of the tubes of T ∪ T with respect to T • . The linear dependence clearly remains separating and local, which concludes when there is a tube t • ∈ T • compatible with both t and t .

(E) t or t belongs to T • . We can assume w.l.o.g. that t = t • belongs to T • . Consider any two adjacent maximal tubings T, T on G such that T {t} = T {t }. Since any tube s in T ∩ T is compatible with t = t • , the t • -coordinate of the compatibility vector d(T • , s) vanishes. The same happens for the vector v

:= d(T • , t) + d(T • , t ) since (t • t) = -1 (as t = t • ) while (t • t ) = 1 (by Proposition 14). The set of vectors {v} ∪ {d(T • , s) | s ∈ T ∩ T } has cardinality |T • | but is contained in the hyperplane of R T • orthogonal to e t • .
Therefore, there is a linear dependence between these vectors, which translates into a linear dependence between the compatibility vectors of the tubes of T ∪ T with the same coefficient on d(T • , t) and d(T • , t ). This coefficient cannot vanish: otherwise, we would have a linear dependence on the compatibility vectors of T with respect to T • . Since T is a maximal tubing on G, and dim(N ( G)) = dim(N (G)) -1, this would contradict Corollary 19 and thus the induction hypothesis for G. This linear dependence is therefore separating. It is automatically local if t = V since all tubes are then subsets of t. Otherwise, we prove that it is local by restriction. We distinguish two cases. We can now prove the Span Property. Lemma 76. For any tube u of G, the span of {d(T • , s) | s ∈ T, s ⊆ u}, for a maximal tubing T on G containing u, is independent of T.

Proof. We proceed by induction on the size of u. The result is immediate if u is a singleton. Consider now two adjacent maximal tubings T, T on G containing u such that T {t} = T {t }. Assume first that t and t are contained in u. By Lemma 75, there exists adjacent maximal tubings S, S on G containing u such that S {t} = S {t } and a linear dependence between the compatibility vectors of the tubes of S ∪ S with respect to T • which is both separating and local. By definition, this implies that there exists α > 0 and α > 0 such that the vector α d(T • , t) + α d(T • , t ) belongs to vect({d(T • , s) | s ∈ S ∩ S , s ⊆ t}). However,

{s ∈ S ∩ S | s ⊆ t} = {t} ∪ {s ∈ S ∩ S | s ⊆ t} ∪ {s ∈ S ∩ S | s ⊆ a} ∪ {s ∈ S ∩ S | s ⊆ a } .
By induction hypothesis applied to each tube of t, we have

vect({d(T • , s) | s ∈ S ∩ S , s ⊆ t}) = vect({d(T • , s) | s ∈ S, s ⊆ t}) (as S (S ∩ S ) = t ⊆ t) = vect({d(T • , s) | s ∈ T, s ⊆ t}) (induction hypothesis) = vect({d(T • , s) | s ∈ T ∩ T , s ⊆ t}) (as T (T ∩ T ) = t ⊆ t)
and similarly replacing t by a or a . It follows that the vector α d(T • , t) + α d(T • , t ) also belongs to vect({d(T • , s) | s ∈ T ∩ T , s ⊆ u}). Since α = 0, this implies that d(T • , t) belongs to vect({d(T • , s) | s ∈ T , s ⊆ u}). Similarly, d(T • , t ) belongs to vect({d(T • , s) | s ∈ T, s ⊆ u}). We therefore obtained that vect({d(T

• , s) | s ∈ T, s ⊆ u}) = vect({d(T • , s) | s ∈ T , s ⊆ u}).
This also clearly holds when t and t are not contained in u. This concludes the proof since the graph of flips on the maximal tubings on G containing u is connected.

We can finally conclude the proof of Theorem 74 using both Lemmas 75 and 76.

Proof of Theorem 74. The Span Property is proved in Lemma 76. It only remains to show the Flip Property for arbitrary adjacent maximal tubings. Consider two adjacent maximal tubings T, T on G with T {t} = T {t }. By Lemma 75, there exists adjacent maximal tubings S, S on G such that S {t} = S {t } and a linear dependence between the compatibility vectors of the tubes of S∪S with respect to T • which is both separating and local. By definition, this implies that there exists α > 0 and α > 0 such that the vector α d(T Theorem 17 shows this condition for primal compatibility matrices and we need to show it for dual compatibility matrices. For this, we notice that the primal and dual compatibility matrices are related by

• , t) + α d(T • , t ) belongs to vect({d(T • , s) | s ∈ S ∩ S , s ⊆ t}). Lemma 76 applied to t ensures that vect({d(T • , s) | s ∈ T ∩ T , s ⊆ t}) = vect({d(T • , s) | s ∈ S ∩ S , s ⊆ t}).
(5) d * (T, T • ) := [(t j t • i )] i,j∈[n] = [(t i t • j )] t i,j∈[n] =: d(T, T • ) t
, where M t denotes the transpose of the matrix M . Consider now two pairs of adjacent maximal tubings T • , T • and T, T on G. From the Separation Flip Property of Theorem 17 applied to the initial maximal tubing T, we obtain that det(d(T, T • )) • det(d(T, T • )) < 0. Similarly, for the initial maximal tubing T , we obtain that det(d(T , T

• )) • det(d(T , T • )) < 0. Multiplying these two inequalities, we get det(d(T, T • )) • det(d(T , T • )) • det(d(T, T • )) • det(d(T , T • )) > 0.
Since the transposition preserves the determinant, we obtain by Equation 5that Remark 77. Observe that this proof does not provide us with any explicit linear dependence between dual compatibility vectors. In particular, we do not know whether the following analogue properties of Theorem 74 hold:

det(d * (T, T • )) • det(d * (T , T • )) • det(d * (T, T • )) • det(d * (T , T • )) > 0.
Dual Span Property: For any tube u of G, the span of {d * (t, T • ) | t ∈ T, t ⊂ u}, for a maximal tubing T on G containing u, is independent of T.

Dual Local Flip Property: For any two maximal tubings T, T with T {t} = T {t }, the unique linear dependence between the dual compatibility vectors of T∪T with respect to T • is supported by tubes not strictly included in a connected component of t = t ∩ t . 6.5. Nested complex isomorphisms (Proposition 41, Proposition 43 and Theorem 44). We now prove various results on nested complex isomorphisms presented in Section 5.2. We first show that the map Ω on the tubes of a spider X n defines a nested complex automorphism that dualizes the compatibility degree.

Proof of Proposition 41. First, Ω clearly sends tubes of X n to tubes of X n . We just have to show that (Ω(t) Ω(t )) = (t t) for any two tubes t, t of X n , and Proposition 14 will imply that Ω is a nested complex automorphism. This follows from the definition of Ω and the fact that

v i j , v i k v i j , v i k = δ i=i • δ j<j ≤k+1<k +1 + δ j <j≤k +1<k+1 , v i j , v i k h∈ v h 0 , v h k h = δ j≤ki+1≤k ,
and

i∈ v i 0 , v i ki i∈ v i 0 , v i k i = | {i ∈ [ ] | k i < k i } | • δ ∃i∈[ ], ki>k i .
Our objective is to show that these maps Ω on spiders are essentially the only non-trivial nested complex isomorphisms. We fix an isomorphism Φ between two nested complexes N (G) and N (G ). We first show that Φ preserves connected components in the following sense.

Lemma 78. Two tubes t and t of G belong to the same connected component of G if and only if their images Φ(t) and Φ(t ) belong to the same connected component of G .

Proof. Observe first that two tubes from distinct connected components are automatically compatible. Assume now that t and t are in the same connected component of G. If t and t are incompatible, then Φ(t) and Φ(t ) are also incompatible and therefore in the same connected component of G . If t and t are compatible, then there exists a tube t incompatible with both t and t :

• if t ∩ t = ∅, consider a path connecting a neighbor of t to a neighbor of t in G[V (t ∪ t )];

• if t ⊆ t , consider a path connecting a neighbor of t to a neighbor of t in G[V t]. We obtain that Φ(t ) is incompatible with both Φ(t) and Φ(t ), so that they all belong to the same connected component of G . This proves one direction. For the other direction, consider Φ -1 . Consequently, the nested complex N (G) records the sizes of the connected components of the graph G. We call connected size partition of G the partition λ(G)

:= |V 1 |, |V 2 |, . . . , |V κ | of |V|, where V 1 , . . . , V κ are the connected components of G ordered such that |V i | ≥ |V i+1 |.
Corollary 79. Two graphs whose nested complexes are isomorphic have the same connected size partitions:

N (G) N (G ) =⇒ λ(G) = λ(G ).
In particular, they have the same number of vertices.

Proof. Consider a maximal tubing T on G and decompose it into subtubings T 1 , . . . , T κ on the connected components V 1 , . . . , V κ of G. Their images Φ(T 1 ), . . . , Φ(T κ ) decompose the maximal tubing Φ(T). Moreover, Lemma 78 ensures that two tubes Φ(t) ∈ Φ(T i ) and Φ(t ) ∈ Φ(T i ) belong to the same connected component of G if and only if i = i . We therefore obtain that λ

(G) = {|V 1 |, . . . , |V κ |} = {|T 1 | + 1, . . . , |T κ | + 1} = {|Φ(T 1 )| + 1, . . . , |Φ(T κ )| + 1} = λ(G ).
Proposition 43 is another immediate consequence of Lemma 78: since it sends all tubes in a connected component H of G to tubes in the same connected component H of G , the map Φ induces a nested complex isomorphism between N (H) and N (H ). From now on, we assume without loss of generality that G is connected. Our next step is a crucial structural property of Φ. Proof. Two vertices v and w of G are adjacent if and only if the two tubes {v} and {w} are incompatible. Since Φ preserves the compatibility relation, this shows that v and w are adjacent if and only if ψ(v) and ψ(w) are, i.e. that ψ defines a graph isomorphism. Let Ψ denote the nested complex isomorphism induced by ψ, i.e. defined by Ψ(t

) := {ψ(v) | v ∈ t}.
We prove by induction on |t| that Φ(t) = Ψ(t) for any tube t on G. It holds for singletons. For the induction step, consider an arbitrary tube t of G. Let v ∈ V t be a neighbor of t. Since {v} and t are incompatible, so are Φ({v}) = {ψ(v)} and Φ(t), and thus ψ(v) is a neighbor of Φ(t). Let w ∈ V be such that ψ(w) is a neighbor of ψ(v) in Φ(t). If w / ∈ t then it is incompatible with t ∪ {v}, and thus Φ({w}) = {ψ(w)} is incompatible with Φ(t ∪ {v}). Therefore, Φ(t ∪ {v}) is adjacent to and does not contain ψ(w) which is in Φ Finally, to prove (iii) we can assume that t is not a singleton. Thus Φ(t) is not an inclusion maximal tube. Let t be a tube of G such that Φ(t ) is a maximal tube of G containing Φ(t). Since Φ -1 swaps Φ(t) and Φ(t ) contains Φ(t), Φ -1 also swaps Φ(t ) by (i). Thus, t is a singleton swapped by Φ and contained in t. We are now ready to prove that any non-trivial nested complex isomorphism coincides, up to composition with a trivial nested complex isomorphism, with the isomorphism Ω on a spider.

(t). Since |Φ(t ∪ {v})| = |t| + 1 = |Φ(t)| + 1, this implies that Φ(t ∪ {v}) is incompatible with Φ(t), a contradiction. Therefore, we know that w ∈ t. Let t 1 , . . . , t k denote the connected components of G[t {w}]. By induction hy- pothesis, Φ(t i ) = Ψ(t i ) for all i ∈ [k]. Moreover, since Φ(t i ) is compatible with Φ(t) and adjacent to ψ(w) ∈ Φ(t), it is included in Φ(t). We thus obtain Ψ(t) = {ψ(w)} ∪ Ψ(t 1 ) ∪ • • • ∪ Ψ(t k ) ⊆ Φ(t) and thus Φ(t) = Ψ(t) since |Φ(t)| = |t| = |Ψ(t)|.
Proof of Theorem 44. The proof works by induction on the number |V| of vertices of G. It is clear when |V| ≤ 2. For the induction step, assume that the result holds for all graphs on less than |V| vertices and consider a non-trivial nested complex isomorphism Φ : N (G) → N (G ). Then Φ does not maintain all tubes of G by Proposition 81, and thus swaps at least one singleton {s} by Lemma 82 (iii). Let s denote the vertex of G such that Φ({s}) = V {s }. The map Φ induces a nested complex isomorphism between the link of {s} in N (G) and the link of Φ({s}) in N (G ). The former is isomorphic to the nested complex of the reconnected complement G := G {s} while the latter is isomorphic to the nested complex of the restriction G := G [Φ({s})]. Let Φ : t → Φ(t) denote the resulting nested complex isomorphism between N ( G) and N ( G ). This isomorphism Φ is non-trivial: by Lemma 82, Φ swaps any tube t containing {s}, so that Φ swaps the tube t {s}. It follows by induction hypothesis that G and G are spiders and that there exists a graph isomorphism ψ : G → G inducing a trivial nested complex isomorphism Ψ : N ( G) → N ( G ) such that Ψ -1 • Φ =: Ω is the automorphism of N ( G) described in Section 5.2. In other words, we can label by v i j the vertices of the spider G and by v i j the vertices of the spider G , with i ∈ [ ] and 0 ≤ j ≤ n i , such that

(6) Φ v i j , v i k = v i ni+1-k , v i ni+1-j and Φ i∈[ ] v i 0 , v i ki = i∈[ ] v i 0 , v i ni-1-ki .
We now claim that G and G are both spiders. To prove it, we distinguish two cases: Body case: all neighbors of s in G are swapped by Φ. Then they form a clique in G (by Lemma 83 (i)), so that G is the spider G where we add one more body vertex s with no attached leg. Moreover, s is necessarily swapped by Φ -1 (otherwise Φ -1 ({s }) would be a neighbor of s maintained by Φ). We conclude by symmetry that G is the spider G where we add one more body vertex s with no attached leg. Leg case: s has a neighbor m maintained by Φ. It is unique by Lemma 83 (iii) and not connected to any other vertex swapped by Φ by Lemma 83 (ii). Therefore, G is the spider G where we replace the edges connecting m to all other body vertices of G by a new body vertex s with an edge to m. Moreover, s is necessarily maintained by Φ -1 (otherwise Φ -1 ({s }) should be V {s} which is not connected). We conclude that G is the spider G where we add one additional leg vertex s to the free endpoint of a leg.

concave and increasing, that

ω(t) + ω(t ) > ω(t) + ω(t), ω(t) + ω(t ) > ω(a) + ω(a ), 2 ω(t) + ω(t ) > ω(t) + ω(a), 2 ω(t) + ω(t ) > ω(t) + ω(a ).
Moreover, the inequalities still hold when we delete terms in their right hand sides since ω is positive. Therefore, ω satisfies Condition (2) of Proposition 52 when we do not flip an initial tube. Finally, initial tubes only appear in the left hand sides of linear dependences, so choosing ω(t • ) = Ω large enough ensures that ω satisfies Condition (2) of Proposition 52 for any flip. Observe that this is essentially the same proof as in [CSZ15, Section 5].

We now adapt this proof for the cycle O n+1 . Clearly, the dependences described above for the path also appear for the cycle (as cycles contain paths). Beside those, when (T ∪ T ) ∩ T • = ∅, a straightforward case analysis shows that the linear dependences can only be of the form

d(T • , t) + d(T • , t ) = 2 d(T • , t 1 ),
where t 1 ∈ t.

Again, no tube of T • can appear in their right hand sides of the linear dependences. Therefore, when t, t / ∈ T • but (T ∩ T ) ∩ T • = ∅, the linear dependences are obtained from the generic ones above by deleting terms in their right hand sides. The dependences when t or t belong to T • will again be treated separately.

We choose the same height function ω as before. For the same reasons, the linear dependences for the path are again transformed to strict inequalities on ω. Moreover, as t 1 ⊆ t ∩ t and f is increasing, we have ω(t) + ω(t ) > 2 ω(t 1 ).

We conclude as before by choosing Ω large enough that ω satisfies the Condition (2) of Proposition 52 for any flip.

Finally, for dual compatibility vectors, a straightforward case analysis shows that the linear dependences are all of the form

d * (t, T • ) + d * (t , T • ) = d * (t, T • ) + d * (t, T • ), d * (t, T • ) + d * (t , T • ) = d * (a, T • ) + d * (a , T • ), 2 d * (t, T • ) + d * (t , T • ) = d * (t, T • ) + d * (a, T • ), 2 d * (t, T • ) + d * (t , T • ) = d * (t, T • ) + d * (a , T • ),
when none of t, t and t have n vertices. We can also have the linear dependences

d * (t, T • ) + d * (t , T • ) = 2 d * (t, T • ) + d * (t, T • ), 2 d * (t, T • ) + d * (t , T • ) = 2 d * (t, T • ) + d * (a, T • ), when |t| = n and d * (t, T • ) + d * (t , T • ) = d * (t 1 , T • ),
where t 1 ∈ t.

when |t| = |t | = n. Again, no tube of T • can appear in the right hand sides of the linear dependences. Therefore, when t, t / ∈ T • but (T ∩ T ) ∩ T • = ∅, the linear dependences are obtained from the generic ones above by deleting terms in their right hand sides.

We now define a height function ω on tubes on O n+1 by

ω(t) =        f (|t|) if t / ∈ T • and |t| = n, f (|t|) 2 if t / ∈ T • and |t| = n, Ω otherwise,
where f : R → R >0 is any strictly concave increasing positive function and Ω ∈ R is a large enough constant. By definition of t, t, a and a , and using that f is concave and increasing, we obtain that ω satisfies a strict inequality for each linear dependence above. We conclude as before by choosing Ω large enough that ω satisfies the Condition (2) of Proposition 52 for any flip.

Our last proof concerns the polytopality of the compatibility fan for the star, for which we have presented a candidate in Section 5.3.

Proof of Proposition 56. We just have to show that for any tube t and any maximal tubing T on X n+1 , the point x(T) belongs to the half-space H ≥ (t) and to the boundary of this half-space if and only if t ∈ T.

Consider first a tube t not in T • . Let t denote the inclusion minimal tube of T ∪ V containing the central vertex * . Then the other tubes of T are all leaves of X n+1 contained in t and a nested chain of tubes t = t |t| t |t|+1 • • • t n+1 = V of X n+1 . Therefore, we have x(T) i = 0 if { i } ⊆ t and x(T) i = j -1 if { i } = t j t j-1 . We conclude that

d(T • , t) | x(T) = i∈[n] i∈t x(t) i = |t|≤j≤n+1 tj tj-1 ⊆t (j -1) ≤ n j=|t| j = f (|t|),
with equality if and only if t j t j-1 ⊆ t for all |t| ≤ j ≤ n + 1, i.e. if and only if t = t |t| .

Finally, for any i ∈ [n], we have d(T • , { i }) | x(T) = -x(T) i ≤ 0, with equality if and only if the inclusion minimal tube of T ∪ V containing i is { i }, i.e. if and only if { i } ∈ T. 6.7. Design compatibility fan (Theorem 61). The proof of Theorem 61 still relies on Proposition 5, that is on the understanding of the linear dependences of the compatibility vectors of the tubes involved in a flip. We now need to distinguish two kinds of flips: we call round flips those exchanging two round tubes, and square flips those exchanging a square to a round tube.

We claim that Theorem 74 still holds for round flips. Indeed, a coordinatewise verification shows that the linear dependences exhibited in Section 6.3 still hold for a initial maximal design tubing T • : the arguments are identical for coordinates corresponding to round tubes and straightforward for coordinates corresponding to square tubes.

It thus remains to show the Separating Flip Property for square flips. It turns out that the proof for square flips is much easier as the linear dependences only involve compatibility vectors of forced tubes. Using the duality trick presented in Section 6.4 and the fact that any two maximal design tubings are connected by a sequence of square flips, it is equivalent to prove the Separating Flip Property for the compatibility fan or for the dual compatibility fan. In the sequel, we prefer to work with the dual compatibility vectors.

Fix an initial maximal design tubing T • on a graph G. Consider a round tube t exchangeable with a square tube v , that is the vertex v is contained in t. The forced tubes of this square flip (i.e. the tubes contained in all flips exchanging t and v ) are the following:

• the square tubes w 1 , . . . w k for the neighbors w 1 , . . . , w k of t in G,

• the round tubes a 1 , . . . , a given by the connected components of G[t {v}]. Let p be number of w i 's which are roots of initial round tubes in T • and let q be the number of a i 's containing an initial square tube of T • . Suppose that

• the w i 's are ordered such that w 1 , . . . , w p are roots of tubes t • 1 , . . . , t • p in T • with t • i ⊇ t • j for 1 ≤ i < j ≤ p, while w p+1 , . . . , w k are square tubes of T • , • the a i 's are ordered such that a 1 , . . . , a q contain an initial square tube of T • while a q+1 , . . . , a do not. With these notations, the reader can check that if p = 0 and q > 0, then the dual compatibility vectors of these forced tubes satisfy the dependence where the coefficients β 1 , . . . , β p are recursively defined by (9)

β i = (t t • i ) - j∈[q] (a j t • i ) -(v t • i ) + r∈[i-1]
β r (w r t • i ) .

To prove it, we check this linear dependence coordinate by coordinate. It boils down to Equation (8) for initial tubes contained in t. It is also clear for the initial square tubes not contained in t as all dual compatibility degrees involved in (9) vanish. Moreover, the coefficients β 1 , . . . , β p are defined in order to compensate for the default of the initial tubes t • 1 , . . . , t • p in Equation (8). Finally, we proceed by induction for the remaining initial tubes of T • , that is the initial round tubes not contained in t and whose root is not one of the w i 's. Namely, since q > 0 and thanks to our special ordering on the w i 's, the coordinate corresponding to such a tube in all terms of Equality ( 9) is a linear combination of the coordinates corresponding to its predecessors in the spine of T • (i.e. the inclusion poset on round tubes of T • ).

Finally, we still have to check the case where q = 0, meaning where t is contained in an initial round tube of T • . We denote by t • the inclusion minimal initial round tube of T • containing t and by z • its root in T • . We then have to distinguish whether or not z • = v:

• If z • = v, call w 1 , . . . , w r (r ≥ 1) the neighbors of t that also belong to t • . We then claim that the following linear dependence holds:

d * (t, T • ) + r d * (v , T • ) = i∈[r]
d * (w i , T • ).

Indeed an initial tube s • of T • either contains t and thus all the vertices v, w 1 , . . . , w r , or does not contain v so that the equality holds by counting the vertices w 1 , . . . , w r in s • . • If z • = v, then z • belongs to one of the tubes a 1 , . . . , a , say a 1 . Let w 1 , . . . , w r be the neighbors of t contained in t • that are also neighbors of a 1 , and w r+1 , . . . , w s be the other neighbors of t contained in t • . Observe that s ≥ 1 since t ⊂ t • . One can then check that the linear dependence we look for is 6.8. Design nested complex isomorphisms (Proposition 64 and Theorem 67). We now prove our characterization of the design nested complex isomorphisms announced in Section 5.4.

In both proofs, we will use the following description of links in design nested complexes, similar to that of [START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF] for links in nested complexes. We leave this proof to the reader.

Lemma 84. The link of a tube t in the design nested complex N (G) is isomorphic,

• for a square tube t = v , to the join N (G 1 ) * • • • * N (G ) of the design nested complexes of the connected components G 1 , . . . , G of G[V {v}]. • for a round tube t, to the join of the nested complex N (G[t]) of the restriction of G to t with the design nested complex N (G t) of the reconnected complement of t in G.

Before proving Proposition 64 and Theorem 67, we need a technical result.

Lemma 85. Let Ḡ and G be connected graphs with vertex sets V and V respectively. Let Φ be an isomorphism from the design nested complex N ( Ḡ) of Ḡ to the design (resp. standard) nested complex N (G) (resp. N (G)) of G. If there exists a vertex v ∈ V such that all tubes of G incompatible with Φ( V) are round tubes containing v, then Ḡ and G are paths.

Proof. Since Φ is an isomorphism, it induces a bijection between the design tubes of Ḡ incompatible with V and the tubes of G incompatible with Φ( V). The former are precisely the square tubes of Ḡ (by definition of the compatibility of design tubes) while the later are some round tubes of G containing v (by assumption). Since all the square tubes of Ḡ are compatible, it follows that their images by Φ are nested in G. Let ū, v ∈ V be the only vertices such that |Φ(ū )| = 1 and |Φ(v )| = |V| -1. For any other vertex w ∈ V, the link of the tube Φ( w ) is the join of two non-trivial design or standard nested complexes by Lemma 84. Since Φ is an isomorphism, so is the link of the square tube w , so that w disconnects Ḡ again by Lemma 84. We conclude that all but two vertices of Ḡ disconnect Ḡ, which implies that Ḡ is a path. In order to show that G is also a path, we now distinguish two situations: (i) Suppose first that Φ is an isomorphism from the design nested complex N ( Ḡ) of Ḡ to the standard nested complex N (G) of G. Then the composition of Φ -1 with the isomorphism Π of Example 62 (ii) is an isomorphism between the standard nested complex N (G) of G and the standard nested complex of a path, which implies by Theorem 44 that G itself is a path. (ii) Suppose now that Φ is an isomorphism from the design nested complex N ( Ḡ) of Ḡ to the design nested complex N (G) of G. Using Lemma 84 and a similar argument as in the proof of Lemma 78, the image Φ( V) of V is either a square tube v of G, or a singleton round tube {v} of G, or the round tube V of G. The last two cases are discarded by our assumption since the square tube v is incompatible with {v} and with V. Therefore, we obtain that Φ( V) = v and the tubes of G incompatible with Φ( V) = v are exactly the round tubes containing v. So the square tubes of Ḡ are in bijection with the tubes of G containing v. Since | V| = |V| (dimensions of isomorphic simplicial complexes), an immediate induction shows that G is a path.

We are now ready to prove our classification of design nested complex isomorphisms.

Proof of Proposition 64. We show the result by induction on | V|, the cases | V| ≤ 2 being trivial. Assume that | V| ≥ 3 and consider an isomorphism Φ : N ( Ḡ) → N (G). We first consider the image Φ( V) of the round tube V of Ḡ. It is either a singleton, or the complement of a singleton. Otherwise, its link would be the join of two non-trivial complexes by Lemma 84, which yields a contradiction using a similar argument as in the proof of Lemma 78. We claim that we can assume that Φ( V) is a singleton adjacent to at least two vertices in G. Indeed,

• if Φ( V) = V {v}, then all tubes incompatible with Φ( V) = V {v} contain v,

• if Φ( V) = {v} where v has a unique neighbor w in G, then all tubes incompatible with Φ( V) = {v} contain w, In both cases, Lemma 85 ensures that Ḡ and G are paths, and we can compose Φ with a rotation p to ensure that Φ( V) is a singleton adjacent to at least two vertices in G.

We now consider a vertex w ∈ V which does not disconnect Ḡ (such a vertex always exists). By Lemma 84, the link of the square tube w is not the join of two non-trivial nested complexes. Since Φ is an isomorphism, so is the link of Φ( w ), so that Φ( w ) is either a singleton or the complement of a singleton again by Lemma 84. Moreover, since w is incompatible with V and Φ is an isomorphism, Φ( w ) is incompatible with Φ( V) = {v}. Therefore, Φ( w ) is either a singleton {w} adjacent to {v}, or the complement V {v} of the singleton {v}. Now, since V contains at least two vertices w, w which do not disconnect G and since Φ( w ) = Φ( w ), we can assume that Φ( w ) is a singleton {w} adjacent to {v}.

It implies that Φ induces an isomorphism from the design nested complex N ( Ḡ[ V { w}]) to the nested complex N (G {w}) of the reconnected complement of the tube {w} in G. The induction hypothesis implies that

• the graph Ḡ[ V { w}] is isomorphic to the spider X n and the graph G {w} is isomorphic to the octopus X n (with head denoted v), for a certain n = {n 1 , . . . , n } ∈ N . • the image Φ( V { w}) of V { w} is the pair {v, w} containing the central vertex of G {w}, • the description of the images of the tubes of Ḡ not containing w is given by Ω, in particular Φ( w ) is a singleton adjacent to v in G {w}. Since Φ( w ) cannot be an edge in G, it then has to be also a singleton {w } in G, non-adjacent to w for compatibility. Since G {w} is an octopus with head v, it follows by definition of the reconnected complement that G is either an octopus with head v or an octopus with head v with an additional edge of the form {v, v 1 i } for a certain i ∈ [ ]. We can now apply the same reasonning to w and since Φ( w )

Figure 1 .

 1 Figure 1. The classical associahedron (left) is the path associahedron (right).

Figure 2 .Figure 3 .

 23 Figure 2. The cyclohedron (left) is the cycle associahedron (right).

D

  (G, T • ) := R ≥0 d(T • , T) | T tubing on G and D * (G, T • ) := R ≥0 d * (T, T • ) | T tubing on G are complete simplicial fans.

2. 1 .

 1 Polyhedral geometry and fans. We first recall classical definitions from polyhedral geometry. More details can be found in the textbooks [Zie95, Lecture 1] and [DRS10, Section 2.1.1].

Figure 5 .

 5 Figure 5. The flip between two maximal tubings T • ex and T ex on G • ex .

Example 18 .

 18 Consider the initial maximal tubing T • ex of the graph G • ex of Figure 4 (right) and the flip T • ex {t • ex } = T ex {t ex } illustrated in Figure 5. The linear dependence between the compatibility vectors of the tubes of T

Example 22 .

 22 Consider the initial maximal tubing T • ex on the graph G • ex of Figure 4 (right) and the flip T • ex {t • ex } = T ex {t ex } illustrated in Figure 5. The linear dependence between the dual compatibility vectors of the tubes of T

Figure 6 .

 6 Figure 6. Compatibility fans of the 3-path (left) and of the triangle (right).

Figure 7 .

 7 Figure 7. All tubes in the top pictures of Figure 8.

Figure 10 .

 10 Figure10. Isomorphism between the simplicial associahedron and the nested complex of a path: diagonals are sent to tubes (left), preserving the compatibility (middle) and incompatibility (right). See also Figure1.

Figure 12 .

 12 Figure 12. Isomorphism between the simplicial cyclohedron and the nested complex of a cycle: centrally symmetric pairs of diagonals are sent to tubes, preserving the compatibility and incompatibility. See also Figure 2.

Remark 30 (

 30 Dual compatibility fan). Since the compatibility degree is not symmetric for tubes of O n+1 , the compatibility fan D(O n+1 , T • ) and the dual compatibility fan D * (O n+1 , T • ) do not coincide. Figures 13 and 14 show both fans for different initial tubings on the cycles O 3 and O 4 .

Figure 13 .

 13 Figure 13. Compatibility (left) and dual compatibility (right) fans for the triangle.

Figure 15 .

 15 Figure 15. The tubing {146, 12468, 123468} corresponds to three non-crossing decreasing lattice paths, and to the ordered partition 57|3|28|146.

  1) tubings with k tubes, where S(m, p) denotes the Stirling number of second kind (i.e. the number of ways to partition a set of m elements into p non-empty subsets) [OEI10, A008277] (to see it, sum over the number i of tubes containing * ), and

Figure 16 .

 16 Figure 16. Two polytopal realizations of the 3-dimensional stellohedron: their normal fans are the nested fan (left) and a compatibility fan (right).

Figure 17 .

 17 Figure17. The compatibility fans D(X n+1 , T • ) for the star X n+1 and the initial tubing T • = { 1 }, . . . , { n } formed by its leaves (for n ∈ {2, 3, 4}).

Figure 18 .

 18 Figure 18. The stellohedron (left) is a secondary polytope (right).

  Figure 19 (right) illustrates Proposition 38 with the compatibility fan of a graph formed by two paths. Compatibility fans of paths are discussed in Section 4.2. Besides all compatibility vectors, the cones of three different tubings are represented in Figure 19 (right).

Figure 19 .

 19 Figure19. The compatibility fan of a disconnected graph is the product (right) of the compatibility fans of its connected components (left and middle).

Figure 20 .

 20 Figure 20. The red tube t • ex = {a, b, d, f, g, h, i, k, l} in the maximal tubing T • (left) yields a maximal tubing T • ex [t • ex ] on the restriction G • ex [t • ex ] (middle) and a maximal tubing T • ex t • ex on the reconnected complement G • ex t • ex (right).

  and in type A by F. Santos [CSZ15, Section 5]. Theorem 50 ([CFZ02, CSZ15]). The d-vector fan (or compatibility fan) is polytopal for • any initial cluster in any type A cluster algebra [CSZ15, Section 5], and • the bipartite initial cluster in any finite type cluster algebra [CFZ02]. The polytopality of the g-vector fan was studied by C. Hohlweg, C. Lange and H. Thomas [HLT11]. See also recent alternative proofs by S. Stella [Ste13] and V. Pilaud and C. Stump [PS15a].

  Polytopality of compatibility fans. We have seen in Section 2.3 that the nested fan is the normal fan of the graph associahedron of [CD06, Dev09, Pos09, Zel06]. For the compatibility fan, the question of the polytopality remains open: Conjecture 53. All primal and dual compatibility fans of graphical nested complexes are polytopal.

Figure 23 .

 23 Figure23. Two Schlegel diagrams for the 4-dimensional stellohedron defined in Proposition 56. The red facet corresponds to all tubings containing the tube { * } while the blue facet corresponds to all tubings containing the tube { }, where is the bottom left leaf of X 5 .

Figure 24 .

 24 Figure24. Two design graph associahedra: the design P 3 -associahedron (left) and the design K 3 -associahedron (right). For readability, round tubes are colored blue while square tubes are colored red.

Figure 25 .

 25 Figure 25. Two Schlegel diagrams for the 4-dimensional design cycle associahedron. The blue facet corresponds to all round tubings while the red facet corresponds to all tubings containing the bottom right square tube of O 4 .

Figure 26 .

 26 Figure26. Two Schlegel diagrams for the 4-dimensional design star associahedron. The blue facet corresponds to all round tubings while the red facet corresponds to all tubings containing the right square tube of X 4 .

  0 by Proposition 14. Combining these equalities, we obtain that Relation (3) holds for any s• ∈ T • .With the same arguments as in Case (B), there exists adjacent maximal tubings T, T on G such that T {t} = T {t } and T

(

  E.1) A tube t • of T • contains t ∪ {r } and is contained in t. Consider the re-stricted graph Ĝ = G[t ∪ {r }].Any tube s of G included in t is also a tube of Ĝ. Therefore, the set T := {s | s ∈ T, s ⊆ t} is a tubing on Ĝ for any tubing T containing t. Define also the tube t := t a of Ĝ. The existence of t• implies that (s • t ) = (s • a ) for any s • ∈ T • not included in t.It follows that the compatibility vector d( T• , t ) is the restriction of d(T • , t )d(T • , a ) to the coordinates indexed by T• . Similarly, for any tube s ∈ T contained in t, the compatibility vector d( T• , s) is the restriction of d(T • , s) to the coordinates indexed by T• . This shows that the linear dependence on d( T• , s) | s ∈ T ∪ T provides a linear dependence on {d(T • , s) | s ∈ T ∪ T , s ⊆ t} ∪ {d(T • , t ) -d(T • , a )}. The resulting linear dependence on {d(T • , s) | s ∈ T ∪ T } is local. (E.2) No tube of T • contains t ∪ {r } and is contained in t. The proof is identical to Case (E.1), replacing d(T • , t ) -d(T • , a ) by d(T • , t ) -d(T • , t). Details are left to the reader.

  and similarly replacing t by a or a . We thus conclude thatvect({d(T • , s) | s ∈ T ∩ T , s ⊆ t}) = vect({d(T • , s) | s ∈ S ∩ S , s ⊆ t}) contains the vector α d(T • , t) + α d(T • , t )with α > 0 and α > 0. In other words, we obtained a separating and local linear dependence on {d(T • , s) | s ∈ T ∪ T }. 6.4. Dual compatibility fan (Theorem 21). The fact that dual compatibility vectors support a complete simplicial fan realizing the nested complex is a direct consequence of Theorem 17, using the following duality trick. Observe first that given n + 1 vectors {u, v, w 1 , . . . , w n-1 } in R n , the hyperplane spanned by {w 1 , . . . , w n-1 } separates u and v if and only if det([u|w 1 | . . . |w n-1 ]) • det([v|w 1 | . . . |w n-1 ]) < 0.

  This implies that the products det(d * (T, T • ))•det(d * (T , T • )) and det(d * (T, T • ))•det(d * (T , T • )) have the same sign. Since we know that det(d * (T, T • ))•det(d * (T , T • )) < 0 for the tubing T • = T, we obtain by repeated flips in T • that det(d * (T, T • )) • det(d * (T , T • )) < 0 for any initial tubing T • and pair of adjacent maximal tubings T, T on G. This shows the Separation Flip Property for dual compatibility vectors. We conclude again by Proposition 5.

Lemma 80 .

 80 For any nested complex isomorphism Φ : N (G) → N (G ) and any tube t of G, either |Φ(t)| = |t| or |Φ(t)| = |V| -|t|.Proof. By Lemma 72, the link of a tube t in N (G) is isomorphic to the nested complex N (G[t] G t) of the union of the restriction G[t] with the reconnected complement G t. The former has |t| vertices while the latter has |V| -|t| vertices. Since Φ induces an isomorphism from the link of t in N (G) to the link of Φ(t) in N (G ), the result follows from Corollary 79.We say that Φ maintains the tube t if |Φ(t)| = |t| and that Φ swaps the tube t if |Φ(t)| = |V| -|t|.Proposition 81. If it maintains all tubes of G, then Φ is the trivial nested complex isomorphism induced by the graph isomorphism ψ : G → G defined by Φ({v}) = {ψ(v)}.

Lemma 82 .

 82 If Φ does not maintain a tube t of G (i.e. |Φ(t)| = |t|), then (i) Φ swaps any tube of G containing t, (ii) Φ maintains any tube of G disjoint from and non-adjacent to t, and (iii) Φ swaps at least one singleton included in t.Proof. Consider a tube s of G strictly containing t. The link of {s, t} in N (G) is isomorphic to the nested complex of the union of the graphs G[t], (G t)[s t], and G s with |t|, |s| -|t| and |V| -|s| vertices respectively. Therefore, Corollary 79 ensures that the link of {Φ(s), Φ(t)} in N (G ) is isomorphic to the nested complex of a graph with three connected components with |t|, |s| -|t| and |V| -|s| vertices respectively. If Φ(s) is not contained in Φ(t), then the link of {Φ(s), Φ(t)} in N (G ) would be isomorphic to the nested complex of a graph with one connected component G [Φ(t)] having |Φ(t)| vertices. We reach a contradiction as|Φ(t)| = |V| -|t| is neither |t| (by assumption on t), nor |V| -|s| (since |s| > |t|), nor |s| -|t| (since |s| < |V|). Therefore, Φ(s) is contained in Φ(t) and the link of {Φ(s), Φ(t)} in N (G ) is isomorphic to the union of the graphs G[Φ(s)], (G Φ(s))[Φ(t) Φ(s)], and G Φ(t) with |Φ(s)|, |Φ(t)| -|Φ(s)| and |V| -|Φ(t)| vertices respectively. If |Φ(s)| = |V| -|s|, then it forces |Φ(s)| = |s| -|t| = |s|, a contradiction. This proves (i). Consider now a tube s of G disjoint from and non-adjacent to t. Note that |s| + |t| < |V| as there is at least a vertex separing them. The link of {s, t} in N (G) is isomorphic to the nested complex of the union of the graphs G[s], G[t], and (G s) t with |s|, |t| and |V| -|s| -|t| vertices respectively. Again, Corollary 79 ensures that the link of {Φ(s), Φ(t)} in N (G ) is isomorphic to the nested complex of a graph with three connected components with |s|, |t| and |V| -|s| -|t| vertices respectively. If Φ(s) is not contained in Φ(t), then the link of {Φ(s), Φ(t)} in N (G ) would be isomorphic to the nested complex of a graph with one connected component G [Φ(t)] having |Φ(t)| vertices. We reach a contradiction as |Φ(t)| = |V| -|t| is neither |t| (by assumption on t), nor |s| (since |s| + |t| < |V|), nor |V| -|s| -|t| (since |s| > 0). Therefore, Φ(s) is contained in Φ(t) and the link of {Φ(s), Φ(t)} in N (G ) is isomorphic to the union of the graphs G[Φ(s)], (G Φ(s))[Φ(t) Φ(s)], and G Φ(t) with |Φ(s)|, |Φ(t)| -|Φ(s)| and |V| -|Φ(t)| vertices respectively. If |Φ(s)| = |s|, then it forces |Φ(s)| = |V| -|s| -|t| = |V| -|s|, a contradiction. This proves (ii).

Lemma 83 .

 83 Denote by M := {v ∈ V | |Φ({v})| = 1} the set of vertices maintained by Φ and by S := {v ∈ V | |Φ({v}|) = |V| -1} the set of vertices swapped by Φ. Then (i) S forms a clique of G, (ii) any vertex in M has at most one neighbor in S, and (iii) any vertex in S has at most one neighbor in M . Proof. Let s, s ∈ S. Since |Φ({s})| = |Φ({s })| = |V| -1, the tubes Φ({s}) and Φ({s }) are incompatible. Therefore {s} and {s } are incompatible, so that s and s are neighbors. The set S thus forms a clique. To prove (ii) and (iii), assume that some vertices m ∈ M and s ∈ S are neighbors. The tubes {m} and {s} are thus incompatible, so that Φ({m}) and Φ({s}) are also incompatible. Since |Φ({m})| = 1 while |Φ({s})| = |V|-1, this implies Φ({s}) = V Φ({m}). It follows that m cannot have another neighbor swapped by Φ and s cannot have another neighbor maintained by Φ.

  (8) d * (t, T • ) = j∈[q] d * (a j , T • ) -d * (v , T • )We now adapt this linear dependence to cover the case when p ≥ 0 and q > 0. Namely, we claim thatd * (t, T • ) = j∈[q] d * (a j , T • ) -d * (v , T • ) + i∈[p] β i d * (w i , T • )

  (s -r + 1) d * (t, T • ) = s d * (a 1 , T • ) -d * (v , T • ) -s i=r+1 d * (w i , T • ) + (s -r + 1) s i=1 d * (w i , T • ).It clearly holds for tubes not contained in t • and for t • itself. Consider thus an initial round tube s • of T • contained in t • . Since z • ∈ a 1 , s • cannot contain a 1 . Thus the first term of the right hand side vanishes for s • , while (t s • ) = i∈[s] (w i s • ), concluding the proof.

  T • ex and T ex on G • ex . Example 8. Figure 5 illustrates the flip between two maximal tubings T • ex and T ex on G • ex . The flipped tubes t •

ex = {a, b, c, d, f, g, h, k, l, m} (with root g) and t ex = {c, d, e, h, i, m} (with root i) are dashed green, while the forced tubes of the exchangeable pair {t • ex , t ex } are red.

2.3. Graphical nested fans and graph associahedra. Although we will not use them in the remaining of this paper, we briefly survey some constructions of the nested fan and graph associahedron to illustrate the previous definitions. The nested fan is constructed implicitly in

[START_REF] Michael | Coxeter complexes and graph-associahedra[END_REF]

, and explicitly in

[START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF][START_REF] Eva | Matroid polytopes, nested sets and Bergman fans[END_REF][START_REF] Zelevinsky | Nested complexes and their polyhedral realizations[END_REF]

in the more general situation of nested complexes on arbitrary building sets.

  • ex of Examples 6 and 8, the compatibility degrees of the green tubes t • ex , t ex and of the red tube t ex = t • ex ∪ t ex of Figure 5 with the tube t • ex of Figure 4 (left) are given by

  • , T) of any maximal tubing T on G has full rank.3.3. Dual compatibility fan.It is also interesting to consider the following dual notion of compatibility vectors, where the roles of t and t • 1 , . . . , t • n are reversed. The results are similar, and the motivation for this dual definition will become clear in Section 4.3. The dual compatibility matrix of a tubing T := {t 1 , . . . , t m } on G with respect to T • is the matrix d * (T, T •

	Definition 20. Let T • := {t • 1 , . . . , t • n } be an arbitrary initial maximal tubing on G. The dual com-patibility vector of a tube t of G with respect to T • is the vector d * (t, T • ) := [(t t • 1 ), . . . , (t t • n )].

  Local: the dependence is supported by tubes included in t, i.e. β s = 0 for all s ⊆ t.Theorem 17 follows from the Separating Flip Property and the characterization of complete simplicial fans in Proposition 5. The Span Property and Local Flip Property are not required to get Theorem 17 but we use them to obtain the proof of the Separating Flip Property.

• , s) | s ∈ T ∩ T } separates d(T • , t) and d(T • , t ), i.

e. the coefficients α and α have the same sign different from 0.

Acknoledgements

We thank Francisco Santos for comments and suggestions on a former version of this paper. We also thank an FPSAC referee for pointing out a misleading over-simplification in a previous version of the proof of Theorem 21. Finally, we thank two anonymous referees of JCTA for valuable comments and suggestions for the final version of the paper.

VP was partially supported by the Spanish MICINN grant MTM2011-22792 and by the French ANR grants EGOS (12 JS02 002 01) and SC3A (15 CE40 0004 01).

We now label by v i j the vertices of G according to the labels v i j of G and by v i j the vertices of G according to the labels v i j of G . We follow the two cases above: Body case: We set := +1, n i := n i for i ∈ [ ] and n = 0. For any i ∈ [ ] and 0 ≤ j ≤ n i , we label by v i j the vertex of G corresponding to the vertex labeled by v i j in G, and similarly we label by v i j the vertex of G corresponding to the vertex labeled by v i j in G . Finally, we label s by v 0 and s by v 0 . Leg case: Assume that the neighbor of s maintained by Φ corresponds to the vertex labeled by v a 0 in G. Then the neighbor of s corresponds to the vertex labeled by v a na in G . We set := , n i := n i for i ∈ [ ] {a} and n a := n a + 1. For any i ∈ [ ] and 0 ≤ j ≤ n i , we label by v i j if i = a and v i j+1 if i = a the vertex of G corresponding to the vertex labeled by v i j in G and by v i j the vertex of G corresponding to the vertex labeled by v i j in G . Finally, we label s by v a 0 and s by v a na . By our previous description of the graphs G and G , these labelings are indeed valid labelings of spiders, meaning that the edges of G are indeed given by

and similarly for G . We moreover claim that Φ is given by

It is immediate for all tubes compatible with {s} = {v a 0 } as it is easily transported from (6). Therefore, we only have to check it for the tubes of G adjacent to s = v a 0 and not containing it. Observe first that Φ v a 1 , v a k is a tube with k vertices (by Lemma 82 (iii)), and that it contains s = v a na since it has to be incompatible with Φ({s}

. with k a = -1). Since the nested tubes t and t ∪ {s} are both swapped, we have Φ(t) = Φ(t ∪ {s}) ∪ {s }. Since Φ(t ∪ {s}) is given by Equation (7), so is Φ(t). This concludes the proof that Φ is given by Equation ( 7), so that it coincides with Ω up to the graph automorphism defined by v i j → v i j . We now prove that if the primal and dual compatibility fans of G with respect to the same initial maximal tubing T • are linearly isomorphic, then G is an octopus whose head is contained in no tube of T • .

Proof of Lemma 46. Consider a graph G and an initial tubing T • such that the fans D(G, T • ) and D * (G, T • ) are linearly isomorphic. The fans D(G, T • ) and D * (G, T • ) both contains precisely n pairs of opposite rays, given by the vectors e i of the canonical basis and their opposites -e i . Therefore, the fans D(G, T • ) and D * (G, T • ) have the same rays, which implies that the compatibility vector d(T • , t) and dual compatibility vector d * (t, T • ) are collinear for any tube t of G. In other words, we have (t

We now prove by induction that this condition implies that G is an octopus whose head is contained in no tube of T • . The result is clear when |V| ≤ 3. Consider thus a connected graph G on more than 4 vertices and a maximal tubing

We know that G 1 is an octopus whose head v is contained in no tube of T • . Otherwise, by induction hypothesis, we could find three tubes t, t

2 are also tubes of G. Assume now that G 1 is not a path. We distinguish five cases:

• Suppose that v is the unique vertex of G 1 adjacent to u.

• Suppose that u is adjacent to a single leg H of G 1 {v} but not to v.

), contradicting our assumption on T • . Thus, G 1 is a path. A similar case analysis shows that G 1 is attached to u only by one of its endpoints. By symmetry, all components G 1 , . . . , G k of G {u} are paths attached to u only by an endpoint, so that G is an octopus whose head is contained in no tube of T • .

Proof of Corollaries 47 and 48. Consider the compatibility fans on all maximal tubings on G. Two maximal tubings related by a graph automorphism of G clearly produce the same primal and dual compatibility fans. Reciprocally, consider two compatibility fans D(G, T • 1 ) and D(G, T • 2 ) of the graph G. As already observed in the introduction of Section 5.2, a linear isomorphism between D(G, T • 1 ) and D(G, T • 2 ) induces a nested complex automorphism Φ of N (G). If Φ is not trivial, then Theorem 44 ensures that G is a spider and Φ dualizes the compatibility degree. Therefore, G is an octopus by Lemma 46. This concludes the proof of Corollary 47 since the path is the only graph which is simultaneously a spider and an octopus. The proof of Corollary 48 follows the same lines, distinguishing the cases of spiders and octopuses. 6.6. Polytopality of compatibility fans (Theorem 54 and Proposition 56). This section provides the proof of the polytopality results presented in Section 5.3. Using a similar method as [CSZ15, Section 5] based on Proposition 52, we first prove that all compatibility and dual compatibility fans of paths and cycles are polytopal.

Proof of Theorem 54. We use the characterization of polytopality of complete simplicial fans given in Proposition 52. For this, we need to understand better the linear dependences on compatibility vectors for paths and cycles.

We specialize the notations introduced in the beginning of the proof of Lemma 75 to the setting of paths and cycles. Let t and t be the exchanged tubes, let r (resp. r ) be the unique neighbor of t (resp. t ) in t t (resp. in t t ), and let t 1 , . . . , t k be the connected components of G[t ∩ t ] (where G is a path or a cycle). We then consider

t i , a := t (t ∪ {r}) and a = t (t ∪ {r }).

Consider first the case of the path. When (T ∪ T ) ∩ T • = ∅, the linear dependences can only be of the form

up to exchanging simultaneously t with t and a with a . If T ∩ T contains a tube t • ∈ T • , then the compatibility degree of all tubes of (T ∪ T ) {t • } with t • vanishes, so that the tube t • cannot appear in the linear dependence. When t, t / ∈ T • but (T ∩ T ) ∩ T • = ∅, the relations are thus obtained from the ones above by deleting terms in their right hand sides. The dependences when t or t belong to T • will be treated separately.

We now define a height function ω on tubes on P n+1 by

where f : R → R >0 is any strictly concave increasing positive function and Ω ∈ R is a large enough constant. When (T ∪ T ) ∩ T • = ∅, we obtain by definition of t, t, a and a , and using that f is and Φ( w ) are non-adjacent singletons in G, we conclude that G is an octopus. Since Φ( V) = {v}, the graph Ḡ is a spider and the reader can check that the restriction of Φ to the link of V in the design nested complex N ( Ḡ) is the non-trivial isomorphism Ω : N ( Ḡ) → N (G {v}) defined in Section 5.2. It follows that Φ coincides with Ω.

Proof of Theorem 67. If G is the path P n , then its design nested complex N (G) is isomorphic to the nested complex N (P n+1 ) by Example 62 (ii). Therefore, the design nested complex N (G ) is also isomorphic to the nested complex N (P n+1 ), which implies that G is the path P n by Proposition 64. We can therefore assume that G and G are not paths. Let V and V denote the vertex sets of G and G . By Lemma 84, the link of V in N (G) is the nested complex N (G). With a similar argument as in the proof of Lemma 78, it follows that its image Φ(V) is either a square tube of G , or a singleton round tube of G , or the round tube V of G . We treat these situations separately.

if Φ(V) = v : All tubes of G incompatible with Φ(V) = v are round tubes containing v . Thus by Lemma 85, the graphs G and G are paths, which we already excluded. if Φ(V) = V : By Lemma 84, Φ induces a non-trivial nested complex isomorphism Ψ from N (G)

to N (G ). It follows from Theorem 44 that G and G are isomorphic spiders and Ψ coincides with the non-trivial nested complex isomorphism Ω described in Section 5.2. It thus suffices to show that the nested complex isomorphism Ω cannot be extended to design nested complexes. For this observe first that such an extension would send square tubes to square tubes. Now consider a singleton {v} of G swapped by Ω. This singleton {v} is incompatible with the square tube v and compatible with all other square tubes of G. Yet its image is incompatible with more than one square tube, a contradiction. if Φ(V) = {v }: The link of {v } in the design nested complex N (G ) is a design nested complex isomorphic to the nested complex N (G). By Proposition 64, we obtain that G is an octopus and Φ -1 (V ) is the singleton containing its central vertex. Since Φ -1 (V ) = V, the same argument applies to Φ -1 and shows that G is also an octopus with the same legs as G. Moreover Proposition 64 describes the images of round tubes of G by Φ and of round tubes of G by Φ -1 , which together forces Φ to coincide with the map Ω .