Generalized Zykov's Theorem

Abstract

For a simple graph $G$, let $n$ denote its number of vertices, and let $N(G,K_t)$ denote the number of copies of $K_t$ in $G$. Zykov's theorem (1949) asserts that for any $K_{r+1}$-free graph and $t\ge 2$, \[ N(G,K_t) \le {r \choose t}\left(\frac{n}{r}\right)^t \] We generalize Zykov's bound within a vertex-based localization framework. For each vertex $v\in V(G)$, let $c(v)$ denote the order of the largest clique containing $v$. In this paper, we show that \[ N(G,K_t) \le n^{t-1} \sum_{v \in V(G)} \frac{1}{c(v)^t} {c(v) \choose t} \] We further show that equality holds if and only if $G$ is a regular complete multipartite graph. \newline Note that if we impose the condition that, $G$ is $K_{r+1}$-free, then $c(v)\le r$ for all $v\in V(G)$. Thus, plugging $c(v)=r$ for all $v\in V(G)$, we retrieve Zykov's bound.