Vol. 10, No. 1, 2021

Download this article
Download this article For screen
For printing
Recent Issues
Volume 13, Issue 1
Volume 12, Issue 4
Volume 12, Issue 3
Volume 12, Issue 2
Volume 12, Issue 1
Volume 11, Issue 4
Volume 11, Issue 3
Volume 11, Issue 2
Volume 11, Issue 1
Volume 10, Issue 4
Volume 10, Issue 3
Volume 10, Issue 2
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
Older Issues
Volume 7, Issue 4
Volume 7, Issue 3
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 4
Volume 6, Issue 2-3
Volume 6, Issue 1
Volume 5, Issue 4
Volume 5, Issue 3
Volume 5, Issue 1-2
Volume 4, Issue 4
Volume 4, Issue 3
Volume 4, Issue 2
Volume 4, Issue 1
Volume 3, Issue 3-4
Volume 3, Issue 2
Volume 3, Issue 1
Volume 2, Issue 4
Volume 2, Issue 3
Volume 2, Issue 2
Volume 2, Issue 1
Volume 1, Issue 4
Volume 1, Issue 3
Volume 1, Issue 2
Volume 1, Issue 1
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
founded and published with the
scientific support and advice of
mathematicians from the
Moscow Institute of
Physics and Technology
Subscriptions
 
ISSN (electronic): 2996-220X
ISSN (print): 2996-2196
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 of n 2 -element subsets of X, one can partition X into n 2 disjoint pairs in such a way that no matter how we pick one element from each of the first n 2 1 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 t 2, we call a family of sets 2X t-separable if there is a t-element subset T X such that for every ordered pair of elements (x,y) of T, there exists 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 with || s is t-separable.

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
Authors
Peter Frankl
Rényi Institute
Hungarian Academy of Sciences
Budapest
Hungary
János Pach
Rényi Institute
Hungarian Academy of Sciences
Budapest
Hungary