New Lower Bounds For Essential Covers Of The Cube

2022/08/31 by Igor Araújo, Araujo, Igor, József Balogh +3 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Packing Problems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2209.00140

openalex publication_date 2022/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An essential cover of the vertices of the n-cube \0,1\ⁿ 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 (n)/(2) \rceil + 1 hyperplanes and showed that Ω(√(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 Ω( \fracn^5/9(log n)^4/9 ) hyperplanes are needed.

Cited by

• Nondegenerate hyperplane covers of the hypercube

Related

• A lower bound for essential covers of the cube
• Stability for hyperplane covers
• On almost k-covers of hypercubes
• Nondegenerate hyperplane covers of the hypercube
• On higher multiplicity hyperplane and polynomial covers for symmetry preserving subsets of the hypercube