Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is combinatorics but similar things come up sometimes in theoretical computer science, for example in randomness extraction.

Define:

$d(x,y)=$ the Hamming distance between binary strings $x$ and $y$ of length $n$, $=$ the cardinality of $\{k: x(k)\ne y(k)\}$.

For a set of strings $A$,

$d(x,A)=\min \{ d(x,y): y\in A\}$.

The $r$-fold boundary of $A\subseteq \{0,1\}^n$ is

$$\{x\in\{0,1\}^n: 0 < d(x,A)\le r\}.$$

Balls centered at $0$ are given by

$$ B(p)=\{x: d(x,0)\le p\}, $$ where $0$ is the string of $n$ many zeroes.

A Hamming-sphere is a set $H$ with $B(p)\subseteq H\subseteq B(p+1)$. (So it's more like a ball than a sphere, but this is the standard terminology...)

Now, Harper in 1966 showed that for each $k$, $n$, $r$, one can find a Hamming-sphere that has minimal $r$-fold boundary among sets of cardinality $k$ in $\{0,1\}^n$. So a ball is a set having minimal boundary -- just like in Euclidean space.

The cardinality of $B(p)$ is ${n\choose 0}+\cdots {n\choose p}$.

The $r$-fold boundary of $B(p)$ is just the set $B(p+r)\setminus B(p)$, which then has cardinality ${n\choose p+1}+\cdots+{n\choose p+r}$.

So far, so good. But now suppose we replace $d$ by a different metric $D$: first let $d_j(x,y)$ be the Hamming distance between the prefixes of $x$ and $y$ of length $j$, and then $$ D(x,y)=\max_{j\le n}\ \frac{d_j(x,y)}{f(j) }$$ where $0\le f(j)\le j$. (For example we could have $f(j)=\sqrt{j}$, or $f(j)=j/\log j$.)

This is supposed to make $D(x,y)$ small if the differences of $x$ and $y$ do not clump together at small values of $j$.

Questions

Is the minimum $r$-fold boundary (under $D$) realized by a $D$-ball?

Is there a better definition of $D$?

Under the metric $D$, what's the minimum size of the $r$-fold boundary of a subset of $\{0,1\}^n$ having cardinality $k$? (A reasonable lower bound would be nice.)

(Cross-posted on CSTheory).

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.