TY - JOUR
T1 - New lower bounds for essential covers of the cube
AU - Araujo, Igor
AU - Balogh, József
AU - Mattos, Letícia
N1 - J. Balogh was partially supported by NSF Grant DMS-1764123, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000), the Langan Scholar Fund (UIUC), the Simons Fellowship, and NSF RTG Grant DMS-1937241.
I. Araujo was partially supported by UIUC Campus Research Board RB 22000.
L. Mattos was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany\u2019s Excellence Strategy \u2013 The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). Acknowledgements
PY - 2024
Y1 - 2024
N2 - 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 ⌈n2⌉+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 Ω(n0.52) hyperplanes. In this paper, building on the method of Yehuda and Yehudayoff, we prove that Ω(n5/9(logn)4/9) hyperplanes are needed.
AB - 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 ⌈n2⌉+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 Ω(n0.52) hyperplanes. In this paper, building on the method of Yehuda and Yehudayoff, we prove that Ω(n5/9(logn)4/9) hyperplanes are needed.
UR - http://www.scopus.com/inward/record.url?scp=85211450056&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85211450056&partnerID=8YFLogxK
U2 - 10.1007/s11856-024-2695-9
DO - 10.1007/s11856-024-2695-9
M3 - Article
AN - SCOPUS:85211450056
SN - 0021-2172
JO - Israel Journal of Mathematics
JF - Israel Journal of Mathematics
ER -