Maximizing subgraph density in graphs of bounded degree and clique number

Abstract

We asymptotically determine the maximum density of subgraphs isomorphic to $H$, where $H$ is any graph containing a dominating vertex, in graphs $G$ on $n$ vertices with bounded maximum degree and bounded clique number. That is, we asymptotically determine the constant $c=c(H,\Delta ,\omega )$ such that ex$(n,H,\{K_{1,\Delta +1},K_{\omega +1}\})=(1-o_n(1))cn$ where $\omega$ is sufficiently large. Following recent interest in the corresponding parameter mex$(m,H,F)$ where where we fix the number of edges $m$ instead of the number of vertices $n$ of the graph, we determine the asymptotics of mex$(m,H,\{K_{1,1,\Delta +1},K_{\omega +1}\})$ when $H$ has at least two dominating vertices. We obtain these results via a uniform proof of a common technical generalization of both, where we fix the number of $u$-cliques in the graph. This general result may be of independent interest. Then we localize these results, proving a tight inequality involving the sizes of the locally largest cliques and complete split graphs.

16 pages