Shattered matchings in intersecting hypergraphs

Publication date 23 February 2021

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

m a t h c a l F

of

f r a c n 2

-element subsets of

X

, one can partition

X

into

f r a c n 2

disjoint pairs in such a way that no matter how we pick one element from each of the first

f r a c n 2 - 1

pairs, the set formed by them can always be completed to a member of

m a t h c a l F

by adding an element of the last pair. The above problem is related to classical questions in extremal set theory. For any

t g e 2

, we call a family of sets

m a t h c a l F s u b s e t 2^{X}

{em

t

-separable} if for any ordered pair of elements

(x, y)

of

X

, there exists

F i n m a t h c a l F

such that

F c a p x, y = x

. For a fixed

t, 2 l e t l e 5

and

n i g h t a r r o w i n f t y

, we establish asymptotically tight estimates for the smallest integer

s = s (n, t)

such that every family

m a t h c a l F

with

| m a t h c a l F | g e s

is

t

-separable.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Shattered matchings in intersecting hypergraphs