Geometry Seminar

---

The Crossing Lemma for multigraphs

Speaker: Géza Tóth, Rényi Institute, Budapest

Location: Warren Weaver Hall 1314

Videoconference link: https://youtu.be/Aa3r6-fmZXQ

Date: Tuesday, October 22, 2024, 6 p.m.

Synopsis:

Let \(G\) be a simple graph with \(n\) vertices and \(e>4n\) edges.  According to the Crossing Lemma, the number of crossings in any drawing of \(G\) is at least \(c{e^3\over n^2}\), for a \(c>0\). This bound cannot be improved apart from the value of \(c\).  There is no such statement for multigraphs in general.  We investigate under what conditions does the statement of the Crossing Lemma, or a similar statement hold for multigraphs.

In particular, we show that if the “lens” enclosed by every pair of parallel edges contains at least one vertex and adjacent edges do not cross, then the original statement holds.  A similar, but weaker bound holds if we only assume that no two edges are homotopic, that is, no two parallel edges can be continuously transformed into each other without passing through a vertex.

Joint work with M. Kaufmann, J. Pach, G. Tardos, T. Ueckerdt.
 

Notes:

In person.  Also simultaneously broadcast on Zoom, contact Boris Aronov for meeting ID.