2025-11-19T18:52:13.613004

On BollobÃ¡s-type theorems of $d$-tuples

Yue

In 1965, BollobÃ¡s proved that for a BollobÃ¡s set-pair system $\{(A_i,B_i)\mid i\in[m]\}$, the maximum value of $\sum_{i=1}^m\binom{|A_i|+|B_i|}{A_i}^{-1}$ is $1$. HegedÃ¼s and Frankl recently extended the concept of BollobÃ¡s systems to $d$-tuples, conjecturing that for a BollobÃ¡s system of $d$-tuples, $\{(A_i^{(1)},\ldots,A_i^{(d)})\mid i\in[m]\}$, the maximum value of $\sum_{i=1}^m\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|}{|A_i^{(1)}|,\ldots,|A_i^{(d)}|}^{-1}$ is also $1$. This paper refutes this conjecture and establishes an upper bound for the sum. In the case $d=3$, the derived upper bound is asymptotically tight. Furthermore, we sharpen an inequality for skew BollobÃ¡s systems of $d$-tuples in HegedÃ¼s and Frankl's paper. Finally, we determine the maximum size of a uniform skew BollobÃ¡s system of $d$-tuples on both sets and spaces.

academic

On Bollobás-type theorems of $d$ -tuples

基本信息

论文ID: 2411.17192
标题: On Bollobás-type theorems of $d$ -tuples
作者: Erfei Yue (匈牙利厄特沃什·罗兰大学数学研究所)
分类: math.CO (组合数学)
发表时间: 2024年11月26日首次提交，2024年12月30日第三版
论文链接: https://arxiv.org/abs/2411.17192

摘要

本文研究了Bollobás型定理在 $d$ -元组上的推广。1965年，Bollobás证明了对于Bollobás集合对系统 $\{(A_i,B_i)\mid i\in[m]\}$ ， $\sum_{i=1}^m\binom{|A_i|+|B_i|}{A_i}^{-1}$ 的最大值为1。Hegedüs和Frankl最近将Bollobás系统的概念扩展到 $d$ -元组，并猜想对于 $d$ -元组的Bollobás系统 $\{(A_i^{(1)},\ldots,A_i^{(d)})\mid i\in[m]\}$ ， $\sum_{i=1}^m\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|}{|A_i^{(1)}|,\ldots,|A_i^{(d)}|}^{-1}$ 的最大值也是1。本文否定了这一猜想，建立了该和式的上界，并在 $d=3$ 的情况下证明了渐近紧性。

研究背景与动机

历史背景

Bollobás型定理起源于1965年Bollobás为解决超图问题而证明的一个重要结果。该定理及其推广在极值集合论中占据核心地位，具有深远的理论意义和广泛的应用价值。

问题的重要性

理论价值: Bollobás型定理是极值集合论的基础工具，为组合优化和图论问题提供了重要的理论支撑
应用广泛: 在自动机理论、代数组合学、超图理论等领域都有重要应用
推广意义: 从集合对到 $d$ -元组的推广是自然且重要的理论发展方向

现有方法的局限性

Hegedüs和Frankl提出的猜想(Conjecture 1)过于乐观，直接类比二元情况的结果
对于 $d\geq 3$ 的情况，缺乏系统的理论分析和精确的上界估计
现有的概率方法和代数方法需要进一步发展以处理高维情况

核心贡献

否定了Hegedüs-Frankl猜想: 通过构造反例(Example 2)证明了对于 $d$ -元组Bollobás系统，相应和式的最大值不是1
建立了新的上界: 对于一般的 $d$ -元组Bollobás系统给出了渐近上界 $\frac{1}{d-1}\binom{n+d-2}{d-2}+O(n^{d-3})$
$d=3$ 情况的紧界: 证明了 $d=3$ 时上界 $\frac{n+3}{2}$ 是渐近紧的
改进了倾斜Bollobás系统的不等式: 将Hegedüs-Frankl的结果改进为更精确的形式(Theorem 1.8)
确定了均匀情况的精确界: 对于均匀倾斜Bollobás系统，在集合和向量空间情况下都给出了精确的最大规模

方法详解

核心概念定义

Bollobás系统( $d$ -元组版本): 设 $F = \{(A_i^{(1)}, \ldots, A_i^{(d)}) \mid i \in [m]\}$ 是 $d$ -元组的集合，若对任意 $i \in [m]$ 和 $p \neq q$ 有 $A_i^{(p)} \cap A_i^{(q)} = \emptyset$ ，且对任意 $i \neq j$ ，存在 $p < q$ 使得 $A_i^{(p)} \cap A_j^{(q)} \neq \emptyset$ ，则称 $F$ 为Bollobás系统。

倾斜Bollobás系统: 将条件" $i \neq j$ "改为" $i < j$ "即得到倾斜Bollobás系统的定义。

主要技术方法

1. 概率方法 (Probabilistic Method)

核心思想: 利用随机排列来分析不同元组之间的相交性质。

对于Theorem 1.6和1.8的证明，作者采用了以下概率论证:

选择随机排列 $\sigma \in S_{n+d-1}$
使用 $\{n+1, \ldots, n+d-1\}$ 作为分隔符
定义事件 $E_i$ 表示元组 $(A_i^{(1)}, \ldots, A_i^{(d)})$ 的元素按特定顺序排列
计算概率 $P(E_i) = \left(\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|+d-1}{d-1}\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|}{|A_i^{(1)}|,\ldots,|A_i^{(d)}|}\right)^{-1}$

关键洞察: 不同的事件 $E_i$ 和 $E_j$ ( $i \neq j$ )不能同时发生，这是因为Bollobás系统的相交条件会导致矛盾。

2. 外积代数方法 (Exterior Algebra Method)

用于处理向量空间上的Bollobás系统(Theorem 1.13)。

核心工具:

外积(楔积): $\alpha_1 \wedge \cdots \wedge \alpha_k$
线性无关性判别: $\alpha_1, \ldots, \alpha_k$ 线性无关当且仅当 $\alpha_1 \wedge \cdots \wedge \alpha_k \neq 0$

证明策略:

利用一般位置论证(Lemma 3.3)构造合适的线性映射 $\phi_k: V \to V_k$
定义线性泛函 $f_i$ 使得 $f_i(\xi_i) \neq 0$ 且 $f_i(\xi_j) = 0$ (当 $i < j$ 时)
证明 $f_1, \ldots, f_m$ 线性无关，从而得到规模上界

3. 归纳法

对于一般 $d$ 的情况，使用数学归纳法结合概率论证来建立递推关系。

反例构造

Example 2的巧妙设计: 对于 $d=3$ ，构造族 $F = \bigcup_{l=0}^{\lfloor n/2 \rfloor} F_l$ ，其中 $F_l$ 包含所有类型为 $(l, n-2l, l)$ 的不相交三元组。

关键性质:

满足Bollobás系统的定义
相应和式的值为 $\lfloor n/2 \rfloor + 1$ ，远大于猜想的上界1
接近作者证明的上界 $\frac{n+3}{2}$ ，显示了上界的紧性

实验结果

主要理论结果

Theorem 1.6 (Bollobás系统的上界):

$d=3$ : $\sum_{i=1}^m \binom{|A_i^{(1)}|+|A_i^{(2)}|+|A_i^{(3)}|}{|A_i^{(1)}|,|A_i^{(2)}|,|A_i^{(3)}|}^{-1} \leq \frac{n+3}{2}$
一般 $d$ : 上界为 $\frac{1}{d-1}\binom{n+d-2}{d-2} + O(n^{d-3})$

Theorem 1.8 (倾斜Bollobás系统的改进): $\sum_{i=1}^m \left(\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|+d-1}{d-1}\binom{|A_i^{(1)}|+\cdots+|A_i^{(d)}|}{|A_i^{(1)}|,\ldots,|A_i^{(d)}|}\right)^{-1} \leq 1$