Lattices and polyhedra from graphs [Elektronische Ressource] / vorgelegt von Kolja Knauer

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2010
• Nombre de lectures: 16
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

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 flows 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 Affine 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-firing 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 flow, 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 flipping two tiles, which share a long side. In this work
we present the first 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 flavor of what we refer to as “unifying generalization”, we show
two consecutive steps of generalizing the domino tilings of a plane region, see the figure.
12
The left-most part of the figure shows two domino tilings, which can be transformed into
each other by a single flip of two neighboring tiles. In the middle of the figure 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 figure 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 defined 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
defined 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 find
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 flows on d