Polytopes
Lectures on Polytopes
- Chapter 1: Polytopes, Polyhedra, and Cones
- Definitions: H-polytope, V-Polyhedron, V-Polytope, Cone, Conical Hull
- Minkowski–Weyl: \(\mathcal{V}\)-polyhedron \( \implies \mathcal{H}\)-polyhedron [using Fourier-Motzkin Elimination]
- Minkowski–Weyl: \(\mathcal{H}\)-polyhedron \( \implies \mathcal{V}\)-polyhedron [TODO]
- Proposition 1.7: Farkas Lemma (I) (Incomplete Notes) [TODO]
- Proposition 1.8: Farkas Lemma (II)
- Proposition 1.9: Farkas Lemma (III)
- Chapter 2: Faces of Polytopes
- Definitions: Faces of Polytopes
- Proposition 2.2: Every polytope is the convex hull of its vertices
- Proposition 2.3(i): The face \(F\) is a polytope, with \(\operatorname{vert}(F)=F\cap V\).
- Proposition 2.3(ii): Every intersection of faces of \(P\) is a face of \(P\).
- Proposition 2.3(iii): The faces of \(F\) are exactly the faces of \(P\) that are contained in \(F\).
- Definitions: Poset, Graded Poset, Lattice,... (+ Example)
- Theorem 2.7(i): For every polytope \(P\), the face poset \(L(P)\) is a graded lattice of length \(\dim(P)+1\), with rank function \(r(F)=\dim(F)+1.\)
Combinatorial Reciprocity Theorems
- Chapter 4: Rational Generating Functions
- Proposition 4.1.2: The sets \((M)\), \((\gamma)\), \((\Delta)\), and \((h^*)\) are bases for the vector space \(\mathbb{C}[x]_{\le d} := \{f \in \mathbb{C}[x] : \deg(f)\le d\}.\)
- Proposition 4.1.3: A sequence \(f(n)\) is given by a polynomial of degree \(\le d\) if and only if \((\Delta^m f)(0)=0 \) for all \(m>d\).
- If \(f(n) = \binom{n}{m}\), then \( F(z) = \sum_{n \geq 0} \binom{n}{m} z^n = \frac{z^m}{(1-z)^{m+1}} \)
- Proposition 4.1.4: A sequence \(f(n)\) is given by a polynomial of degree \(\le d\) if and only if \[ \sum_{n\ge 0} f(n)z^n = \frac{h(z)}{(1-z)^{d+1}} \] for some polynomial \(h(z)\) of degree \(\le d\). Furthermore, \(f(n)\) has degree \(d\) if and only if \(h(1)\neq 0\).
- Proposition 4.1.5: Let \((f(n))_{n\ge0}\) be a sequence of numbers. Then \((f(n))_{n\ge0}\) satisfies a linear recurrence of the form (4.1.10) (with \(c_0,c_d\neq0\)) if and only if \[ F(z)=\sum_{n\ge0} f(n)z^n =\frac{p(z)}{c_d z^d+c_{d-1}z^{d-1}+\cdots+c_0} \] for some polynomial \(p(z)\) of degree \(< d\).
- Chapter 5: Subdivision