lecture  tuesday 1012  Arnimallee 6 SR 007/008  
wednesday 1012  Arnimallee 6 SR 007/008  
recitation  wednesday 1416  Arnimallee 6 SR 031 
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

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 
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 GaussLucas 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; inclusionminimal "generating
set" for polytope are its vertices; faces of simplices fvectors; faces intersect in faces; face of a face is a face; dpolytopes have kfaces for every \(0\le k \le d1\); cyclic polytopes and univariate polynomials; points in general position; simplicial polytopes; kneighborly polytopes; cyclic polytopes are \(\lfloor \frac{d}{2}\rfloor\)neighborly 
Oct 28/29 
cyclic polytopes are `maximally' neighborly,
(2k1)faces of kneighborly 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 fvector); pyramids; joins (faces and fvector) 
Nov 4/5 
polyhedra: intersections of finitely many halfspaces;
examples, operations: intersection, Cartesian product;
linear programming problems; convex cones, finitely
generated cones; pointed cones; MinkowskiWeyl 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
MinkowskiWeyl for cones (ConeMW); ConeMW is equivalent to MinkowskiWeyl 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 fulldim 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 \(dk\) facets;
polytope simple if every \(k\)face contained in exactly
\(dk\) facets; associated faces of the polar polytope;
inclusionreversing bijection between \(k\)faces of \(P\)
and \(\mathrm{dim}(P)k1\)faces of \(P^\triangle\);
vertices \(\leftrightarrow\) facets; edges
\(\leftrightarrow\) ridges; simple polytopes
\(\stackrel{\triangle}{\longleftrightarrow}\) simplicial
polytopes
Birkhoff polytope: polytope of doublystochastic matrices; dimension, facets; BirkhoffvonNeumann theorem: Vertices are exactly the permutation matrices; generalized permutahedra; SchurHorn theorem (easy implication); partially ordered sets (posets); examples, face lattices; bounded posets; intervals and locally finite posets; meets and joins; meet and joinsemilattice 
Nov 25/26 
finite + minimum + meetsemilattice = 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; kskeletons 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
3polytopes; 2faces correspond exactly to chordless,
nonseparating cycles; planar embeddings and regions; dual
graph unique for 3connected, planar graphs
Steinitz: graphs of 3polytopes are exactly the 3connected, planar graphs (with \(\ge 4\) vertices); every such graph has triangular region or degree3 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_{n1}) \cong K_n \cong G(\mathrm{Cyc}_4(n))\);
dimensionally kambiguous polytopes; Thm(BlindMani).
Graph of simple polytope determines face lattice; Kalai's
simple (and beautiful!) way to tell simple polytope from
graph
facet subgraphs are exactly the (d1)regular, connected, initial subgraphs; yields algorithm for reconstructing \(\mathcal{L}(P)\) from \(G(P)\); even polytime (Friedmann'09); problem: which graphs are graphs of simple polytopes; Perles conjecture and HaaseZiegler's counterexample; fvectors of polytopes; Steinitz' theorem in dimension 3; EulerPoincare 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: EulerPoincare is the only linear relation;
fpolynomials and extended fpolynomials; more linear
relations on simple/simplicial polytopes, e.g. \(d f_0 = 2
f_1\); hvector associated to an orientation
\(\mathcal{O}_c\); determines face numbers and is
independent of orientation: \(h_P(t) = f_P(t1)\);
Stanley's trick for computation; DehnSommerville
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 hvectors; local information; localtoglobal; putting it together 
Jan 6/7 
simplicial complexes: geometric and abstract; dimension,
pure, pseudomanifold, strongly connected; fvectors and
hvectors; partitionable complexes; Thm: partitionable
\(\Rightarrow h_i \ge 0\); shellable complexes; Prop:
shellable implies partitionable; Prop: shellable implies
strongly connected;
BruggesserMani shelling of (simplicial) polytopes; link and reduced Euler characteristic; Eulerian complexes; Thm: Eulerian implies DehnSommerville 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_{d2}(P) \ge d f_{d1}(P)  \binom{d+1}{2}\); in terms
of hvectors: \( h_{d2}  h_{d1} \ge 0\); Proof of
BlindBlind 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 gTheorem; M and Osequences; Macaulay's theorem and KruskalKatona; 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: 8polytope 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 