times
syllabus
literature
homeworks
what happened so far
| 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 |
|
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 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 |