Skip to main content
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

A note on saturation for \(k\)-wise intersecting families

Published Web Location Commons 'BY' version 4.0 license

A family \(\mathcal{F}\) of subsets of \(\{1,\dots,n\}\) is called \(k\)-wise intersecting if any \(k\) members of \(\mathcal{F}\) have non-empty intersection, and it is called maximal \(k\)-wise intersecting if no family strictly containing \(\mathcal{F}\) satisfies this condition. We show that for each \(k\geq 2\) there is a maximal \(k\)-wise intersecting family of size \(O(2^{n/(k-1)})\). Up to a constant factor, this matches the best known lower bound, and answers an old question of Erdős and Kleitman, recently studied by Hendrey, Lund, Tompkins, and Tran.

Mathematics Subject Classifications: 05D05

Keywords: Intersecting family, saturation, set system

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View