Note on large subsets of binary vectors with similar distances

Authors:

Abstract: We consider vectors from

{0, 1}^{n}

. The weight of such a vector

v

is the sum of the coordinates of

v

. The distance ratio of a set

L

of vectors is

m d r (L) := m a x h o (x, y) : x, y i n L / m i n h o (x, y) : x, y i n L, x e q y,

where

h o (x, y)

is the Hamming distance between

x

and

y

. We prove that (a) for every constant

l a m b d a > 1

there are no positive constants

a l p h a

and

C

such that every set

K

of at least

l a m b d a^{p}

vectors with weight

p

contains a subset

K^{'}

with

| K^{'} | g e | K |^{a l p h a}

and

m d r (K^{'}) l e C

, % even when

| K | g e l a m b d a

, (b) For a set

K

of vectors with weight

p

, and a constant

C > 2

, there exists

K^{'} s u b s e t e q K

such that

m d r (K^{'}) l e C

and

| K^{'} | g e | K |^{a} l p h a

, where

a l p h a = 1 / l c e i l l o g (p / 2) / l o g (C / 2) c e i l

.

Recommendations

Cited In (3)

This page was built for publication: Note on large subsets of binary vectors with similar distances