March 17, 2017 Leave a comment
Suppose that we want to construct subsets with the following properties:
- for all
- for all
The goal is to construct as large a family of such subsets as possible (i.e., to make as large as possible). If , then up to constants it is not hard to show that the optimal number of sets is (that is, the trivial construction with all sets disjoint is essentially the best we can do).
Here I am interested in the case when . In this case I claim that we can substantially outperform the trivial construction: we can take . The proof is a very nice application of the asymmetric Lovasz Local Lemma. (Readers can refresh their memory here on what the asymmetric LLL says.)
Proof. We will take a randomized construction. For , , let be the event that . We will take the to be independent each with probability . Also define the events
It suffices to show that with non-zero probability, all of the and are false. Note that each depends on , and each depends on . Thus each depends on at most other and other , and each depends on at most of the . Also note that and (by the Chernoff bound). It thus suffices to find constants such that
We will guess , , in which case the bottom inequality is approximately (which is satisfied for large enough , and the top inequality is approximately , which is satisfied for (assuming ). Hence in particular we can indeed take , as claimed.