Discrete Geometry I

Winter Semester 2014/2015

news     times     syllabus     literature     homeworks     what happened so far

Prof. Raman Sanyal, Arnimallee 2, room 105 (office hours: TBA)

Dr. Arnau Padrol , Arnimallee 2, room 103 (office hours: TBA)


All updates will posted on the mailing list. Please make sure you subscribed!


lecture tuesday 10-12 Arnimallee 6 SR 007/008
wednesday 10-12 Arnimallee 6 SR 007/008
recitation wednesday 14-16 Arnimallee 6 SR 031

syllabus / prerequisites / formalities

This is the first in a series of three courses on discrete geometry. The aim of the course is a skillful handling of discrete geometric structures including analysis and proof techniques. The material will be a selection of the following topics:
Basic structures in discrete geometry
  • polyhedra and polyhedral complexes
  • configurations of points, hyperplanes, subspaces
  • Subdivisions and triangulations (including Delaunay and Voronoi)
Polytope theory
  • Representations and the theorem of Minkowski-Weyl
  • polarity, simple/simplicial polytopes, shellability
  • shellability, face lattices, f-vectors, Euler- and Dehn-Sommerville
  • graphs, diameters, Hirsch (ex-)conjecture
Geometry of linear programming
  • linear programs, simplex algorithm, LP-duality
Combinatorial geometry / Geometric combinatorics
  • Arrangements of points and lines, Sylvester-Gallai, Erdos-Szekeres,
  • Szemeredi--Trotter
  • Arrangements, zonotopes, zonotopal tilings, oriented matroids
Examples, examples, examples
  • regular polytopes, centrally symmetric polytopes
  • extremal polytopes, cyclic/neighborly polytopes, stacked polytopes
  • combinatorial optimization and 0/1-Polytope
For students with an interest in discrete mathematics and geometry, this is the starting point to specialize in discrete geometry. The topics addressed in the course supplement and deepen the understanding for discrete-geometric structures appearing in differential geometry, topology, combinatorics, and algebraic geometry.


Solid background in linear algebra. Knowledge in combinatorics and geometry is advantageous.


To successfully pass the course, you need to...



There will be one homework sheet per week (posted here). You have to hand them in Wednesday before the recitation. Hand in the solutions in pairs. Let us know if you couldn't find a partner. Try to solve all the problems but mark two solutions. Only these will be graded. You can earn 20 points on every homework sheet (10 per exercise). You can get extra credit by solving the bonus problems. State who wrote up the solution. Everybody has to write up at least 25 percent of the solutions. Everybody has to present at least one problem in the recitation session.
Homework #1 due Oct 22
Homework #2 due Oct 29 (Solutions for Ex 1 and Ex 2iii)
Homework #3 due Nov 5
Homework #4 due Nov 12 (Code for Ex 2)
Homework #5 due Nov 19
Homework #6 due Nov 26
Homework #7 due Dec 3
Homework #8 due Dec 10
Homework #9 due Jan 7
Homework #10 due Jan 14
Homework #11 due Jan 21
Homework #12 due Jan 28
Homework #13 due Feb 4

what happened so far (for the lecture notes click the dates)

Oct 14/15 5 minutes to fall in love with discrete geometry (and the permutahedron); linear and affine subspaces; line segments and convex sets; examples: unit balls, positive semidefinite matrices, epigraphs of convex functions; convexity in optimization: local optima = global optima; operations on convex sets: intersections, products, affine maps, Minkowski sums; building blocks: hyperplanes and halfspaces; closed convex set as intersections of halfspaces; supporting hyperplanes

Separation Theorem; convex hulls and convex combinations; polytopes; polygons and the Gauss-Lucas theorem; affinely independent points; affine hull and dimension; (standard) \(k\)-dimensional simplices; any two \(k\)-simplices are affinely isomorphic; every polytope is affine image (projection) of a simplex

Oct 15 Introduction to SAGE (you can download the worksheet)
Oct 21/22 Caratheodory's theorem; discrete boundary of polytopes: faces (including empty and improper); vertices, edges, ridges, facets; face of polytope is a polytope; polytopes have finitely many faces; inclusion-minimal "generating set" for polytope are its vertices; faces of simplices

f-vectors; faces intersect in faces; face of a face is a face; d-polytopes have k-faces for every \(0\le k \le d-1\); cyclic polytopes and univariate polynomials; points in general position; simplicial polytopes; k-neighborly polytopes; cyclic polytopes are \(\lfloor \frac{d}{2}\rfloor\)-neighborly

Oct 28/29 cyclic polytopes are `maximally' neighborly, (2k-1)-faces of k-neighborly polytopes are simplices, Radon's lemma, combinatorial isomorphism, simplicial polytopes, the vertices of a simplicial polytope can be perturbed

crosspolytopes, centrally symmetric polytopes, every c.s. polytope is a projection of a crosspolytope, if F is a face of a c.s. polytope, so is -F; Products (faces and f-vector); pyramids; joins (faces and f-vector)

Nov 4/5 polyhedra: intersections of finitely many halfspaces; examples, operations: intersection, Cartesian product; linear programming problems; convex cones, finitely generated cones; pointed cones; Minkowski-Weyl theorem; polytopes are bounded polyhedra; (linear) sections of polytopes (f.g. cones) are polytopes (f.g. cones); projections of polyhedra are polyhedra; lineality space and pointed/linefree polyhedra; recession cone; polyhedral cones

Minkowski-Weyl for cones (ConeMW); ConeMW is equivalent to Minkowski-Weyl via homogenizations; proof of the first half: polyhedral cones are finitely generated; cone polarity

Nov 11/12 Bipolar theorem and properties of cone polarity; Proof of ConeMW - second half via polarity; Farkas lemma; polarity and solvability of systems of linear equations with nonnegativity constraints; polarity for general sets; Interlude: interiors and relative interiors

Polarity for polytopes; vertices and inequalities; every full-dim polytope is intersection of unique halfspaces; every face is intersection of \(\dim P\) many bounding hyperplanes

Nov 18/19 irredudant inequalities are in correspondence with facets; every \(k\)-face is intersection of \(d-k\) facets; polytope simple if every \(k\)-face contained in exactly \(d-k\) facets; associated faces of the polar polytope; inclusion-reversing bijection between \(k\)-faces of \(P\) and \(\mathrm{dim}(P)-k-1\)-faces of \(P^\triangle\); vertices \(\leftrightarrow\) facets; edges \(\leftrightarrow\) ridges; simple polytopes \(\stackrel{\triangle}{\longleftrightarrow}\) simplicial polytopes

Birkhoff polytope: polytope of doubly-stochastic matrices; dimension, facets; Birkhoff-vonNeumann theorem: Vertices are exactly the permutation matrices; generalized permutahedra; Schur-Horn theorem (easy implication); partially ordered sets (posets); examples, face lattices; bounded posets; intervals and locally finite posets; meets and joins; meet- and join-semilattice

Nov 25/26 finite + minimum + meet-semilattice = lattice; (co)atoms and (co)atomic posets; chains, graded posets, rank; Eulerian posets; Prop: \(\mathcal{L}(P)\) graded; opposite posets and polar polytopes; Prop. \([F,G]_{\mathcal{L}}\) face lattice of polytope; diamond property; Thm: \(\mathcal{L}(P)\) is graded, atomic and coatomic, Eulerian lattice with diamond property

simple and simplicial in poset language; k-skeletons and neighborliness; direct products of posets and joins/products/direct sums of polytopes; graphs of polytopes; Lemma: Neighbors of higher value; graph of polytope is connected; Thm (Balinski'61). \(G(P)\) is \(\dim P\)-connected

Dec 2/3 geometric perspective of linear programming and the simplex algorithm: walking on the graph of a polytope; how to get the initial vertex?; how long will the path be?; Hirsch Conjecture and Santo's example; graphs of 3-polytopes; 2-faces correspond exactly to chordless, nonseparating cycles; planar embeddings and regions; dual graph unique for 3-connected, planar graphs

Steinitz: graphs of 3-polytopes are exactly the 3-connected, planar graphs (with \(\ge 4\) vertices); every such graph has triangular region or degree-3 vertex; ``right'' planar embedding with Tutte's ``rubberband'' embedding; lifting to a polytope; consequences: rational coordinates, isotopy, (prescribed faces)

Dec 9/10 graphs of polytopes of dimension \(\ge 4\) contain no information about \(\mathcal{L}(P)\) in general: \(G(\Delta_{n-1}) \cong K_n \cong G(\mathrm{Cyc}_4(n))\); dimensionally k-ambiguous polytopes; Thm(Blind-Mani). Graph of simple polytope determines face lattice; Kalai's simple (and beautiful!) way to tell simple polytope from graph

facet subgraphs are exactly the (d-1)-regular, connected, initial subgraphs; yields algorithm for reconstructing \(\mathcal{L}(P)\) from \(G(P)\); even poly-time (Friedmann'09); problem: which graphs are graphs of simple polytopes; Perles conjecture and Haase-Ziegler's counterexample; f-vectors of polytopes; Steinitz' theorem in dimension 3; Euler-Poincare formula in all dimensions; valuative property of \(\chi(\cdot)\); special cases: pyramids and Cayley polytopes; Thm: \(\chi(P) = 1\) for all nonempty polytopes \(P\)

Dec 16/17 Thm: Euler-Poincare is the only linear relation; f-polynomials and extended f-polynomials; more linear relations on simple/simplicial polytopes, e.g. \(d f_0 = 2 f_1\); h-vector associated to an orientation \(\mathcal{O}_c\); determines face numbers and is independent of orientation: \(h_P(t) = f_P(t-1)\); Stanley's trick for computation; Dehn-Sommerville equations; Thm: No other linear relations

the upper bound problem/conjecture; McMullen's Upper Bound Theorem (including equality case); reduction to simple/simplicial polytopes; in terms of h-vectors; local information; local-to-global; putting it together

Jan 6/7 simplicial complexes: geometric and abstract; dimension, pure, pseudomanifold, strongly connected; f-vectors and h-vectors; partitionable complexes; Thm: partitionable \(\Rightarrow h_i \ge 0\); shellable complexes; Prop: shellable implies partitionable; Prop: shellable implies strongly connected;

Bruggesser-Mani shelling of (simplicial) polytopes; link and reduced Euler characteristic; Eulerian complexes; Thm: Eulerian implies Dehn-Sommerville equations; Upper Bound Theorem for spheres; the lower bound problem: very difficult; truncation/stacked polytopes and the Lower Bound Theorem;

Jan 13/14 for LBT it is sufficient to prove \(f_{d-2}(P) \ge d f_{d-1}(P) - \binom{d+1}{2}\); in terms of h-vectors: \( h_{d-2} - h_{d-1} \ge 0\); Proof of Blind-Blind via sweeping; (infinitesimal) rigidity of frameworks; rigidity matrix and rank; frameworks of simplicial polytopes are (infinitesimally) rigid; Kalai's extension to manifolds and spheres

the g-Theorem; M- and O-sequences; Macaulay's theorem and Kruskal-Katona; Gale transforms; acyclic and totally cyclic configurations; Gale transforms encode face structure; examples, examples, examples...

Jan 20/21 more Gale transforms; recovering cone up to linear transformation; recovering polytope up to affine transformation; Gale transform only defined up to linear iso; projective transformations and linear transformations on cones

effect of projective transformations on Gale transformations; deletions and contractions; subpolytopes and vertex figures; affine gale transformations; face conditions in terms of colored point configurations; application: 8-polytope with 12 vertices that cannot be realized over the rational numbers.

Jan 27/28 projection lemma; geometry of Gale transforms; projections of cubes, zonotopes, zonal diagrams;

normal cones, normal fans, normally equivalent polytopes; cones of polytopes