Extremal number of cliques of given orders in graphs with a forbidden clique minor

Alon and Shikhelman initiated the systematic study of a generalization of the extremal function. Motivated by algorithmic applications, the study of the extremal function (Formula presented.), that is, the number of cliques of order (Formula presented.) in (Formula presented.) -minor free graphs on (Formula presented.) vertices, has received much attention. In this paper, we determine essentially sharp bounds on the maximum possible number of cliques of order (Formula presented.) in a (Formula presented.) -minor free graph on (Formula presented.) vertices. More precisely, we determine a function (Formula presented.) such that for each (Formula presented.) with (Formula presented.), every (Formula presented.) -minor free graph on (Formula presented.) vertices has at most (Formula presented.) cliques of order (Formula presented.). We also show this bound is sharp by constructing a (Formula presented.) -minor-free graph on (Formula presented.) vertices with (Formula presented.) cliques of order (Formula presented.). This bound answers a question of Wood and Fox–Wei asymptotically up to (Formula presented.) in the exponent except the extreme values when (Formula presented.) is very close to (Formula presented.).

Duke Scholars

Author Ruilin Shi Mathematics

Author Fan Wei Mathematics