Problem:
Let be a positive integer and be a collection of distinct -element subsets of . Show that there exists such that .
, 2020
Solutions — 2
Solution 1
Solution:
Assume for the sake of contradiction that there exist no such . Pair up each subset with its complement, like so:
Note that for each pair, we can have at most one of the two in . Since has of the total number of subsets with size , it must be that we have exactly one element from each pair in . For any , none of the subsets that share exactly one element with can be in , so their complements must be in . This means that every subset with shared elements with must be in . Without loss of generality, assume . Then, , so . Continuing on in this manner, we eventually reach , contradiction.
Solution 2
Solution:
Let . Consider the following cycle of sets such that any two adjacent sets have an intersection of size :
If contains two adjacent elements of the cycle then we are done. For each permutation of , we can consider the cycle of sets obtained after applying , i.e. and so on. In total, each subset of with size appears times across all the cycles , so
where the sum is over all permutations of . This means that on average across possible cycles, of its elements are in . Thus, if we select a cycle uniformly at random, with positive probability we will have , so two adjacent elements in this cycle will be in . Therefore, there must exist some two subsets in that share at most one element.
This proof will work under the weaker condition .
Remark. A family of sets such that for every pair of distinct sets is called -intersecting. Ahlswede and Khachatrian solved the problem of determining the largest -uniform -intersecting family. See "Katona's Intersection Theorem: Four Proofs" or "The Complete Intersection Theorem for Systems of Finite Sets" for exact results.