Alon–Wormald–Zhou conjecture on packing two Kneser graphs

From papers

Let m>w1m>w\ge 1. The Kneser graph KG(m,w)\operatorname{KG}(m,w) has as vertices the ww-element subsets of an mm-element set, with two vertices adjacent when the corresponding subsets are disjoint. Two copies of this graph are said to pack into a graph on the same vertex set when their edge sets can be realized as edge-disjoint copies. Writing N=(mw)N=\binom{m}{w}, Alon–Wormald–Zhou's packing conjecture. If two copies of KG(m,w)\operatorname{KG}(m,w) can be packed into the complete graph on NN vertices, then

w=Ω(m).w=\Omega(m).

In the cited work, the weaker bound w=Ω(m/(logm)2)w=\Omega(m/(\log m)^2) was proved under the same assumption, so the conjectured linear bound remains open.

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

Ryan Alweiss, “Set System Blowups”, arXiv:2003.11202 (2025).

Solutions 0

No solutions have been posted yet.