On Mappings on the Hypercube with Small Average Stretch

Abstract: Let

A s u b s e t e q {0, 1}^{n}

be a set of size

2^{n - 1}

, and let

p h i c o l o n {0, 1}^{n - 1} o A

be a bijection. We define the average stretch of

p h i

as

s f a v g S t r e t c h (p h i) = m a t h b b E [s f d i s t (p h i (x), p h i (x^{'}))]

, where the expectation is taken over uniformly random

x, x^{'} i n {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. (1) For any set

A s u b s e t e q {0, 1}^{n}

of density

1 / 2

there exists a bijection

p h i_{A} c o l o n {0, 1}^{n - 1} o A

such that

s f a v g s t r e t c h (p h i_{A}) = O (s q r t n)

. (2) For

n = 3^{k}

let

A_{s f r e c e x t - m a j} = x i n {0, 1}^{n} : s f r e c e x t - m a j (x) = 1

, where

s f r e c e x t - m a j : {0, 1}^{n} o 0, 1

is the function recursive majority of 3's. There exists a bijection

p h i_{s f r e c e x t - m a j} c o l o n {0, 1}^{n - 1} o A_{s f r e c e x t - m a j}

such that

s f a v g s t r e t c h (p h i_{s f r e c e x t - m a j}) = O (1)

. (3) Let

A_{s f t r i b e s} = x i n {0, 1}^{n} : s f t r i b e s (x) = 1

. There exists a bijection

p h i_{s f t r i b e s} c o l o n {0, 1}^{n - 1} o A_{s f t r i b e s}

such that

s f a v g s t r e t c h (p h i_{s f t r i b e s}) = O (l o g (n))

. These results answer the questions raised by Benjamini et al. (FOCS 2014).

This page was built for publication: On Mappings on the Hypercube with Small Average Stretch

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6319454)