We will use the following books for most of the lectures. Columbia students can get free PDF copies (just search for them on CLIO).
We will also use the following book for one lecture.
There will be one homework assignment, due on the last day of classes. This shouldn't be a lot of work; it's just meant to give you some incentive to think about the material in the weeks when you aren't presenting.
When we get to Lectures on Discrete Geometry, I will start posting problems from the book each week. Each problem has a difficulty rating next to it. At the end of the semester, you can turn in any set of problems whose difficulties sum to at least 15. Many problems have several sub-parts; each sub-part counts separately (so you would get 5 for doing both parts of 1.2.6, for example). I recommend doing a problem each week so that you aren't stuck trying to do them all at the last minute.
You may discuss the problems with other students, but you should write up the solutions on your own.
You can choose from among these problems:
Most weeks, there will be two lectures of about 50 minutes each. There will be a few weeks when we have three slightly shorter lectures.
| Proofs from THE BOOK | ||
|---|---|---|
| Date | Topic | Speaker |
| Monday, January 25 | Sylvester-Gallai theorem, Euler's formula (11, 13) | Dan |
| Monday, February 1 | One square and an odd number of triangles (22) | Riaz |
| Monday, February 1 | Five-coloring plane graphs (38) | Angela |
| Monday, February 8 | Tiling rectangles (26) | Jennifer |
| Monday, February 8 | Every large point set has an obtuse angle (17), Pick's theorem (13) | Dan |
| Monday, February 15 | The slope problem (12) | Tracy |
| Monday, February 15 | Sperner's lemma (27.6), How to guard a museum (39) | Eric |
| Monday, February 22 | Hilbert's third problem (10) | Lilly |
| Monday, February 22 | Cauchy's rigidity theorem (14) | Sarah |
| Monday, February 29 | Touching simplices (16) | Karim |
| Monday, February 29 | Borsuk's conjecture (18) | Xi |
| Lectures on Discrete Geometry | ||
| Date | Topic | Speaker |
| Monday, March 7 | Linear and affine subspaces (1.1) | Jessie |
| Monday, March 7 | Convex sets, Radon's lemma (1.2-1.3.1) | Neranjan |
| Monday, March 21 | Helly's theorem, Centerpoint and ham sandwich (1.3.2-1.4) | Tomer |
| Monday, March 21 | Asymptotics (Concrete Mathematics 9.1-9.2) | Shelby |
| Monday, March 28 | Incidence problems: formulation and lower bounds (4.1-4.2.3) | Liz |
| Monday, March 28 | Lower bound for unit distances, point-line incidences via crossing numbers (4.2.4-4.3) | Tomer |
| Monday, April 4 | Distinct distances (4.4) | Riaz |
| Monday, April 4 | Arrangements (6.1-6.2 bottom of p130) | Karim |
| Monday, April 11 | Segments and Davenport-Schinzel sequences (7.1-just before 7.1.1) | Sarah |
| Monday, April 11 | Superlinear complexity of the lower envelope (7.1.1-7.2 end of p170) | Lilly |
| Monday, April 11 | Superlinear complexity (7.2 starting on p171) | Eric |
| Monday, April 18 | More on Davenport-Schinzel sequences (7.3) | Neranjan |
| Monday, April 18 | Tight upper bound (7.4 p178-179) | Tracy |
| Monday, April 18 | Tight upper bound (7.4 p180-181) | Jessie |
| Monday, April 25 | Minkowski's theorem (2.1) | Liz |
| Monday, April 25 | General lattices (2.2) | Shelby |
| Monday, April 25 | An application in number theory (2.3) | Jennifer |
| Monday, May 2 | Geometric duality, H-polytopes and V-polytopes (5.1-statement of 5.2.2) | Angela |
| Monday, May 2 | H-polytopes and V-polytopes, Faces of a convex polytope (just after statement of 5.2.2-5.3.3) | Xi |