Скачать или смотреть Finding Regular Subgraphs - Richard Montgomery

Computer Science/Discrete Mathematics Seminar I
10:30am|Simonyi Hall 101 and Remote Access
Topic: Finding Regular Subgraphs
Speaker: Richard Montgomery
Affiliation: University of Warwick
Date: February 24, 2025

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 (one in which each vertex is in r edges). The best upper bound on this problem was for a long time one of Pyber from 1985, but the last few years have seen rapid developments, initiated by Janzer and Sudakov, and we now have an efficient framework to find regular subgraphs for not only constant r but the whole range of possible values of r.

I will discuss this framework and its components, which include 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.