Lévy family of graphs (${\alpha }_n(\epsilon )\to 0$)

A Lévy family of graphs consists of finite connected graphs with their uniform probability measures and graph distances divided by their diameters, whose concentration of measure functions vanish at every fixed positive normalized radius. Equivalently, every family occupying at least half the vertices has a radius-$\lfloor \epsilon D_n\rfloor$ neighbourhood occupying a proportion tending to one, uniformly over such families. Harper theorem and binomial distribution tail bounds prove this for the hypercube graphs.

Equip $[n{]}^d$ with uniform probability measure and its nearest-neighbour graph distance divided by $d(n-1)$, for fixed positive $d$. The set $\{x:x_1\le \lceil n/2\rceil \}$ has at least half the vertices. Its radius-$\epsilon d(n-1)$ graph neighbourhood still omits a proportion tending to $1/2-\epsilon d$ when $0<\epsilon <1/(2d)$. These grids therefore do not form a Lévy family of graphs.

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-$\epsilon 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 $\epsilon n$, the omitted mass is at most $n/[4(\epsilon n-C_{\delta }\sqrt{n}-O(1){)}^2]$, which tends to zero.