Clique count bound for Kₜ-immersion-free graphs
Conjecture on maximum cliques with no $K_t$-immersion · arXiv:1606.06810
Status open high confidence
Fox and Wei construct a graph achieving $2^{t-2}(n-t+3)$ cliques with no $K_t$-immersion (take $K_{t-2}$ and attach $n-t+2$ universal vertices over it), and conjecture this is optimal. Their paper proves an upper bound of $2^{t+\log^2 t}n$, which falls short of the conjectured exact value by a factor of $2^{O(\log^2 t)}$. No follow-up paper proving or disproving the sharp bound was found in an exhaustive web search as of May 2026.
Reviewer notes. The Fox-Wei paper proves an upper bound of $2^{t+\log^2 t}n$ cliques for $K_t$-immersion-free graphs (Theorem 1.3), which is sharp up to a $2^{O(\log^2 t)}$ factor. The conjecture asks for the exact extremal value $2^{t-2}(n-t+3)$, a linear function in $n$ with leading coefficient $2^{t-2}$. No published or arXiv paper resolving this sharp form was found in five web searches.
Context
The authors construct a graph on $n$ vertices with no weak $K_t$-immersion achieving $2^{t-2}(n-t+3)$ cliques: begin with a clique $K$ on $t-2$ vertices and attach $n-t+2$ additional vertices each with neighborhood $K$. Since every vertex outside $K$ has degree $t-2 < t-1$, no $K_t$-immersion exists. The authors conjecture this construction is optimal.
Notes. PDF source — stated in running prose in the introduction without a labeled conjecture environment; math notation garbled in extraction and reconstructed.
Source paper
On the number of cliques in graphs with a forbidden subdivision or immersion
Jacob Fox, Fan Wei · 2018-08-07
https://arxiv.org/abs/1606.06810
PDF source