MIT OpenCourseWare

Browse materialsMIT 18.319 · Fall 2005

Geometric Combinatorics

Subjects: Algebra · Geometry · Mathematics

Art: Max Brückner (1860 – 1934), Brückner Vielflache Tafel 07 · Public domain

Instructor: Dr. Csaba Toth
Term: Fall 2005
Level: Graduate
What's inside: 6 problem sets · 1 reading · 7 other files · 4 web pages
Materials open: MIT OCW

Start here

Start course: Lecture 1: Sylvester-Gallai Theorem, Scott’s Problem about the…Find a topic

Progress is saved in this browser.

Export or import progress

About this course

Source: MIT OpenCourseWare 18.319 Geometric Combinatorics, Fall 2005, Dr. Csaba Toth — original course page on ocw.mit.edu ↗. License: CC BY-NC-SA 4.0. Study order: MIT's own listing order, section by section. Taken from MIT's published course files, downloaded from ocw.mit.edu on September 23, 2026. How RedLectern is built.

Materials are grouped the way MIT organized them. A verified, course-wide order has not been established here.

Before you start

Prerequisites are not listed here. Check MIT's own syllabus for this course.

How this course was organized

What's here, and what isn't

A lecture sequence of 25 items is confirmed. Assignment and exam materials exist too, but MIT's own order for them could not be verified, so they're shown as materials below rather than a sequence.

Not included here

37 items from the source could not be safely included:

MIT's page format for this item wasn't recognized clearly enough to place it safely. (36 items)
Referenced in a table, but without MIT's own verified order, so it isn't used to claim a sequence.

Materials by section

Grouped by section, as MIT organized them. Not sequenced or ordered.

Readings

Assignments

Projects

MIT OpenCourseWare, Dr. Csaba Toth, 18.319 Geometric Combinatorics, Fall 2005.

License: CC BY-NC-SA 4.0 · Edition: Fall 2005 · Open the original course on OCW ↗

Organized by RedLectern, independent of MIT and not endorsed by MIT.

Per-resource rights are recorded on each resource; All-Rights-Reserved items are link-only, never mirrored.

Geometric Combinatorics

Before you start

What's here, and what isn't

Not included here

Materials by section

Readings

Assignments

Projects

Lecture 1: Sylvester-Gallai Theorem, Scott’s Problem about the Number of Distinct Slopes in the Plane

Lecture 2: Scott’s Problem about the Number of Distinct Directions in Three-space

Lecture 3: Motzkin-Rabin Theorem on Monochromatic Lines

Lecture 4: Szemerédi-Trotter Theorem (Two Equivalent Formulations), Crossing Lemma

Lecture 5: Unit Distances, Unit Area Triangles, Beck’s Two Extremities Theorem, Weak Dirac Conjecture

Lecture 6: Crossing Lemma for Multigraphs, Minimum Number of Distinct Distances

Lecture 7: Pach-Sharir Theorem on Incidences of Points and Combinatorial Curves

Lecture 8: Various Crossing Numbers, Embedding Technique

Lecture 9: More on Crossing Numbers Sum vs. Product Sets

Lecture 10: Lipton-Tarjan and Gazit-Miller Separator Theorems

Lecture 11: Cutting Circles into Pseudo-segments, Lenses, Transversal and Packing Numbers, d -intervals

Lecture 12: Intersection Reverse Sequences

Lecture 13: Arrangements, Levels, Lower Envelopes, Davenport-Schinzel Sequences

Lecture 14: Davenport-Schinzel Sequences of Order 3

Lecture 15: Complexity of the First k -levels, Clarkson-Shor Technique, Cutting Lemma

Lecture 16: Proof of Cutting Lemma, Simplicial Partitions

Lecture 17: Spanning Trees with Low Stabbing Numbers

Lecture 18: k -levels, k -sets, Halving Lines

Lecture 19: VC-dimension and ε-nets

Lecture 20: Optimal ε-approximations, Links to Discrepancy Theory

Lecture 21: Binary Space Partitions

Lecture 22: Geometric Graphs and Forbidden Subgraphs

Lecture 23: Zig-zag and Alternating Paths for Disjoint Segments

Lecture 24: Crossing-free Hamiltonian Cycles and Long Monochromatic Paths

Lecture 25: Pseudo-triangulations and Art Gallery Problems