Probabilistic Method – 2
February 10, 2011 Leave a comment
Q.1. Let be positive integers. Let be a collection of pairwise intersecting element subsets of (i.e. if , then ). Prove that .
Let be a element subset of selected uniformly at random from the possible such subsets.
We will try to prove that .
Let be selected as follows. Take a random permutation . Take a random index , and let (wrapped around ).
Now, if given a fixed , , then .
Further, since there are at most possible indices for such that (wrapping around ) can be a part of (due to the property of pairwise intersection), .