On the minimum size of maximal k-wise intersecting families

2026/07/20 by Haoran Luo
#math.CO

paper · pdf

Abstract

A family F of subsets of [n] := \1,2,…, n\ is called maximal k-wise intersecting if every collection of at most k members of F has a non-empty intersection, and adding any other set to F breaks this property. An old question by Erdős and Kleitman from 1974 asks for the minimum size of a maximal k-wise intersecting family. The case k = 3 is known for all sufficiently large n, but the problem remains open for all k \geqslant 4. The previous best-known upper bound is by Janzer, which has a leading term (k-1)2^k-32^n/(k-1) for sufficiently large n divisible by k-1. In this note, we improve this bound to (4k-10)2^n/(k-1), which reduces the dependence on k in the leading coefficient from exponential to linear and is within a factor of 4 of the known lower bound.

Related

• Maximal 3-wise intersecting families
• Maximal 3-wise Intersecting Families with Minimum Size: the Odd Case
• An improved threshold for the number of distinct intersections of intersecting families
• The structure of maximal non-trivial d-wise intersecting uniform families with large sizes
• On the size of maximal intersecting families