Skip to main content
Download PDF
- Main
A note on saturation for \(k\)-wise intersecting families
© 2022 by the author(s). Learn more.
Abstract
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.
If you recently published or updated this item, please wait up to 30 minutes for the PDF to appear here.
Enter the password to open this PDF file:
File name:
-
File size:
-
Title:
-
Author:
-
Subject:
-
Keywords:
-
Creation Date:
-
Modification Date:
-
Creator:
-
PDF Producer:
-
PDF Version:
-
Page Count:
-
Page Size:
-
Fast Web View:
-
Preparing document for printing…
0%