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

Basic Information

• Paper ID: 2411.17192
• Title: On Bollobás-type theorems of $d$-tuples
• Author: Erfei Yue (Institute of Mathematics, Eötvös Loránd University, Hungary)
• Classification: math.CO (Combinatorics)
• Submission Timeline: First submitted November 26, 2024; third version December 30, 2024
• Paper Link: https://arxiv.org/abs/2411.17192

Abstract

This paper investigates generalizations of Bollobás-type theorems to $d$-tuples. 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 and conjectured 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, establishes upper bounds for this sum, and proves asymptotic tightness for the case $d=3$.

Research Background and Motivation

Historical Context

Bollobás-type theorems originated from an important result proved by Bollobás in 1965 to solve hypergraph problems. This theorem and its generalizations occupy a central position in extremal set theory, with profound theoretical significance and broad applications.

Importance of the Problem

1. Theoretical Value: Bollobás-type theorems are fundamental tools in extremal set theory, providing important theoretical support for combinatorial optimization and graph theory problems
2. Wide Applications: Important applications in automata theory, algebraic combinatorics, hypergraph theory, and related fields
3. Significance of Generalization: The extension from set pairs to $d$-tuples is a natural and important direction for theoretical development

Limitations of Existing Methods

• The conjecture proposed by Hegedüs and Frankl (Conjecture 1) is overly optimistic, directly analogizing results from the binary case
• For cases with $d\geq 3$, there is a lack of systematic theoretical analysis and precise upper bound estimates
• Existing probabilistic and algebraic methods require further development to handle higher-dimensional cases

Core Contributions

1. Refutation of the Hegedüs-Frankl Conjecture: Through construction of counterexamples (Example 2), proves that for $d$-tuple Bollobás systems, the maximum value of the corresponding sum is not 1
2. Establishment of New Upper Bounds: Provides asymptotic upper bounds $\frac{1}{d-1}\binom{n+d-2}{d-2}+O(n^{d-3})$ for general $d$-tuple Bollobás systems
3. Tight Bounds for $d=3$: Proves that the upper bound $\frac{n+3}{2}$ for $d=3$ is asymptotically tight
4. Improved Inequalities for Skew Bollobás Systems: Refines the Hegedüs-Frankl result to a more precise form (Theorem 1.8)
5. Exact Bounds for Uniform Cases: Provides exact maximum sizes for uniform skew Bollobás systems in both set and vector space settings

Methodology Details

Core Concept Definitions

Bollobás System ($d$-tuple version): Let $F = \{(A_i^{(1)}, \ldots, A_i^{(d)}) \mid i \in [m]\}$ be a collection of $d$-tuples. $F$ is called a Bollobás system if for any $i \in [m]$ and $p \neq q$, we have $A_i^{(p)} \cap A_i^{(q)} = \emptyset$, and for any $i \neq j$, there exist $p < q$ such that $A_i^{(p)} \cap A_j^{(q)} \neq \emptyset$.

Skew Bollobás System: Obtained by replacing the condition "$i \neq j$" with "$i < j$" in the definition of Bollobás systems.

Main Technical Methods

1. Probabilistic Method

Core Idea: Utilizes random permutations to analyze intersection properties among different tuples.

For the proofs of Theorems 1.6 and 1.8, the author employs the following probabilistic argument:

• Select a random permutation $\sigma \in S_{n+d-1}$
• Use $\{n+1, \ldots, n+d-1\}$ as separators
• Define event $E_i$ representing elements of tuple $(A_i^{(1)}, \ldots, A_i^{(d)})$ arranged in a specific order
• Calculate probability $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}$

Key Insight: Different events $E_i$ and $E_j$ ($i \neq j$) cannot occur simultaneously, as the intersection conditions of Bollobás systems lead to contradictions.

2. Exterior Algebra Method

Used for handling Bollobás systems on vector spaces (Theorem 1.13).

Core Tools:

• Exterior product (wedge product): $\alpha_1 \wedge \cdots \wedge \alpha_k$
• Linear independence criterion: $\alpha_1, \ldots, \alpha_k$ are linearly independent if and only if $\alpha_1 \wedge \cdots \wedge \alpha_k \neq 0$

Proof Strategy:

1. Utilize general position arguments (Lemma 3.3) to construct appropriate linear maps $\phi_k: V \to V_k$
2. Define linear functionals $f_i$ such that $f_i(\xi_i) \neq 0$ and $f_i(\xi_j) = 0$ (when $i < j$)
3. Prove that $f_1, \ldots, f_m$ are linearly independent, thereby obtaining size bounds

3. Mathematical Induction

For general $d$, mathematical induction combined with probabilistic arguments establishes recursive relationships.

Counterexample Construction

Clever Design of Example 2: For $d=3$, construct the family $F = \bigcup_{l=0}^{\lfloor n/2 \rfloor} F_l$, where $F_l$ contains all disjoint triples of type $(l, n-2l, l)$.

Key Properties:

• Satisfies the definition of Bollobás systems
• The value of the corresponding sum is $\lfloor n/2 \rfloor + 1$, far exceeding the conjectured upper bound of 1
• Approaches the author's proven upper bound $\frac{n+3}{2}$, demonstrating tightness of the bound

Experimental Results

Main Theoretical Results

Theorem 1.6 (Upper Bound for Bollobás Systems):

• $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}$
• General $d$: Upper bound is $\frac{1}{d-1}\binom{n+d-2}{d-2} + O(n^{d-3})$

Theorem 1.8 (Improvement for Skew Bollobás Systems): $\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$

Theorems 1.9 & 1.13 (Exact Bounds for Uniform Cases): For uniform skew Bollobás systems, the maximum size is exactly $\binom{a_1+\cdots+a_d}{a_1,\ldots,a_d}$.

Tightness Analysis

• Example 2 shows that the upper bound for $d=3$ is asymptotically tight
• For $d>3$, the tightness of the upper bound remains an open problem
• In the uniform case, Example 1 provides a construction achieving the bound

Related Work

Historical Development

1. Bollobás (1965): Original set pair version theorem
2. Frankl (1982): Extension to skew Bollobás systems
3. Lovász (1977): Generalization to matroids and vector spaces using exterior algebra
4. Hegedüs & Frankl (2024): Proposed generalization to $d$-tuples and conjecture

Development of Technical Methods

• Probabilistic Method: Developed from Yue's (2023) work
• Exterior Algebra: Originated from Lovász's pioneering work
• General Position Arguments: Standard technique in combinatorial geometry

Application Areas

• Intersection families in extremal set theory
• State complexity in automata theory
• Error-correcting code construction in coding theory

Conclusions and Discussion

Main Conclusions

1. Negative Result: The Hegedüs-Frankl conjecture does not hold; the $d$-tuple case is more complex than the set pair case
2. Constructive Result: Provides new upper bounds, particularly asymptotically tight bounds for $d=3$
3. Completeness Result: Resolves the maximum size problem for uniform skew Bollobás systems

Limitations

1. Tightness for $d>3$: For $d>3$, gaps remain between upper bounds and known constructions
2. Construction Methods: Lack of systematic methods to construct examples approaching the bounds
3. Computational Complexity: No discussion of computational complexity of related problems

Future Directions

1. Tight Bound Problem: Determine tightness of bounds for $d>3$
2. Algorithmic Problems: Study algorithmic complexity of related optimization problems
3. Generalization Directions: Consider more general intersection conditions or geometric structures

In-Depth Evaluation

Strengths

1. Significant Theoretical Contribution: Refutes a natural conjecture and establishes a new theoretical framework
2. Methodological Innovation: Skillfully combines probabilistic and algebraic methods with rich technical approaches
3. Complete Results: Provides negative results, constructive upper bounds, and exact solutions for uniform cases
4. Clear Presentation: Well-structured paper with detailed technical exposition, easy to understand and verify

Weaknesses

1. Tightness Undetermined for Some Results: Gaps remain for $d>3$
2. Limited Construction Techniques: Counterexample construction is relatively simple, lacking deeper combinatorial insights
3. Insufficient Application Discussion: Limited discussion of practical applications of results

Impact

1. Theoretical Impact: Provides new research directions and technical tools for extremal set theory
2. Methodological Impact: Improvements to probabilistic methods may apply to other combinatorial problems
3. Open Problems: Proposed questions will drive further development in the field

Applicable Scenarios

• Theoretical research in extremal set theory
• Constraint satisfaction problems in combinatorial optimization
• Related problems in coding theory and information theory
• Complexity theory research in computer science

Additional Technical Details

Generalization of Multinomial Coefficients

The multinomial coefficient $\binom{n}{k_1,\ldots,k_t} = \frac{n!}{k_1!\cdots k_t!(n-k_1-\cdots-k_t)!}$ used in the paper is a natural generalization of binomial coefficients with important status in combinatorics.

Sophistication of Probabilistic Arguments

The author's use of separator techniques in the proofs is particularly clever. By introducing $d-1$ additional elements as separators, complex intersection conditions are transformed into simple ordering problems, a method with strong generality.

Overall Assessment: This is a high-quality combinatorics paper that resolves an important theoretical problem with novel methods and complete results. While some open problems remain, it makes significant contributions to the development of the field.