Families of sets with no matchings of sizes 3 and 4. (January 2019)

• Record Type: Journal Article
• Authors: Frankl, Peter; Kupavskii, Andrey
• Is Part Of: European journal of combinatorics. Volume 75(2019)
• Page Start: 123
• Page End: 135
• Publication Date: 2019-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2018.08.005
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: In this paper, we study the following classical question of extremal set theory: what is the maximum size of a family of subsets of [ n ] such that no s sets from the family are pairwise disjoint? This problem was first posed by Erdős and resolved for n ≡ 0, − 1 ( mod s ) by Kleitman in the 60s. Very little progress was made on the problem until recently. The only result was a very lengthy resolution of the case s = 3, n ≡ 1 ( mod 3 ) by Quinn, which was written in his PhD thesis and never published in a refereed journal. In this paper, we give another, much shorter proof of Quinn's result, as well as resolve the case s = 4, n ≡ 2 ( mod 4 ) . This complements the results in our recent paper, where, in particular, we answered the question in the case n ≡ − 2 ( mod s ) for s ≥ 5 .