Name
Title | ||
|---|---|---|
Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances |
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 ${\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) for every constant $\lambda>1$ there are no positive constants $\alpha$ and $C$ such that every set $K$ of at least $\lambda^p$ vectors with weight $p$ contains a subset $K'$ with $|K'|\ge |K|^{\alpha}$ and ${\rm dr}(K')\le C$, % even when $|K|\ge \lambda$, (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$. |
Year | Venue | Field |
|---|---|---|
2012 | arXiv: Discrete Mathematics | Discrete mathematics,Combinatorics,Hamming distance,Mathematics,Lambda,Binary number |
DocType | Volume | Citations |
Journal | abs/1202.6260 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gregory Gutin | 1 | 1583 | 142.47 |
| Mark Jones | 2 | 25 | 7.09 |