Alon–Wormald–Zhou conjecture on packing two Kneser graphs

About 6 years old · traced to

Let m>w≥1m>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/(log⁡m)2)w=\Omega(m/(\log m)^2) was proved under the same assumption, so the conjectured linear bound remains open.

References

Primary source

Ryan Alweiss, “Set System Blowups”, arXiv:2003.11202 (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.