Abstract We prove a new lower bound for the almost 20-year-old problem of determining the smallest possible size of an essential cover of the $n$ -dimensional hypercube $\{\pm 1\}^n$ , that is, the smallest possible size of a collection of hyperplanes that forms a minimal cover of $\{\pm 1\}^n$ and such that, furthermore, every variable appears with a non-zero coefficient in at least one of the hyperplane equations. We show that such an essential cover must consist of at least $10^{-2}\cdot n^{2/3}/(\log n)^{2/3}$ hyperplanes, improving previous lower bounds of Linial–Radhakrishnan, of Yehuda–Yehudayoff, and of Araujo–Balogh–Mattos.

Lisa Sauermann

Zixuan Xu

Combinatorics Probability Computing

双月刊出版的《组合数学、概率与计算》致力于组合数学、概率论和理论计算机科学三个领域。涵盖的主题包括经典和代数图论、极值集理论、拟阵理论、概率方法和随机组合结构；随机组合结构的组合概率和极限定理；算法理论（包括复杂性理论）、随机算法、算法概率分析、计算学习理论和优化。

"Combinatorics Probability and Computing" is a bi-monthly journal dedicated to the fields of combinatorial mathematics, probability theory, and theoretical computer science. The topics covered include classical and algebraic graph theory, extremal set theory, matroid theory, probabilistic methods, and random combinatorial structures; combinatorial probabilities and limit theorems of random combinatorial structures; algorithm theory (including complexity theory), randomized algorithms, probabilistic analysis of algorithms, computational learning theory, and optimization.

《Combinatorics Probability and Computing》是一本双月刊，专注于组合数学、概率论和理论计算机科学三个领域。期刊涵盖的主题包括经典和代数图论、极值集理论、拟阵理论、概率方法和随机组合结构；随机组合结构的组合概率和极限定理；算法理论（包括复杂性理论）、随机算法、算法概率分析、计算学习理论和优化。

Category	Quartile
数学	4
数学, 统计学与概率论	3
数学, 计算机理论方法	4
数学, 数学	4

Essential covers of the hypercube require many hyperplanes

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info

Category	Quartile
STATISTICS & PROBABILITY	3