Timeline for Isoperimetric inequality on the Hamming cube
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 7, 2015 at 4:46 | vote | accept | rajatsen91 | ||
| May 7, 2015 at 3:36 | answer | added | Yoav Kallus | timeline score: 6 | |
| May 6, 2015 at 21:11 | comment | added | rajatsen91 | The $1/2$ is not a typo I think. But it is trivial to prove this for $\delta = 1/10$ . The cited reference is a 1966 paper by Kleitman, but I am having trouble using the results there to prove this. | |
| May 6, 2015 at 21:03 | comment | added | Benoît Kloeckner | @rajatsen91: did you have a look at the cited reference (Kleitman 1966)? Moreover, reading below the lemma it is written that other factors than $1/2$ in the distance lower bound would do for that paper, and the choice cited is $1/10$. Given Robert Israel's answer, I would bet that the $1/2$ in the paper is a typo. | |
| May 6, 2015 at 20:36 | comment | added | Christian Remling | @YoavKallus: I think this gets you to about (not quite) $D=m/3$, but it doesn't seem good enough for the full claim. | |
| May 6, 2015 at 20:05 | comment | added | rajatsen91 | @BenoîtKloeckner : I found this stated without a proof in a paper. math.washington.edu/~rothvoss/publications/… | |
| May 6, 2015 at 20:03 | answer | added | Robert Israel | timeline score: 5 | |
| May 6, 2015 at 19:25 | comment | added | Yoav Kallus | Did you try the following: Let $D$ be the diameter of $X$, i.e., $\max_{x,y\in X} ||x-y||$, then $X$ is in the intersection of two Hamming balls of radius $D$ with centers a distance $D$ apart. Does this give you a tight enough bound? | |
| May 6, 2015 at 19:04 | comment | added | Benoît Kloeckner | Why "isoperimetric inequality"? This looks like something that should follow from the concentration of measure phenomenon. Why are you interested in this? | |
| May 6, 2015 at 17:58 | history | edited | GH from MO | CC BY-SA 3.0 |
fixed spelling
|
| May 6, 2015 at 15:55 | history | asked | rajatsen91 | CC BY-SA 3.0 |