Discrete Geometry III

Winter Semester 2013/2014

news     times     syllabus     literature     homeworks     what happened so far

Prof. Raman Sanyal, Arnimallee 2, room 105

Dr. Arnau Padrol, Arnimallee 2, room 103

For office hours send us an e-mail to make an appointment.


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


lecture tuesday 10-12 Seminarraum Arnimallee 2 (Villa)
recitation wednesday 14-16 046/T9 Seminarraum (Takustr. 9)

syllabus / prerequisites / formalities

This is the third in a series of three courses on discrete geometry. This advanced course centers around the `g-Theorem', that is, the complete characterization of face numbers of simplicial convex polytopes. Combining ideas from the combinatorics (Discrete Geometry I) and the convex geometry (Discrete Geometry II) of polytopes naturally leads to McMullen's polytope/weight algebra. In this setup the g-Theorem and its proof can be clearly phrased. If time permits we will also address connections of the `algebra of polytopes' to intersection theory in toric and tropical geometry.


Preferably Discrete Geometry I and II. Background in discrete geometry (polytopes, subdivisions, h-vectors) and convex geometry (mixed volumes, Brunn-Minkowski, Alexandrov-Fenchel) should suffice.


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


Most of the references from Discrete Geometry I and Discrete Geometry II are still available in the Semesterapparat at the math library. Further bibliography will be anounced in the lectures.


There will be about 10 homework sheets (posted here). You can write your solution to the homeworks in pairs. Please try to solve all problems. This will deepen the understanding of the material covered in the lectures. You are welcome to ask (in person or email) for additional hints for any exercise. Please think about the exercise before you ask. Please mark two of your solutions. Only these will be graded. Some problems are mandatory. You can earn 20 points on every homework sheet. You can get extra credit by solving the bonus problems. State who wrote up the solution. You have to hand in the solutions before the recitation on Wednesday. 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 #9 due February 12
Homework #8 due January 29
Homework #7 due January 22
Homework #5 & #6 due December 18 & January 8
Homework #4 due December 11
Homework #3 due November 27
Homework #2 due November 13
Homework #1 due October 30

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

We are putting together a LaTeXed set of lecture notes here. 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 us know!

Feb 11/12
see TeXed notes.
more details on flips (and what they do to facets); transition polytope \(T\) between \(P\) and \(Q\); correspondence between weight spaces via everts; Proof of the g-Theorem: 1. \(\log(P)\) and \(\log(T)\) induces quad forms on \(\Omega(P)\) with same signature; 2. \(\log(T)\) and \(\log(Q)\) induce quad form on \(\Omega(P)\subset\Omega(Q)\); this is done via explicit calculations with the everts. What else can be done with g-Theorem and weight algebra? Centrally-symmetric polytopes etc.; Connection to Stanley-Reisner rings (and algebra of piecewise polynomials); Wrap up and thanks to everybody who participated!

Feb 4/5
see TeXed notes.
HRM in dim \(d-1\) imply Lefschetz decomposition in dim \(d\); \(P,P^\prime\) normally equivalent implies \(\Omega(P)=\Omega(P^\prime)\); Lemma: corresponding quad. forms have same signature; strategy of proof: change right-hand side and track changes in signatures; space of \(A\)-polytopes, chamber fans, and type cones; flips: passing a wall in the type cone; \(Q\) obtained from \(P\) by a \(m\)-flip with \(1 \le m \le \frac{d}{2}\) then \(g(Q) = g(P) + e_m\).

January 28
see TeXed notes.
a special product formula; separation and an algebraic prove of the Dehn-Sommerville equations; isomorphism to the (real) polytope algebra \(\Pi(P)\); back to the g-Conjecture: weak and strong Lefschetz property; Lefschetz decomposition; non-degenerate quadratic forms; Hodge-Riemann-Minkowski inequalities and Minkowski's second inequality

January 21
see TeXed notes.
Evaluating frame functionals is computation of mixed volumes; Recap: Mixed volumes as coefficients of \(\mathrm{vol}(\lambda_1P_1 + \cdots + \lambda_kP_k)\); a mixed subdivision formula for multiplying weights (proof skipped); the full weight algebra \(\Omega(P),+,\cdot)\); the first weight space via weak Minkowski summands up to translation; generalized support vectors

January 14
see TeXed notes.
the Minkowski relation and weights on polytopes; dimension of the weight spaces \(\Omega_d(P),\Omega_{d-1}(P),\Omega_{0}(P)\); Theorem: If \(P\) is simple, then \(\dim \Omega_r(P) = h_r(P)\); Proof via sweeping; Corollary: If \(P\) simple, then \(\Omega(P) \rightarrow \Omega(F)\) surjective for all faces \(F \subseteq P\); how to compute frame functionals

January 7
see TeXed notes.
separation in the polytope algebra and frame functionals; (weak) Minkowski summands; Shephard's theorem on Minkowski summands; graded subrings \(\Pi(P)\) associated to polytopes; the polytope algebra as an inverse limit of the subrings \(\Pi(P)\); (finite) separation for subrings.

December 17
see TeXed notes.
the nilradical of \(\Pi\); the polytope algebra as a graded ring; motivation and intuition via homogeneous valuations; \(\Pi\) as a \(\mathbb{Q}\)-vector space (torsion and unique divisibility); logarithms and exponentials of polytopes; the graded structure via `taylor expansion'; explicit description of the first graded piece \(\Pi_1\) and structure of \(\mathbb{R}\)-vector space; translation invariant group of polytopes and piecewise linear functions modulo linears

December 10
see TeXed notes.
translation invariant valuations and the translation ideal; the polytope algebra \(\Pi^d = \mathrm{S}\mathcal{P}_d/\mathcal{T}\); Theorem: \(([P]-1)^{\dim P +1} = 0\) in \(\Pi^d\); polyhedral complexes, subdivisions, and triangulations; Hilbert's 3rd problem and the translation ideal; the polytope algebra on the real line; Main result: polytope algebra is a graded ring; First step: \(\Pi = \mathbb{Z} \oplus \Pi_+\) where \(\Pi_+ = \ker \chi\)

December 3
see TeXed notes.
a gallery of separating homomorphisms: projections to subspaces, generalized support functions, and face maps separate; face map: \([P] \mapsto [P^c]\) for some direction \(c\); examples of valuations with `polynomial' behaviour; What are polynomials?; some calculus of finite differences; Prop: \(g : \mathbb{N} \rightarrow G\) polynomial of degree \(< m\) iff \(\Delta^mg \equiv 0\); translation invariant valuations give rise to polynomials; what is a `universal' polynomial valuation?

November 26 Euler map as extension of valuation; the group \(\mathbf{S}\mathcal{P}_d^\times\) of invertible polytopal functions; Theorem: \(f\) invertible iff \(f = \pm [P]\star[Q]^{-1}\); context: non-empty polytopes form cancellative monoid under Minkowski sum; can form Grothendieck group: \(G(\tilde{\mathcal{P}}_d) = (\tilde{\mathcal{P}}_d \times \tilde{\mathcal{P}}_d) / \sim\); Cor: \(G(\tilde{\mathcal{P}}_d)\) is exactly \(\mathbf{S}\mathcal{P}_d^\times\); Observation: \(\ell_*f\) invertible whenever \(f\) is; consider invertibles in subalgebra \(\mathbf{S}\mathcal{P}_d^0\); support functions of polytopal simple functions; separating/distinguishing sets of homomorphisms

November 19 Operations on polytopal simple functions; dilation operator \( \Delta_\lambda [P] = [\lambda P]\); Pullback: \( T : \mathbb{R}^d \rightarrow \mathbb{R}^e \Rightarrow T^* \mathbf{S}\mathcal{Q}_e \rightarrow \mathbf{S}\mathcal{Q}_d\) with \( T^*[P] = [T^{-1}(P)]\); Pushforward (non-trivial!): \( T : \mathbb{R}^d \rightarrow \mathbb{R}^e \Rightarrow T_* \mathbf{S}\mathcal{Q}_d \rightarrow \mathbf{S}\mathcal{Q}_e\) with \( T_*[P] = [T(P)]\); yields new (and powerful) multiplication with \([P] \star [Q] = [P+Q]\); Unit: \([0]\); Invertible elements? Theorem: \( [P]^{-1} = (-1)^{\dim P} [\mathrm{relint}(-P)]\)

November 12 polyhedral simple functions; (intersection) product: \([P] \cdot [Q] = [P \cap Q]\); ring of polyhedral simple functions \((\mathbf{S}\mathcal{Q}_d,+,\cdot)\); valuations on polytopes; Theorem (Volland, Perles-Sallee, Grömer): Correspondence \(\phi : \mathcal{P}_d \rightarrow G\) and \(\phi: \mathbf{S}\mathcal{Q}_d \rightarrow G\); Cor: \(P \mapsto [P]\) is the universal valuation; Cor: Valuations on polytopes have inclusion-exclusion property; polyconvex sets and extension of valuations; the Euler characteristic \(\chi\); extension of \(\chi\) to polyconvex sets and polyhedral simple functions

November 5 f-vectors, h-vectors and Hilbert series of Stanley-Reisner rings; pure and partitionable complexes; Q: When is \(H: \mathbb{Z}_{\ge0} \rightarrow \mathbb{Z}_{\ge0} \) Hilbert function of standard k-algebra?; multicomplexes / order ideals and O-sequences / M-sequences; Thm(Macaulay): \(H(n)\) Hilbert function of standard k-algebra iff O-sequence; binomial representation; Macaulay conditions; Thm: \((h_0,\dots,h_d)\) h-vector of shellable \((d-1)\)-dim simplicial complex iff Macaulay conditions hold iff Hilbert function of standard artinian algebra; Proof of Upper Bound Theorem; Idea for GLBC: Find k-algebra as above and Lefschetz element; the g-Conjecture/Theorem (finally!)

October 29 simplicial complexes, f-vectors, h-vectors; Generalized Lower Bound conjecture and equality cases; convex hull of simplicial f-vectors; g-vectors; commutative algebra: rings, ring maps, ideals, quotients; finitely generated k-algebras, graded rings/algebras and ideals, homogeneous ring maps;finitely generated standard graded algebras; Hilbert function, Hilbert series; Thm: standard \(\Rightarrow (1-t)^dH(R,t)\) polynomial; Stanley-Reisner rings/ideals

October 22 Euler characteristic, Euler-Poincaré formula; only linear relation on all face numbers; more for simplicial polytopes; dual setting: simple polytopes; summing Euler characteristics of k-faces; general linear functions, sweeping, and h-vectors; Dehn-Summerville equations and consequences; UBT and LBT in terms of h-numbers

October 15 towards the g-Theorem; polyhedra, polytopes, cones; convex hull, conical hull; Minkowski-Weyl, affine hull, dimension, support function, faces, f-vectors; Steinitz characterization in dimension 3; the misery in dimension 4; linear programming and combinatorial complexity; Upper Bound Conjecture (Motzkin); k-neighbortly polytopes, neighborliness and neighborly polytopes; cyclic polytopes; Upper Bound Theorem (McMullen 1970); simplicial polytopes; lower bounds on face numbers; simplicial polytopes and stacking; Lower Bound Conjecture (Klee/Grünbaum); proved by Barnette also in 1970