Let
be an
-element
set, where
is even. We refute a conjecture of J. Gordon and Y. Teplitskaya,
according to which, for every maximal intersecting family
of
-element
subsets of
, one
can partition
into
disjoint pairs in such a way that no matter how we pick one element from each of the
first
pairs, the set formed by them can always be completed to a member of
by
adding an element of the last pair.
The above problem is related to classical questions in extremal set theory. For any
, we call a
family of sets
-separable if there is
a
-element subset
such that for every
ordered pair of elements
of
, there
exists
such
that
. For
a fixed
,
, and
,
we establish asymptotically tight estimates for the smallest integer
such that
every family
with
is
-separable.
Keywords
extremal set theory, shattered set, matching,
Vapnik–Chervonenkis dimension, separability