🔢 数学

$K_{2, t+1}$ -free graphs containing an optimal number of $K_{t, t}$ 's

本文提供了一个显式构造，表明对于素数幂 $t$ 及特定的 $n$ ，在不含 $K_{2,t+1}$ 的图中， $K_{t,t}$ 副本的最大数量渐近为 $(1 + o(1))\frac{n^2}{2t(t-1)}$ ，从而在这些情形下确定了广义图兰数 $ex(n, K_{t, t}, K_{2, t+1})$ 的精确常数因子。

原作者： Vladislav Taranchuk

发布于 2026-06-03

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Vladislav Taranchuk

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在举办一场拥有 $n$ 名宾客的大型派对。你想以一种非常特定的方式来安排座位和互动，以最大化你能形成的“完美配对”数量，但你必须遵守一条严格的规则：不能有两个人拥有过多的共同朋友。

这篇论文旨在探讨在遵循该规则的前提下，你能创造出的“完美配对”的绝对极限是多少。

以下是这篇论文故事的拆解，已将其转化为日常语言：

游戏规则

宾客 ( $n$ )： 你拥有一大群人。
“完美配对” ( $K_{t,t}$ )： 用数学术语来说，这是一个群体，其中一边的 $t$ 个人与另一边的 $t$ 个人全都是朋友。可以把它想象成一个完美的舞池，两组各有 $t$ 名舞者，他们中的每一个人都与对方组中的所有人手牵手。
禁忌模式 ( $K_{2,t+1}$ )： 这是你必须避免的规则。你不能让两个人拥有超过 $t$ 个共同朋友。如果两个人有 $t+1$ 个共同朋友，派对就“毁了”（或者用数学术语来说，这个图是不合法的）。

核心问题： 在一个规模为 $n$ 的派对中，在不意外制造出“过多共同朋友”情况的前提下，你最多能构建多少个这样的“完美舞池” ( $K_{t,t}$ )?

我们以前知道什么

最近，其他数学家已经发现，答案的增长量大约与宾客数量的平方 ( $n^2$ ) 成正比。他们证明了这种可能性确实存在，但他们的方法就像一个魔术：他们使用复杂的几何学和概率论来表示，“嘿，这样一个派对可能存在”，却并没有实际向你展示宾客名单或座位表。

作者的新招数

Vladislav Taranchuk（作者）说：“我可以做得更好。我可以显式地构建这个派对。”

他不仅是在说派对存在，他还写下了谁应该坐在谁旁边的确切规则。然而，这里有一个限制：这个特定的座位表只有在宾客数量 ( $n$ ) 是特定类型（与质数和幂相关）时才能完美运作。

构造方法（“如何做”）：
想象宾客是分布在一个巨大的、多维网格上的点。

作者使用一种特殊的数学公式（多项式）来决定谁是朋友，谁不是。
规则： 如果两个人的坐标满足一个涉及该公式的特定方程，那么他们就是朋友。
结果：
- 如果你挑选任意两个人，他们将至多拥有 $t$ 个共同朋友。（因此，禁忌模式永远不会发生）。
- 由于该公式的设计方式，你最终会得到海量的那些“完美舞池” ( $K_{t,t}$ )。

重大发现

作者证明了，对于这些特定的派对规模，你可以创造的完美舞池数量几乎精确等于：
$\frac{n^2}{2t(t-1)}$

这是一个重大的突破，因为它与之前数学家们计算出的理论最大极限（“天花板”）相吻合。这就像是说：“我们曾以为最多能得 100 分，而现在我带来了一支真正能拿到 100 分的队伍。”

为什么这很重要（用通俗的话说）

从“也许”到“就在这里”： 之前的研究说：“一个完美的派对是可能的。”而这篇论文说：“这是构建完美派对的精确蓝图。”
效率： 作者展示了你不可能做得比这更好。你获得的完美配对数量已经达到了数学上可能的最高水平，仅差一点点微不足道的差距。
猜想： 作者相信这个公式实际上适用于所有派对规模，而不仅仅是他构建出的这些特殊规模。他认为他所发现的“天花板”才是所有人的真实极限。

类比总结

把这想象成建造一座桥梁。

之前的研究证明了通过抽象物理学，一座足以承受某种重量的桥梁可能存在。
这篇论文则使用具体的钢梁和螺栓建造了这座桥。它证明了对于特定的长度，这座桥在不坍塌的前提下，能承受最大重量。
作者很有信心，这种设计是所有长度的桥梁中最优的设计，尽管目前他只为特定的长度构建了证明。

简而言之： 作者找到了一个精确的、循序渐进的配方，用来创建一个连接网络，使其在不破坏“共同朋友过多”这一规则的前提下，尽可能地挤满“完美群体”。

技术摘要：包含最优数量 $K_{t,t}$ 的 $K_{2,t+1}$ -free 图

问题陈述
本文研究了广义 Turán 数，记作 $\text{ex}(n, H, F)$ ，它表示在具有 $n$ 个顶点的 $F$ -free 图中可以存在的 $H$ 的最大副本数。具体而言，作者研究了当 $H = K_{t,t}$ 且 $F = K_{2,t+1}$ 时的情形。目标是确定 $\text{ex}(n, K_{t,t}, K_{2,t+1})$ 的渐近行为。

虽然近期由 Pohoata, Tidor 和 Yu 完成的工作确立了对于所有整数 $t \ge 3$ ， $\text{ex}(n, K_{t,t}, K_{2,t+1}) = \Theta_t(n^2)$ ，但其证明依赖于概率方法和子空间规避集（subspace-evasive sets），导致得到的下界系数不一定是最优的。本文旨在通过一种显式构造，为特定的 $n$ 和 $t$ 值提供精确的渐近公式。

方法论
作者采用了基于有限域和线性化多项式的确定性代数构造法。

图构造 ( $\Gamma_{t,e}$ ):
- 令 $t$ 为素数幂， $e > 1$ 为整数。定义 $q = t^e$ 。
- 令 $L$ 为 $\mathbb{F}_q[x]$ 上的 $\mathbb{F}_t$ -线性化多项式，使得其核（kernel）的维数为 1。其像空间 $R_L$ 的大小为 $t^{e-1}$ 。
- 顶点集定义为 $V = \mathbb{F}_q \times R_L$ ，从而得到 $n = q \cdot t^{e-1} = t^{2e-1}$ 个顶点。
- 两个不同的顶点 $(v_1, v_2)$ 和 $(w_1, w_2)$ 相邻，当且仅当 $v_2 + w_2 = L(v_1 w_1)$ 。通过移除由该方程隐含的自环来确保这是一个简单图。
上界推导:
- 作者首先建立了一个精确的上界，用于描述 $\text{ex}(n, K_{t,t}, K_{2,t+1})$ 。
- 该论证依赖于这样一个事实：在任何 $K_{2,t+1}$ -free 图中，任意两个顶点最多共享 $t$ 个公共邻居。
- 通过计数顶点对并分析 $K_{t,t}$ 通过其组成对被计数的次数，他们推导出了该界限：
  $\text{ex}(n, K_{t,t}, K_{2,t+1}) \le \frac{\binom{n}{2}}{2\binom{t}{2}}$
构造的结构分析:
- $K_{2,t+1}$ -freeness: 作者证明了 $\Gamma_{t,e}$ 不包含 $K_{2,t+1}$ 。对于任意两个顶点，其公共邻居的数量由涉及 $L$ 的线性方程解的数量决定。由于 $L$ 是一个 $t$ -to-1 的映射，因此最多有 $t$ 个公共邻居。
- $K_{t,t}$ 的形成: 证明的核心在于分析非相邻顶点。作者表明，任何具有不同第一坐标的非相邻顶点都会唯一地定义两个集合 $M$ $M$ 和 $N$ $N$ ，其势（cardinality）均为 $t$ $t$ 。
  - $N$ 是公共邻居的集合（一个 $\mathbb{F}_t$ -直线）。
  - $M$ 是包含这两个顶点的 $\mathbb{F}_t$ -直线。
  - $M$ 中的每个顶点在代数意义上都与 $N$ 中的每个顶点相邻。
- 如果 $M \cap N = \emptyset$ ，则由 $M \cup N$ 诱导的子图是 $K_{t,t}$ 。如果 $|M \cap N| = 1$ ，则该结构形成一个三部完全图 $K_{1, t-1, t-1}$ 。

主要贡献与结果
主要贡献是构造了一个显式的图族，该图族在无限个 $n$ 的集合上达到了理论上 $K_{t,t}$ 副本数的上界（忽略低阶项）。

定理 1.1: 当 $t$ 为素数幂且 $n = t^{2e-1}$ （其中 $e > 1$ 是整数）时，广义 Turán 数满足：
$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$
与先前界的比较: 文中指出，来自 [5] 的先前最佳下界形式为 $(1-o(1)) \frac{n^2}{4t^2 t!}$ 。对于 $t > 5$ 的素数幂，新结果显著提高了该系数。
非最优情况的可忽略性: 作者证明了导致 $K_{1, t-1, t-1}$ 情况（即 $|M \cap N| = 1$ ）的配置数量（ $O(n)$ ）相对于 $K_{t,t}$ 总数（ $O(n^2)$ ）是可忽略的，从而确保了 $K_{t,t}$ 计数的渐近主导地位。

意义与主张
本文声称提供了一个“简单且完全显式的构造”，针对的是一个无限的、尽管是稀疏的 $n$ 集合，这与此前可用的概率存在性证明形成了对比。该构造与 Lazebnik 和 Mubayi 在多色 Ramsey 数背景下研究过的图是同构的，尽管本文将其专门应用于广义 Turán 问题。

作者得出结论并猜想，推导出的上界对于所有 $n$ 都是紧确的，而不仅仅是构造中所涉及的特定素数幂情况：
$\text{ex}(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) \frac{n^2}{2t(t-1)}$
这项工作旨在完善对二部图广义 Turán 数增长率的理解，使其从数量级估计转向特定机制下的精确渐近常数。