Packing conjecture for graphs with many large complete bipartite subgraphs

From papers

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

WnV(G)2\frac{W}{n}|V(G')|^2

edges of GG' are contained in some complete bipartite graph KV(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.

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.