Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-070 | 15th April 2017 12:40

Probabilistic Existence of Large Sets of Designs


Authors: Shachar Lovett, Sankeerth Rao, Alex Vardy
Publication: 23rd April 2017 10:01
Downloads: 258


A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet positive, probability.
Herein, we strengthen both the method and the result of Kuperberg, Lovett, and Peled as follows.
We modify the random choice and the analysis to show that, under the same conditions, not only does a $t- (n,k,?)$ design exist but, in fact, with positive probability there exists a large set of such designs —that is, a partition of the set of $k$-subsets of $[n]$ into $t-(n,k,?)$ designs. Specifically, using the probabilistic approach derived herein, we prove that for all sufficiently large $n$, large sets of $t-(n,k,?)$ designs exist whenever $k > 9t$ and the necessary divisibility conditions are satisied. This resolves the existence conjecture for large sets of designs for all $k > 9t$.

ISSN 1433-8092 | Imprint