首页    期刊浏览 2024年07月07日 星期日
登录注册

文章基本信息

  • 标题:Probabilistic Existence of Large Sets of Designs
  • 本地全文:下载
  • 作者:Shachar Lovett ; Sankeerth Rao ; Alex Vardy
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 9t"> k 9 t and the necessary divisibility conditions are satisied. This resolves the existence conjecture for large sets of designs for all 9t"> k 9 t .

  • 关键词:Combinatorial Designs ; Large Sets ; lattice ; Local Central Limit Theorem ; Random Walks
国家哲学社会科学文献中心版权所有