Algebraic Graph Theory Seminar - Qianqian Yang
Title: Essential Covers of the Cube by Hyperplanes
Speaker: | Igor Araujo |
Affiliation: | University of Illinois Urbana-Champaign |
Location: | contact Sabrina Lato for Zoom link |
Abstract: 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 $\Omega(\sqrt{n})$ hyperplanes are required.