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 \geq 2$, \[ N(G,K_t) \leq \binom{r}{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$. Then \[ N(G,K_t) \leq n^{t-1} \sum_{v \in V(G)} \frac{1}{c(v)^t}\binom{c(v)}{t}. \] Moreover, when $G$ contains a copy of $K_t$, equality holds if and only if $G$ is a regular complete multipartite graph. Note that if we impose the condition that $G$ is $K_{r+1}$-free, then $c(v) \leq r$ for all $v \in V(G)$, and the monotonicity of $s \mapsto \binom{s}{t}/s^t$ gives Zykov's bound.
From: Rajat Adak [view email]
[v1]
Tue, 2 Dec 2025 17:35:32 UTC (12 KB)
[v2]
Wed, 3 Dec 2025 17:25:42 UTC (12 KB)
[v3]
Sun, 13 Sep 2026 10:56:17 UTC (11 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。