Optimal clique count exponent for K_t-subdivisions
Conjecture on optimal exponential constant for $K_t$-subdivision clique count · arXiv:1606.06810
Status open high confidence
The conjecture that the maximum number of cliques in an $n$-vertex graph with no $K_t$-subdivision is $3^{2t/3+o(t)}n$ remains open. The best known upper bound from the source paper is $2^{1.817t+o(t)}n$, improving on Lee--Oum's $2^{(5+o(1))t}n$, while Wood's lower-bound construction (which is also $K_t$-subdivision free) shows the exponent cannot drop below $\frac{2}{3}\log_2 3 \approx 1.06$. A wide web search through May 2026 found no paper improving the upper bound toward the conjectured optimum.
Reviewer notes. No follow-up resolving the conjecture was found. The related paper arXiv:2408.12082 (Shi--Wei, 2024) determines sharp bounds for fixed clique sizes in $K_t$-minor free graphs (a different, stronger restriction than $K_t$-subdivision free), and does not address the subdivision variant. The conjecture posits that the gap between the proved $3^{2t/3+o(t)}n$ bound for $K_t$-minor free graphs and the $2^{1.817t+o(t)}n$ bound for $K_t$-subdivision free graphs can be closed to match the minor bound.
Context
Theorem 1.2 establishes an upper bound of $2^{1.817t+o(t)}n$, improving on Lee and Oum. Wood's lower bound construction (which also forbids clique subdivisions) shows the constant cannot be reduced below $\frac{2}{3}\log_2 3 \approx 1.06$. The authors proved $c(t) = 3^{2t/3+o(t)}$ for $K_t$-minors in earlier work [10] and conjecture the same bound holds for $K_t$-subdivisions.
Notes. PDF source — stated in both the abstract and the introduction in running prose without a labeled conjecture environment; math notation garbled in extraction and reconstructed. The conjecture is presented consistently in two places.
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