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

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.