The quadratic-logarithmic conjecture for regular subgraphs

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 r12lognr\leq \frac{1}{2}\log n, every nn-vertex graph with average degree at least

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

contains an rr-regular subgraph. The paper establishes matching-order bounds for r12lognr\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.

Sources & referencesView supporting material

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.