On the minimum size of maximal $k$-wise intersecting families
Abstract
A family $\mathcal{F}$ of subsets of $[n] := \{1,2,\ldots, n\}$ is called maximal $k$-wise intersecting if every collection of at most $k$ members of $\mathcal{F}$ has a non-empty intersection, and adding any other set to $\mathcal{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-3}2^{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.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요