# Discrete Geometry I

## Winter Semester 2014/2015

news     times     syllabus     literature     homeworks     what happened so far

### news

All updates will posted on the mailing list. Please make sure you subscribed!
• Nachklausur / make-up exam: Thursday, 16.4.2015, 12-14, A6 HS001
• Klausureinsicht: Friday, 13.2.2015, 9-11, A2 (Villa) seminar room
• the written exam will take place on 11.2.2015, 10-12
• class starts Tuesday, October 14

### times

 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.

#### prerequisites

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

#### Formalities

To successfully pass the course, you need to...
• ...actively participate in the recitations,
• ...get at least 60 percent of the total number of homework points (see homeworks),
• ...present at least one of the homework problems in the recitation, and
• ...pass the written exam at the end of the semester (There will be a mock exam around Christmas.)

### homeworks

 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