Paper detail

Maximizing the density of $K_t$'s in graphs of bounded degree and clique number

Zykov showed in 1949 that among graphs on $n$ vertices with clique number $ω(G) \le ω$, the Turán graph $T_ω(n)$ maximizes not only the number of edges but also the number of copies of $K_t$ for each size $t$. The problem of maximizing the number of copies of $K_t$ has also been studied within other classes of graphs, such as those on $n$ vertices with maximum degree $Δ(G) \le Δ$. We combine these restrictions and investigate which graphs with $Δ(G) \le Δ$ and $ω(G) \le ω$ maximize the number of copies of $K_t$ per vertex. We define $f_t(Δ,ω)$ as the supremum of $ρ_t$, the number of copies of $K_t$ per vertex, among such graphs, and show for fixed $t$ and $ω$ that $f_t(Δ,ω) = (1+o(1))ρ_t(T_ω(Δ+\lfloor\fracΔ{ω-1}\rfloor))$. For two infinite families of pairs $(Δ,ω)$, we determine $f_t(Δ,ω)$ exactly for all $t\ge 3$. For another we determine $f_t(Δ,ω)$ exactly for the two largest possible clique sizes. Finally, we demonstrate that not every pair $(Δ,ω)$ has an extremal graph that simultaneously maximizes the number of copies of $K_t$ per vertex for every size $t$.