Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances

Details Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances

2012-02-28

arxiv.org/abs/1202.6260v1

Computer Science

Discrete Mathematics

Scientific paper

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 ${\rm dr}(L):=\max \{\rho(x,y):\ x,y \in L\}/ \min \{\rho(x,y):\ x,y \in L,\ x\neq y\},$ where $\rho(x,y)$ is the Hamming distance between $x$ and $y$. We prove that (a) there are no positive constants $\alpha$ and $C$ such that every set $K$ of vectors with weight $p$ contains a subset $K'$ with $|K'|\ge |K|^{\alpha}$ and ${\rm dr}(K')\le C$, even when $|K|\ge 2^p$, (b) for a set $K$ of vectors with weight $p$, and a constant $C>2$, there exists $K'\subseteq K$ such that ${\rm dr}(K)\le C$ and $K' \ge |K|^\alpha$, where $\alpha = 1/ \lceil \log(p/2)/\log(C/2) \rceil$.

Affiliated with

Also associated with

No associations

Rating

Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-611255