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 n vertices and more than C_kn \log \log n 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 n \log n   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 f_k(n)) for an n-vertex graph guarantee a k-regular subgraph. In 1985 Laszlo Pyber proved that for some C_k every graph with n vertices and C_kn \log n edges contains a k-regular graph. A few years later Pyber, Rodl and Szemeredi found a construction of a graph with n vertices and  c n \log \log n edges that contains no k-regular subgraph for every k \ge 3. (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 x_e. Consider the two polynomial

P= \prod_{v \in V(G)} ((\sum_{e: v \in e}x^2_e)^2-1), and

Q=\prod_{e\in E(G)}(x_e^2-1)

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 n^{1.01} 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 m is roughly 2n

a) (for m=2n-2) you must have a subgraph with all degrees larger than 2

b) (for m= 2n+1) you must have a subgraph with all degrees divisible by 3 (AFK84), and

c) (for m=2n+1) you also must have a subgraph H 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 m guarantees

d) such an H 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 n vertices and n^{1.01} 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‏.

This entry was posted in Combinatorics and tagged , . Bookmark the permalink.

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

  1. Yevgeny Levanzov says:

    Hi Gil,

    They improved the C_k n logn to C_k n loglogn, so the bounds in the first paragraph should be corrected.

    GK: Thanks, Yevgeny, corrected

  2. Laci Pyber says:

    Is the related problem of ensuring the existence of 3-regular induced subgraphs still open?

    • Gil Kalai says:

      Dear Laci, many thanks for the comment. What is the precise question? Gil

      • Laci Pyber says:

        What is the maximal number of edges of a graph on n vertices which does not contain a 3-regular induced subgraph? It may (or may not) appear in the old book of Bollobás.

      • Gil Kalai says:

        Ahh. Very nice problem! Silly question: is the answer known to be smaller than the Turan number for K_4?

      • Laci Pyber says:

        Actually this may give the only known bound. But a decades have passed since I looked at the problem.

      • Zach Hunter says:

        We can do a bit a better than $ex(n,K_4)$ (which is a positive fraction of edges).

        It suffices to find a copy of $K_{6,6}$ (which may not be necessarily induced). If either part of the copy contains a triangle, then we find a $K_4$ and we are done. Otherwise, by Ramsey’s theorem, we can find independent sets of size 3 on both sides. Together, they induce a copy of $K_{3,3}$.

        However, getting a better bound would be much nicer.

  3. Pingback: Greatest Hits 2015-2022, Part II | Combinatorics and more

  4. Laci Pyber says:

    I found my copy of the book of Bollobás on “Extremal Graph Theory”. The extremal problem I mentioned is a special case of Problem 21 at the end of the chapter on Topological subgraphs. The more general problem of determining the maximal number of edges of an n-vertex graph without a k-regular induced subgraph was in fact suggested by Szemerédi.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s