ECCC-Report TR17-070https://eccc.weizmann.ac.il/report/2017/070Comments and Revisions published for TR17-070en-usSun, 23 Apr 2017 10:01:19 +0300
Paper TR17-070
| Probabilistic Existence of Large Sets of Designs |
Shachar Lovett,
Sankeerth Rao Karingula,
Alex Vardy
https://eccc.weizmann.ac.il/report/2017/070A 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$.Sun, 23 Apr 2017 10:01:19 +0300https://eccc.weizmann.ac.il/report/2017/070