Shattered matchings in intersecting hypergraphs

Frankl, Péter and Pach, János (2020) Shattered matchings in intersecting hypergraphs. MOSCOW JOURNAL OF COMBINATORICS AND NUMBER THEORY. ISSN 2220-5438

Preview

Text 2005.pdf Available under License Creative Commons Attribution. Download (169kB) | Preview

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 F of n2-element subsets of X, one can partition X into n2 disjoint pairs in such a way that no matter how we pick one element from each of the first n2−1 pairs, the set formed by them can always be completed to a member of F by adding an element of the last pair. The above problem is related to classical questions in extremal set theory. For any t≥2, we call a family of sets F⊂2X {\em t-separable} if for any ordered pair of elements (x,y) of X, there exists F∈F such that F∩{x,y}={x}. For a fixed t,2≤t≤5 and n→∞, we establish asymptotically tight estimates for the smallest integer s=s(n,t) such that every family F with |F|≥s is t-separable.

Actions (login required)

Edit Item