An asymptotic isoperimetric inequality (Q1266178)

For a finite metric space \(V\) with a metric \(\rho\) and probability measure \(\mu\), let \(V^n\) be the product metric space in which the distance between \(a= (a_1,\dots, a_n)\) and \(b= (b_1,\dots, b_n)\) is \(\rho_n(a,b)= \sum_i\rho(a_i, b_i)\) and the measure \(\mu_n(a_1,\dots, a_n)= \prod_i\mu(a_i)\). For any \(d\geq 0\) the \(d\)-neighbourhood of \(S\subseteq V^n\) is \[ B[S,d]= \{u\in V^n: \exists v\in S,\;\rho_n(u,v)\leq d\}. \] The authors are interested in maximizing \(\mu_n(V^n\setminus B[S,d])\) over all sets \(S\) with \(\mu_n(S)\geq 1/2\). Their central result provides an asymptotic formula for the logarithm of the corresponding maximum when \(n\to\infty\) and \(d/\sqrt n\to\infty\). The authors provide self-contained probabilistic proofs of their results. As they note, the formulations of results are closely related to the probabilistic theory of large deviations.