Combinatorics and Geometry: Crossing paths—in the age of AI.

Live Video Link.

Crossing numbers: Dead or alive.

The crossing number of a graph \(G\), denoted by \(cr(G)\), is the smallest number of edge crossings in any drawing of \(G\) in the plane. Clearly, \(cr(G)=0\) if and only if \(G\) is planar. Garey and Johnson proved that determining \(cr(G)\) is an NP-complete problem. Over the past forty years, crossing numbers have proven to play a vital role in various fields, including discrete and computational geometry, number theory, and circuit layout (such as providing lower bounds on the chip area required for a graph's physical layout). Yet, many of the foundational questions that inspired research in this area remain open, and new mysteries continue to emerge. Quo vadis?

What makes the chromatic number of a graph large?

There have been many attempts to answer this question. The most natural approach is to look for unavoidable substructures in graphs of large chromatic number. In 1943, Hadwiger made the conjecture that every graph of chromatic number \(r\) can be transformed into a complete graph of \(r\) vertices by a series of edge contractions and vertex and edge deletions. This is one of the most important unsolved problems in graph theory. After giving a somewhat biased survey of the problem, I plan to report on some related recent results, joint with Fox and Suk.