Balogh–Kemkes–Lee–Young's weighted Hajnal–Szemerédi conjecture

About 1 year old · traced to

Let G=(V,E,w)G=(V,E,w) be an edge-weighted complete graph on nn vertices, where w:E→[0,1]w:E\to[0,1]. For v∈Vv\in V, define its weighted degree by dw(v):=∑uv∈Ew(uv)d^w(v):=\sum_{uv\in E}w(uv) and let δw(G):=min⁡{dw(v):v∈V}\delta^w(G):=\min\{d^w(v):v\in V\}. A copy of KrK_r is tt-heavy if the sum of the weights of its (r2)\binom{r}{2} edges is strictly greater than (r2)t\binom{r}{2}t; a KrK_r-factor is a collection of vertex-disjoint copies of KrK_r covering VV. Balogh–Kemkes–Lee–Young's conjecture. For any μ>0\mu>0, r≥2r\ge 2, t∈(0,1)t\in(0,1), and any sufficiently large n∈rNn\in r\mathbb{N}, if

δw(G)≥(1r+(1−1r)t+μ)n,\delta^w(G)\ge \left(\frac{1}{r}+\left(1-\frac{1}{r}\right)t+\mu\right)n,

then GG contains a tt-heavy KrK_r-factor. This is a weighted analogue of the Hajnal–Szemerédi theorem, asking for the minimum weighted-degree threshold guaranteeing a perfect heavy clique tiling; the supplied parser gives no evidence that the conjecture has been resolved.

References

Primary source

Wanting Sun, Shunan Wei and Donglei Yang, “Packing tetrahedrons in edge-weighted graphs”, arXiv:2506.07147 (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.