This article is available for purchase or by subscription. See below.
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{\mathcal{F}}$ 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{\mathcal{F}}$ 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{\mathcal{F}}\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{\mathcal{F}}$ 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{\mathcal{F}}$
with
$\left\mathcal{\mathcal{F}}\right\ge s$ is
$t$separable.

PDF Access Denied
However, your active subscription may be available on Project Euclid at
https://projecteuclid.org/moscow
We have not been able to recognize your IP address
3.235.173.155
as that of a subscriber to this journal.
Online access to the content of recent issues is by
subscription, or purchase of single articles.
Please contact your institution's librarian suggesting a subscription, for example by using our
journalrecommendation form.
Or, visit our
subscription page
for instructions on purchasing a subscription.
You may also contact us at
contact@msp.org
or by using our
contact form.
Or, you may purchase this single article for
USD 40.00:
Keywords
extremal set theory, shattered set, matching,
Vapnik–Chervonenkis dimension, separability

Mathematical Subject Classification
Primary: 05C65, 05D05, 05D40

Milestones
Received: 10 May 2020
Revised: 27 July 2020
Accepted: 12 August 2020
Published: 16 January 2021

