About almost covering subsets of the hypercube
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914622276108288 |
|---|---|
| author | Ghosh, Arijit Kayal, Chandrima Nandi, Soumi |
| author_facet | Ghosh, Arijit Kayal, Chandrima Nandi, Soumi |
| contents | Let $\mathbb{F}$ be a field, and consider the hypercube $\{ 0, 1 \}^{n}$ in $\mathbb{F}^{n}$. Sziklai and Weiner (Journal of Combinatorial Theory, Series A 2022) showed that if a polynomial $P ( X_{1}, \dots, X_{n} ) \in \mathbb{F}[ X_{1}, \dots, X_{n}]$ vanishes on every point of the hypercube $\{0,1\}^{n}$ except those with at most $r$ many ones then the degree of the polynomial will be at least $n-r$. This is a generalization of Alon and Füredi's fundamental result (European Journal of Combinatorics 1993) about polynomials vanishing on every point of the hypercube except at the origin (point with all zero coordinates). Sziklai and Weiner proved their interesting result using Möbius inversion formula and the Zeilberger method for proving binomial equalities. In this short note, we show that a stronger version of Sziklai and Weiner's result can be derived directly from Alon and Füredi's result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_10573 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | About almost covering subsets of the hypercube Ghosh, Arijit Kayal, Chandrima Nandi, Soumi Combinatorics Discrete Mathematics 05D40, 51D20 F.2.2; G.2.1 Let $\mathbb{F}$ be a field, and consider the hypercube $\{ 0, 1 \}^{n}$ in $\mathbb{F}^{n}$. Sziklai and Weiner (Journal of Combinatorial Theory, Series A 2022) showed that if a polynomial $P ( X_{1}, \dots, X_{n} ) \in \mathbb{F}[ X_{1}, \dots, X_{n}]$ vanishes on every point of the hypercube $\{0,1\}^{n}$ except those with at most $r$ many ones then the degree of the polynomial will be at least $n-r$. This is a generalization of Alon and Füredi's fundamental result (European Journal of Combinatorics 1993) about polynomials vanishing on every point of the hypercube except at the origin (point with all zero coordinates). Sziklai and Weiner proved their interesting result using Möbius inversion formula and the Zeilberger method for proving binomial equalities. In this short note, we show that a stronger version of Sziklai and Weiner's result can be derived directly from Alon and Füredi's result. |
| title | About almost covering subsets of the hypercube |
| topic | Combinatorics Discrete Mathematics 05D40, 51D20 F.2.2; G.2.1 |
| url | https://arxiv.org/abs/2409.10573 |