具有较小有界匹配数的K3?4图的确切Turán数

《Discrete Applied Mathematics》：The exact Turán number of K3?4 with small bounded matching number

　　摘要：我们研究了避免特定3-图??和大小为??+1的匹配??3??+1的3-图的Turán数。用??3?4表示顶点集为[4]、边集为{123,124,234}的3-图。Chen等人（2025年）确定了当??≥3且??足够大时，ex?(??,{??3?4,??3??+1})的渐近值。在本文中，我们对于所有??≥400的情况，确定了ex?(??,{??3?4,??3??+1})的确切值。

引言：组合数学中的Turán类型极值问题起源于20世纪40年代Turán的工作，旨在确定Turán数ex?(??,??)——即在??个顶点上不存在固定子图??的??-图的最大大小。??的Turán密度定义为???(??)?lim??→∞?ex?(??,??)/(????)。这一极限的存在性是基于Katona–Nemetz–Simonovits [1]的平均论证，该论证表明ex?(??,??)/(????)随??的增加而非递减。对于图（??=2），当禁止的子图??是非二分图时，Turán数已经得到了很好的理解。然而，对于超图（??≥3），即使是针对特定家族的结果也很稀缺；参见Keevash的综述[2]。

让??????+1表示大小为??+1的匹配，即由??+1条独立边组成的??-图，让????+1表示有??+1个顶点的完全图。Turán图???(??,??)是指在[??]上的完全??-图，其各部分的大小相差不超过1；根据Turán定理，它是（在同构意义下）在??个顶点上唯一的不存在????+1的极端图。Erd?s和Gallai [3]确定了图的路径和匹配的Turán数。对于一般的??，Erd?s [4]给出了当??足够大时匹配的Turán数。最近，Alon和Frankl [5]开始研究具有有界匹配数的图的Turán问题。具体来说，他们确定了当??是一个团时，或者当??是任意色临界图且??足够大时，ex?(??,{????+1,??})的确切值。

定理1.1 [5]：对于??≥2??+1和??≥2，有ex?(??,{??2??+1,????+1})=max?{???(???(2??+1,??}}, ???(???(??,??,??)}，其中???(??,??)是在??个顶点上的Turán图（即几乎平衡的完全??-图），???(??,??,??)是在??个顶点上的完全??-图，其中一个部分的大小为?????，其他部分的大小为??????1?或??????1?。

随后，Gerbner [6]推广了这一结果，表明如果图??的色数至少为3（即???(??)≥3）且??足够大，那么ex?(??,{????+1,??})=ex?(??,???(??))+??(?????)，其中???(??)是通过从??中删除一个独立集得到的图族。

超图的Turán问题比它们的图对应问题要复杂得多。对于??≥3，Gerbner、Tompkins和Zhou [7]研究了所有色数???(??)≥3的??-图??的ex?(??,{??,??????+1})。然而，当???(??)=2时，这个问题变得明显更加困难。他们为这种情况建立了ex?(??,{??,??????+1})的一般上下界，并且只解决了少数特殊情况。较早之前，J. Wang、W. Wang和W. Yang [8]确定了当??是一个团时，或当??是任意色临界图且??足够大时，ex?(??,{??5,??3??+1})的确切值。这里??5=([5],{123,124,345})。

完整的星形图????是指在??+1个顶点上的3-图，其中包含一个中心顶点??0和其他??个顶点，边集包括所有包含??0的三元组。3-图??3?4是通过从完全3-图??34中移除一条边得到的。注意到??3与??3?4是同构的。关于????的Turán数的已知结果很少。实际上，已知最好的下界构造来自于daisy超图[9]。最近，N. Chen、M. Liu、Y. Qi和C. Yang [10]确定了ex?(??,{????,??3??+1})的渐近值。

定理1.2 [10]：对于每个??≥1、??≥3和足够大的??，有ex?(??,{????,??3??+1})=??????(?????,???1)+???(??)。特别地，对于??=3、??=1,2和??≥150的情况，有ex?(??,{??3?4,??3??+1})=?{ {?{ {?2?(???2)24?+1，如果??=2且??为奇数，否则为???(?????)24?}。

基于这些结果，并受到??3?4情况的启发，我们确定了ex?(??,{??3?4,??34})的确切值。

定理1.3：对于??≥400，有ex?(??,{??3?4,??34})=3?(???3)24?+3?(?? mod 2)。

本文的其余部分结构如下：第2节我们介绍必要的符号和初步的引理。第3节我们给出定理1.3的证明。

初步部分：我们首先介绍一些必要的符号。对于一个正整数??，定义[??]={1,2,…,??}。设??是一个3-图，其顶点集为???(??)，边集为???(??)。我们用???(??)表示??中的边数，用|??|表示??中的顶点数。给定一个顶点集??????(??)，用???[??]表示由??诱导的??的子图。如果??不包含??中的任何边，我们称??为??的一个弱独立集。对于???(??)中的顶点??，定义?????(??,??)={??????∈(??2):????????∈???(??)}和?????(??,??)=|?????(??,??)|。这里的?????(??,??)被称为链接图。

证明定理1.3：在本节中，我们证明定理1.3。以下构造提供了下界。在本文的所有图中，红色、蓝色和橙色边分别属于红色、蓝色和橙色顶点的链接图。粗色的边表示完全二分连接：两个集合对应部分之间的所有顶点对都通过该颜色的边相连。

设???(??)是从完全的3部分3-图??=({1,2},??1,??2)得到的3-图（见图3.1）。