超图中完全多部子图的禁止问题：Zarankiewicz数的指数阈值改进

《Combinatorics, Probability and Computing》：Hypergraphs without complete partite subgraphs

本文聚焦于极值图论中的Zarankiewicz问题，针对r部r-一致超图K(s1,…,sr-1,t)的禁止问题，研究者Dhruv Mubayi通过引入Behrend构造（无三项等差数列集）的新方法，显著改进了完全多部子图存在性的阈值条件。研究证明当t > 3s+o(s)时（其中s=∏si），Zarankiewicz数zr(n,K)达到nr-1/s-o(1)的渐进下界，将此前Pohoata和Zakharov提出的阶乘阈值((r-1)(s-1))!优化为指数阈值，并在小参数情形（如K(2,2,7)）中实现了指数最优性。该成果推动了极值超图理论的发展，对组合数学、计算机科学等领域具有重要理论意义。

　　

在组合数学的广阔天地里，极值图论始终扮演着探路者的角色，它致力于探索在各种限制条件下，图或超图结构所能达到的“最大”或“最小”规模。其中，一个历经数十年而魅力不减的核心问题便是：在一个庞大的图或超图中，最多可以容纳多少条边，才能确保它不包含某个特定的、我们不希望出现的子结构？这个问题犹如在拥挤的派对中安排宾客，既要保证交流充分（边数尽可能多），又要避免某些特定的“小团体”（禁止的子图）形成。当我们将场景从普通的图（边由两个点构成）推广到超图（边可以由多个点构成）时，问题的复杂度和挑战性呈指数级增长，但其在理论计算机科学、编码理论、离散几何等领域的应用前景也更为诱人。

具体到超图领域，有两个孪生问题备受关注：Turán问题和Zarankiewicz问题。前者关心在任意n顶点超图中避免特定子图的最大边数；后者则限制在顶点集被预先划分为若干部分的“多部”超图中，要求禁止的子图必须恰好从每个部分取点。Zarankiewicz问题可以看作是Turán问题在多部设置下的精细化版本，其研究往往能反过来推动一般情形的进展。早在1964年，数学大师Paul Erd?s就给出了一个普遍的上界：对于完全r部r-一致超图K(s₁,…,s_r)（其中s₁≤…≤s_r），其禁止问题的边数上界为O(n^r-1/s)，这里s = s₁s₂?s_r-1。一个自然且根本性的疑问随之而来：这个上界是否是最优的？即，是否存在超图构造，其边数能够达到这个上界的数量级（在指数意义上）？

寻找匹配上界的构造（即下界证明）是极值组合学中的重大挑战。对于图的情形（r=2），经过Erd?s–Rényi、Brown等人数十年的努力，对K(2,t)和K(3,t)等得到了最优下界。对于一般的K(s₁, s₂)，Kollár–Rónyai–Szabó以及Alon–Rónyai–Szabó的开创性工作证明了最优下界的存在，但要求第二部分的大小s₂大于一个阶乘函数(s₁-1)!。近年来，Bukh将这一阈值大幅改进至s₂> 9^s₁+o(s₁)。当r≥3进入超图领域后，问题变得异常棘手。早期的突破来自于Mubayi本人对K(2,2,3)以及Katz-Krop-Maggioni对K(2,2,2)的构造。随后，Ma, Yuan, Zhang以及Verstra?te等人通过扩展Bukh的方法，在理论上证明了匹配Erd?s上界的下界存在，但其证明中最后一个部分s_r所需满足的阈值条件非常巨大且未明确计算。直到最近，Pohoata和Zakharov才明确证明，当s_r> ((r-1)(s-1))!时，下界n^r-1/s成立。然而，这个阶乘级别的阈值距离理想的常数或指数级别阈值相去甚远，特别是在s较大的情况下，该条件几乎无法满足，限制了结果的应用范围。因此，能否将这一阈值从阶乘降低到指数级别，成为该领域一个亟待解决的关键问题。

正是在这样的背景下，伊利诺伊大学芝加哥分校的Dhruv Mubayi教授在《Combinatorics, Probability and Computing》上发表了题为“Hypergraphs without complete partite subgraphs”的研究论文。该研究引入了一种新颖而强大的方法，成功地将Zarankiewicz问题中完全多部子图存在的阈值条件从阶乘级别((r-1)(s-1))!显著优化至指数级别3^s+o(s)，实现了该问题的重大突破。这一改进不仅具有理论上的优美性，而且使得最优下界在许多实际相关的小参数情形中得以实现，例如，它直接给出了K(2,2,7)的紧下界n^11/4-o(1)，而此前的最佳结果需要将7替换为巨大的721。

本研究的关键技术方法核心在于创造性地将低维组合结构进行“提升”以构造高维禁示超图。主要步骤包括：1. 归纳框架：建立Zarankiewicz数z_r(n,K)与z_r-1(n,K‘)之间的递归关系，通过将r部超图的构造问题转化为r-1部超图的构造问题。2. Behrend型图应用：利用基于Behrend无三项等差数列集构造的二分图，该图具有n^2-o(1)条边，且其边集可划分为n个诱导匹配（induced matchings），这一性质是保证最终构造中不出现禁止子图的核心。3. 超图膨胀构造：将低维超图H‘的边中的特定顶点，用上述二分图中对应匹配的边对进行“替换”或“膨胀”，从而系统性地生成高维超图H的边，并利用诱导匹配的性质验证其避免目标完全多部子图。

2. Proof（证明）

本研究的主要结果体现在定理1及其推论2中。证明过程通过精心设计的超图构造来实现。

• •
  核心构造：研究者首先选取一个避免较小完全多部子图K‘ = K(s₁,…, s_r-3, s_r-2s_r-1, t)的(r-1)-部(r-1)-一致超图H‘。然后，利用一个特殊的二分图G，其边集由n个诱导匹配M₁, …, M_n构成，且总边数为n^2-o(1)。关键的创新步骤是构建一个新的r-部r-一致超图H：对于H‘中每一个包含顶点j ∈ [n]的边，将其中的顶点j替换为图G中匹配M_j的所有边所对应的顶点对(a,b) ∈ A×B，从而生成H的一条边。通过这种“边膨胀”操作，H的边数e(H)被证明至少为n^1-o(1)e(H‘)。
• •
  禁止子图论证：证明的关键在于说明如此构造的H不包含目标禁止子图K = K(s₁,…, s_r-1, t)。论证采用反证法。假设H中包含一个拷贝L，其最后两个部分（大小分别为s_r-2和s_r-1）位于集合A和B中。由于L是完全多部的，其位于A和B中的顶点之间必须形成所有可能的s_r-2s_r-1条“边”（在H的语境下，是构成r-边所需的顶点对）。研究通过分析发现，这些顶点对必须来源于G中完全不同的匹配M_j。这是因为G的匹配是诱导的，同一个匹配中不能提供L所需的所有“交叉边”。这意味着有s_r-2s_r-1个不同的索引j被涉及，而这些j恰恰对应于H‘中的s_r-2s_r-1个顶点，它们在H‘中与L的其他部分一起，恰好构成了一个禁止的K‘的拷贝，这与H‘的定义矛盾。
• •
  下界推导：通过递归应用定理1，可以将z_r(n,K)的下界估计问题最终转化为z₂(n, K(s, t))的估计问题，即二分图的情形。结合Bukh关于二分图中禁止K(s,t)子图的最新结果（当t > 3^s+o(s)时，z₂(n, K(s, t)) = Ω(n^2-1/s)），最终推导出本文的主要结论（推论2）：当t > 3^s+o(s)时，z_r(n, K(s₁,…, s_r-1, t)) = n^r-1/s-o(1)。

Remarks（评论）

在论文的讨论部分，作者指出了本研究的几个重要方面和未来方向。首先，当前的方法主要适用于Zarankiewicz问题（多部设置），而能否将其推广到一般的Turán问题（任意超图）是一个重要的未解难题，这将是未来研究的一个有价值的方向。其次，作者提到，这种利用低维结构构造高维禁示超图的方法可能具有更广泛的适用性，或许可以应用于其他类型的多部超图禁示问题，从而催生更多的新结果。最后，作者对证明中所需的图性质进行了反思，指出虽然论文中使用了“诱导匹配”这一较强条件，但实际上一个稍弱的条件（任何两个同属一个匹配的边ab和a‘b’，其交叉边ab‘或a’b不能同时出现在任何其他匹配中）可能就已足够，但作者也指出，这种弱化似乎无助于改进证明中的n^o(1)误差项。

综上所述，Dhruv Mubayi的这项研究通过引入Behrend构造和创新的超图提升技术，在极值超图理论的经典难题上取得了显著进展。它将完全多部子图Zarankiewicz数最优下界成立的阈值条件从难以处理的阶乘级别大幅降低到指数级别，这不仅在理论上是一个质的飞跃，而且使得最优结果对于更广泛、更实际的重要参数情形成为可能。这项工作深化了人们对超图极值行为的理解，展示了经典数论构造（如Behrend集）在现代组合学中的强大应用，为后续研究提供了新的思路和工具。