Finding regular subgraphs

Zoom Link

Finding regular subgraphs can be useful. Many results assume a graph is regular or are easier to prove when they are. In 1975, Erdős and Sauer asked for an estimate, for any constant r, on the maximum number of edges an n-vertex graph can have without containing an r-regular subgraph. In 2023, Janzer and Sudakov gave an upper bound of the form C(r)n log log n, matching an earlier lower bound by Pyber, Rödl and Szemerédi and thus resolving the Erdős-Sauer problem.

We develop the methods for finding a regular subgraph, showing not only that we can take C(r)=O(r^2), which is optimal up to the implicit constant, but giving estimates for the maximum number of edges an n-vertex graph can have without containing an r-regular subgraph for all possible values of r, which are similarly tight except for around a small `transition point' at r=log n.

I will discuss the framework now developed to find regular subgraphs efficiently, which uses algebraic techniques of Alon, Friedland and Kalai, the recent breakthroughs on the sunflower conjecture, techniques to find almost-regular subgraphs developed from Pyber’s work, and, crucially, a novel random process that efficiently finds a very nearly regular subgraph in any almost-regular graph.

Joint work with Debsoumya Chakraborti, Oliver Janzer and Abhishek Methuku.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.