We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On mappings on the hypercube with small average stretch.
- Authors
Boczkowski, Lucas; Shinkar, Igor
- Abstract
Let $A \subseteq \{0,1\}^n$ be a set of size $2^{n-1}$ , and let $\phi \,:\, \{0,1\}^{n-1} \to A$ be a bijection. We define the average stretch of $\phi$ as \begin{equation*} {\sf avgStretch}(\phi) = {\mathbb E}[{{\sf dist}}(\phi (x),\phi (x'))], \end{equation*} where the expectation is taken over uniformly random $x,x' \in \{0,1\}^{n-1}$ that differ in exactly one coordinate. In this paper, we continue the line of research studying mappings on the discrete hypercube with small average stretch. We prove the following results. For any set $A \subseteq \{0,1\}^n$ of density $1/2$ there exists a bijection $\phi _A \,:\, \{0,1\}^{n-1} \to A$ such that ${\sf avgStretch}(\phi _A) = O\left(\sqrt{n}\right)$. For $n = 3^k$ let ${A_{\textsf{rec-maj}}} = \{x \in \{0,1\}^n \,:\,{\textsf{rec-maj}}(x) = 1\}$ , where ${\textsf{rec-maj}} \,:\, \{0,1\}^n \to \{0,1\}$ is the function recursive majority of 3's. There exists a bijection $\phi _{{\textsf{rec-maj}}} \,:\, \{0,1\}^{n-1} \to{A_{\textsf{rec-maj}}}$ such that ${\sf avgStretch}(\phi _{{\textsf{rec-maj}}}) = O(1)$. Let ${A_{{\sf tribes}}} = \{x \in \{0,1\}^n \,:\,{\sf tribes}(x) = 1\}$. There exists a bijection $\phi _{{\sf tribes}} \,:\, \{0,1\}^{n-1} \to{A_{{\sf tribes}}}$ such that ${\sf avgStretch}(\phi _{{\sf tribes}}) = O(\!\log (n))$. These results answer the questions raised by Benjamini, Cohen, and Shinkar (Isr. J. Math 2016).
- Subjects
ISRAEL; RECURSIVE functions; BIJECTIONS; TRIBES
- Publication
Combinatorics, Probability & Computing, 2023, Vol 32, Issue 2, p334
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S0963548322000281