Robust Hajnal–Szemerédi conjecture for induced KrK_r-factors

Let r2r\geq 2, let nn be divisible by rr, and let GG be an ((r1)nr+1)(\tfrac{(r-1)n}{r}+1)-regular graph on nn vertices. A subset of V(G)V(G) induces a KrK_r-factor if its induced subgraph has a partition into vertex-disjoint copies of KrK_r. Robust Hajnal–Szemerédi conjecture. For every r2r\geq 2, there is an ε>0\varepsilon>0 such that at least

ε2n\varepsilon 2^n

subsets of V(G)V(G) induce a KrK_r-factor.

This is a robust analogue of the Hajnal–Szemerédi theorem, replacing the existence of one KrK_r-factor by a positive proportion of subsets inducing one. The supplied source gives no resolution status.

Sources & referencesView supporting material

Primary source

Nemanja Draganić, Peter Keevash and Alp Müyesser, “Cyclic subsets in regular Dirac graphs”, arXiv:2503.01826 (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.