Rachel Kirsch

Many cliques with no large stars

The problem of maximizing the number of cliques has been studied within several classes of graphs. For example, among graphs on n vertices with clique number at most r, the Turán graph T_r(n) maximizes the number of copies of K_t for each size t. Among graphs on m edges, the colex graph C(m) maximizes the number of K_t's for each size t. In recent years, much progress has been made on the problem of maximizing the number of cliques among graphs with n vertices and maximum degree at most r.

In this talk, we discuss the edge analogue of this problem: which graphs with m edges and maximum degree at most r have the maximum number of cliques? We prove in some cases that the extremal graphs contain as many disjoint copies of K_{r+1} as can fit, with the leftovers in another component. These remaining edges form a colex graph. We will then see a related problem where the extremal graphs are not the same for every clique size t.