Alon–Wormald–Zhou conjecture on packing two Kneser graphs
Alon–Wormald–Zhou conjecture on packing two Kneser graphs
Let . The Kneser graph has as vertices the -element subsets of an -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 , Alon–Wormald–Zhou's packing conjecture. If two copies of can be packed into the complete graph on vertices, then
In the cited work, the weaker bound 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
Sign in to submit a solution.
No solutions have been posted yet.