Maximal 3-wise intersecting families

2021/10/25 by Balogh, József, Chen, Ce, Hendrey, Kevin +4
#05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2110.12708

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.

Related

• Maximal 3-wise Intersecting Families with Minimum Size: the Odd Case
• On the minimum size of maximal k-wise intersecting families
• Non-trivially intersecting multi-part families
• Intersecting families of sets and permutations: a survey
• The structure of maximal non-trivial d-wise intersecting uniform families with large sizes