论文标题
部分可观测时空混沌系统的无模型预测
Expansion of random $0/1$ polytopes
论文作者
论文摘要
Mihail和Vazirani的猜想指出，每$ 0/1 $ polytope的图形的边缘膨胀至少一个。边缘膨胀上的任何下限都可以在多层图上随机行走的混合时间上的上限。这样的随机步行很重要，因为它们可用于随机均匀地从一组组合对象中生成元素。 Mihail和Vazirani的猜想的一种较弱的形式说，$ 0/1 $ polytope的边缘扩展在$ \ Mathbb {r}^d $中比$ d $的某些多项式函数大于1。这种猜想的较弱版本足以满足所有应用程序。我们的主要结果是，$ \ textit {andural} $ $ 0/1 $ polytope in $ \ mathbb {r}^d $的边缘扩展至少是$ \ frac {1} {1} {12D} $，概率很高。
A conjecture of Mihail and Vazirani states that the edge expansion of the graph of every $0/1$ polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a $0/1$ polytope in $\mathbb{R}^d$ is greater than 1 over some polynomial function of $d$. This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of a $\textit{random}$ $0/1$ polytope in $\mathbb{R}^d$ is at least $\frac{1}{12d}$ with high probability.
