Abstract
A family F on ground set [n] : = { 1 , 2 , … , n} is maximal k-wise intersecting if every collection of at most k sets in F has non-empty intersection, and no other set can be added to F while maintaining this property. In 1974, Erdős and Kleitman asked for the minimum size of a maximal k-wise intersecting family. We answer their question for k= 3 and sufficiently large n. We show that the unique minimum family is obtained by partitioning the ground set [n] 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.
Original language | English (US) |
---|---|
Pages (from-to) | 1045-1066 |
Number of pages | 22 |
Journal | Combinatorica |
Volume | 43 |
Issue number | 6 |
DOIs | |
State | Published - Dec 2023 |
Keywords
- Intersecting
- Maximal
- Saturation
- Set-system
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics