everything.study
18.319

Geometric Combinatorics

Graduate · Historical course

Fall 2005

Topics

  • Sylvester-Gallai Theorem, Scott’s Problem about the Number of Distinct Slopes in the Plane
  • Scott’s Problem about the Number of Distinct Directions in Three-space
  • Motzkin-Rabin Theorem on Monochromatic Lines
  • Szemerédi-Trotter Theorem (Two Equivalent Formulations), Crossing Lemma
  • Unit Distances, Unit Area Triangles, Beck’s Two Extremities Theorem, Weak Dirac Conjecture
  • Crossing Lemma for Multigraphs, Minimum Number of Distinct Distances
  • Pach-Sharir Theorem on Incidences of Points and Combinatorial Curves
  • Various Crossing Numbers, Embedding Technique
  • More on Crossing Numbers
  • Lipton-Tarjan and Gazit-Miller Separator Theorems
  • Cutting Circles into Pseudo-segments, Lenses, Transversal and Packing Numbers, d -intervals
  • Intersection Reverse Sequences
  • Arrangements, Levels, Lower Envelopes, Davenport-Schinzel Sequences
  • Davenport-Schinzel Sequences of Order 3
  • Complexity of the First k -levels, Clarkson-Shor Technique, Cutting Lemma
  • Proof of Cutting Lemma, Simplicial Partitions
  • Spanning Trees with Low Stabbing Numbers
  • k -levels, k -sets, Halving Lines
  • VC-dimension and ε-nets
  • Optimal ε-approximations, Links to Discrepancy Theory
  • Binary Space Partitions
  • Geometric Graphs and Forbidden Subgraphs
  • Zig-zag and Alternating Paths for Disjoint Segments
  • Crossing-free Hamiltonian Cycles and Long Monochromatic Paths
  • Pseudo-triangulations and Art Gallery Problems

Readings

Sources