The very-large-clique conjecture for graphs excluding a complete minor

About 11 years old · traced to

Let cliques(n,t,k)\textup{cliques}(n,t,k) denote the maximum number of kk-cliques in an nn-vertex graph with no KtK_t-minor. Very-large-clique conjecture. There is some λ∈[13,1)\lambda\in[\tfrac13,1) such that, for all integers t≥3t\geq 3, k≥λtk\geq\lambda t, and n≥t−1n\geq t-1,

cliques(n,t,k)≤(t−2k−1)(n−(k−1)(t−1)k).\textup{cliques}(n,t,k)\leq \binom{t-2}{k-1}\left(n-\frac{(k-1)(t-1)}{k}\right).

This conjecture asserts that the lower bound established earlier is tight for cliques whose size is a fixed positive fraction of tt. The source presents it as open; it concerns the extremal regime of very large cliques in KtK_t-minor-free graphs.

References

Primary source

David R. Wood, “Cliques in Graphs Excluding a Complete Graph Minor”, arXiv:1511.04655 (2016).

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.