Essential covers of the hypercube require many hyperplanes
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918002814877696 |
|---|---|
| author | Sauermann, Lisa Xu, Zixuan |
| author_facet | Sauermann, Lisa Xu, Zixuan |
| contents | 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$, i.e. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_05775 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Essential covers of the hypercube require many hyperplanes Sauermann, Lisa Xu, Zixuan Combinatorics 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$, i.e. 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. |
| title | Essential covers of the hypercube require many hyperplanes |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.05775 |