Packing conjecture for graphs with many large complete bipartite subgraphs

At least 5 years old · documented by

Let GG be a graph on NN vertices. Suppose there is a parameter WW such that, for every induced subgraph G′G' and every nn, all but at most

Wn∣V(G′)∣2\frac{W}{n}|V(G')|^2

edges of G′G' are contained in some complete bipartite graph K∣V(G′)∣/n,∣V(G′)∣/nK_{|V(G')|/n,|V(G')|/n}. Say that two copies of GG pack into KNK_N when they can be embedded on the same NN-vertex set with edge-disjoint edge sets. Packing conjecture. If, in addition, two copies of GG pack into KNK_N, then

N=WO(1).N=W^{O(1)}.

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.

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.