论可遗传族的 r-横截 t-相交子族

《Discrete Mathematics》：On r-cross t-intersecting subfamilies of hereditary families

　　

**摘要**

我们研究了关于遗传族的 r-交叉 t-相交子族的度量最大和的极值问题。具体而言，给定族 ?1,…,??? ?2[??]，其中 ?? ≥?? ≥2，若对任意选取的 r 个不同元素 ??1,…,???? ∈[??] 以及任意集合 ????1 ∈???1,…,?????? ∈?????，它们的交集满足 |????1∩?∩??????| ≥??，则称它们是 r-交叉 t-相交的。近年来，??= 2 和 ??= ?? 的情形已得到广泛研究。若族 ? ?2[??] 在取子集下封闭，则称其为遗传族。在本文中，我们建立了遗传族的 r-交叉 t-相交（均匀或非均匀）子族度量之和的紧上界，从而在某些约束条件下验证了 Borg 的两个猜想。此外，我们的结果统一并推广了 Gupta 等人以及 Liu 关于 2[??] 和 ([??]≤????) 子族的两项关键结果。进而，我们推得了 r-交叉 t-相交分离族大小之和的最优界，其特殊情形 ??= ??= 2 给出了 Liu 的主要结果。

**引言**

设 ?? ≥0 和 ?? ≥1 为整数。记 [??] 为集合 {1,2,…,??}，[??,??] 为 {??,??+1,…,??}。记 2[??] 为 [??] 的所有子族的族。记 ([??]??)= {???[??],|??|=??} 和 ([??]≤??)= ?????=0([??]??)。对于族 ? ?2[??]，我们定义 ?(??)= {??∈?,|??|=??}。

若 ? ?([??]??)，则称族 ? ?2[??] 为 k-均匀的，否则称为非均匀的。若对任意 ??,??′ ∈? 满足 |?? ∩??′| ≥??，则称族 ? ?2[??] 为 t-相交的。通常，我们将 1-相交简称为相交。相交族及其极值性质的研究是组合学的一块基石。该领域的核心支柱之一是 Erd?s–Ko–Rado 定理 [9]，该定理建立了当 ?? ≥2?? 时相交族 ? ?([??]??) 的最大规模为 (???1???1)。这一开创性结果，以及 Frankl [12] 和 Wilson [30]、Ahlswede 和 Khachatrian [2] 将其推广到 t-相交族的工作，激发了对相交集合系统的结构性质和定量性质的大量研究。

这些经典结果的自然扩展在于研究多个族。称族 ?1,…,??? ?2[??]（?? ≥2）为 s-交叉 t-相交的，若对任意 ??1 ∈?1,…,???? ∈???，有 |???∈[??]????| ≥??；当 ??= 2 时简称为交叉 t-相交；若进一步要求 ??= 1，则称为交叉相交。此外，称 ?1,…,??? ?2[??]（?? ≥2）为成对交叉 t-相交的，若对任意 1 ≤??< ?? ≤??，??? 和 ??? 交叉 t-相交；当 ??= 1 时简称为成对交叉相交。

均匀族交叉交集的研究可追溯至 Hilton 和 Milner [23] 的结果，他们证明了若 ?,?? ?([??]??) 是非空交叉相交的且 ?? ≥2??，则 |?|+ |??| ≤(????)? (???????)+ 1。Frankl 和 Tokushige [14] 将 Hilton–Milner 的结果推广到成员阶数不同的两个均匀族。更一般地，Wang 和 Zhang [29] 确定了非空交叉 t-相交族 ? ?([??]??) 和 ?? ?([??]?) 的大小之和的最大值，Frankl 和 Kupavskii [17] 独立地获得了相同均匀族的结果。Frankl [13] 还给出了 Hilton–Milner 不等式的另一种推广。Wu、Feng 和 Li [31] 进一步推广了该结果，他们称之为半捆绑交叉相交族。对于多个交叉相交族，Shi、Frankl 和 Qian [28] 给出了 ([??]??) 的非空成对交叉相交子族大小之和最大值的紧上界，这可以看作是对 Hilton 和 Milner 结果的另一种推广。他们还提出了一些关于成对交叉 t-相交均匀族大小之和最大值的问题。更多关于此类结果的信息可参见 [24]、[25]、[27]。与均匀情形相比，非均匀交叉相交族的研究要复杂得多。Frankl 和 Wong [18] 最近的工作建立了 2[??] 的非空交叉 t-相交子族大小之和的最大值。Borg 和 Feghali [7] 解决了非空交叉相交族 ? ?([??]≤??) 和 ?? ?([??]≤?) 的最大和问题。Gupta 等人 [22] 通过优雅的必要交点方法获得了一些更一般的结果，考虑了 2[??] 和 ([??]????)（?? ∈[??]）的 s-交叉 t-相交子族度量之和的最大值。后来，Liu [26] 研究了交叉 t-相交族 ? ?([??]≤??) 和 ?? ?([??]≤?) 度量之和的最大值。

我们在更广泛的度量背景下呈现这些结果，此时关注点从最大化族的大小转向最大化其度量。形式地，设 ?? :2[??] →?≥0 为将权重分配给 [??] 的每个子集的函数。族 ? ?2[??] 的度量定义为 ???(?) := ∑??∈????(??)。两种标准度量为乘积度量 ???? 和均匀度量 ????。对于 ?? ∈[0,1]，乘积度量由 ?????(??) := ??|??|?(1???)???|??|（?? ∈2[??]）给出。这对应于以概率 p 独立包含 [??] 中每个元素而得到集合 F 的概率。其中 ?? ∈[??] 的均匀度量 ???? 满足：当 |??|= ?? 时 ?????(??) := 1/(????)，否则 ?????(??)= 0。对这些度量可推导 Erd?s–Ko–Rado 定理的类似结果。对于均匀度量，若 2?? ≤?? 且 ? ?([??]??) 是相交的，则 ?????(?) ≤????。对于乘积度量，文献 [1] 证明了若 ?? ≤1/2 且 ? ?2[??] 是相交的，则 ?????(?) ≤??；另见 [8]、[15]、[19]、[20] 获取替代证明。关于交叉相交族的特定度量的进一步结果可见 [4]、[5]、[10]、[11]、[21]、[22]。简要综述参见 [16, 第 12 章和第 28 章]。

设 ?? :[0,??] →?≥0 为非递增函数，即对于 ??,?? ∈[0,??]，若 ?? ≤??，则 ???(??) ≥???(??)。对于集合 ?? ?[??]，我们考虑度量 ???(??)= ???(|??|)。进而，对于 ? ?2[??]，我们定义 ???(?)= ∑??∈????(??)。特别地，令每个 ?? ∈? 满足 ???(??)= 1，则得 ???(?)= |?|。获得考虑 s-交叉 t-相交族度量而非大小的更一般结果是十分有趣的。以下两个定理由 Gupta 等人在近期工作 [22] 中给出。

**定理 1.1** [22] 设 ??,?? ≥1 和 ?? ≥2 为整数。对于 ?? ∈[??]，设 ???? :[0,??] →?≥0 为非递增的，且设 ??? ?([??]????)，满足 ??1 ≥??2 ≥? ≥????。若 ?1,…,??? 为非空 s-交叉 t-相交族且 ?? ≥2??1+ ?????1? ??，则

∑??∈[??]?????(???)≤max??∈[??,??]??{ {?{ {?????(???(??,??,??)(???))+∑??∈[??]﹨{?}?????(??(??,??)(????))?{ {?{ {?,

其中 ???(??,??,??)= {???[??]:|??∩[??]|≥??} 和 ??(??,??)= {???[??]:[??]???}，且最大值在 ? ∈[??] 和 ??= min??∈[??]﹨{?}????? 上取得。

**定理 1.2** [22] 设 ??,?? ≥1 和 ?? ≥2 为整数。对于 ?? ∈[??]，设 ???? :[0,??] →?≥0 为非递增的，且设 ??? ?2[??]。若 ?1,…,??? 为非空 s-交叉 t-相交族，则

∑??∈[??]?????(???)≤max??∈[??,??]??{ {?{ {?????(???(??,??,??))+∑??∈[??]﹨{?}?????(??(??,??))?{ {?{ {?,

其中 ???(??,??,??)= {???[??]:|??∩[??]|≥??} 和 ??(??,??)= {???[??]:[??]???}，且最大值在 ? ∈[??] 上取得。

**各节摘要**

**主要结果**

在本文中，我们引入以下定义，它是 s-交叉 t-相交族和成对交叉 t-相交族的推广。

**定义 2.1** 给定族 ?1,…,??? ?2[??]，其中 ?? ≥?? ≥2，若对任意选取的 r 个不同元素 ??1,…,???? ∈[??] 以及任意 ????1 ∈???1,…,?????? ∈?????，其交集满足 ∣???∈[??]??????∣ ≥??，则称它们是 r-交叉 t-相交的。

当 ??= 2 时，这就是成对交叉 t-相交。当 ??= ?? 时，r-交叉 t-相交即为普通的 s-交叉 t-

**必要交点**

本文使用的方法是移位算子方法和必要交点方法。首先，我们引入移位算子的以下重要性质。

**引理 3.1** [22] 设 1 ≤??< ?? ≤??。若 ?1,…,??? ?2[??] 是 r-交叉 t-相交的，则族 ????????(?1),…,????????(???) 是 r-交叉 t-相交的。

现在我们介绍必要交点的一个变体，这是 Gupta 等人在近期工作 [22] 中开创的一种创新方法。

**定义 3.2** 设 ?1,…,??? ?2[??] 是 r-交叉 t-相交的

**定理 2.2 的证明**

借助引理 3.6，我们准备好证明定理 2.2。

**定理 2.2 的证明**

设 ??? ??(????)，?? ∈[??] 为非空 r-交叉 t-相交族，且 ∑??∈[??]?????(???) 最大。此外，我们可以假设它们在所有此类族中具有最小的最大必要交点。由于 ? 是移位的，且 ∑??∈[??]?????(???) 在移位下保持不变，由引理 3.4，我们可以进一步假设 ?1,…,??? 是移位的。设 a 为它们的最大必要交点。

若 ??= ??，则对任意 r-元集合 ?? ?[??] 和任意 ???? ∈???，?? ∈??，

**结语**

在本文中，我们引入了 r-交叉 t-相交族的概念，它是 s-交叉 t-相交族和成对交叉 t-相交族的推广。对于 ??+2/2 ≤?? ≤??，我们推得了移位遗传族的 r-交叉 t-相交（均匀或非均匀）子族度量之和的紧上界。此外，我们推得了 r-交叉 t-相交分离族大小之和的最优界。这些结果统一并推广了许多已知的

Zhiyi Liu|Yongjiang Wu|Yongtao Li|Tingzeng Wu|Lihua Feng