The quadratic-logarithmic conjecture for regular subgraphs

About 2 years old · traced to

Let d(r,n)d(r,n) be the smallest average degree such that every nn-vertex graph with average degree at least d(r,n)d(r,n) contains an rr-regular subgraph. Quadratic-logarithmic conjecture. There exists some constant CC such that, whenever r≤12log⁡nr\leq \frac{1}{2}\log n, every nn-vertex graph with average degree at least

Cr2log⁡(log⁡nr)Cr^2 \log\left(\frac{\log n}{r}\right)

contains an rr-regular subgraph. The paper establishes matching-order bounds for r≥12log⁡nr\geq \frac{1}{2}\log n and gives lower and upper bounds differing in the logarithmic factor in the stated range, so this refinement remains open.

References

Primary source

Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku and Richard Montgomery, “Regular subgraphs at every density”, arXiv:2411.11785 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.