Kővári–Sós–Turán 定理

若图有很多边，右侧顶点平均会连接许多左侧点，于是每个右侧顶点贡献大量 $s$ 元邻点组。另一方面，固定的左侧 $s$ 元组最多被 $t-1$ 个右侧顶点共同连接，否则它与这 $t$ 个共邻点组成 $K_{s,t}$。同一批“中心在右、叶在左的 $s$ 星”既有由度数凸性给出的下界，又有禁图条件给出的上界；比较两边便限制总边数。

双重计数骨架 ​

若任一部为空，则边数为零，结论直接成立；下面取 $m,n\ge 1$。令 $d(y)=|N(y)|$。数所有满足 $S\subseteq N(y)$、$|S|=s$ 的二元组 $(S,y)$，得到

右端的 $t-1$ 正对应右侧允许的最大共同邻点数。令 $f_s(x)=0$（$0\le x\le s-1$），而 $f_s(x)=x(x-1)\cdots (x-s+1)/s!$（$x\ge s-1$）；这是非负实轴上的凸函数，在整数度数处等于 $(\genfrac{}{}{0ex}{}{x}{s})$。若平均度 $e(G)/n\ge s-1$，对全部度数以等权重应用Jensen 不等式理路Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。，得到

再用 $(\genfrac{}{}{0ex}{}{x}{s})\ge (x-s+1{)}^s/s!$ 与 $(\genfrac{}{}{0ex}{}{m}{s})\le m^s/s!$，整理即得定理。若平均度小于 $s-1$，线性误差项已直接覆盖。这个推导也固定了参数方向：求和遍历 $Y$，选择的是 $X$ 中的 $s$ 元组。

取 $s=t=2$。定理化为

当 $m=n=N$ 时得到 $N^{3/2}+N$。在 $3\times 3$ 情形，这个通式只给 $z\le 8.19\dots$，取整数为至多 $8$；直接保留二项式计数则能证明精确值是 $6$。因此 KST 是统一渐近上界，不承诺每个小参数上精确。

对 $K_{2,2}$，有限射影平面的点—线关联图给出同阶 $\mathrm{\Omega }(N^{3/2})$ 下界，说明指数 $3/2$ 正确。对一般固定 $s\le t$，$N^{2-1/s}$ 的匹配下界在若干范围和构造中成立，尤其当 $t$ 相对 $s$ 足够大；但不能据此声称所有 $s,t$ 的常数乃至数量级都已解决。许多具体 Zarankiewicz 问题仍是开放的。

当 $m,n$ 极不平衡时，线性误差项可能主导，且转置后的界可能更强。只背诵对称写法 $O(N^{2-1/s})$ 会抹去这种方向信息。定理也只排除普通子图；若要求诱导 $K_{s,t}$、有向矩形或带符号模式，星计数上界必须重新检查。

KST 定理证明所有固定完全二分禁图的极值数为 $o(N^2)$，并给出显式幂次，补足Erdős–Stone 定理理路Erdős–Stone 定理Erdős–Stone theorem · Erdős–Stone–Simonovits theorem · 厄多斯–斯通定理固定禁图的色数决定其极值数的二次主项，而不决定低阶误差与精确取等结构。在二分情形只给零密度的不足。对一般二分禁图，先把它嵌入足够大的 $K_{s,t}$ 也可得到某个次二次上界，尽管通常并不最优。

共同邻域计数广泛用于禁四圈图、关联几何、集合相交与数据库矩形问题。依赖随机选择理路依赖随机选择Dependent random choice · DRC · 依赖随机选取随机抽取一组顶点并取其公共邻域，从平均稠密性中提炼出对所有小子集都成立的共邻结构。保留了同一核心直觉，却不只数平均的 $s$ 元组：它从高平均度中抽取一个较大顶点集，使其中每个小子集都有许多共邻点，从而可以贪心嵌入结构更复杂的二分图。