文章背景与核心概要

扎兰基维奇问题（Zarankiewicz problem）是极端图论中的核心问题之一，旨在寻找包含特定完全二部子图（如 $K_{s,t}$）的最大边数。长期以来，确定特定参数下的精确扎兰基维奇数（Zarankiewicz numbers）因计算复杂度和状态空间爆炸而极具挑战。

本文由 Koyar Afrasyab 撰写，聚焦于 $K_{3,3}$ 配置，通过创新的“证书驱动”（certificate-based）计算机辅助证明方法，成功计算出了多个有限切片和前沿区域的精确值与严格界限。该研究的亮点在于结合了浮点优化（仅用于发现证书）与精确的有理数/整数算术验证（确保结果的绝对严谨性），为图论中的极值问题开辟了高可靠性的计算新路径。

两个有限前沿切片上的扎兰基维奇精确值

作者： Koyar Afrasyab
主要学科： 组合数学 (math.CO)
arXiv ID： 2608.08154
提交时间： 2026年8月8日
代码仓库： GitHub - KAVentures/z1322-exact

Author: Koyar Afrasyab
Primary Subject: Combinatorics (math.CO)
arXiv ID: 2608.08154
Submitted: August 8, 2026
Repository: GitHub - KAVentures/z1322-exact

📌 摘要

本文研究了扎兰基维奇数 $Z(m, n, s, t)$，其定义为阶数分别为 $m$ 和 $n$ 且不包含同构于 $K_{s,t}$ 的子图的二部图中的最大边数。

📌 Summary

The paper investigates the Zarankiewicz number $Z(m, n, s, t)$, defined as the maximum number of edges in a bipartite graph with parts of orders $m$ and $n$ that contains no subgraph isomorphic to $K_{s,t}$.

通过采用组合式的、基于证书的计算机辅助证明方法，作者针对 $K_{3,3}$ 配置，在多个有限切片和前沿区域上确立了精确值与严格的界限。该方法仅依赖浮点优化来发现证书，而所有最终的断言均通过标准库的 Python 工具利用精确的整数和有理数算术进行独立验证。

Using a combined, certificate-based computer-assisted proof approach, the author establishes exact values and rigorous bounds across multiple finite slices and frontier regions for $K_{3,3}$ configurations. The methodology relies on floating-point optimization solely for discovering certificates, while all final claims are independently verified using exact integer and rational arithmetic via standard-library Python tools.

🔑 核心结果与贡献

有限切片的广义公式： $$Z(12, n, 3, 3) = 6n \quad \text{当 } 18 \le n \le 22 \text{ 时}$$
特定切片的精确边数：
$Z(13, 22, 3, 3) = 137$
$Z(13, 18, 3, 3) = 116$
$Z(14, 18, 3, 3) = 124$
$Z(15, 18, 3, 3) = 132$
$Z(14, 17, 3, 3) = 118$
$Z(15, 17, 3, 3) = 126$
严格的区间界限：
$132 \le Z(16, 17, 3, 3) \le 133$（由于仅对 132 边的下界见证以及已发表的 133 上界进行了形式化认证，故以区间形式报告）。

🔑 Key Results & Contributions

Generalized Formula for Finite Slices: $$Z(12, n, 3, 3) = 6n \quad \text{for } 18 \le n \le 22$$

Exact Edge Counts for Specific Slices:

$Z(13, 22, 3, 3) = 137$

$Z(13, 18, 3, 3) = 116$

$Z(14, 18, 3, 3) = 124$

$Z(15, 18, 3, 3) = 132$

$Z(14, 17, 3, 3) = 118$

$Z(15, 17, 3, 3) = 126$

Rigorous Interval Bounds:

$132 \le Z(16, 17, 3, 3) \le 133$ (reported as an interval since only the 132-edge lower witness and the published 133 upper bound are formally certified).

🛠️ 方法论亮点

上界证书： 精确的 $12 \times 18$ 和 $13 \times 18$ 证书包确立了支撑性的上界。轨道证书（Orbit certificates）系统性地排除了在下一个边数下的所有假设矩阵。
单元闭包： 删除引理（Deletion lemmas）和显式见证成功封闭了前沿上的四个相邻单元。
针对 $13 \times 22$ 的简化策略：
将问题简化为 83 个不同的度数分布（degree profiles）。
有理数分离其中 77 个分布。
利用先进技术消除了其余六个分布，包括标记行同余（marked-row congruences）、剩余枚举（leave enumeration）、模 Gram 测试（modular Gram tests）以及精确的法卡斯证书（exact Farkas certificates）。

🛠️ Methodological Highlights

Upper Bound Certificates: Exact $12 \times 18$ and $13 \times 18$ certificate packages establish load-bearing upper bounds. Orbit certificates systematically exclude every hypothetical matrix at the next edge count.

Cell Closure: Deletion lemmas and explicit witnesses successfully close four neighboring cells on the frontier.

Reduction Strategy for $13 \times 22$:

Reduces the problem to 83 distinct degree profiles.

Rationally separates 77 of these profiles.

Eliminates the remaining six profiles using advanced techniques, including marked-row congruences, leave enumeration, modular Gram tests, and exact Farkas certificates.