Maximal 3-wise Intersecting Families with Minimum Size: the Odd Case

József Balogh, Ce Chen, Haoran LuoarXiv 2022 · DOI · arXiv

Abstract

A family $\mathcal{F}$ on a ground set $[n] = \{1, 2, \ldots, n\}$ is defined as maximal $k$-wise intersecting if every collection of $k$ sets within $\mathcal{F}$ has a non-empty intersection, and no additional set can be added to $\mathcal{F}$ without violating this property. This paper addresses a problem posed by Erdős and Kleitman in 1974 concerning the minimum possible size of such families. While previous research established the minimum size for $k=3$ and large even $n$, this work completes the characterization for $k=3$ and large odd $n$. We prove that the unique minimum family is a "balanced pair of linked cubes," constructed by partitioning the ground set into two nearly equal parts. The proof utilizes a stability result regarding 2-generator set systems.

Introduction

In extremal set theory, a common objective is to determine the maximum size of a family of sets that satisfies a specific intersection property. The Erdős-Ko-Rado theorem is the most famous example of such a result. However, the study of the minimum size of maximal families—often referred to as saturation problems—presents a different set of challenges.

A family $\mathcal{F}$ is $k$-wise intersecting if for any $A_1, \ldots, A_k \in \mathcal{F}$, the intersection $\cap_{i=1}^k A_i \neq \emptyset$. It is maximal if it is not contained in any other $k$-wise intersecting family. Erdős and Kleitman (1974) sought to find the minimum size of such a family, denoted by $m(n, k)$. This paper focuses on the case $k=3$ when $n$ is a large odd integer, building upon the work of Hendrey, Lund, Tompkins, and Tran, who solved the even case.

The Optimal Construction: Linked Cubes

The authors demonstrate that the unique family achieving the minimum size for $k=3$ and large odd $n$ is the balanced pair of linked cubes.

To construct this family, the ground set $[n]$ is partitioned into two sets, $A$ and $B$, with sizes as equal as possible: $|A| = \lfloor n/2 \rfloor$ and $|B| = \lceil n/2 \rceil$. The family $\mathcal{F}$ is then defined as the collection of all proper supersets of $A$ and all proper supersets of $B$. Formally: $$\mathcal{F} = \{S \subseteq [n] : A \subsetneq S \text{ or } B \subsetneq S\}$$

For large odd $n$, this structure is significantly smaller than other maximal intersecting families, such as a "star" (which contains $2^{n-1}$ sets). The size of this unique minimum family is exactly: $$|\mathcal{F}| = 2^{\lceil n/2 \rceil} + 2^{\lfloor n/2 \rfloor} - 3$$

Methodology and Stability

The proof strategy relies on translating the intersection property into a structural property of the complement of the family.

1. The 2-Generator Property

A key observation is that if $\mathcal{F}$ is a maximal 3-wise intersecting family, then its complement $\mathcal{F}^c = \mathcal{P}([n]) \setminus \mathcal{F}$ must be a "2-generator" for the power set. This means that for almost every subset $S \subseteq [n]$, either $S \in \mathcal{F}^c$ or $S$ can be expressed as the union of two sets from $\mathcal{F}^c$. This shift allows the authors to apply tools from additive combinatorics and the theory of set generation.

2. Stability Results

The authors leverage a stability theorem by Ellis and Sudakov. This theorem suggests that if a 2-generator set system is relatively small, its structure must closely resemble a "pair of cubes" (the set of all subsets of a partition). The stability approach allows the researchers to start with an "approximate" structure and then use combinatorial refinements to prove that the balanced linked cubes construction is the exact and unique optimizer.

3. Handling Parity

The transition from even $n$ to odd $n$ introduces technical complexities. In the even case, the partition is perfectly symmetric ($n/2, n/2$). In the odd case, the slight imbalance ($l, l+1$) requires more delicate handling of the combinatorial bounds to ensure that the balanced partition remains the global minimum.

Conclusion

This paper provides the final piece of the puzzle for the $k=3$ case of the Erdős-Kleitman problem for large $n$. By showing that the balanced pair of linked cubes is the unique minimum family for odd $n$, the authors have fully characterized the behavior of $m(n, 3)$ for all sufficiently large $n$.

Future research remains open for $k \ge 4$. As $k$ increases, the structure of maximal $k$-wise intersecting families becomes significantly more complex. While recent bounds suggest the size grows at an order of $O(2^{n/(k-1)})$, the exact extremal structures are likely to be far more intricate than the linked cubes identified in the $k=3$ case. Additionally, the behavior of these families for small $n$ remains an area where the structured stability of large $n$ may not yet apply.

Summary updated

Abstract

A family $\mathcal{F}$ on ground set $\{1,2,\ldots, n\}$ is maximal $k$-wise intersecting if every collection of $k$ sets in $\mathcal{F}$ has non-empty intersection, and no other set can be added to $\mathcal{F}$ while maintaining this property. Erdős and Kleitman asked for the minimum size of a maximal $k$-wise intersecting family. Complementing earlier work of Hendrey, Lund, Tompkins and Tran, who answered this question for $k=3$ and large even $n$, we answer it for $k=3$ and large odd $n$. We show that the unique minimum family is obtained by partitioning the ground set into two sets $A$ and $B$ with almost equal sizes and taking the family consisting of all the proper supersets of $A$ and of $B$. A key ingredient of our proof is the stability result by Ellis and Sudakov about the so-called $2$-generator set systems.
BibTeX
@misc{balogh2022maximal,
  author = {József Balogh and Ce Chen and Haoran Luo},
  title = {{Maximal 3-wise Intersecting Families with Minimum Size: the Odd Case}},
  year = {2022},
  eprint = {2206.09334},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.09334},
}
Figure