Mathematical Sciences Research Institute

Home » Workshop » Schedules » The Crossing Lemma Revisited

The Crossing Lemma Revisited

Introductory Workshop: Geometric and Topological Combinatorics September 05, 2017 - September 08, 2017

September 08, 2017 (03:30 PM PDT - 04:30 PM PDT)
Speaker(s): Janos Pach (École Polytechnique Fédérale de Lausanne (EPFL))
Location: MSRI: Simons Auditorium
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC


The Crossing Lemma  of Ajtai, Chvatal, Newborn, Szemeredi (1982) and Leighton (1983)states that if a graph of n vertices and e>4n edges is drawn in the plane, then the number of crossings between its edges must be at least constant times e^3/n^2. This statement, which is asymptotically tight, has found many applications in combinatorial geometry and in additive combinatorics. However, most results obtained using the Crossing Lemma do not appear to be optimal, and there is a quest for improved versions of the lemma for graphs satisfying certain special properties. In this talk, I describe some recent extensions of the lemma to multigraphs (joint work with G. Toth) and to families of continuous arcs in the plane (joint work with N. Rubin and G. Tardos, and with G. Tardos).

Supplements No Notes/Supplements Uploaded
Video/Audio Files


H.264 Video 18-Pach.mp4 204 MB video/mp4 rtsp://videos.msri.org/data/000/029/370/original/18-Pach.mp4 Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

See more of our Streaming videos on our main VMath - Streaming Video page.