Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2410.20498 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912089404080128 |
|---|---|
| author | Alon, Noga Axenovich, Maria Goldwasser, John |
| author_facet | Alon, Noga Axenovich, Maria Goldwasser, John |
| contents | Let $d \geq 1$ and $s \leq 2^d$ be nonnegative integers. For a subset $A$ of vertices of the hypercube $Q_n$ and $n\geq d$, let $λ(n,d,s,A)$ denote the fraction of subcubes $Q_d$ of $Q_n$ that contain exactly $s$ vertices of $A$. Let $λ(n,d,s)$ denote the maximum possible value of $λ(n,d,s,A)$ as $A$ ranges over all subsets of vertices of $Q_n$, and let $λ(d,s)$ denote the limit of this quantity as $n$ tends to infinity. We prove several lower and upper bounds on $λ(d,s)$, showing that for all admissible values of $d$ and $s$ it is larger than $0.28$. We also show that the values of $s=s(d)$ such that $λ(d,s)=1$ are exactly $\{0,2^{d-1},2^d\}$. In addition we prove that if $0<s< d/8$, then $λ(d, s) \leq 1 - Ω(1/s)$, and that if $s$ is divisible by a power of $2$ which is $Ω(s)$ then $λ(d,s) \geq 1-O(1/s)$. We suspect that $λ(d,1)=(1+o(1))/e$ where the $o(1)$-term tends to $0$ as $d$ tends to infinity, but this remains open, as does the problem of obtaining tight bounds for essentially all other quantities $λ(d,s)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_20498 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On hypercube statistics Alon, Noga Axenovich, Maria Goldwasser, John Combinatorics Let $d \geq 1$ and $s \leq 2^d$ be nonnegative integers. For a subset $A$ of vertices of the hypercube $Q_n$ and $n\geq d$, let $λ(n,d,s,A)$ denote the fraction of subcubes $Q_d$ of $Q_n$ that contain exactly $s$ vertices of $A$. Let $λ(n,d,s)$ denote the maximum possible value of $λ(n,d,s,A)$ as $A$ ranges over all subsets of vertices of $Q_n$, and let $λ(d,s)$ denote the limit of this quantity as $n$ tends to infinity. We prove several lower and upper bounds on $λ(d,s)$, showing that for all admissible values of $d$ and $s$ it is larger than $0.28$. We also show that the values of $s=s(d)$ such that $λ(d,s)=1$ are exactly $\{0,2^{d-1},2^d\}$. In addition we prove that if $0<s< d/8$, then $λ(d, s) \leq 1 - Ω(1/s)$, and that if $s$ is divisible by a power of $2$ which is $Ω(s)$ then $λ(d,s) \geq 1-O(1/s)$. We suspect that $λ(d,1)=(1+o(1))/e$ where the $o(1)$-term tends to $0$ as $d$ tends to infinity, but this remains open, as does the problem of obtaining tight bounds for essentially all other quantities $λ(d,s)$. |
| title | On hypercube statistics |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.20498 |