ICS Theory Group

ICS 269, Winter 1996: Theory Seminar

23 February 1996:
Thrackles
Mike Dillencourt, ICS, UC Irvine

A thrackle is a graph that can be drawn in the plane so that
  1. its edges are represented by simple curves; and
  2. any two distinct edges either meet at a single common endpoint or cross at exactly one point, interior to both curves.
Thirty years ago, Conway conjectured that an n-vertex thrackle has at most n edges. Lovász, Pach and Szegedy recently made major progress towards resolving this conjecture, by proving that an n-vertex thrackle has at most 2n edges. In this talk, I will present their proof.