MATH 669 - COMBINATORICS OF POLYTOPES (Alexander Barvinok)

MATH 669: COMBINATORICS OF POLYTOPES

Alexander Barvinok

Abstract. These are rather condensed notes, not really proofread or edited, presenting key definitions and results of the course that I taught in Winter 2010 term.

Problems marked by are easy and basic, problems marked by

∗ may be difficult.

1. Basic definitions 3

2. Carath´eodory’s Theorem 4

3. Radon’s Theorem 5

4. Helly’s Theorem 6

5. Euler characteristic 7

6. Polyhedra and linear transformations 10

7. Minkowski sum 12

8. Examples of valuations 14

9. The structure of polyhedra 16

10. The Euler-Poincar´e formula 23

11. The Birkhoff polytope 24

12. The Schur-Horn Theorem 26

13. Transportation polyhedra 27

14. The permutation polytope 28

15. Cyclic polytopes 31

16. Polarity 32

17. Polytopes and polarity 36

18. Regular triangulations and subdivisions 38

19. The secondary polytope 39

20. Fiber polytopes 43

21. Identities modulo polyhedra with lines 46

22. The exponential valuation 49

23. A formula for the volume of a polytope 54

24. Simple polytopes and their h-vectors 55

25. The Upper Bound Theorem 58

26. Balinski’s Theorem 61

27. Reconstructing a simple polytope from its graph 63

28. The diameter of the graph of a polyhedron 65

29. Edges of a centrally symmetric polytope 66

30. Approximating a convex body by an ellipsoid 68

31. Spherical caps 70

32. An inequality for the number of faces of a centrally symmetric polytope 72

33. Gale transforms and symmetric Gale transforms 75

34. Almost Euclidean subspaces of ℓ

and centrally symmetric polytopes

with many faces 77

35. The volume ratio and almost Euclidean subspaces

LINK DOWNLOAD