On maximal weakly separated set-systems

DOI 10.1007/s10801-010-0224-x

On maximal weakly separated set-systems

Vladimir I. Danilov·Alexander V. Karzanov· Gleb A. Koshevoy

Received: 10 November 2009 / Accepted: 23 March 2010 / Published online: 21 April 2010

© Springer Science+Business Media, LLC 2010

Abstract For a permutation ω∈Sn, Leclerc and Zelevinsky in Am. Math. Soc.

Transl., Ser. 2 181, 85–108 (1998) introduced the concept of anω-chamber weakly separated collection of subsets of{1,2, . . . , n}and conjectured that all inclusionwise maximal collections of this sort have the same cardinality(ω)+n+1, where(ω)is the length ofω. We answer this conjecture affirmatively and present a generalization and additional results.

Keywords Weakly separated sets·Rhombus tiling·Generalized tiling·Weak Bruhat order·Cluster algebras

1 Introduction

For a positive integern, let[n] denote the ordered set of elements 1,2, . . . , n. We deal with two binary relations on subsets of[n].

(1.1) ForA, B⊆ [n], we write:

(i) AB if B−A is nonempty and ifi < j holds for anyi∈A−B and j∈B−A(whereA−Bstands for the set difference{i:Ai∈B});

V.I. Danilov·G.A. Koshevoy

Central Institute of Economics and Mathematics of the RAS, 47, Nakhimovskii Prospect, 117418 Moscow, Russia

V.I. Danilov

e-mail:danilov@cemi.rssi.ru G.A. Koshevoy

e-mail:koshevoy@cemi.rssi.ru

A.V. Karzanov (

Institute for System Analysis of the RAS, 9, Prospect 60 Let Oktyabrya, 117312 Moscow, Russia e-mail:sasha@cs.isa.ru

(ii) AB if bothA−B andB−Aare nonempty and if the setB−Acan be (uniquely) expressed as a disjoint unionBBof nonempty subsets so that BA−BB.

Note that these relations need not be transitive in general. For example, 132324 but 1324; similarly, 346256157 but 346157, where for brevity we write i . . . jinstead of{i} ∪ · · · ∪ {j}.

Definition 1 SetsA, B⊆ [n]are called weakly separated (from each other) if either AB, or BA, orAB and|A| ≥B, orBA and|B| ≥ |A|, orA=B. A collectionC⊆2^[n]is called weakly separated if any two of its members are weakly separated.

We will usually abbreviate the term “weakly separated collection” to “ws- collection”. When a setXis weakly separated from a setY (from all sets in a collec- tionC), we writeX

ws Y (resp.X

ws C).

Definition 2 Letωbe a permutation on[n]. A subsetX⊂ [n]is called anω-chamber set ifi∈X,j < iandω(j ) < ω(i)implyj∈X. A ws-collectionC⊆2^[n]is called anω-chamber ws-collection if all members ofCareω-chamber sets.

These notions were introduced by Leclerc and Zelevinsky in [8] where their im- portance is demonstrated, in particular, in connection with the problem of characteriz- ing quasicommuting quantum flag minors of a genericq-matrix. (Note that [8] deals with a relation≺which is somewhat different from; nevertheless, Definition1is consistent with the corresponding definition in [8]. The term “ω-chamber” for a set Xis motivated by the fact that such anX corresponds to a face, or chamber, in the pseudo-line arrangement related to some reduced word forω; see [1].)

Let(ω)denote the length ofω, i.e. the number of pairsi < j such thatω(j ) <

ω(i)(inversions). It is shown in [8] that the cardinality |C|of anyω-chamber ws- collectionC⊆2^[n]does not exceed(ω)+n+1 and is conjectured (Conjecture 1.5 there) that this bound is achieved by any (inclusionwise) maximal collection among these:

(C) For any permutation ωon [n],|C| =(ω)+n+1 holds for all maximal ω- chamber ws-collectionsC⊆2^[n].

The main purpose of this paper is to answer this conjecture.

Theorem A Statement (C) is valid.

The longest permutationω0on[n](defined byi→n−i+1) is of especial inter- est, many results in [8] are devoted just to this case, and (C) withω=ω0has been open so far as well. Sinceω0(j ) > ω0(i)for anyj < i, no “chamber conditions” are imposed in this case in essence, i.e. the set ofω0-chamber ws-collections consists of all ws-collections. The length ofω0is equal to_n

2

, so the above upper bound turns into_n+1

2

+1. Then the assertion in the above theorem is specified as follows.

Theorem B All maximal ws-collections in 2^[n]have the same cardinality_n+1

2

+1.

We refer to a ws-collection of this cardinality as a largest one and denote the set of these collections by Wn. An important instance is the setIn of all intervals [p..q] := {p, p+1, . . . , q}in[n], including the “empty interval”∅. One can see that for a ws-collectionC, the collection{[n]−X:X∈C}is weakly separated as well; it is called the complementary ws-collection ofCand denoted by co-C. Therefore, co-In, the set of co-intervals in[n], is also a largest ws-collection. In [8] it is shown that Wnis preserved under so-called weak raising flips (which transform one collection into another) and is conjectured (Conjecture 1.8 there) that in the poset structure on Wninduced by such flips,Inand co-Inare the unique minimal and unique maximal elements, respectively. That conjecture was affirmatively answered in [4].

We will show that TheoremAcan be obtained relatively easily from TheoremB.

The proof of the latter theorem is more intricate and takes the most part of this paper.

The breakthrough step on this way consists of showing the following lattice property for a largest ws-collectionC: the partial order≺^∗onC given byA≺^∗B⇐⇒A B&|A| ≤ |B|forms a lattice. To prove this and some other intermediate results we will essentially use results and constructions from our previous work [4].

The main result in [4] shows the coincidence of four classes of collections: (i) the set of semi-normal bases of tropical Plücker functions on 2^[n]; (ii) the set of spectra of certain collections ofncurves on a disc in the plane, called proper wirings (which generalize commutation classes of pseudo-line arrangements); (iii) the set STn of spectra of so-called generalized tilings on an n-zonogon (a 2n-gon representable as the Minkowsky sum of n generic line segments in the plane); and (iv) the set Wn. Objects mentioned in (i) and (ii) are beyond our consideration in this paper (for definitions, see [4]), but we will extensively use the generalized tiling model and rely on the equality STn=Wn. Our goal is to show the following property:

Any ws-collection can be extended to the spectrum of some generalized tiling, whence TheoremBwill immediately follow. Due to this property, generalized tilings give a geometric model for ws-collections.

Roughly speaking, a generalized tiling, briefly called a g-tiling, is a certain gen- eralization of the notion of a rhombus tiling. While the latter is a subdivision of an n-zonogonZinto rhombi, the former is a cover ofZwith rhombi that may overlap in a certain way. (It should be noted that rhombus tilings have been well studied, and one of important properties of these is that their “spectra” turn out to be exactly the maximal strongly separated collections, whereC⊆2^[n]is called strongly separated if any two members ofCobey relationas in (1.1)(i). Leclerc and Zelevinsky explored such collections in [8] in parallel with ws-collections. In particular, they established a counterpart of TheoremAsaying that the cardinality of any maximal strongly sepa- ratedω-chamber collection is exactly(ω)+n+1. For a wider discussion and related topics, see also [1,3,5–7,9].)

This paper is organized as follows. Section2explains how to reduce TheoremAto TheoremB. Then we start proving the latter theorem; the whole proof lasts through- out Sects.3–6. Section 3 recalls the definitions of a g-tiling and its spectrum and gives a review of properties of these objects established in [4] that are important for us. Sections4proves TheoremBunder the assumption of validity of the above- mentioned lattice property of largest ws-collections. Then there begins a rather long

way of proving the latter property stated in Theorem4.1. In Sect.5we associate to a g-tilingT a certain acyclic directed graphΓ =Γ_T whose vertex set is the spectrum ST ofT (forming a largest ws-collection) and show that the natural partial order≺Γ

induced byΓ forms a lattice, which is not difficult. Section6is devoted to proving the crucial property that≺Γ coincides with the partial order≺^∗onS_T, thus yield- ing Theorem4.1and completing the proof of TheoremB; this is apparently the most sophisticated part of the paper where special combinatorial techniques of handling g- tilings are elaborated. The concluding Sect.7presents additional results and finishes with a generalization of TheoremA. This generalization (TheoremA) deals with two permutationsω, ωon[n]such that each inversion ofωis an inversion ofω(in this case the pair(ω, ω)is said to obey the weak Bruhat relation). It asserts that all maximal ws-collections whose membersX areω-chamber sets and simultaneously satisfy the condition:i∈X&j > i&ω(j ) < ω(i)⇒j∈X, have the same car- dinality, namely,(ω)−(ω)+n+1. Whenωis the identical permutationi→i, this turns into TheoremA.

In the following, for a setX⊂ [n], distinct elementsi, . . . , j ∈ [n] −X and an elementk∈X, we usually abbreviateX∪ {i} ∪ · · · ∪ {j}asXi . . . j, andX− {k}as X−k.

2 Maximalω-chamber ws-collections

In this section we explain how to derive TheoremAfrom TheoremB. The proof given here is direct and relatively short, though rather technical. Another proof, which is more geometric and appeals to properties of tilings, will be seen from a discussion in Sect.7. Letωbe a permutation on[n].

Fork=0, . . . , n, letI_ω^k denote the setω⁻¹[k] = {i:ω(i)∈ [k]}, calledk-th ideal forω(it is an ideal of the linear order on[n]given by:i≺j ifω(i) < ω(j )). We will use the following auxiliary collection

C⁰=Cω⁰:=

I_ω^k∩ [j..n]: 1≤j≤ω⁻¹(k),0≤k≤n

, (2.1)

where possible repeated sets are ignored and whereI_ω⁰:= ∅. The role of this collec- tion is emphasized by the following

Theorem 2.1 LetX⊂ [n]andX∈C⁰. The following properties are equivalent:

(i) X

ws C⁰(i.e.Xis weakly separated from all sets inC⁰);

(ii) Xis anω-chamber set.

Due to this property, we callC⁰the (canonical) ω-checker. (We shall explain in Sect.7thatC⁰is chosen to be the spectrum of a special tiling and that there are other tilings whose spectra can be taken as a checker in place ofC⁰in Theorem2.1; see Corollary7.2.) It is easy to verify that: (a)C⁰is a ws-collection; (b) its subcollection

Iω:=

I_ω⁰, I_ω¹, . . . , I_ωⁿ

(2.2) consists ofω-chamber sets; and (c) any member ofC⁰−Iωis not anω-chamber set.

Relying on TheoremsBand2.1, we can prove TheoremAas follows. Given an ω-chamber ws-collectionC⊂2^[n], considerC:=C∪C⁰. By Theorem2.1,C is a ws-collection. AlsoC∩C⁰⊆Iω, in view of (c) above. Extend C to a largest ws- collectionD, which is possible by TheoremB. LetD:=(D−C0)∪Iω. ThenD includesCand is anω-chamber ws-collection by Theorem2.1. Since the cardinality ofD is always the same (as it is equal to_n+1

2

+1− |C⁰−Iω|),D is a largest ω-chamber ws-collection, and now TheoremAfollows from the fact that the upper size bound(ω)+n+1 is achieved by someω-chamber weakly (or even strongly) separated collection.

The rest of this section is devoted to proving Theorem2.1. The proof of implica- tion (i)⇒(ii) falls into three lemmas. LetX⊂ [n]be such thatX∈C⁰andX

ws C⁰, and letk:= |X|andY :=I_ω^k.

Lemma 2.2 NeitherY XnorY Xcan take place.

Proof SupposeY X orY X. Letk be the maximum number such that either YXorYX, whereY:=I_ω^k. Thenk≤kandY⊆Y. Define

Δ:=Y−X and Δ:=

i∈X−Y:Δ{i} .

ThenΔ, Δ= ∅and|Δ| ≥ |Δ|. The maximality ofkimplies that|Δ| =1 and that the unique element ofΔ, say,a, is exactlyω⁻¹(k+1)(in all other cases eitherk+1 fits as well, orXis not weakly separated fromI_ω^k+1).

Letb be the maximal element inΔ. Thena > band the elementk˜:=ω(b)is at mostk. We assert that there is nod ∈Xsuch thatd < b. To see this, consider the setsI_ω^k˜andZ:=I_ω^k˜∩ [b..n]. ThenZ∈C⁰andZ⊆I_ω^k˜⊆Y. Therefore,a∈X−Z.

Alsob∈Z−X. Moreover,Z−X= {b}, by the maximality ofb. Now ifXcontains an elementd < b, then we have|X|>|Z|(in view ofa, d∈X−Zand|Z−X| =1) andZX(in view ofd < b < a), which contradictsX

ws C⁰.

Thus, all elements ofXare greater thanb. This andX−Y= {a}imply that the setU:=Y∩ [b..n]satisfiesX−U= {a}andU−X= {b}. ThenXcoincides with the setI_ω^k+1∩[b+1..n]. But the latter set belongs toC⁰(sinceω⁻¹(k+1)=a > b).

SoXis a member ofC⁰; a contradiction.

Lemma 2.3 XY cannot take place.

Proof SupposeXY. Take the maximalksuch that the setY:=I_ω^k satisfiesX− Y= ∅. Thenk≥kand|X−Y| =1. Sincek≤kimpliesY⊆Y, we haveXY. Also|Y−X| ≥ |Y−X| ≥2. Then|X|<|Y|, contradictingX

ws Y.

In view of X

ws Y, Lemmas 2.2and 2.3imply that only the case XY is possible.

Lemma 2.4 LetXY. ThenXis anω-chamber set.

Proof Suppose that there existi∈X andj∈X such thatj < i andω(j ) < ω(i).

Consider possible cases.

Case 1:i∈Y. Thenω(j ) < ω(i)implies thatj ∈Y. Taked ∈X−Y (existing since|X| = |Y|). Thend < j (sinceXY andj ∈Y −X). LetY:=I_ω^{ω(j )}. We havej∈Y,i∈Yandd∈Y. This together withX

ws Yandd < j < i implies YX. But|X| = |Y|>|Y|(in view ofω(j ) < ω(i)≤k); a contradiction.

Case 2:i, j∈Y. Thenω(i), ω(j ) > k. Takea∈Y −X. SinceXY, we have a > i. Alsoω(a)≤k. LetY:=I_ω^{ω(j )}. Then|Y|>|Y|(in view ofω(j ) > k). Also a, j∈Y−Xandi∈X−Y. Therefore,XY, contradicting|X| = |Y|<|Y|.

Finally, the case withi∈Y andj∈Y is impossible sincei > jandXY. Thus, (i)⇒(ii) in Theorem2.1is proven. Now we prove the other direction.

Lemma 2.5 LetX⊂ [n]be anω-chamber set. ThenX

ws C⁰.

Proof Consider an arbitrary setY=I_ω^k∩ [j..n]inC⁰(wherej≤ω⁻¹(k)). One may assume that bothX−Y andY−Xare nonempty. Leta∈Y−Xandb∈X−Y. We assert thata > b(whenceXY follows).

Indeed,a∈Y impliesω(a)≤k. Ifb∈I_ω^k, thenω(b) > k≥ω(a). In casea < b we would havea∈X, by theω-chamberness ofX. Therefore,a > b, as required.

Now supposeb∈I_ω^k. Thenb∈I_ω^k− [j..n], and therefore,b < j. Sincej≤a, we

again obtaina > b.

This completes the proof of Theorem2.1, reducing TheoremAto TheoremB.

3 Generalized tilings and their properties

As mentioned in the Introduction, the proof of TheoremBwill essentially rely on results on generalized tilings from [4]. This section starts with definitions of such objects and their spectra. Then we review properties of generalized tilings that will be important for us later: Subsect.3.2describes rather easy consequences from the defining axioms and Subsect.3.3is devoted to less evident properties.

3.1 Generalized tilings

Tiling diagrams that we deal with live within a zonogon, which is defined as follows.

In the upper half-planeR×R₊, takennon-colinear vectorsξ₁, . . . , ξ_nso that:

(3.1) (i) ξ₁, . . . , ξ_nfollow in this order clockwise around(0,0), and (ii) all integer combinations of these vectors are different.

Then the set

Z=Z_n:= {λ1ξ1+ · · · +λ_nξ_n:λ_i∈R, 0≤λ_i≤1, i=1, . . . , n}

is a 2n-gon. Moreover,Zis a zonogon, as it is the sum ofnline segments{λξ_i: 1≤ λ≤1},i=1, . . . , n. Also it is the image by a linear projectionπ of the solid cube

conv(2^[n])into the planeR², defined by π(x):=x₁ξ₁+ · · · +x_nξ_n.The boundary bd(Z) of Z consists of two parts: the left boundary lbd(Z) formed by the points (vertices)z_i :=ξ₁+ · · · +ξ_i(i=0, . . . , n) connected by the line segmentsz_i−1z_i :=

z_i−1+ {λξ_i: 0≤λ≤1}, and the right boundary rbd(Z)formed by the pointsz^r_i :=

ξi+1+ · · · +ξn(i=0, . . . , n) connected by the line segmentsz^r_iz^r_i−1. Soz₀=z^r_n is the minimal vertex ofZ, denoted asz0, andz_n=z^r₀is the maximal vertex, denoted asz_n. We direct each segmentz_i−1z_i fromz_i−1toz_i and direct each segmentz_i^rz^r_i−1 fromz^r_i toz^r_i−1.

When it is not confusing, a subsetX⊆ [n] is identified with the corresponding vertex of the n-cube and with the point

i∈Xξ_i in the zonogon Z (and we will usually use capital letters when we are going to emphasize that a vertex (or a point) is considered as a set). Due to (3.1)(ii), all such points inZare different.

By a (pure) tiling diagram we mean a subdivisionT ofZinto tiles, each being a parallelogram of the formX+ {λξ_i+λξ_j: 0≤λ, λ≤1}for somei < j and some subsetX⊂ [n](regarded as a point inZ); so the tiles are pairwise non-overlapping (have no common interior points) and their union isZ. A tileτ determined byX, i, j is called anij-tile atXand denoted byτ (X;i, j ). According to a natural visualiza- tion ofτ, its verticesX, Xi, Xj, Xijare called the bottom, left, right, top vertices of τ and denoted byb(τ ),(τ ),r(τ ),t (τ ), respectively. The edge fromb(τ )to(τ )is denoted by bl(τ ), and the other three edges ofτ are denoted as br(τ ),lt(τ ),rt(τ )in a similar way.

In fact, it is not important for our purposes which set of base vectorsξ_i is chosen, subject to (3.1). (In works on a similar subsect, it is most often when the ξ_i are assumed to have equal Euclidean norms; in this case each tile forms a rhombus and T is usually referred to as a rhombus tiling.) However, to simplify technical details and visualization, it will be convenient for us to assume that these vectors always have unit height, i.e. eachξ_i is of the form(a_i,1). Then each tile becomes a parallelogram of height 2. Accordingly, we say that: a point (subset)Y ⊆ [n]is of height|Y|; the set of vertices of tiles inT having heighthformsh-th level; and a pointY lies to the right of a pointYif|Y| = |Y|and

i∈Yξi≥

i∈Yξi.

In a generalized tiling, or a g-tiling, some tiles may overlap. It is a collectionT of tilesτ (X;i, j )which is partitioned into two subcollectionsT^wandT^b, of white and black tiles, respectively, obeying axioms (T1)–(T4) below. WhenT^b= ∅,T becomes a pure tiling.

We associate toT the directed graph G_T =(V_T, E_T)whose vertices and edges are, respectively, the points and line segments occurring as vertices and sides in the tiles ofT (not counting multiplicities). An edge connecting vertices X and Xi is directed from the former to the latter; such an edge (parallel toξi) is called an edge with labeli, or ani-edge ([4] uses the term “color” rather than “label”). For a vertex v∈VT, the set of edges incident withv is denoted byET(v), and the set of tiles having a vertex atvis denoted byF_T(v).

(T1) Each boundary edge ofZ belongs to exactly one tile. Each edge in E_T not contained in bd(Z)belongs to exactly two tiles. All tiles inT are different, in the sense that no two coincide in the plane.

(T2) Any two white tiles having a common edge do not overlap, i.e. they have no common interior point. If a white tile and a black tile share an edge, then these tiles do overlap. No two black tiles share an edge.

See the picture; here all edges are directed up and the black tiles are drawn in bold.

(T3) Letτ be a black tile. None ofb(τ ), t (τ )is a vertex of another black tile. All edges inET(b(τ )) leaveb(τ ), i.e. they are directed fromb(τ ). All edges in E_T(t (τ ))entert (τ ), i.e. they are directed tot (τ ).

We refer to a vertexv∈V_T as terminal ifv is the bottom or top vertex of some black tile. A nonterminal vertexvis called ordinary if all tiles in F_T(v)are white, and mixed otherwise (i.e.vis the left or right vertex of some black tile). Note that a mixed vertex may belong, as the left or right vertex, to several black tiles.

Each tileτ∈T corresponds to a square in the solid cube conv(2^[n]), denoted by σ (τ ): if τ =τ (X;i, j ) thenσ (τ ) is the convex hull of the points X, Xi, Xj, Xij in the cube (so π(σ (τ ))=τ). (T1) implies that the interiors of these squares are pairwise disjoint and that

(σ (τ ):τ∈T )forms a 2-dimensional surface, denoted by D_T, whose boundary is the preimage byπof the boundary ofZ. The last axiom is:

(T4) D_T is a disc, in the sense that it is homeomorphic to{x∈R²:x₁²+x₂²≤1}.

The reversed g-tilingT^revof a g-tilingT is formed by replacing each tileτ (X;i, j ) ofT by the tileτ ([n] −Xij;i, j )(or, roughly speaking, by changing the orientation of all edges inE_T, in particular, in bd(Z)). Clearly (T1)–(T4) remain valid forT^rev.

The spectrum of a g-tilingT is the collectionST of (the subsets of[n]represented by) nonterminal vertices inG_T. Figure1illustrates an example of g-tilings; here the unique black tile is drawn by thick lines and the terminal vertices are indicated by black rhombi.

The following result on g-tilings is of most importance for us.

Theorem 3.1 ([4]) The spectrum ST of any generalized tiling T forms a largest ws-collection. Conversely, for any largest ws-collectionC⊆2^[n], there exists a gen-

Fig. 1 A g-tiling instance forn=4

eralized tilingT onZ_nsuch thatS_T =C. (Moreover, such aT is unique and there is an efficient procedure to constructT fromC.)

In what follows, when it is not confusing, we may speak of a vertex or edge of G_T as a vertex or edge ofT. The map σ of the tiles inT to squares in conv(2^[n]) is extended, in a natural way, to the vertices, edges, subgraphs or other objects in GT. Note that the embedding ofσ (GT)in the discDT is planar (unlikeGT andZ, in general), i.e. any two edges ofσ (G_T)can intersect only at their end points. It is convenient to assume that the clockwise orientations onZ andD_T are agreeable, in the sense that the image byσ of the boundary cycle(z0, z₁, . . . , z_n, z^r₁, . . . , z^r_n=z0) is oriented clockwise around the interior ofDT. Then the orientations on a tileτ∈T and on the squareσ (τ )are consistent whenτ is white, and different whenτ is black.

3.2 Elementary properties of generalized tilings

The properties of g-tilings reviewed in this subsection can be obtained rather easily from the above axioms; see [4] for more explanations. LetT be a g-tiling onZ=Z_n. 1. Let us say that the edges ofT occurring in black tiles (as side edges) are black, and the other edges ofT are white. For a vertexvand two edgese, e∈E_T(v), letΘ(e, e) denote the cone (with angle< π) in the plane pointed atv and generated by these edges (ignoring their directions). When another edgee∈ET(v)(a tileτ∈FT(v)) is contained inΘ(e, e), we say thate (resp.τ) lies betweeneande. When these e, eare edges of a tileτ, we also writeΘ(τ;v)forΘ(e, e)(the conic hull ofτ at v), and denote byθ (τ, v)the angle of this cone taken with sign+ifτ is white, and sign−ifτ is black. The sum

(θ (τ, v):τ∈F_T(v))is denoted byρ(v)and called the full angle atv. Terminal vertices ofT behave as follows.

Corollary 3.2 Letvbe a terminal vertex belonging to a blackij-tileτ. Then:

(i) v is not connected by edge with any other terminal vertex ofT (in particular, E_T(v)contains exactly two black edges, namely, those belonging toτ);

(ii) ET(v)contains at least one white edge and all such edges e, as well as all tiles inFT(v), lie between the two black edges inET(v)(soeis aq-edge with i < q < j);

(iii) ρ(v)=0;

(iv) vdoes not belong to the boundary ofZ(so each boundary edgeeofZ, as well as the tile containinge, is white).

Note that (ii) implies that

(3.2) if a black tileτ and a white tileτ share an edge and if v is their common nonterminal vertex (which is either left or right in bothτ, τ), thenτ is con- tained in the coneΘ(τ;v).

Using this and applying Euler’s formula to the planar graphσ (G_T)onD_T, one can specify the full angles at nonterminal vertices.

Corollary 3.3 Letv∈V_T be a nonterminal vertex.

(i) Ifv belongs to bd(Z), then ρ(v) is equal to the (positive) angle between the boundary edges incident tov.

(ii) Ifvis inner (i.e. not in bd(Z)), thenρ(v)=2π.

2. Using (3.2) and Corollary3.3, one can obtain the following useful (though rather lengthy) description of the local structure of edges and tiles at nonterminal vertices.

Corollary 3.4 Let v be a nonterminal (ordinary or mixed) vertex of T different fromz0, z_n. Let e1, . . . , e_p be the sequence of edges leavingv and ordered clock- wise aroundv (or by increasing their labels), ande₁, . . . , e_p the sequence of edges enteringv and ordered counterclockwise aroundv (or by decreasing their labels).

Then there are integersr, r≥0 such that:

(i) r+r<min{p, p}, the edgeser+1, . . . , e_p−r and e_r+1, . . . , e_p−r are white, the other edges inE_T(v)are black,r=0 ifv∈lbd(Z), andr=0 ifv∈rbd(Z);

(ii) forq=r+1, . . . , p−r−1, the edgese_q, e_q+1are spanned by a white tile (so such tiles have the bottom atvand lie betweene_r+1ande_p−r);

(iii) forq=r+1, . . . , p−r−1, the edgese_q, e_q+1are spanned by a white tileτ (so such tiles have the top atvand lie betweene_r+1ande_p−r);

(iv) unless v ∈ lbd(Z), each of the pairs {e₁, e_r+1},{e₂, e_r}, . . . ,{e_r+1, e₁} is spanned by a white tile, and each of the pairs{e₁, e_r},{e₂, e_r−1}, . . . ,{e_r, e₁} is spanned by a black tile (all tiles have the right vertex atv);

(v) unless v ∈ rbd(Z), each of the pairs {e_p, e_p−r},{e_p−1, e_p−r+1}, . . . , {e_p−r, e_p} is spanned by a white tile, and each of the pairs {ep, e_p−r+1}, {e_p−1, e_p−r+2}, . . . ,{e_p−r+1, e_p}is spanned by a black tile (all tiles have the left vertex atv).

In particular, (a) there is at least one white edge leavingvand at least one white edge enteringv; (b) the tiles in (ii)–(v) give a full list of tiles inF_T(v); and (c) any two tilesτ, τ∈F_T(v)withr(τ )=(τ)=v do not overlap (have no common interior point).

Also: forv=z₀, z_n, all edges in E_T(v) are white and the pairs of consecutive edges are spanned by white tiles.

(Whenv is ordinary, we have r=r=0.) The case withp=4,p=5,r=2, r=1 is illustrated in the picture; here the black edges are drawn in bold and the thin (bold) arcs indicate the pairs of edges spanned by white (resp. black) tiles.

3. In view of (3.1)(ii), the graph G_T =(V_T, E_T)is graded for each label i∈ [n], which means that for any closed pathP inG_T, the amounts of forwardi-edges and backwardi-edges inP are equal. In particular, this easily implies that

(3.3) if four vertices and four edges ofG_T form a (non-directed) cycle, then they are the vertices and edges of a tile (not necessarily contained inT).

Hereinafter, a path in a directed graph is meant to be a sequenceP =(v˜0,e˜1,v˜1, . . . ,e˜r,v˜r) in which eache˜p is an edge connecting vertices v˜p−1,v˜p; an edgee˜p

is called forward if it is directed fromv˜_p−1 to v˜_p (denoted ase˜_p =(v˜_p−1,v˜_p)), and backward otherwise (whene˜_p=(v˜_p,v˜_p−1)). Whenv₀=v_r andr >0, P is a closed path, or a cycle. The pathP is called directed if all its edges are forward, and simple if all vertices v0, . . . , v_r are different. P^rev denotes the reversed path (v˜r,e˜r,v˜r−1, . . . ,e˜1,v˜0). Sometimes we will denote a path without explicitly indi- cating its edges:P =(v˜0,v˜1, . . . ,v˜r). A directed graph is called acyclic if it has no directed cycles.

3.3 Strips, contractions, expansions, and others

In this subsection we describe additional, more involved, results and constructions concerning g-tilings that are given in [4] and will be needed to prove TheoremB.

They are described in Propositions3.5–3.11below.

3.3.1 Strips inT

Definition 3 Leti∈ [n]. Ani-strip (or a duali-path) inT is a maximal alternating sequenceQ=(e₀, τ₁, e₁, . . . , τ_r, e_r)of edges and tiles ofT such that: (a)τ₁, . . . , τ_r are different tiles, each being anij- orj i-tile for somej, and (b) forp=1, . . . , r, e_p−1ande_pare the oppositei-edges ofτ_p.

(Recall that speaking of an ij-tile, we assume that i < j.) In view of ax- iom (T1), Q is determined uniquely (up to reversing it, and up to shifting cycli- cally whene₀=e_r) by any of its edges or tiles. Forp=1, . . . , r, lete_p=(v_p, v_p).

Define the right boundary of Q to be the (not necessarily directed) path R_Q= (v0, a1, v1, . . . , a_r, v_r), where a_p is the edge ofτ_p connectingv_p−1andv_p. Simi- larly, the left boundary ofQis the pathLQ=(v₀, a₁, v₁, . . . , a_r, v_r), where a_p is the edge ofτpconnectingv_p−1andv_p. Then two edgesap, a_p have the same label.

ConsideringR_Qand using the fact thatG_T is graded, one shows that (3.4) Qcannot be cyclic, i.e. the edgese0ande_r are different.

In view of the maximality ofQ, (3.4) implies that one ofe0, er belongs to the left boundary, and the other to the right boundary of the zonogonZ; we assume thatQis directed so thate₀∈lbd(Z)(justifying the assignment of the right and left boundaries forQ). Properties of strips are described in the following

Proposition 3.5 For eachi∈ [n], there is exactly onei-strip, sayQi. It contains all i-edges ofT, begins with the edgez_i−1z_i of lbd(Z)and ends with the edgez_i^rz^r_i−1 of rbd(Z). Furthermore, each ofR_Qi andL_Qi is a simple path,L_Qi is disjoint from R_Qi and is obtained by shiftingR_Qi by the vectorξ_i. An edge ofR_Qi is forward if and only if it belongs to either a whitei∗-tile or a black∗i-tile inQ_i, and similarly for the edges ofL_Qi.

3.3.2 Strip contractions

Leti∈ [n]. PartitionT into three subsetsT_i⁰, T_i⁻, T_i⁺, whereT_i⁰consists of alli∗- and∗i-tiles,T_i⁻ consists of the tilesτ (X;i, j)withi, j=iandi∈X, andT_i⁺ consists of the tilesτ (X;i, j)withi, j=iandi∈X. ThenT_i⁰is the set of tiles occurring in thei-stripQ_i, and the tiles inT_i⁻are vertex disjoint from those inT_i⁺. Definition 4 Thei-contraction of T is the collection T / i of tiles obtained by re- movingT_i⁰, keeping the members ofT_i⁻, and replacing eachτ (X;i, j)∈T_i⁺ by τ (X−i;i, j). The black/white coloring of tiles inT / i is inherited fromT.

So the tiles ofT / i live within the zonogon generated by the vectorsξ_q forq∈ [n] −i. Clearly if we remove from the discD_T the interiors of the edges and squares inσ (Q_i), then we obtain two closed simply connected regions, one containing the squaresσ (τ )for allτ ∈T_i⁻, denoted asD_T−

i , and the other containingσ (τ )for all τ ∈T_i⁺, denoted asD_T+

i . ThenD_{T / i} is the union ofD_T−

i andD_T+

i −_i, where_i isi-th unit base vector inR^[n]. In other words,D_T+

i is shifted by−_i and the path σ (LQ_i)in it (the left boundary ofσ (Qi)) merges with the pathσ (RQ_i)inD_T−

i . In general,D_T−

i andD_T+

i −_i may intersect at some other points, and for this reason, D_{T / i}need not be a disc. Nevertheless,D_{T / i}is shown to be a disc in two important special cases:i=nandi=1; moreover, the following property holds.

Proposition 3.6 Then-contractionT /nofT is a (feasible) g-tiling on the zonogon Z_n−1 generated by the vectors ξ₁, . . . , ξ_n−1. Similarly, the 1-contractionT /1 is a g-tiling on the(n−1)-zonogon generated by the vectorsξ₂, . . . , ξ_n.

(If wished, labels 2, . . . , nforT /1 can be renamed as 1, . . . , (n−1).) We will use then- and 1-contraction operations in Sects.4and6.

3.3.3 Legal paths and strip expansions

Next we describe the n-expansion and 1-expansion operations; they are converse, in a sense, to then-contraction and 1-contraction ones, respectively. We start with introducing the operation forn.

Then-expansion operation applies to a g-tilingT on the zonogonZ=Zn−1gen- erated byξ1, . . . , ξn−1and to a simple (not necessarily directed) pathP in the graph GT beginning at the minimal vertexz0and ending at the maximal vertexz_n−1ofZ.

Thenσ (P )subdivides the discDT into two simply connected closed regionsD, D such that:D∪D=DT,D∩D=σ (P ),Dcontainsσ (lbd(Z)), andDcontains σ (rbd(Z)). LetT:= {τ∈T:σ (τ )⊂D}andT:=T −T. We disconnectD, D alongσ (P )by shiftingD by the vector_n, and then connect them by adding the corresponding strip of∗n-tiles.

More precisely, we construct a collectionT˜ of tiles on the zonogon Z_n, called the n-expansion of T along P, as follows. The tiles of T are kept and each tile τ (X;i, j )∈T is replaced byτ (Xn;i, j ); the white/black coloring on these tiles is

inherited. For each edgee=(X, Xi)ofP, we add tileτ (X;i, n), making it white if eis forward, and black ifeis backward inP. The resultingT˜ need not be a g-tiling in general; for this reason, we impose additional conditions onP.

Definition 5 P as above is called ann-legal path if it satisfies the following three conditions:

(i) all vertices ofP are nonterminal;

(ii) P contains no pair of consecutive backward edges;

(iii) for ani-edgeeand aj-edgee such thate, eare consecutive edges occurring in this order inP: ifeis forward andeis backward inP, theni > j, and ifeis backward andeis forward, theni < j.

In view of (ii),P is represented as the concatenation ofP₁, . . . , P_n−1, whereP_h is the maximal subpath ofP whose edges connect levelsh−1 andh(i.e. are of the form(X, Xi)with|X| =h−1). In view of (iii), each pathP_hhas planar embedding inZ; it either contains only one edge, or is viewed as a zigzag path going from left to right. The first and last vertices of these subpaths are called critical vertices ofP. The importance of legal paths is seen from the following

Proposition 3.7 Then-expansion ofT alongPis a (feasible) g-tiling on the zonogon Z_nif and only ifP is ann-legal path.

Under then-expansion operation, the pathP generates then-stripQ_nof the re- sulting g-tilingT˜; more precisely, the right boundary ofQ_nis the reversed pathP^rev toP, and the left boundary ofQ_n is obtained by shiftingP^rev by ξ_n. A possible fragment ofP consisting of three consecutive edgese, e, e forming a zigzag and the corresponding fragment inQ_n (with two white tiles created frome, e and one black tile created frome) are illustrated in the picture; here the shiftede, e, e are indicated with tildes.

Then-contraction operation applied toT˜ returns the initialT. A relationship be- tweenn-contractions andn-expansions is described in the following

Proposition 3.8 The correspondence(T , P )→ ˜T, whereT is a g-tiling onZ_n−1,P is ann-legal path forT, andT˜ is then-expansion ofT alongP, gives a bijection between the set of such pairs(T , P )and the set of g-tilings onZ_n.

In its turn, the 1-expansion operation applies to a g-tilingT on the zonogonZ generated by the vectorsξ₂, . . . , ξ_n(so we deal with labels 2, . . . , n) and to a simple pathP inG_T from the minimal vertex to the maximal vertex ofZ; it produces a

g-tilingT˜ on Z_n. This is equivalent to applying the n-expansion operation in the mirror-reflected situation: when labeliis renamed as labeln−i+1 (and accordingly a tileτ (X;i, j )inT is replaced by the tileτ ({k:n−k+1∈X};n−j +1, n−i+ 1), preserving the basic vectorsξ1, . . . , ξ_n). The corresponding “1-analogues” of the above results onn-expansions are as follows.

Proposition 3.9 (i) The 1-expansionT˜ ofT alongP is a g-tiling onZnif and only ifP is a 1-legal path, which is defined as in Definition 5 with the only difference that each subpathP_h ofP (formed by the edges connecting levelsh−1 andh) either contains only one edge, or is a zigzag path going from right to left.

(ii) The 1-contraction operation applied toT˜ returns the initialT.

(iii) The correspondence(T , P )→ ˜T, whereT is a g-tiling on the zonogon gener- ated byξ₂, . . . , ξ_n,P is a 1-legal path forT, andT˜is the 1-expansion ofT alongP, gives a bijection between the set of such pairs(T , P )and the set of g-tilings onZn. 3.3.4 Principal trees

LetT be a g-tiling onZ=Z_n. We distinguish between two sorts of white edgese ofG_T by saying thateis fully white if both of its end vertices are nonterminal, and semi-white if one end vertex is terminal. (Recall that an edgeeofG_T is called white if no black tile containse(as a side edge); the case when both ends ofeare terminal is impossible, cf. Corollary3.2(i).) In particular, all boundary edges ofZ are fully white.

The following result on structural features of the set of white edges is obtained by using Corollary3.4.

Proposition 3.10 Forh=1, . . . , n, letH_h denote the subgraph ofG_T induced by the set of white edges connecting levelsh−1 andh(i.e. of the form(X, Xi)with

|X| =h−1). ThenH_his a forest. Furthermore:

(i) there exists a component (a maximal tree)K_hofH_hthat contains all fully white edges ofHp(in particular, the boundary edgesz_h−1z_handz^r_n−h+1z^r_n−h) and no other edges; moreover,Khhas planar embedding inZ;

(ii) any other componentKofH_hcontains exactly one terminal vertexv; thisKis a star atvwhose edges are the (semi-)white edges incident tov.

It follows that the subgraphG^fw=G^fw_T ofGT induced by the fully white edges has planar embedding inZ. We refer toK_h in (i) of the proposition as the principal tree inH_h. The common vertices of two neighboring principal treesK_h, K_h+1 will play an important role later; we call them critical vertices forT in levelh.

3.3.5 Additional facts

Two more useful facts (which look so natural but their proofs are not straightforward) concern relations between vertices and edges inG_T and tiles inT.

Proposition 3.11 (i) Any two nonterminal vertices of the formX, XiinG_T are con- nected by edge. (Such an edge need not exist when some ofX, Xiis terminal.)

(ii) If four nonterminal vertices are connected by four edges forming a cycle in G_T, then there is a tile inT having these vertices and edges. (Cf. (3.3).)

4 Proof of TheoremB

In this section we explain how to obtain TheoremBunder the assumption of validity of the following statement, which is interesting in its own right. Recall that for sets A, B⊆ [n], we writeA≺^∗BifABand|A| ≤ |B|.

Theorem 4.1 LetC be a largest ws-collection. Then the partial order onC deter- mined by≺^∗forms a lattice.

Here the fact that(C,≺^∗)is a poset (partially ordered set) is an immediate con- sequence of the following simple, but important, property established in [8], which describes a situation when the relationbecomes transitive:

(4.1) for sets A, A, A⊆ [n], if AAA, A

ws A and|A| ≤ |A| ≤ |A|, thenAA.

Theorem4.1 will be proved in Sects. 5 and6. Relying on this, the method of proving that any ws-collectionC⊆2^[n]is contained in a largest ws-collection in 2^[n] (yielding TheoremB) is roughly as follows. We first reduceCto a ws-collection of subsets of[n−1]and then extend the latter to a maximal ws-collectionCin 2^[n−1]. One may assume by induction onnthatC is a largest ws-collection; so, by Theo- rem 3.1,Cis the spectrum of some g-tilingT on the zonogonZ_n−1. Theorem4.1 applied toCis then used to show the existence of an appropriaten-legal pathP for T. Applying then-expansion operation to(T, P )(as described in Subsect.3.3.3), we obtain a g-tilingT onZ_nwhose spectrum containsC, whence the result follows.

We need two lemmas (where we writeXY if eitherXY orX=Y).

Lemma 4.2 (i) LetACandBC. Then eitherC⊂A∪B orA∪BC. (ii) LetCAandCB. ThenCA∪B.

Proof (i) IfC⊂A∪BorA∪B⊆C, we are done. So assume that bothC−(A∪B) and(A∪B)−C are nonempty and consider an elementc in the former and an elementxin the latter of these sets. One may assume thatx∈A. Sincex∈C,c∈A, andAC, we havex < c. This impliesA∪BC.

(ii) IfC⊆A∪B, we are done. So assume this is not the case, and letc∈C−(A∪ B). Letxbe an element of the set(A∪B)−C(which is, obviously, nonempty). One may assume thatx∈A−C. Thenc∈C−AandCAimplyc < x, as required.

Definition 6 LetL,R⊆2^[n]. We call(L,R)a left–right pair, or, briefly, an lr-pair, ifL∪Ris a ws-collection and

(LR): LRholds for anyL∈LandR∈Rwith|L| ≤ |R|.