Packing conjecture for graphs with many large complete bipartite subgraphs
Packing conjecture for graphs with many large complete bipartite subgraphs
Let be a graph on vertices. Suppose there is a parameter such that, for every induced subgraph and every , all but at most
edges of are contained in some complete bipartite graph . Say that two copies of pack into when they can be embedded on the same -vertex set with edge-disjoint edge sets. Packing conjecture. If, in addition, two copies of pack into , then
This generalizes the preceding Kneser-graph packing question by proposing that the abundance of large complete bipartite subgraphs obstructs packing unless the number of vertices is polynomially bounded in the exceptional-edge parameter. No resolution is given in the source.
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.