Article ID Journal Published Year Pages File Type
5777111 Electronic Notes in Discrete Mathematics 2017 7 Pages PDF
Abstract

Let k⩾2, s⩾2 be positive integers. Let [n] be an n-element set, n⩾ks. Subsets of 2[n] are called families. If F⊂([n]k), then it is called k-uniform. What is the maximum size ek(n,s) of a k-uniform family without s pairwise disjoint members? The well-known Erdős Matching Conjecture would provide the answer for all n, k, s in the above range. For n>2ks it is known that the maximum is attained by A1(T):={A⊂[n]:|A|=k,A∩T≠∅} for some fixed (s−1)-element set T⊂X. We discuss recent progress on this problem. In particular, our recent stability result states that for n>(2+o(1))ks and a k-uniform family F,F⊈A1(T), then |F| is considerably smaller.This result is applied to obtain the corresponding anti-Ramsey numbers in a wide range.Removing the condition of uniformness, we arrive at another classical problem of Erdős, which was solved by Kleitman for n≡0 or −1 (mod s). We succeeded in resolving this long-standing problem for n≡−2(mods) via a new averaging technique which might prove useful in various other situations.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,