LATTICES AND POLYHEDRA FROM GRAPHS

vorgelegt von

Diplom-Mathematiker

Kolja Knauer

aus Oldenburg

Von der Fakulta¨t II – Mathematik und Naturwissenschaften

der Technischen Universita¨t Berlin

zur Erlangung des akademischen Grades

Doktor der Naturwissenschaften

– Dr. rer. nat. –

genehmigte Dissertation

Promotionsausschuss:

Vorsitzender: Prof. Dr. rer. nat. Jo¨rg Liesen

Berichter: Prof. Dr. rer. nat. Stefan Felsner

Prof. Dr. rer. nat. Michael Joswig

Tag der wissenschaftlichen Aussprache: 9. November 2010

Berlin 2010

D 83ACKNOWLEDGEMENTS

My work related to this thesis was mainly done in Berlin – me being a part of the research

group Diskrete Strukturen. This was really nice mainly because of the members of this

group and the communicative, relaxed, and productive atmosphere in the group. Thank you

a lot: Daniel Heldt, Stefan Felsner, Andrea Hoffkamp, Mareike Massow, Torsten Ueckerdt,

Florian Zickfeld.

I am thankful for Stefan’s helpful advice on how to do, write and talk math. I really

enjoyed working with him as my advisor and also as my coauthor. I also want to thank my

Mexican coauthors Ricardo Go´mez, Juancho Montellano-Ballesteros and Dino Strausz for

the nice time working and discussing at UNAM in Mexico. My stays in Mexico would not

have been possible without the help of Isidoro Gitler. Ulrich Knauer, Torsten, Gu¨nter Rote,

´Eric Fusy made helpful comments and fruitful discussions. Ulrich and Torsten moreover

helped me a big deal by proofreading parts of the thesis.

Another big helper who made this work possible was SOLAC with its 18bar of pure

pressure and many cups of coffee.

I should also mention that this work would not have been possible without the funding by

the DFG Research Training Group “Methods for Discrete Structures”.

Finally, I want to express my gratitude again to Stefan and also to Michael Joswig for

reading this thesis. I hope you enjoy some of it, but I know this is quite some work and so I

stumbled over something that Douglas Adams [1] said and which seemed adequate to me:

“Would it save you a lot of time if I just gave up and went mad now?”

Thanks a lot,

KoljaContents

What is this thesis about? 1

1 Lattices 5

1.1 Preliminaries for Posets and Lattices . . . . . . . . . . . . . . . . . . . . . 9

1.2 Generalizing Birkhoff’s Theorem . . . . . . . . . . . . . . . . . . . . . . . 13

1.2.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.2.2 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.3 Hasse Diagrams of Upper Locally Distributive Lattices . . . . . . . . . . . 28

1.4 The Lattice of Tensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

1.4.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

1.4.2 The lattice ofc-orientations (Propp [92]) . . . . . . . . . . . . . . 44

1.4.3 The lattice of ﬂows in planar graphs (Khuller, Naor and Klein [66]) 46

1.4.4 Planar orientations with prescribed outdegree (Felsner [39], Ossona

de Mendez [88]) . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

1.5 Chip-Firing Games, Vector Addition Languages, and Upper Locally Dis-

tributive Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

1.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

2 Polyhedra 65

2.1 Polyhedra and Poset Properties . . . . . . . . . . . . . . . . . . . . . . . . 68

2.2 Afﬁne Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

2.3 Upper Locally Distributive Polyhedra . . . . . . . . . . . . . . . . . . . . 75

iii

2.3.1 Feasible Polytopes of Antimatroids . . . . . . . . . . . . . . . . . 80

2.4 Distributive Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

2.4.1 Towards a Combinatorial Model . . . . . . . . . . . . . . . . . . . 85

2.4.2 Tensions and Alcoved Polytopes . . . . . . . . . . . . . . . . . . . 87

2.4.3 General Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 90

2.4.4 Planar Generalized Flow . . . . . . . . . . . . . . . . . . . . . . . 96

2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

3 Cocircuit Graphs of Uniform Oriented Matroids 103

3.1 Properties of Cocircuit Graphs . . . . . . . . . . . . . . . . . . . . . . . . 105

3.2 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

3.3 Antipodality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

Bibliography 112

Notation Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123What is this thesis about?

The title “Lattices and Polyhedra from Graphs” of this thesis is general though describes

quite well the aim of this thesis. Among the most important objects of this work are dis-

tributive lattices and upper locally distributive lattices. While distributive lattices certainly

are one of the most studied lattice classes, also upper locally distributive lattices enjoy fre-

quent reappearance in combinatorial order theory under many different names. Upper locally

distributive lattices correspond to antimatroids and abstract convex geometries – objects of

major importance in combinatorics.

Besides results of a purely lattice or order theoretic kind we present new characterizations

of (upper locally) distributive lattices in terms of antichain-covers of posets, arc-colorings

dof digraphs, point sets inN , vector addition languages, chip-ﬁring games, and vertex and

(integer) point sets of polyhedra. We exhibit links to a wide range of graph theoretical,

combinatorial, and geometrical objects. With respect to the latter we study and characterize

polyhedra which seen as subposets of the componentwise ordering of Euclidean space form

(upper locally) distributive lattices.

Distributive lattice structures have been constructed on many sets of combinatorial

objects, such as lozenge tilings, planar bipartite perfect matchings, pla-

nar orientations with prescribed outdegree, domino tilings, planar circu-

lar ﬂow, orientations with prescribed number of backward arcs on cycles

and several more. A common feature of all of them is that the Hasse di-

agram of the distributive lattice may be constructed applying local trans-

formations to the objects. These local transformations lead to a natural

arc-coloring of the diagram. For an example see the distributive lattice on

the domino-tilings of a rectangular region on the side. The local transfor-

mation consists in ﬂipping two tiles, which share a long side. In this work

we present the ﬁrst unifying generalization of all such instances of graph-

related distributive lattices. We obtain a distributive lattice structure on

the tensions of a digraph.

In order to provide a ﬂavor of what we refer to as “unifying generalization”, we show

two consecutive steps of generalizing the domino tilings of a plane region, see the ﬁgure.

12

The left-most part of the ﬁgure shows two domino tilings, which can be transformed into

each other by a single ﬂip of two neighboring tiles. In the middle of the ﬁgure we show

how planar bipartite perfect matchings model

domino tilings. The local transformation now cor-

responds to switching the matching on an alter-

nating facial cycle. More generally, the right-most

part of the ﬁgure shows how to interpet the pre-

ceeding objects as orientations of prescribed out-

degree of a bipartite planar graph. Every yellow

vertex has outdegree 1 and every blue vertex has

outdegree(deg−1). Reversing the orientation on directed facial cycles yields a distributive

lattice structure on the set of orientations with these outdegree constraints.

A particular interest of this work lies in embedding lattices into Euclidean space. The

motivation is to combine geometrical and order-theoretical methods and perspectives. We

investigate polyhedra, which seen as subposets of the componentwise ordering of Euclidean

space form upper locally distributive or distributive lattices. In both cases we obtain full

characterizations of these classes of polyhedra in terms of their description as intersection of

bounded halfspaces.

In particular we obtain a polyhedral structure on known discrete distributive lattices on

combinatorial objects as those mentioned above as integer points of distributive polytopes.

A classical polytope which was deﬁned in the spirit of combining discrete geometry and

order-theory appears as a special case of our considerations, and thus might provide an idea

of what kind of objects we will study: Given a posetP, Stanley’s order polytopeP may beP

deﬁned as the convex hull of the characteristic vectors of the ideals of a posetP.

z

y

z

y

x x

Figure 1: A posetP with an ideal on the left with its order polytope P and the vertex theP

corresponding to the ideal, on the right.

Our characterization of upper locally distributive polyhedra opens connections to the the-

ory of feasible polytopes of antimatroids. In the setting of distributive polyhedra we ﬁnd

graph objects that might be considered as the most general ones, which form a distributive

lattice and carry a polyhedral structure. The connection to polytope theory links distributive

lattices to generalized ﬂows on digraphs. Thus, there is a link to important objects of com-INTRODUCTION 3

binatorial optimization. Moreover we exhibit new contributions to the theory of bicircular

oriented matroids.

Large parts of the thesis are based on publications between 2008 and 2010 [40, 43, 41,

42, 54, 69]. In the following we give a rough overview over each single chapter. For more

detailed introductions we refer to the ﬁrst pages of the individual chapters.

Chapter 1: Lattices

The ﬁrst chapter of the thesis is about lattices. It is based on papers [41, 42, 69] and

includes joint work with Stefan Felsner. After giving a more detailed introduction into lattice

theory and the chapter itself, we present some basic notation and vocabulary in Section 1.1.

The main result of Section 1.2 is a new representation result for general ﬁnite lattices. We

provide a one-to-one correspondence between ﬁnite lattices and antichain-covered posets.

As an application we strengthen a characterization of upper locally distributive lattices in

terms of antichain-partitioned posets due to Nourine. The “smallest” special case of our the-

orem is the Fundamental Theorem of Finite Distributive Lattices alias Birkhoff’s Theorem.

Section 1.3 proves three classes of combinatorial objects to be equivalent. We show

that acyclic digraphs with a certain arc-coloring and unique source, cover-preserving join-

dsublattices ofN and upper locally distributive lattices correspond to each other. The charac-

terization turns out to be very useful in many applications where one actually wants to prove

an (upper locally) distributive lattice structure on a given set of objects. Another applica-

tion of this section is a generalization of Dilworth’s Embedding Theorem for Distributive

Lattices to upper locally distributive lattices.

In Section 1.4 we present the distributive lattice of Δ-tensions of a digraph. As men-

tioned before, many known distributive lattices coming from graphs are special cases of

Δ-tensions. At the end of the section we show reductions to the most important special cases

ofΔ-tensions: Flow in planar graphs, prescribed outdegree orientations of planar graphs, and

orientations with prescribed circular ﬂow-difference of general graphs.

Section 1.5 is motivated by Bjo¨rner and Lova´sz’ chip-ﬁring game on directed graphs.

As an easy application of the results in the sections above, chip-ﬁring games lead to upper

locally distributive lattices. Moreover chip-ﬁring games have a representation as vector ad-

dition languages. We capture the most important features of such languages to generalize the

concept to generalized chip-ﬁring games. In contrast to ordinary chip-ﬁring games, the latter

indeed are general enough to represent every upper locally distributive lattice. Moreover we

show that every such lattice is representable as the intersection of ﬁnitely many chip-ﬁring

games.

We close the chapter with concluding remarks and open problems in Section 1.6.4

Chapter 2: Polyhedra

This chapter is based on parts of [43, 69] and partial joint work with Stefan Felsner. After

a brief introduction, make ﬁrst observation about order-theoretic properties of convex subset

dofR with respect to the componentwise ordering of the space in Section 2.1. In particular

we deﬁne upper locally distributive and distributive polyhedra.

As a basic ingredient Section 2.2 is devoted to afﬁne Euclidean space satisfying poset

properties. We characterize distributive afﬁne space by a representation in terms of directed

graphs. This is an important part of the characterizations of upper locally distributive and

distributive polyhedra in the following sections.

In Section 2.3 we characterize upper locally distributive polyhedra via their description

as nitersection of bounded halfspaces. We ﬁnd relations of these polyhedra to feasible poly-

topes of antimatroids and draw connections to a membership problem discussed by Korte

and Lova´sz. We show how to view every upper locally distributive polyhedron as the inter-

section of polyhedra associated to chip-ﬁring games.

Section 2.4 develops the theory of distributive polyhedra. We obtain a characterization

of their description as intersection of bounded halfspaces. We obtain that these polyhedra

are dual to polyhedra of generalized digraph ﬂows, i.e., ﬂows on digraphs with lossy and

gainy arcs. We establish a correspondence between distributive polyhedra and generalized

tensions of digraphs yielding in a sense the most general distributive lattices arising from a

graph, in Subsection 2.4.1. We show how to obtain the lattices from Section 1.4 as integer

point lattices of special distributive polyhedra and prove that these polyhedra coincide with

alcoved polytopes and polytropes, known in the literature before, in Subsection 2.4.2. The

combinatorial model for general distributive polyhedra is closely related to oriented bicircu-

lar matroids. This will be made explicit in Subsection 2.4.3. As a special application we ﬁnd

the ﬁrst distributive lattice on generalized ﬂows of planar digraphs in Subsection 2.4.4.

Section 2.5 concludes with some open questions and further remarks.

Chapter 3: Cocircuit Graphs of Uniform Oriented Matroids

The last chapter is not strongly related to the rest of the thesis. It is based on the pa-

pers [54, 40] and is joint work with Stefan Felsner, Ricardo Go´mez, Juan Jose´ Montellano-

Ballesteros, and Ricardo Strausz. We present the ﬁrst cubic-time algorithm which takes a

graph as input and decides if the graph is the cocircuit graph of a uniform oriented ma-

troid. In the afﬁrmative case the algorithm returns the set of signed cocircuits of the oriented

matroid. This improves an algorithm proposed by Babson, Finschi and Fukuda.

Moreover we strengthen a result of Montellano-Ballesteros and Strausz characterizing

cocircuit graphs of uniform oriented matroids in terms of crabbed connectivity.