On sait qu'à volume fixé, parmi les objets dans $\mathbb{R}^d$, c'est la boule euclidienne qui minimise la surface. Pour généraliser cette notion à un contexte abstrait, on peut formuler cette idée de façon équivalente comme:
De tous les objets $A$ d'un volume fixé dans $\mathbb{R}^d$, l'objet tel que l'ensemble $A_t = \{x \in \mathbb{R}^d, d(x, A) \leq t\}$ a le volume minimal (ici $Leb(A_t)$) est la boule Euclidienne.
Une inégalité sera dite isopérimétrique si elle est de la forme $\mathbb{P}(A_t) \geq f(\mathbb{P}(A))$, où $A_t$ est défini à partir d'une distance quelconque, et $f$ est une fonction qui peut dépendre de $t$.
Soit $(\Omega, \mathcal(A), \mu)$ un espace de probabilité. On peut considérer $\Omega$ métrique, et $\mathcal{A} = \mathcal{B}(\Omega)$.
On note $\mathbb{P} = \mu^{\otimes n}$ sur $\Omega^n$.
Distance de Talagrand
Pour tout $x \in \Omega^n$, pour tout $A$ fermé de $\Omega^n$, on note : $$d_T(x, A) = \sup_{\alpha \in \mathbb{R}^n, \|\alpha \|_2 = 1} \inf_{y \in A} \sum_{i=1}^n \alpha_i \mathbb{1}_{x_i \neq y_i}.$$
Remarque
On a $$d_T(x,A) \geq \frac{1}{\sqrt{n}} \inf_{y \in A} \sum_{i=1}^n \mathbb{1}_{x_i \neq y_i}.$$
Théorème
Soit $X$ de loi $\mathbb{P}$. On a, pour tout $A$ sous-ensemble de $\mathbb{R}^n$, $$\mathbb{E}\left[ e^{d_T(x,A)/4} \right] \leq \frac{1}{\mathbb{P}(A)}$$ On obtient $$\mathbb{P}(A^c_t) = \mathbb{P}(d_T(X, A)> t) \leq \frac{e^{-t^2/4}}{\mathbb{P}(A)}.$$ Ainsi, on obtient l'inégalité isopérimétrique: $$\mathbb{P}(A_t) \geq 1- \frac{e^{-t^2/4}}{\mathbb{P}(A)}.$$
Soit $\Omega = [0,1]$, $\mu = Leb$.
Si $x = (x_1, \dots, x_n)$ est dans $[0,1]^n$, on appelle sous-suite croissante une sous-suite $(x_{i_1}, \dots, x_{i_k})$ telle que $i_1 < \dots < i_k$.
On note $I_n(x)$ la longueur des plus longues sous-suites croissantes.
On note $M$ la médiane de $I_n$.
Théorème On a pour tout $u >0$, $$\mathbb{P}(I_n(X) \geq M+u) \leq 2 \exp\left(- \frac{u^2}{4(M+u)} \right)$$ et $$\mathbb{P}(I_n(X) \leq M+u) \leq 2 \exp\left(- \frac{u^2}{4M} \right).$$
J. Michael Steele. Probability Theory and Combinatorial Optimization (1997). Society for Industrial and Applied Mathematics.
Michel Talagrand. Concentration of measure and isoperimetric inequalities in product spaces (1995). Publications mathématiques de l'I.H.É.S. Disponible sur ce lien .