Number of Cliques in Minor-Closed Classes

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

All graphs are finite, undirected and simple. A $K_t$ minor is obtained by deleting vertices or edges and contracting edges; equivalently there are $t$ disjoint connected vertex sets pairwise joined by an edge. A clique is any set of pairwise adjacent vertices, without maximality; let $\kappa(G)$ count all cliques, including the empty set. For $t\geq2$ set \[c_* =\inf\left\{c>0:\kappa(G)\leq c^t|V(G)|\ \text{for every nonempty }K_t\text{-minor-free graph }G\text{ and every }t\geq2\right\}.\]

Statement recorded in the supplied source.

Is $c_*<\infty$? More explicitly, is there one absolute constant $c$ such that every $n$-vertex $K_t$-minor-free graph has at most $c^t n$ cliques for all $n\geq1,t\geq2$? Determine the minimum universal constant, and the optimal asymptotic exponential rate as $t\to\infty$. [S2]

Short English statement

Is there one exponential-in-t bound, linear in the number of vertices, on all cliques in graphs excluding a complete minor, and what is the smallest possible exponential constant?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3107 (OPG-37081). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Wood, David R., Number of Cliques in Minor-Closed Classes, Open Problem Garden, node 37081. Complete problem, discussion and bibliography (including mathematical image alt text). https://www.openproblemgarden.org/op/number_of_cliques_in_minor_closed_classes.