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

From papers

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 vVv\in V, define its weighted degree by dw(v):=uvEw(uv)d^w(v):=\sum_{uv\in E}w(uv) and let δw(G):=min{dw(v):vV}\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, r2r\ge 2, t(0,1)t\in(0,1), and any sufficiently large nrNn\in r\mathbb{N}, if

δw(G)(1r+(11r)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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Wanting Sun, Shunan Wei and Donglei Yang, “Packing tetrahedrons in edge-weighted graphs”, arXiv:2506.07147 (2025).

Solutions 0

No solutions have been posted yet.