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

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 t3t\geq 3, kλtk\geq\lambda t, and nt1n\geq t-1,

cliques(n,t,k)(t2k1)(n(k1)(t1)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.

Sources & referencesView supporting material

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.