Zarankiewicz 问题

全一 $s\times t$ 子矩阵表示 $s$ 个左侧对象共同连接到同一组 $t$ 个右侧对象。要放入许多 $1$ 又避免这种共同邻域，不能只控制每行或每列的总和，还要让不同行的 $1$ 尽量少地反复重叠。问题的核心因而是“高密度”与“低共邻重复”之间的张力。

这也解释了它与一般非二分极值问题的差异。完全二分禁图的色数只有二，Turán 密度为零；答案的有效信息藏在次二次幂次和常数中。几何中的点—线关联、集合族的交模式和通信矩阵中的禁矩形都直接产生同一零一矩阵问题。

考虑 $z(3,3;2,2)$。矩阵

有 $6$ 个 $1$，任意两行只在一列同时为 $1$，所以没有 $2\times 2$ 全一子矩阵；对应二分图是一条六圈。现在证明不能放入 $7$ 个 $1$：七个 $1$ 分到三列后，列和至少可写成 $3,2,2$ 或更不均衡，故同列中行对的总出现次数至少

三行只有 $(\genfrac{}{}{0ex}{}{3}{2})=3$ 对，鸽巢原理迫使某对行在至少两列同时为 $1$，形成禁用矩形。因此 $z(3,3;2,2)=6$。

参数 $s=1$ 或 $t=1$ 会退化成度数约束。例如禁止一个左点连接 $t$ 个右点时，每个左点度至多 $t-1$，答案立即线性；经典研究通常假设 $s,t\ge 2$。若 $s>m$ 或 $t>n$，禁图根本放不下，答案就是 $mn$。

普通极值数 $\mathrm{ex}(N,K_{s,t})$ 不预先指定二分划分，Zarankiewicz 函数则固定两侧并带方向。通过取二分子图和把二分图视为普通图，可在适当对称参数下互相给出常数因子界，但二者不是逐参数相等的记号。尤其在 $m$ 与 $n$ 高度不平衡时，保留两变量比把总顶点数压成 $N=m+n$ 更有信息。

Kővári–Sós–Turán 定理公理库Kővári–Sós–Turán 定理Kővári–Sós–Turán theorem · KST theorem · 科瓦里–索什–图兰定理通过共同邻域的凸性计数，为不含固定完全二分子图的图给出次二次边数上界。通过数共同邻域给出 $z(m,n;s,t)$ 的通用上界；有限几何的关联图则在若干参数上提供匹配或近匹配下界。$K_{2,2}$-free 情形等价于二分图无四圈，也是配置几何与纠错码中反复出现的模型。

在理论计算机科学中，零一通信矩阵里的大全一矩形对应一组输入对共享同一输出行为；禁矩形界可转化为电路、数据结构和显式图构造的限制。依赖随机选择公理库依赖随机选择Dependent random choice · DRC · 依赖随机选取随机抽取一组顶点并取其公共邻域，从平均稠密性中提炼出对所有小子集都成立的共邻结构。则反向利用高密度必然产生大共同邻域，帮助嵌入更一般的稀疏二分图。应用时仍需核对它保证的是哪一侧的共同邻域以及参数是否固定。