Probabilistic existence of large sets of designs
Probabilistic existence of large sets of designs
复制标题
大量设计的概率存在
DOI：
10.1016/j.jcta.2020.105286
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Vardy, Alexander
中科院分区：
文献类型：
--
作者：
Lovett, Shachar;Rao, Sankeerth;Vardy, Alexander
Kuperberg、Lovett 和 Peled 最近提出了一种新的概率技术，用于确定某些规则组合结构的存在性（STOC 2012）。使用这种技术，可以证明，在某些条件下，随机选择的结构具有 at-(n, k, λ) 组合设计所需的属性，概率很小，但为正。在这里，我们强化了 Kuperberg、Lovett 和 Peled 的方法和结果，如下所示。我们修改了随机选择和分析，以表明在相同条件下，不仅存在 at-(n,k,λ) 设计，而且事实上，以正概率存在大量此类设计 — 即，将 [n] 的 k 子集集合划分为 t-(n, k, λ) 设计。具体来说，使用本文导出的概率方法，我们证明对于所有足够大的大集合 t-(n, k, λ) 设计，只要 k> 9t 且满足必要的整除条件，就存在。这解决了 allk> 9t 的大型设计集的存在猜想。
A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been recently 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 at-(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 at-(n,k,λ) design exist but, in fact, with positive probability there exists alarge setof such designs — that is, a partition of the set ofk-subsets of [n] intot-(n, k, λ) designs. Specifically, using the probabilistic approach derived herein, we prove that for all sufficiently largen, large sets oft-(n, k, λ) designs exist wheneverk> 9tand the necessary divisibility conditions are satisfied. This resolves the existence conjecture for large sets of designs for allk> 9t.