#### Vol. 10, No. 1, 2021

 Download this article For screen For printing  Recent Issues Volume 10, Issue 1 Volume 9, Issue 4 Volume 9, Issue 3 Volume 9, Issue 2 Volume 9, Issue 1 Volume 8, Issue 4 Volume 8, Issue 3 Volume 8, Issue 2 Volume 8, Issue 1  The Journal About the Journal Editorial Board Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement founded and published with the scientific support and advice of the Moscow Institute of Physics and Technology ISSN (electronic): 2640-7361 ISSN (print): 2220-5438 Previously Published Author Index To Appear Other MSP Journals  Shattered matchings in intersecting hypergraphs

### Peter Frankl and János Pach

Vol. 10 (2021), No. 1, 49–59
##### 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 $\mathsc{ℱ}$ 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 $\mathsc{ℱ}$ 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 $\mathsc{ℱ}\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 \mathsc{ℱ}$ 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 $\mathsc{ℱ}$ with $|\mathsc{ℱ}|\ge s$ is $t$-separable.

##### Keywords
extremal set theory, shattered set, matching, Vapnik–Chervonenkis dimension, separability
##### Mathematical Subject Classification
Primary: 05C65, 05D05, 05D40