图兰数（Turán number）与极值图理论：关于奇数棱柱（odd prism）的精确结果
贺小聪（Xiaocong He），李永涛（Yongtao Li），冯立华（Lihua Feng）等人近期在《离散数学》（Discrete Mathematics）期刊上发表了一项关于图论中极值问题的研究。贺小聪来自河北师范大学数学科学学院，而李永涛和冯立华则来自中南大学数学与统计学院。这篇题为《Extremal graphs for the odd prism》（奇数棱柱的极值图）的论文已于2024年9月在线发表，其正式刊出卷期为2025年的第348卷。该研究属于极值图论（Extremal Graph Theory）领域，旨在精确确定一类称为“奇数棱柱”的图在任意大顶点数下的图兰数，并完整刻画达到该最大边数的所谓“极值图”（extremal graphs）。研究动机源于图兰数理论的经典问题，特别是由Paul Turán本人提出的关于确定正多面体图图兰数的系列工作。该研究成功解决了奇数棱柱这一正多面体变体图的精确图兰数问题，不仅推广了相关结果，还揭示了其极值结构与另一种图（路径平方）之间的深刻联系。
学术背景与研究目标 图兰数是极值图论的核心概念之一。对于一个给定的图H，ex(n, H)定义为：在所有不包含H作为子图的n个顶点的图中，所能拥有的最大边数。这个问题起源于Turán的著名定理，它完全刻画了不包含完全图Kr+1的极值图，即完全r部图Tr(n)。此后，确定各类具体图H的精确图兰数ex(n, H)成为极具挑战性的研究方向。Turán本人曾提出研究由正多面体的顶点和边构成的图（如立方体、正十二面体、正二十面体等）的图兰数。Simonovits等人在这方面做出了一系列重要工作。本研究所关注的“奇数棱柱”，定义为奇数圈C_{2k+1}和一条边K2的笛卡尔积（Cartesian product）C{2k+1} ▢ K2，它可以被视为立方体图的一种变体。根据经典的Erdős–Stone–Simonovits定理，对于色数（chromatic number）为3的奇数棱柱，其图兰数的渐近值为(1 - 1/(3-1)) * (n^2⁄2) + o(n^2) = n^2⁄4 + o(n^2)。然而，该定理无法给出精确值。因此，本研究的首要目标就是“精炼”这个误差项，对于所有充分大的n，确定ex(n, C{2k+1} ▢ K_2)的精确表达式，并描述所有达到该边数的极值图的结构。其次，对于最小的情形——三角柱（triangular prism, 即k=1，C_3 ▢ K_2），研究团队希望克服“n充分大”的限制，确定其对于每一个n（而非仅充分大的n）的精确图兰数及所有极值图。
详细研究流程与分析方法 本研究并非实验科学，而是理论数学的证明工作。其“流程”体现为严密的逻辑推理和理论工具的应用，主要分为以下几个关键部分或步骤：
第一步：确定分解族（Decomposition Family）并建立下界。 研究的起点是应用Simonovits提出的“分解族”理论。对于目标图L（此处为奇数棱柱），其分解族M(L)是一类最小图的集合，将这些图嵌入到一个大的Turán图（即平衡完全二部图）的一个部分中，就会产生一个L。研究团队首先证明了核心引理：奇数棱柱的分解族M(C_{2k+1} ▢ K_2) = {P4}，即仅包含一条4个顶点的路径。这一结论至关重要。基于此，利用一个标准构造：在一个平衡完全二部图K{n_a, n_b}的较大一部分（大小为n_a）中，嵌入一个对P_4而言的极值图（即边数最多且不含P4的子图），所得到的图必然不包含奇数棱柱。这个构造给出了图兰数的一个明确下界：ex(n, C{2k+1} ▢ K2) ≥ max{n_a+n_b=n} { n_a * n_b + ex(n_a, P_4) }。因此，问题转化为证明这个下界同时也是上界。
第二步：应用Simonovits结构定理进行初步结构分析。 为了刻画极值图的结构，研究团队运用了Simonovits的一个深刻定理。该定理指出，如果一个图的分解族包含线性森林（各连通分支均为路径的图），那么对于充分大的n，其极值图具有高度对称和简单的结构。由于已证M(C_{2k+1} ▢ K_2) = {P_4}，而P_4是线性森林，满足定理条件。应用该定理后可知，在删除有限个（常数个）顶点后，剩余的极值图G‘可以写成两个图的“张量积”（join）形式：G‘ = G_1 ⊗ G_2，这意味着G_1的每个顶点都与G_2的所有顶点相连。此外，|V(G_i)| ≈ n/2，且每个G_i由若干大小有界的连通分支组成，这些分支在G中对称。
第三步：结合稳定性论证与具体图性质进行精细化分析。 在获得上述大体结构后，研究进入了更精细的论证。主要利用了以下工具和逻辑： 1. 利用图的度条件： 作为极值图，其最小度δ(G)必须接近(1 - 1/χ)n = n/2（由Erdős–Simonovits的稳定性引理保证）。这个条件帮助控制了顶点集之间的边密度。 2. 分析G_1和G_2的内部结构： 基于引理3.2（关于笛卡尔积图中如何产生奇数棱柱的条件），论证了G_1和G_2不可能同时包含边。因此可以假设G_2是独立集（无边图）。再结合分解族的定义，可以证明G_1本身必须是P_4-自由的。 3. 运用路径图兰数的稳定性结果： 由于G_1是P_4-自由的且边数接近ex(|G_1|, P_4)，可以应用Yuan（2022）关于P4-自由图稳定性的引理。该引理指出，这样的图要么包含许多（数量级为n）个互不相交的三角形，要么包含一个很大的星图K{1, ℓ}。研究对这两种情况分别进行讨论。 4. 分情况讨论并完成上界证明： * 情况1：G_1包含许多不相交的三角形。 在这种情况下，可以进一步论证G_2必须完全是独立集（不能有任何边）。否则，利用G_1中的三角形和G_2中的边，结合它们之间几乎完全的二分连接，可以构造出奇数棱柱，导致矛盾。一旦G_2是独立集，整个图G的边数就是两部分之间的边数加上G_1内部的边数，即e(G) = n_1*n_2 + e(G_1)。由于G_1是P_4-自由的，e(G_1) ≤ ex(n_1, P_4)。因此，e(G) ≤ n_1*n_2 + ex(n_1, P_4)。结合第一步的下界，这正好就是所需的精确值。 * 情况2：G1包含一个很大的星图K{1, ℓ}。 设中心顶点为u。详细分析u在G_1和G_2中的邻居集合，利用引理3.2(a)以及避免出现P_4的条件，可以证明与u相邻的大部分顶点在各自部分中几乎不参与其他边。通过对边数的精心上界估计，最终也能导出e(G) ≤ n_1*n_2 + ex(n_1, P4)的结论。 5. 刻画极值图结构： 在证明上界的过程中，同时分析了等号成立的条件。这导致了对极值图结构的完整描述：任何一个极值图都同构于这样一个图——取一个完全二部图K{n_a, n_b}，然后在大小为n_a的那个部分中，嵌入一个在n_a个顶点上、边数最多的P_4-自由图（即P_4的极值图）。而P_4的极值图本身已有完全的分类（由Erdős–Gallai, Faudree–Schelp, Kopylov等人的结果可知，主要是由三角形和星图组成的特定结构）。
第四步：专门处理三角柱（k=1）的小n情形。 对于三角柱C_3 ▢ K_2，研究团队采用了不同的、更精细的组合分析方法，目标是消除“n充分大”的条件。主要流程如下： 1. 建立与P_6^2图的联系： 他们注意到，三角柱的图兰数下界可以通过一类已知的极值图（由Xiao等人确定的关于六顶点路径的平方图P_6^2的极值图）来达到。令人惊讶的是，初步分析显示ex(n, C_3 ▢ K_2)的下界与ex(n, P_6^2)的已知值完全相同。 2. 对包含P_6^2子图的C_3▢ K_2-自由图进行详尽分析： 为了证明上界，考虑一个不含三角柱的n顶点图G。如果G不包含P_6^2，那么直接套用Xiao等人关于ex(n, P_6^2)的上界即可。难点在于处理G包含P_6^2的情况。研究团队通过一系列细致的引理（引理4.3-4.6），分析了在P_6^2之外添加的顶点与这个固定P_6^2子图之间的连接可能性。他们分类讨论了外部顶点与P_6^2有4条、3条或更少连边的情况，并排除了许多会导致三角柱出现的配置。 3. 运用数学归纳法： 以n=6和n=11作为归纳基础（n=5是例外，其图兰数为10，大于通项公式给出的9，因此公式对n≠5成立），假设结论对更小的n成立，来推导对n的结论。在归纳步骤中，他们利用“图中包含一个P_6^2”的假设，结合之前引理得到的结构限制，对图的边数进行逐项估计。通过复杂的计数和归纳假设的应用，最终证明了对于所有n≥6且n≠5，都有e(G) ≤ ex(n, P_6^2)，并且等号成立时，极值图就是Xiao等人给出的那些图，以及三个小的例外图G1, G2, G3（当n=6,7,8时）。
主要研究结果 1. 对于一般奇数棱柱（k≥1，n充分大）： * 得到了精确的图兰数公式： ex(n, C_{2k+1} ▢ K2) = max{n_a+n_b=n} { n_a * n_b + ex(n_a, P_4) }。 其中ex(n_a, P_4)有明确的表达式（见推论2.3），取决于na模3的余数。 * 完整刻画了极值图：所有极值图都是由一个完全二部图K{n_a, n_b}，在其大小为n_a的那一部分中嵌入一个P_4-自由极值图而构成。
研究结论与价值 本研究成功解决了奇数棱柱的精确图兰数问题，并完全描述了其极值图。主要结论是：奇数棱柱的极值图具有一种“二分加内部结构”的简单模式，即一个完全二部图加上其中一个部分内部的特定P_4-自由图。对于三角柱，该结论对所有n成立，并且其极值图与另一个看似不同的图（P_6^2）的极值图惊人地一致。
这项研究的科学价值体现在以下几个方面： 1. 推进了正多面体图兰数问题： 继承并推进了由Turán和Simonovits开创的关于正多面体图极值问题的研究纲领，为这一经典系列增添了关于棱柱这一重要图类的完整答案。 2. 展示了分解族理论的威力： 研究是应用Simonovits分解族理论及相应结构定理的典范。它表明，一旦确定了分解族是简单的线性森林（如P_4），极值图的结构就可以被完全确定。这为处理具有类似分解族的其他图类提供了范例。 3. 揭示了图类间的深刻联系： 在三角柱的特例中，发现其图兰数与极值图竟然与路径平方图P_6^2完全相同。这一现象并非显然，它提示我们，有时两个结构迥异的图可能共享相同的极值函数和极值图族，而这很可能源于它们拥有相同的分解族（本研究指出二者确实都有M = {P_4}）。这加深了我们对不同图类在极值意义下内在联系的理解。 4. 提供了方法论上的贡献： 对于一般k的大n证明，综合运用了分解族、稳定性方法、最小度条件以及针对P_4-自由图的精细分析。对于k=1的小n证明，则展示了如何通过结合已知结果（关于P_6^2的图兰数）、细致的结构分析（分析包含特定子图时的约束）以及巧妙的归纳论证，来克服“充分大n”的限制，获得所有n的完整结果。这两种方法具有借鉴意义。
研究亮点 1. 重要发现： 确定了奇数棱柱图兰数的精确闭形表达式，并给出了极值图的清晰构造性描述。 2. 新颖性与特殊性： * 将Simonovits的深刻结构定理成功应用于一类具体的笛卡尔积图，并完成了从渐近到精确的关键跨越。 * 发现了三角柱与路径平方图P_6^2在极值性质上的完全等价性，这是一个有趣且不平凡的发现。 * 对于三角柱，实现了“对所有n”的完全分类，这比常见的“对充分大n”的结果更强，在极值图论中此类完全结果相对稀少。 3. 研究对象的特殊性： 所研究的奇数棱柱是图论中一个非常自然且结构对称的图类，既是正则多面体的变体，又是奇数圈与边的笛卡尔积，具有多重背景意义。
其他有价值的内容 论文在引言部分详细综述了图兰数问题的发展脉络，包括从Mantel、Turán的奠基性工作，到Erdős–Stone–Simmonovits定理，再到近年来关于各类具体图（如花图、轮图、路径幂等）的精确结果，为读者提供了良好的学术背景。此外，论文在最后提出了开放性问题，例如能否确定立方体Q_8图兰数的下界，以及能否将本结果推广到更一般的笛卡尔积图类（如偶圈与边的积），这为后续研究指明了方向。