2016/06/22 by Fox, Jacob, Wei, Fan
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1606.06810
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 ≥ t vertices with no Kt-immersion has at most 2t+log2 tn 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. 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.