Discrete Geometry II

Summer Semester 2013


news     times     syllabus     literature     homeworks     what happened so far


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

Dr. Ivan Izmestiev, Arnimallee 2, room 106 (office hours: Wednesday, 16-17)

news

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

times

lecture tuesday 10-12 Arnimallee 6 SR 007/008
thursday 12-14 Arnimallee 2 (Villa) seminarroom starting April 17
recitation wednesday 14-16 Arnimallee 6 SR 007/008

syllabus / prerequisites / formalities

This is the second in a series of three courses on discrete geometry. The aim of the course is a skillful handling of discrete geometric structures with an emphasis on convex geometric properties. In the course we will develop central themes in discrete and convex geometry including proof techniques and applications to other areas in mathematics. The material will be a selection of the following topics:

Basic structures in discrete and convex geometry

Notions and tools Geometric inequalities Geometry of numbers Sphere packings The target audience are students with an interest in discrete mathematics and (convex) geometry. The course is a good entry point for a specialization 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 and some analysis. Basic knowledge and experience with polytopes and/or
convexity will be helpful.

Formalities

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

literature

A good part of the mentioned books is in the Semesterapparat at the math library.

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. (The supplementary problems do not count; they are for your enjoyment.) You can earn 20 points on every homework sheet (10 per exercise). There are marked problems that are mandatory. 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 July 10
Homework #12 due July 3
Homework #11 due June 26
Homework #10 due June 20
Homework #9 due June 12
Homework #8 due June 5
Homework #7 due May 29
Homework #6 due May 22
Homework #5 due May 15
Homework #4 due May 8
Homework #3 due May 2
Homework #2 due April 24
Homework #1 due April 17

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

We are putting together a LaTeXed set of lecture notes here (July 2). Mind you, the notes are not necessary up-to-date and we don't take any responsibility errors or completeness. What happend in the lectures is what counts. However, if you find errors or short-comings, please let Miriam know!

July 9/11 lattices are exactly discrete subgroups not contained in a hyperplane; fundamental cell; determinnant of lattice; sublattices and the index; covering and volume

Blichfeldt's theorem; geometry of numbers and Minkowski's fundamental theorem; looking out of a forest; approximation of irrational numbers; the 2-square theorem

July 2/4 Minkowski's second inequality; Alexandrov-Fenchel inequalities \(MV(K_1,\dots,K_d)^2 \ge MV(K_1,K_1,K_3,\dots,K_d) MV(K_2,K_2,K_3,\dots,K_d) \); application to combinatorics: unimodal, concave, and log-concave sequences; log-concave sequences from convex bodies; Converse (Shephard): every log-concave sequences arises as the mixed volumes of two convex bodies; \(G\) connected graph with selection of edges \(S \subset E\); \(b_i = \) spanning trees \(T\) with \(i = |T \cap S|\) is log-concave; Mason's conjecture for graphs: \(I_i\) number of forests on \(i\) edges; \(I_0,\dots,I_d\) is log-concave

discrete volume \(E_S(n) = |nS \cap \mathbb{Z}^d|\); yields volume \(\lim_{n\rightarrow\infty} E_S(n)/n^d = \mathrm{vol}_d(S)\); Theorem (Ehrhart): \(P\) lattice polytope \(\rightarrow\) \(E_P(n)\) agrees with polynomial of degree \(\dim(P)\) for all \(n\ge1\); multi-subsets and Ehrhart polynomials of simplices; valutions on lattice polytopes; proof of Ehrhart's theorem in the plane; Ehrhart-Macdonald reciprocity; proof in the plane; the coeffients and Pick's theorem

June 25/27 Theorem: \(MV(P,\dots,P,Q) = \frac{1}{d}\sum_{i} h_Q(a_i) \mathrm{vol}_{d-1}(P^{a_i})\) where \(a_1,\dots,a_n\) are unit normals to facets of \(P\); proof via existence of certain exact mixed subdivisions; general form \(MV(P_1,\dots,P_{d-1},K) = \frac{1}{d}\sum_{i} h_K(a_i) MV(P_1^{a_i},P_2^{a_i},\dots,P_{d-1}^{a_i})\) where \(a_i\) are the unit facet normals of \(P_1+\cdots+P_{d-1}\); Minkowski's first inequality: \(MV(K,L[d-1])^d \ge \mathrm{vol}_d(K) \mathrm{vol}_d(L)^{d-1} \)

surface area \(S(K) = \frac{1}{d}MV(K[d-1],B_d)\); properties; Steiner polynomial and `Quermassintegrale'; the isoperimetric problem; isoperimetric inequality: \(\tfrac{S(K)^d}{V(K)^{d-1}} \ge \tfrac{S(B_d)^d}{V(B_d)^{d-1}}\); isoperimetric quotient and Lindelöf's result on polytopes.

June 18/20 the mixed volume \(MV(K_1,\dots,K_d)\) of \(d\) convex bodies \(K_1,\dots,K_d\subset \mathbb{R}^d\); mixed volume is symmetric in its arguments, continuous, non-negative (via mixed subdivisions), rigid motion invariant, and equal to the volume if \(K_1=\cdots=K_d\); mixed volume completely describes the coefficients of \(\mathrm{vol}_d(\lambda_1 K_1 + \cdots \lambda_n K_n)\) for arbitrary \(n\) (this is polarization of algebraic forms!); \(MV(\cdot)\) is linear in its arguments; \(MV(\cdot,K_2,\dots,K_d)\) is a valuation; mixed volume via inclusion-exclusion of (Minkowski) subsums;

application of mixed volumes: Bernstein's theorem on number of solutions of polynomial systems with fixed Newton polytopes; Monotonicity of mixed volume (via mixed subdivisions); Theorem: \(MV(P,\dots,P,Q) = \frac{1}{d}\sum_{i} h_Q(a_i) \mathrm{vol}_{d-1}(P^{a_i})\) where \(a_1,\dots,a_n\) are unit normals to facets of \(P\)

June 11/13 understanding the function \( V_A(b) := \mathrm{vol}_d(P_A(b))\), the closed inner region \(\bar{\mathcal{B}}_A \subset \mathcal{B}_A / \mathrm{im}(A)\), (weak) Minkowski summand as partial order, normal equivalence, polyhedral subdivision of \(\bar{\mathcal{B}}_A\) by type cones; restricted to a type cone, the function \(V_A(\cdot)\) is of the form \(\mathrm{vol}_d( \lambda_1P_1 + \cdots + \lambda_n P_n)\); Thm(Minkowski). the function \(\mathrm{vol}_d( \lambda_1K_1 + \cdots + \lambda_n K_n)\) is a homogeneous polynomial of degree \(d\); sufficient to prove for polytopes; special case: exact Minkowski sums

mixed subdivisions and exact mixed subdivisions; Proof of Minkowski's theorem; fine mixed subdivisions are exact; Existence of (fine) mixed subdivisions via the Cayley trick;

June 4/6 Minkowskis's existence/uniqueness problem: polytope \(P\) with unit facet normals \(a_1,\dots,a_n\) and facet volumes \( \alpha_1, \dots, \alpha_n >0\) iff \(\sum_i\alpha_i = 0\); \(P\) unique up to translation; Proof uses Brunn-Minkowski + equality cases; \(\mathcal{M}_A = \{ b : \mathrm{vol}_d P_A(b) \ge 1 \}\) is a smooth convex body with lineality space = column-span of \(A\); Proof is algorithmic (minimizing a convex function over convex domain); complexity question;

Applications: If for every facet of \(P\) there is a parallel facet of equal volume, then \(P\) is centrally-symmetric (cs); If \(P\) has dissection by cs polytopes, then \(P\) is cs; If all \(k\)-faces (\(k > 1\)!) are cs, then \(P\) is cs; orthant-shaped polyhedra; Thm (Pogorelov): For \(a_1,\dots,a_n \in \mathbb{R}^d_{>0}\) and \(\alpha_1,\dots,\alpha_n >0\) there is a unique(!) orthant shaped polyhedron with \(\{a_i\}\) normals to bounded facets and \(\{\alpha_i\}\) corresponding facet volumes.

May 28/30 geometric-arithmetic mean inequality; isoperimetric inequality for rectangles; Minkowski's inequality; proof of theorem from last week; volumes of slices of a convex body; unimodality; Brunn's `slice inequality'; Brunn-Minkowski inequality

Brunn-Minkowski inequality and the equality cases; Cayley embeddings and proof of Brunn's theorem; polyboxes; BM-inequality for convex bodies from BM-inequality for polyboxes; BM-inequality for boxes via Minkowski inequality; proof of BM-inequality for polyboxes

May 21/23 intuition in high dimensions: volumes of crosspolytopes, unit balls, and cubes; Busemann-Petty problem; complexity (e.g., #vertices) for approximation of unit ball; Thm: Polytopes with polynomially many vertices give bad approximation of (volume of) the unit ball; bad news for deterministic algorithms that approximate volume;

approximation by ellipsoids; Fritz John's theorem; Thm: \(\sqrt[n]{\det(A)}\) is strictly concave on positive definite matrices; uniqueness of maximal volume ellipsoid

May 14/16 polyhedral complex, subdivision of a polytope (=dissection with more structure); valuations and inclusion-exclusion (IE) formula, Volland's Theorems: IE holds for valuations on polytopes / independence of choice of dissection; boundary complexes, complex of bounded faces; regular subdivisions via projections of complex of bounded faces; non-regular subdivisions

regular subdivisions and piecewise-linear convex functions; refinements and Baues poset; regular subdivisions and secondary polytopes; n-gons and associahedra; cubes and minimal triangulations; Delaunay triangulations; computing triangulations via beneath-beyond; pushing triangulations and number of iterations via Upper Bound Theorem

May 7 flags of faces, barycentric subdivision; volume of polytopes via barycentric subdivisions; independence of the choice \(b_F \in \mathrm{relint}(F)\); pyramids, heights, volume of pyramid; Lemma: Facet volumes give linear dependence of unit facet normals; Minkowski's theorem (first appearance)
April 30/May 2 distance function \(d_K\) of a convex body; Thm: \(d_K = h_{K^\triangle}\); specifying convex bodies: polytopes and memebership/separation oracles; outer parallel bodies, Hausdorff distance, Thm: \(d(K,L)=\|h_K-h_L\|_\infty\); cone of convex bodies is isometric to cone of pos. linear convex functions; approximation by (rational, simplicial) polytopes; boxes and volumes, polyboxes and Jordan measurable sets; Thm: convex bodies are Jordan measurable; volume of convex body via Lebesque measure

volume from first principles: properties of volume; dissections of polytopes; equidecomposable/scissor congruence; Hilbert's 3rd problem; Dehn invariant, Hadwiger's theorem; Hadwidger's volume theorem; dissection of unit cube into \(d!\) simplices; volume of simplex via parallelpipeds; determinant formula

April 16/18 hyperplanes and halfspaces, (strictly) separating hyperplane; Separation theorem for \(p\) and \(A\) closed convex; supporting hyperplane, closed convex sets are intersections of halfspaces; support function \(h_K\) determines convex body \(K\); Minkowski sums and support functions; separation more general; supporting hyperplane through every point \(p \in \partial K\); proof of Minkowski's theorem;

faces and exposed faces; relative interiors of faces partition \(K\); face lattice; in general not graded; not every face is exposed; polarity, polar of a set; properties; Bipolar theorem; Minkowski-Weyl light: \(K\) polytope \(\Leftrightarrow K^\triangle\) polytope

April 23/25 Farkas lemma; proof of Minkowski-Weyl light; polytopes are bounded polyhedra; irredundant inequalities, facets; facets are exposed; conjugate faces, properties; smooth points

support functions are positively linear and convex; Theorem: this characterizes support functions of convex bodies; Radon's lemma; Helly's theorem for finite families; Helly for infinite families (see also the survey on generalizations of Helly's theorem); proof of characterization via Helly and Farkas; Corollary: \( \{ K \subseteq \mathbb{R}^d : K \neq \emptyset \text{ convex body}\} \cong \{ f: \mathbb{R}^d \rightarrow \mathbb{R} : \text{ pos. linear, convex} \} \) as convex cones.

April 16/18 hyperplanes and halfspaces, (strictly) separating hyperplane; Separation theorem for \(p\) and \(A\) closed convex; supporting hyperplane, closed convex sets are intersections of halfspaces; support function \(h_K\) determines convex body \(K\); Minkowski sums and support functions; separation more general; supporting hyperplane through every point \(p \in \partial K\); proof of Minkowski's theorem;

faces and exposed faces; relative interiors of faces partition \(K\); face lattice; in general not graded; not every face is exposed; polarity, polar of a set; properties; Bipolar theorem; Minkowski-Weyl light: \(K\) polytope \(\Leftrightarrow K^\triangle\) polytope

April 9/10 linear/affine subspaces, linear/affine hulls, convexity, convex combinations; examples: polygons, polytopes, unit balls (for various norms), positive semidefinite matrices, positive polynomials, sums-of-squares, epi-graphs of convex functions; convex hulls = convex combinations of finitely many points; application: Gauss-Lucas theorem;
affine dependence, Caratheodory's theorem; \(X\) compact \(\Rightarrow\) \(\mathrm{conv}(X)\) compact; convex bodies; (relative) interior and boundary; \(\mathrm{relint}(X)\) is convex; affine hull and dimension; relative interior of simplices; extreme points; Minkowski's theorem: \(K = \mathrm{conv}(\mathrm{ext}(K))\) if \(K\) compact; nearest point map: well-defined and unique; characterization of closed convex sets