MATH Seminar

Title: Crossing and Color
Seminar: Combinatorics
Speaker: János Pach, PhD of Rényi Institute of Mathematics, Budapest
Contact: Liana Yepremyan, liana.yepremyan@EMORY.EDU
Date: 2025-02-28 at 4:30PM
Venue: MSC W301
Download Flyer
Abstract: Turán defined cr(G), the crossing number of a graph G, as the smallest number of edge crossings in a proper drawing of G in the plane. This notion has turned out to play an important role in combinatorial geometry, additive number theory, chip design, and elsewhere. The computation of cr(G) is a classical NP-hard problem, so it is not surprising that there are very few graphs whose crossing numbers are known. In particular, we do not even know the asymptotic value of the crossing number of the complete graph K_r on r vertices, as r tends to infinity. Nevertheless, Albertson made the conjecture that cr(G) is at least cr(K_r), for any graph G whose chromatic number is at least r. After giving a short and biased survey of some important results on crossing numbers, we explain the relationship between crossings and coloring, and settle Albertson's conjecture for graphs whose number of vertices is not much larger than their chromatic number. Joint work with Jacob Fox and Andrew Suk.