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

Zoom Link

Motivated by algorithmic applications, the study of the extremal function ex(n, K_k, K_t-minor), i.e., the number of cliques of order k in K_t-minor free graphs on n vertices, has received much attention. In this talk, we will show essentially sharp bounds on the maximum possible number of cliques of order k in a K_t-minor free graph on n vertices. More precisely, we determine a function C(k,t) such that for each k < t with t-k >> log_2 t, every K_t-minor free graph on n vertices has at most n C(k, t)^{1+o_t(1)} cliques of order k. We also show this bound is sharp by constructing K_t-minor-free graphs on n vertices with C(k, t) n cliques of order k. This bound answers a question of Wood and Fox-Wei asymptotically up to o_t(1) in the exponent except the extreme values when k is very close to t. This talk is based on a joint work with Ruilin Shi.