论文标题
多维数据集基本覆盖的新下限
New Lower Bounds For Essential Covers Of The Cube
论文作者
论文摘要
$ n $ -cube $ \ {0,1 \}^n $的顶点的基本覆盖物是一个最小的覆盖物，其中没有超平面是冗余的，并且每个变量至少出现在一个至少一个超平面的方程中。 Linial和Radhakrishnan用$ \ lceil \ frac {n} {2} {2} \ rceil + 1 $ hyperplanes进行了基本封面的结构，并表明需要$ω（\ sqrt {n}）$ hyperpranes。最近，Yehuda和Yehudayoff通过表明$ n $ -Cube的任何基本覆盖物至少包含$ω（n^{0.52}）$超plans，改善了下限。在本文中，以Yehuda和Yehudayoff的方法为基础，我们证明了$ω\ left（\ frac {n^{5/9}}} {（\ log n）^{4/9}}} \ right）$ hyperplanes是需要的。
An essential cover of the vertices of the $n$-cube $\{0,1\}^n$ by hyperplanes is a minimal covering where no hyperplane is redundant and every variable appears in the equation of at least one hyperplane. Linial and Radhakrishnan gave a construction of an essential cover with $\lceil \frac{n}{2} \rceil + 1$ hyperplanes and showed that $Ω(\sqrt{n})$ hyperplanes are required. Recently, Yehuda and Yehudayoff improved the lower bound by showing that any essential cover of the $n$-cube contains at least $Ω(n^{0.52})$ hyperplanes. In this paper, building on the method of Yehuda and Yehudayoff, we prove that $Ω\left( \frac{n^{5/9}}{(\log n)^{4/9}} \right)$ hyperplanes are needed.
