Pat Morin

In 1982, Ajtai, Chvátal, Newborn, and Szemerédi
proved that in any plane drawing of an *n*-vertex graph with
*m* ≥ 4*n* edges, the number of crossing pairs of
edges is Ω(*m*^{3}/*n*^{2}). 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 Ω((*m*^{2}/*N*)log *N*) for *d* = 3 and Ω(*m*^{2}/*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.