Conjecture on bounded-size regular subgraphs

Let s3s\geq 3 be an integer and let ε>0\varepsilon>0. Bounded-size regular-subgraph conjecture. There is a positive integer tt such that, for all sufficiently large nn, every nn-vertex graph GG of average degree at least n12s+εn^{1-\frac{2}{s}+\varepsilon} contains an ss-regular subgraph on at most tt vertices. This is a regular-subgraph strengthening of the bounded-size dense-subgraph problem. The source states that it is known when ss is even or when s=3s=3, but leaves the general case open.

Sources & referencesView supporting material

Primary source

Oliver Janzer, Benny Sudakov and István Tomon, “Small subgraphs with large average degree”, arXiv:2207.02170 (2022).

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.