2025/11/26 by Andrey Kupavskii, Kupavskii, Andrey, G. A. Sokolov +1 · 1 citation
Mathematics · #Analytic Number Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2511.21628
openalex publication_date 2025/11/26 · openalex created_date 2025/11/28 · openalex updated_date 2026/07/28
Given integers n≥ s≥ 2, let e(n,s) stand for the maximum size of a family of subsets of an n-element set that contains no s pairwise disjoint members. The study of this quantity goes back to the 1960s, when Kleitman determined e(sm-1,s) and e(sm,s) for all integer m,s≥ 1. The question of determining e(n,s) is closely connected to its uniform counterpart, the subject of the famous Erdős Matching Conjecture. The problem of determining e(n,s) has proven to be very hard and, in spite of some progress during these years, even a general conjecture concerning the value of e(n,s) is missing. In this paper, we completely solve the problem for n≤ 3s. In this regime, the average size of a set in an s-matching is at most 3, and it is a delicate interplay between the `missing' 2- and 3-element sets that plays a key role here. Four types of extremal families appear in the characterization. Our result sheds light on how the extremal function e(n,s) may behave in general.