The quadratic-logarithmic conjecture for regular subgraphs
Let be the smallest average degree such that every -vertex graph with average degree at least contains an -regular subgraph. Quadratic-logarithmic conjecture. There exists some constant such that, whenever , every -vertex graph with average degree at least
contains an -regular subgraph. The paper establishes matching-order bounds for 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
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.