= Concentration of discrete cubes at diameter scale
{title2=$d_n(x,y)=d_{Q_n}(x,y)/n$}
Equip the <Boolean hypercube> with uniform <probability measure> and <graph distance> divided by its <graph diameter>. These spaces form a <Lévy family of graphs>. The <vertex-isoperimetric inequality in the discrete cube> reduces the complement of a positive-density <set>'s radius-$\varepsilon n$ <graph neighbourhood> to a <binomial distribution> tail. For fixed density $\delta>0$, <Chebyshev's inequality> puts a lower density quantile at least $n/2-C_\delta\sqrt n-O(1)$. After enlarging by $\varepsilon n$, the omitted mass is at most $n/[4(\varepsilon n-C_\delta\sqrt n-O(1))^2]$, which tends to zero.
Back to article page
