Abstract

Let $X$ be an $n$-element set, where $n$ is even. We refute a conjecture of J. Gordon and Y. Teplitskaya, according to which, for every maximal intersecting family $\mathcal{ℱ}$ of $\frac{n}{2}$-element subsets of $X$, one can partition $X$ into $\frac{n}{2}$ disjoint pairs in such a way that no matter how we pick one element from each of the first $\frac{n}{2}-1$ pairs, the set formed by them can always be completed to a member of $\mathcal{ℱ}$ by adding an element of the last pair.

The above problem is related to classical questions in extremal set theory. For any $t\ge 2$, we call a family of sets $\mathcal{ℱ}\subset 2^X$ $t$-separable if there is a $t$-element subset $T\subseteq X$ such that for every ordered pair of elements $\left(x,y\right)$ of $T$, there exists $F\in \mathcal{ℱ}$ such that $F\cap \left\{x,y\right\}=\left\{x\right\}$. For a fixed $t$, $2\le t\le 5$, and $n\to \infty$, we establish asymptotically tight estimates for the smallest integer $s=s\left(n,t\right)$ such that every family $\mathcal{ℱ}$ with $\left|\mathcal{ℱ}\right|\ge s$ is $t$-separable.

Keywords

Mathematical Subject Classification

Milestones

Authors