Oliver Janzer and Benny Sudakov Settled the Erdős-Sauer Problem

Norbert Sauer

The news in brief:  In the new paper Resolution of the Erdős-Sauer problem on regular subgraphs Oliver Janzer and Benny Sudakov proved that any graph G with vertices and more than edges contains a k-regular subgraph. This bound matches the lower bound of Pyber, Rödl and Szemerédi and thus completely resolved the well-known problem of Erdős and Sauer from 1975. The new bound substantially improves an 1985 result of Pyber, who showed that   edges suffice.

The history of the Erdős -Sauer problem 1975-2022

Erdos and Sauer asked in 1975 how many edges (let’s denote the minimum number ) for an n-vertex graph guarantee a k-regular subgraph. In 1985 Laszlo Pyber proved that for some every graph with vertices and edges contains a k-regular graph. A few years later Pyber, Rodl and Szemeredi found a construction of a graph with n vertices and  edges that contains no k-regular subgraph for every . (The paper appeared in 1995 but the result is from the late 80s.)

Paul Erdős  mentioned the problem among his favorites in a famous paper in 1980 (Vol 1. Issue 1. of Combinatorica) and mentioned the results of Pyber and of Pyber, Rodl and Szemeredi in his 1989 paper.

Oliver and Benny proved an upper bound on the number of edges of k-regular free graphs that matches the Pyber, Rodl and Szemeredi lower bound. Congratulations!

AFK84 and the Berge-Sauer problem

Theorem: Every graph (or hypergraph) G with n vertices and 2n+1 edges contains a nontrivial subgraph H with all vertex-degrees divisible by 3.

This is a theorem of Noga Alon,  Shmuel Friedland, and me (AFK) from 1984.)

Before the proof: If we want to get a subgraph with all vertex degrees even then we need n edges (or n+1 edges for hypergraphs). This has a simple linear algebra proof which also gives an efficient algorithm.

From-scratch proof scatch: Associate to every edge e of the graph a variable . Consider the two polynomial

P= , and

Q=

If the theorem is false then P-Q=0, as polynomials over the field with three elements. This is impossible since P is a polynomial of degree 4n while Q is a polynomial which has a monomial of degree 4n+2 with nonzero coefficient.

The theorem follows more directly from a theorem of Chevallay and even more directly from a theorem of Olson.

AFK84 was a necessary ingredients of Pyber 1985 upper bound as well as the Janzer-Sudakov new upper bound. It will be very nice to get rid of this ingredient. AFK84 came a little short of proving the Berge-Sauer conjecture that every 4-regular graph contains a 3-regular subgraph.  This conjecture was proved in a 1982 paper by Taskinov.

Three problems

A) Is it true that every graph with n vertices and 2n+1 edges with maximum degree 5 contains a 3-regular graph of type I? (Namely a 3-regular 3-edge colorable subgraph.)

B) How many edges for a 3-uniform hypergraph on n vertices guarantees a k-regular sub-hypergraph? (Here we refer to “3-regular hypergraph as a hypergraph so that every vertex belongs to three (or zero) edges. You can also demand that every pair of vertices belongs to three or zero edges.)

C) Is there a polynomial-time algorithm to find a r-regular subgraph for a graph with n vertices and edges.

Climbing the Turan ladder

Climbing the Turan ladder refers to unavoidable subgraphs of a graph of n vertices and m edges as m grows. (The Erdos-Renyi ladder is a similar notion for random graphs.)

Problem A) is related to the following:

When is roughly

a) (for ) you must have a subgraph with all degrees larger than 2

b) (for ) you must have a subgraph with all degrees divisible by 3 (AFK84), and

c) (for ) you also must have a subgraph such that you can color its edges with three colors so that every (non-isolated) vertex have neighbors of the all color.

We don’t know what guarantees

d) such an so that for every vertex the number of edges of each color is the same modulo three.

Condition d) is stronger than both b) and c) and each of them is stronger than a). Both a), b) and c) extend to hypergraphs.

The relevance of Christos’s classes and the PME-conjecture.

The Probabilistic Method is Efficient (PME) Conjecture asserts: Every mathematical proof based on the probabilistic method can be transformed into an efficient (randomized) algorithm.

This is a vague and controversial conjecture that I mentioned in the post Poznań: Random Structures and Algorithms 2013. (There I  referred to it as the Kalai-Spencer conjecture.) Now, if we can get rid of AFK84 and find a purely combinatorial/probabilistic  proof even just for the fact that every graph with vertices and edges contains a 3-regular subgraph, this would be nice on its own and may lead (especially for PME-believers) to an efficient algorithm. AFK84 is not supported by an efficient algorithm and, in fact it is related to one of Christos Papadimitriou’s classes describing the algorithmic difficulty for finding objects guarantees by mathematical proofs. See Papadimitriou’s  1994 paper: On the complexity of the parity argument and other inefficient proofs of existence‏.