Pat Morin
In 1982, Ajtai, Chvátal, Newborn, and Szemerédi proved that in any plane drawing of an n-vertex graph with m ≥ 4n edges, the number of crossing pairs of edges is Ω(m3/n2). since then, this result, which has become known as the Crossing Lemma has found numerous applications, especially in the field of combinatorial geometry.
This talk will present tight versions of the Crossing Lemma for graphs whose vertices are the points of a d-dimensional (d ≥ 3) grid of volume N and whose edges are drawn as straight lines joining their endpoints. In particular, the number of crossing pairs of edges is Ω((m2/N)log N) for d = 3 and Ω(m2/N) for d > 3. Applications of this result to counting the number of non-crossing grid graphs will also be discussed.
This is joint work with Vida Dujmović (U. Ottawa) and Adam Sheffer (Tel Aviv U.) and is available as arxiv:1301.0303.