times
syllabus
literature
homeworks
what happened so far
| lecture | tuesday 16-18 | 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 #13 | due Feb 13 |
|
| Homework #12 | due Feb 6 | |
| Homework #11 | due Jan 30 | |
| Homework #10 | due Jan 23 | |
| Homework #9 | due Jan 16 | |
| Homework #\(8\frac{1}{2}\) | due Jan 9 | |
| Homework #8 | due Dec 19 | |
| Homework #7 | due Dec 12 | |
| Homework #6 | due Nov 28 | |
| Homework #5 | due Nov 28 | |
| Homework #4 | due Nov 14 | |
| Homework #3 | due Nov 7 | |
| Homework #2 | due Oct 31 | |
| Homework #1 | due Oct 24 |
| Oct 16/17 |
convexity, convex sets, linear/affine subspaces Operations: intersections, products and Minkowski sums, linear transformations supporting hyperplanes, separation theorem convex hulls, polytopes, vertices, affine hulls, dimension faces, faces are polytopes, f-vectors Platonic solids: tetrahedron, cube, octahedron, dodecahedron, icosahedron
vertices are faces, vertex set is well-defined |
| Oct 23/24 |
Veronese/moment map, hyperplanes and univariate
polynomials, cyclic polytopes, simplicial polytopes,
\(k\)-neighborly polytopes, cyclic polytopes are \(\lfloor
\frac{d}{2}\rfloor\)-neighborly, cyclic polytopes are
`maximally' neighborly, \(2k-1\)-faces of \(k\)-neighborly
polytopes are simplices, Radon's lemma,
Octahedra/Crosspolytopes, faces, centrally symmetric
polytopes, every c.s. polytope is the image of a
crosspolytope, unit ball for the \(\ell_1\)-norm
face of a face is a face, intersection of faces is a face, cubes, faces, every vertex incident to at least dim many edges, simple polytopes, simple iff \(d f_0 = 2f_1\), unit ball for \(\ell_\infty\)-norm, zonotopes = Minkowski sums of segments = affine images of cubes, zonotope of degree sequences, vertices \(\leftrightarrow\) threshold graphs, the permutahedron \(\Pi_{d-1}\) is a zonotope |
| Oct 30/31 |
permutahedron is a zonotope (finished), closed convex sets
are intersections of halfspaces, polyhedron = intersection
of finitely many halfspaces, linear programming, convex
cones, polyhedral cones, Minkowski Weyl: polyhedron iff
polytope + cone, polytope = bounded intersection of
halfspaces, lineality space and pointed convex sets,
Minkowski Weyl for cones, equivalence via homogenization
First half of Minkowski-Weyl: \(C = \{Ax \le 0\} \Rightarrow C = \mathrm{cone}\{u_1,u_2,\dots,u_s\}\) via induction on dimension, polarity, polar set is convex cone, Bipolar theorem \(C^{\circ\circ} = C\), in case of halfspaces, basic properties, for polyhedral cones, Second half of Minkowski-Weyl via polarity, Farkas lemma |
| Nov 6/7 |
recession cone of polyhedron, partially ordered sets
(posets), face poset (lattice) \(\mathcal{L}(P)\) of a
polytope \(P\),
Hasse diagrams, bounded posets, intervals, cover
relations, meets \(x \wedge y\) and joins \(x \vee y\),
lattice, finite + lattice = bounded, atoms, atomic posets,
\(\mathcal{L}(P)\) is atomic,
chains, graded
posets, rank, \(\mathcal{L}(P)\) is graded, downsets,
vertex figures, face figures, \([F,P] \cong
\mathcal{L}(P/F)\)
combinatorially isomorphic polytopes, interior and relative interior, polarity of polyhedra \(P^\triangle\) via cone polarity, irredundant inquality systems, facets, polar faces \(F^\diamond\), \(\dim F^\diamond = \dim P - \dim F - 1 \), coatoms, coatomic posets, \(\mathcal{L}(P)\) is coatomic, \(k\) faces are intersections of \(d-k\) facets, relative interiors of faces partition polyhedra, dual posets, \(\mathcal{L}(P^\triangle) \cong \mathcal{L}(P)^\mathrm{op}\), simple and simplicial polytopes, \((\text{simple})^\triangle = \text{simplicial}\), simplicial polytopes are ``stable'' under perturbing vertices, simple polytopes are ``stable'' under perturbing facets |
| Nov 13/14 |
f-vectors and (extended) f-polynomials, combinatorial
constructions (e.g., not Minkowski sums), pyramids, faces,
\(f_{\mathrm{pyr}(P)}^\circ(t) = f_P^\circ(t) (1+t)\),
combinatorics independent of choice of apex,
\(\mathrm{pyr}(P)^\triangle \cong
\mathrm{pyr}(P^\triangle)\), joins of polytopes, \((P *
Q)^\triangle \cong P^\triangle * Q^\triangle \), products
prisms, variations: twisted prism, anti-prism, prismoid/prismatoid/Cayley polytope, bipyramids, free/direct sums, \((P \oplus Q)^\triangle \cong P^\triangle \times Q^\triangle \), linear programming, functions in generation position w.r.t. P, graph of a polytope, acyclic orientations, unique sink/source, connected, k-(vertex-)connected graphs, Balinski: \(G(P)\) is \(\dim(P)\)-connected |
|
Nov 20
Nov 21 |
Guest lectures by Francisco
Santos Graphs of polyhedra, the Hirsch conjecture (and dual version), sufficient to consider simple/simplicial polyhedra, polynomial Hirsch conjecture, quasi-polynomial bound, linear bound in fixed dimension, wedge of polytopes (dually: one point suspensions), d-step conjecture equivalent to Hirsch conjecture equivalent to non-revisiting path conjecture, three variations: bounded/monotone/combinatorial version of Hirsch conjecture, counter-examples, spindles/prismatoids, Strong d-step theorem for spindles/prismatoids |
|
Nov 27/28
|
When is \(f=(f_0,\dots,f_{d-1})\) f-vector of d-polytope?
Steinitz: Complete answer in dimension \(d=3\), Euler's
formula, the Euler-Poincare characteristic, \(\chi(P) =
1\) for \(P\) non-empty polytope, first proof via
`valuations'
(Lawrence 1997), hyperplane arrangements, induced
subdivisions, \(\mathcal{A}\)-sets, valuative property,
inclusion-exclusion, independent on arrangement,
\(\chi(P^h) =0 \)
Second proof of Euler-Poincare theorem: Euler characteristic under section with hyperplane, for pyramids, for Cayley polytopes, chopping polytope along a generic linear function; Euler characteristic of unbounded polyhedra, \(\chi(Q) = 0\) for unbounded but pointed polyhedron |
|
Dec 4/5
|
Euler characteristic is the only linear relation for
general polytopes; h=vectors via general linear functions,
\(f_P(t) = h_P(t+1)\); h-vector
independent of chosen linear function; Stanley's trick for
computations, Dehn-Sommerville equations \(h_i(P) =
h_{d-i}(P)\)
Dehn-Sommerville equations determine affine span of f-vectors of simple d-polytopes; Upper Bound Theorem: sufficient to prove for simple polytopes (McMullen), \(f_k(P) \le f_k(\mathrm{Cyc}_d(n))^\triangle\) for all \(k\) and all simple d-polytopes \(P\) with \(n\) facets; equality iff \(P^\triangle\) is neighborly |
|
Dec 11/12
|
Lower bounds \(\phi_k(n,d)\) on k-faces for general
d-polytopes with n
vertices (or facets); very difficult in general,
conjectured for \(\phi_{d-1}(n,d)\); almost proved by
Deza; truncating vertex; iterated truncations of simplex;
Lower Bound Conjecture/Theorem for simple
polytopes, suffices to prove \(f_{d-2}(P) \ge f_{d-1}d -
\tbinom{d+1}{2}\); suffices to prove \(f_{d-2}(P) \ge
f_{d-1}d - K_d \) for some constant depending on d;
equivalent to prove that \(h_{2}(P) - h_{1}(P) \ge 0\);
sketch of proof due to Blind-Blind; yields equality case
(as compared to Barnette's proof)
graphs of general polytopes do not determine dimension (simplices vs. cyclic polytopes); graphs of simple polytopes determine complete face lattice; Kalai's `simple way to tell simple polytope from its graph': good acyclic orientations and total number of faces; facet subgraphs and initial sets |
|
Dec 18
|
Projective transformations |
|
Jan 08/09
|
geometric and abstract simplicial complexes, equivalent
concepts; pure complexes, pseudo-manifold, strongly
connected; boundary complex of simplicial polytope; f- and
h-polynomials; partitionable simplicial complexes,
partitionable \(\Rightarrow h(\Delta) \ge 0\); reduced
Euler characteristic, \(\tilde{\chi}(\Delta) = (-1)^{d-1}
h_d\) where \(d = \dim \Delta\)
shellable simplicial complexes, shellable implies partitionable, shellable implies strongly connected, Bruggesser-Mani `line shellings' of (simplicial) polytopes, relation to h-vectors of simple polytopes, link of a face, Eulerian manifold, Eulerian manifolds satisfy Dehn-Sommerville equations, Eulerian implies pseudo-manifold, boundary complex of simplicial polytopes are Eulerian manifolds |
|
Jan 15
Jan 16 |
f-vectors of simplicical complexes (example: graphs),
collections of sets, boundaries/shadows, reverse
lexicographic order of subsets of \(\mathbb{N}\),
compressed complexes, Kruskal-Katona theorem; multisets
and multicomplexes, Macaulay's theorem; g-vector of
simple/simplicial polytopes, the g-Theorem
Steinitz theorem: \(G\) is the graph of a 3-polytope if and only if \(G\) is simple, planar, and 3-connected. Proof via \(Y-\Delta\)-transformations; equilibrium embedding plus lifting (sketch); circle packings (sketch) |
|
Jan 22/23
|
vector configurations, faces and cofaces, acyclic
configurations, Gale transform of vector configuration,
totally cyclic configurations, \(U\) acyclic iff \(G\)
totally cyclic, positive dependence, main lemma: cofaces
and positive dependent sub-configs, Gale transforms of
polytopes via homogenization; examples;
classification of d-polytopes with d+2 vertices
affine dependencies and hyperplanes spanned by Gale transform; affine Gale diagrams, characterizations of aff-GTs of polytopes; faces in aGTs; application: a non-rational 8-polytope on 12 vertices |
|
Jan 29/30
|
deletion and contraction in vector configurations,
deletion/contraction are Gale dual operations; vertex
figures via deletion in Gale transforms; facets of
4-polytopes are not prescribable;
faces under linear projection; the projection lemma; diagrams associated to polytope projections; zonal diagrams; fans; complete, simplicial, pointed; face fans, normal fans, fans induced by hyperplane arrangements; operations on fans: direct sums, restrictions, common refinements; normal fan of zonotope is induced by corresponding hyperplane arrangement |
|
Feb 5/6
|
cells of an arrangement of hyperplanes, correspondance
between cells and faces of the zonotope, deletion and
restriction for arrangements, the dual hyperplane
arrangement, deletion/contraction for counting regions,
every arrangement of \(n\) hyperplanes has \(\ge 2n\)
simplicial regions; normal fan induced by hyperplane
arrangement does not characterize zonotopes; if every
2-face is centrally symmetric, then \(P\) is a zonotope;
Minkowski summands, indecomposable polytopes,
characterization of Minkowski summands in terms of edge
weights
all 2-faces simplicial \(\Rightarrow\) indecomposable; all polygons \(\neq\) triangle are decomposable; weights are edge weights of summand if they satisfy linear condition for each 2-face; the polytope of all Minkowski summands |
|
Feb 12/13
|
polytope of Minkowski summands, 2-faces centrally
symmetric \(\Rightarrow\) zonotope, P simple polytope
\(\neq\) simplex \(\Rightarrow\) decomposable
weak Minkowski summands and refinements of normal fans; polytopes with facet normals in a fixed set; type cones; discrete geometry tapas: Randon & Helly, centerpoint theorem, Caratheodory & Tverberg |