On the number of cliques in graphs with a forbidden subdivision or immersion

How many cliques can a graph on n vertices have with a forbidden substructure? Extremal problems of this sort have been studied for a long time. This paper studies the maximum possible number of cliques in a graph on n vertices with a forbidden clique subdivision or immersion. We prove for t sufficiently large that every graph on n \geq t vertices with no Kt-immersion has at most n2t+log22 t cliques, which is sharp apart from the 2O(log2 t) factor. We also prove that the maximum number of cliques in an n-vertex graph with no Kt-subdivision is at most 21.817tn for sufficiently large t. This improves on the best known exponential constant by Lee and Oum. We conjecture that the optimal bound is 32t/3+o(t)n, as we proved for minors in place of subdivision in earlier work.

Duke Scholars

Author Fan Wei Mathematics