The 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. Large-clique conjecture. There are constants c1,c2>0c_1,c_2>0 such that, for all integers t3t\geq 3, kc1logtk\geq c_1\log t, and nt1n\geq t-1,

cliques(n,t,k)(c2t)kn.\textup{cliques}(n,t,k)\leq (c_2t)^k n.

For fixed kk, the quantity is known up to a constant factor of order (tlogt)k1n(t\sqrt{\log t})^{k-1}n, while the conjectured bound is known for sufficiently large kk, leaving the intermediate range open.

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.