\documentclass[8pt]{beamer}
\usepackage[ansinew]{inputenc}
\usepackage{amssymb, color}
\usepackage[french]{babel}
\usepackage{graphicx}
\usepackage{beamerthemesplit}

\title{Avatars du théorème de plongement d'Assouad}
\author{P. Pansu}
\date{13 avril 2011}

\newtheorem{thm}{Théorème}
\newtheorem{lem}{Lemme}
\newtheorem{prop}[lem]{Proposition}
\newtheorem{cor}[lem]{Corollaire}
\newtheorem{defi}[lem]{Définition}
\newtheorem{rem}[lem]{Remarque}
\newtheorem{nota}[lem]{Notation}
\newtheorem{ques}[lem]{Question}
\newtheorem{prob}[lem]{Problème}
\newtheorem{sol}[lem]{Solution}
\newtheorem{conc}[lem]{Conclusion}
\newtheorem{ex}[lem]{Exemple}
\newtheorem{exs}[lem]{Exemples}
\newtheorem{res}[lem]{Résultats}
\newtheorem{plan}[lem]{Plan of lecture}
\newtheorem{scheme}[lem]{Schéma de la preuve}

\def\proof{\par\medskip\noindent {\bf Preuve}}
\def\qed{~q.e.d.}

\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\H{\mathbb{H}}
\def\N{\mathbb{N}}
\def\holder{Holder}
\def\n#1{{|\hskip-1pt | #1 |\hskip-1pt |}}
\def\eps{\epsilon}

\mode<presentation>{\usetheme{Warsaw}}

\begin{document}


\begin{frame}
\titlepage
\end{frame}

\begin{frame}
On décrit le problème du plongement d'espaces doublants dans des espaces euclidiens.%\pause

\medskip

\begin{enumerate}
\item Assouad (1983) : plongement en dimension dépendant de l'exposant.%\pause
\item Naor et Neiman (décembre 2010) : plongement en dimension indépendante de l'exposant.%\pause
\item Lien avec avec les empilements de boules.%\pause
\item Thurston 1993, Benjamini et Schramm (1995-2010) : résultats sur les empilements de boules.
\item Preuve du théorème de Naor et Neiman.
\end{enumerate}


\end{frame}

\section{Plongements fractionnaires}

\begin{frame}

%\begin{thm}
%\textcolor{red}{\em (Bourgain 1985, Johnson-Lindenstrauss 1982)}. Every
%$n$-point metric space embeds in $\ell_{2}^{O(\log n)}$ with distorsion $O(\log n)$.
%\end{thm}

\begin{defi}[\textcolor{red}{Bouligand 1928}]
La \emph{dimension métrique} $\mathrm{dim}(X)$ d'un espace métrique $X$ est la borne inférieure des $d$ tels qu'il existe $C$ tel que pour tout sous-ensemble $a$-séparé $Y\subset X$ de diamètre $D$, $|Y|\leq C\,(\frac{D}{a})^{d}$.
\end{defi}%\pause

\begin{ex}
$\R^n$, $Heis^{n}$ ($n$ impair) ont une dimension métrique linéaire en $n$.
\end{ex}%\pause

%Motivation: Russ Cox, Frank Dabek, Frans Kaahoek, Jinyang Li and Robert
%Morris's Vivaldi software embeds large parts of the Internet equipped with
%its latency metric in bounded dimensional Euclidean space with distorsion
%$<1.15$. Latency is time taken by packets to travel from a node to an
%other. 

%\begin{thm}
%\textcolor{red}{\em (Gupta, Krauthgamer, Lee 2003)}. Let $p\geq 1$. Every
%$n$-point metric space embeds in $\ell_{p}$ with distorsion 
%$$O(\mathrm{dim}(X)(\log n)^{\mathrm{min}(\frac_{1}{2},\frac{1}{p})}).$$

%This is sharp for $p=2$: there are $n$-point metric spaces (Laakso spaces)
%of uniformly bounded doubling dimension, which require distorsion
%$\Omega(\sqrt{\log n})$ when embedded in $\ell_{2}$. And for $p=1$ as well
%\textcolor{red}{\em (Lee, Mendel, Naor 2004)}: the same Laakso spaces require distorsion $\Omega(\sqrt{\frac{\log n}{\log D}})$ when embedded in $\ell_{1}^{D}$. 
%\end{thm}

\begin{rem}
Si $X$ a un plongement bilipschitzien dans $Y$, alors $\mathrm{dim}(X)\leq\mathrm{dim}(Y)$. Si $X'=(X,d_{X}^{1-\epsilon})$, alors $\mathrm{dim}(X')=\frac{1}{1-\epsilon}\mathrm{dim}(X)$.
\end{rem}%\pause

\begin{thm}[\textcolor{red}{Assouad 1983}]
Pour tout $\epsilon\in(0,1)$ et $d>0$, il existe $D(d,\epsilon)$ et $N(d,\epsilon)$ tels que pour tout espace métrique $X$ de dimension $d$, la {\em métrique fractionnaire}
$(X,d_{X}^{1-\epsilon})$ admet un plongement bilipschitzien dans l'espace euclidien $\ell_{2}^{N}$ de distorsion $\leq D$.
\end{thm}
%\pause

\begin{ques}
Donner des bornes optimales sur $D$ and $N$.
\end{ques}

\end{frame}

\subsection{Dimension des plongements fractionnaires}

\begin{frame}

\begin{thm}[\textcolor{red}{Gupta, Krauthgamer, Lee 2003; Lee, Mendel, Naor 2004}]
Dans le théorème d'Assouad, on peut prendre
$N\leq O(\frac{d\log d}{\epsilon})$ et
$D\leq O(\frac{d}{\sqrt{\epsilon}})$. 
% back of the envelope calculation by James Lee
\end{thm}%\pause

\begin{thm}[\textcolor{red}{Naor, Neiman décembre 2010}]
Dans le théorème d'Assouad, on peut prendre, pour tout $\theta\in]0,1]$,
$N\leq O(\frac{d}{\theta})$ et
$D\leq O((\frac{d}{\epsilon})^{1+\theta})$. 
\end{thm}%\pause

\begin{rem}
A une constante près, c'est optimal, car $N\geq\frac{\mathrm{Hausdim}(X)}{1-\eps}\geq\Omega(d)$.%\pause
\end{rem}

\begin{ques}
Dans des exemples, donner une meilleure borne inférieure sur la dimension du plongement.
\end{ques}%\pause

\begin{thm}[\textcolor{red}{Kahane 1981, Assouad 1983}]
Pour l'espace euclidien $(\ell_2^d ,d_{\ell_2}^{1-\eps})$, la dimension de plongement optimale est le plus petit entier strictement supérieur à $\frac{d}{1-\eps}$, i.e.
$N=\lfloor \frac{d}{1-\eps} \rfloor+1$. 
\end{thm}

\end{frame}

\section{Lien avec les empilements de boules}

\begin{frame}

\begin{defi}[\textcolor{red}{Benjamini, Schramm}]
Soit $G$ un graphe. $G$ est {\em empilable} dans $\R^d$ si $G$ est le graphe d'incidence d'un empilement de boules dans $\ell_2^d$.
\end{defi}%\pause

\begin{defi}[provisoire]
Soit $G$ un graphe. $G$ est {\em $k$-empilable} dans $\R^d$ si $G$ est le graphe de $k$-incidence d'un empilement de boules dans $\ell_2^d$ (i.e. on relie une boule $B$ à toutes les boules qui intersectent $kB$).

Un espace métrique $X$ est empilable dans $\R^d$ s'il est quasiisométrique à un graphe $k$-empilable dans $\R^d$.
\end{defi}%\pause

\begin{prop}
Soit $X$ un espace métrique à géométrie bornée. Si $X$ possède un plongement fractionnaire dans $\ell_2^d$, alors $X$ est empilable dans $\R^d$. 
\end{prop}


\end{frame}

\subsection{Séparation}

\begin{frame}

En 1979, R. Lipton et R. Tarjan ont trouvé un algorithme qui coupe en deux un graphe planaire en ôtant au plus $2\sqrt{2n}$ sommets. W. Thurston a proposé une autre méthode, reposant sur le théorème de Koebe qui réalise toute triangulation du plan comme graphe d'incidence d'un empilement de disques. En voici la généralisation $d$-dimensionnelle. 

\begin{thm}[\textcolor{red}{Miller, Teng, Thurston, Vavasis 1993-1998}]
Soit $G$ un graphe fini $k$-empilable dans $\R^d$, à $n$ sommets. Alors il existe un sous-ensemble $S$ de sommets de taille $|S|\leq O(k\,n^{(d-1)/d})$ qui sépare $G$ en deux sous-graphes de tailles $\leq \frac{d+1}{d+2}n$.
\end{thm}%\pause

Cela motive la définition suivante.
\begin{thm}[\textcolor{red}{Benjamini, Schramm}]
Soit $X$ un espace métrique à géométrie bornée. La {\em séparation} de $X$ est la plus petite fonction $sep_X :\R_+ \to\R_+$ telle que tout sous-espace de volume $n$ de $X$ puisse être séparé en deux morceaux de volume $\leq$ moitié par un ensemble $S$ tel que volume$(S+1)\leq sep_X (n)$.
\end{thm}%\pause

\begin{ex}[\textcolor{red}{Benjamini, Schramm}]
$sep_{\mathrm{arbre}}(n)=O(1)$, $sep_{\R^d}(n)=\Theta(n^{(d-1)/d})$, $sep_{\mathrm{arbre}\times\mathrm{arbre}}(n)=\Theta(\frac{n}{\log n})$. 
\end{ex}

\end{frame}

\subsection{Cohomologie \texorpdfstring{$L_p$}{}
}

\begin{frame}

\begin{nota}
$R^{1}_{p}(X)=$ {\em cohomologie $L_p$ réduite en degré} $1=$ fonctions de gradient $L_p$ modulo l'adhérence des fonctions $L_p$.
\end{nota}

\begin{defi}
$X$ est {\em $p$-parabolique} s'il existe des fonctions à support compact $u:X\to\R$, valant $1$ sur un ouvert fixé, et d'énergie $\int|du|^p$ arbitrairement petite.
\end{defi}%\pause

\begin{thm}[\textcolor{red}{Benjamini, Schramm}]
Si $X$ est empilable dans $\R^d$, alors 
\begin{itemize}
  \item ou bien $X$ est $d$-parabolique ;
  \item ou bien $R^{1}_{d}(X)$ est non nul.
\end{itemize}
\end{thm}%\pause

\begin{ex}
Si $X=Cay(\Gamma)$, $X$ est $p$-parabolique $\Leftrightarrow$ $\Gamma$ est à croissance polynômiale de degré $d\leq p$. 

Si $X$ est un groupe de Lie, $R^{1}_{d}(X)\not=0 \Leftrightarrow X$ est hyperbolique et $\mathrm{Confdim}(\partial X)\leq d$.
\end{ex}


\end{frame}

\begin{frame}

Aucun des exemples ci-dessus ne donne une borne inférieure pour la dimension de plongement fractionnaire meilleure que la dimension métrique. Par exemple, l'argument de \textcolor{red}{Miller, Teng, Thurston, Vavasis 1993-1998} s'étend au groupe de Heisenberg et donne une séparation $sep(n)=n^{3/4}$. Les graphes autosimilaires diamant ou de \textcolor{red}{Laakso} sont planaires.

\begin{ques}
Existe-t'il des espaces doublants $X$ de dimension métrique $d$ tels que $sep_{X}(n)\gg n^{(d-1)/d}$ ?
\end{ques}
Pas sûr.%\pause

\begin{ques}
Un espace doublant de dimension métrique $d$ est-il forcément $p$-parabolique pour tout $p\geq d$ ?
\end{ques}
Cela paraît probable.

\end{frame}

\section{Preuve du théorème de Naor et Neiman}

\begin{frame}

La construction est un cas particulier de celle de \textcolor{red}{Abraham, Bartal, Neiman 2008}.

\smallskip

\textbf{Préliminaire}. \textcolor{red}{Assouad, Bretagnolle, Dacunha-Castelle, Krivine} : on peut supposer $X$ fini, diamètre$(X)<\infty$, dimension$(X)=d$.%\pause

\begin{scheme}
Etant donné $\theta\in]0,1]$, on construit une distribution sur les applications $F:X\to\ell_2^N$, $N=\lceil \frac{d}{\theta}\rceil$. Toutes satisfont à une estimation Hölder $|F(x)-F(y)|\leq (\frac{d}{\eps})^{1+\theta}d(x,y)$. L'inégalité inverse est satisfaite avec probabilité non nulle.
\end{scheme}%\pause

Pour $i\in \N$, soit $s_i =(\frac{\eps}{d})^{i\theta/(1-\eps)}$. Soit $Y_i$ un $s_i$-réseau de $X$. On tire indépendamment au hasard $N$ rayons $R^{k}(y)\in[\frac{s_i}{4},\frac{s_i}{2}]$ pour chaque point $y\in Y_i$. On constitue $N$ partitions de $X$ au moyen des boules $B(y_1 ,R^{k}(y_1))$, $B(y_2 ,R^{k}(y_2))\setminus B(y_1 ,R^{k}(y_1)),...$ centrées sur $Y_i$. Pour chaque pièce $P$ de l'une de ces partitions, on tire au hasard un réel $U(P)\in[0,1]$. Pour $x\in X$, on note $P_i^k (x)$ la pièce qui contient $x$ et
\begin{eqnarray*}
f_i^k (x)=\textcolor{red}{d\,d(x,X\setminus P_i^k (x))}.
\end{eqnarray*}


\end{frame}

\begin{frame}

La construction est un cas particulier de celle de \textcolor{red}{Abraham, Bartal, Neiman 2008}.

\smallskip

\textbf{Préliminaire}. \textcolor{red}{Assouad, Bretagnolle, Dacunha-Castelle, Krivine} : on peut supposer $X$ fini, diamètre$(X)<\infty$, dimension$(X)=d$.

\begin{scheme}
Etant donné $\theta\in]0,1]$, on construit une distribution sur les applications $F:X\to\ell_2^N$, $N=\lceil \frac{d}{\theta}\rceil$. Toutes satisfont à une estimation Hölder $|F(x)-F(y)|\leq (\frac{d}{\eps})^{1+\theta}d(x,y)$. L'inégalité inverse est satisfaite avec probabilité non nulle.
\end{scheme}

Pour $i\in \N$, soit $s_i =(\frac{\eps}{d})^{i\theta/(1-\eps)}$. Soit $Y_i$ un $s_i$-réseau de $X$. On tire indépendamment au hasard $N$ rayons $R^{k}(y)\in[\frac{s_i}{4},\frac{s_i}{2}]$ pour chaque point $y\in Y_i$. On constitue $N$ partitions de $X$ au moyen des boules $B(y_1 ,R^{k}(y_1))$, $B(y_2 ,R^{k}(y_2))\setminus B(y_1 ,R^{k}(y_1)),...$ centrées sur $Y_i$. Pour chaque pièce $P$ de l'une de ces partitions, on tire au hasard un réel $U(P)\in[0,1]$. Pour $x\in X$, on note $P_i^k (x)$ la pièce qui contient $x$ et
\begin{eqnarray*}
f_i^k (x)=\textcolor{red}{U(P_i^k (x))}\,d\,\textcolor{red}{s_i^{-\eps}}d(x,X\setminus P_i^k (x)).
\end{eqnarray*}
 

\end{frame}

\begin{frame}

La construction est un cas particulier de celle de \textcolor{red}{Abraham, Bartal, Neiman 2008}.

\smallskip

\textbf{Préliminaire}. \textcolor{red}{Assouad, Bretagnolle, Dacunha-Castelle, Krivine} : on peut supposer $X$ fini, diamètre$(X)<\infty$, dimension$(X)=d$.

\begin{scheme}
Etant donné $\theta\in]0,1]$, on construit une distribution sur les applications $F:X\to\ell_2^N$, $N=\lceil \frac{d}{\theta}\rceil$. Toutes satisfont à une estimation Hölder $|F(x)-F(y)|\leq (\frac{d}{\eps})^{1+\theta}d(x,y)$. L'inégalité inverse est satisfaite avec probabilité non nulle.
\end{scheme}

Pour $i\in \N$, soit $s_i =(\frac{\eps}{d})^{i\theta/(1-\eps)}$. Soit $Y_i$ un $s_i$-réseau de $X$. On tire indépendamment au hasard $N$ rayons $R^{k}(y)\in[\frac{s_i}{4},\frac{s_i}{2}]$ pour chaque point $y\in Y_i$. On constitue $N$ partitions de $X$ au moyen des boules $B(y_1 ,R^{k}(y_1))$, $B(y_2 ,R^{k}(y_2))\setminus B(y_1 ,R^{k}(y_1)),...$ centrées sur $Y_i$. Pour chaque pièce $P$ de l'une de ces partitions, on tire au hasard un réel $U(P)\in[0,1]$. Pour $x\in X$, on note $P_i^k (x)$ la pièce qui contient $x$ et
\begin{eqnarray*}
f_i^k (x)=U(P_i^k (x))\,\textcolor{red}{\min\{s_i^{1-\eps},}d\,s_i^{-\eps}d(x,X\setminus P_i^k (x))\textcolor{red}{\}}.
\end{eqnarray*}
 

\end{frame}

\subsection{Constante de Hölder}

\begin{frame}

On pose
\begin{eqnarray*}
F(x)=\frac{1}{\sqrt{N}}\sum_{i=1}^{\infty}(f_i^1 (x),\ldots,f_i^N (x)).
\end{eqnarray*}
 
\begin{lem}
On a toujours $|F(x)-F(y)|\leq \mathrm{const.}(\frac{d}{\eps})^{1+\theta}d(x,y)^{1-\eps}$. 
\end{lem}

On montre aisément que pour tout $i\in\N$, $k\in[N]$, $x$, $y\in X$, 
$$|f_i^k (x)-f_i^k (y)|\leq \mathrm{const.}\min\{s_i^{1-\eps},d\,s_i^{-\eps}d(x,y)\}.$$
En sommant sur $i$, on utilise la majoration par $d\,s_i^{-\eps}d(x,y)$ pour $i\leq\log d(x,y)$, et la majoration par $s_i^{1-\eps}$ pour $i$ plus grand. La somme est majorée par $d(x,y) \exp(-\eps\log d(x,y))=d(x,y)^{1-\eps}$.

\end{frame}

\subsection{Constante de Hölder inverse}

\begin{frame}

Pour chaque $i\in\N$, on pose $\delta_i =(\frac{\eps}{d})^{1/(1-\eps)}s_i$ et on choisit un $\delta_i$-réseau $N_i$ de $X$. Soit $E$ l'évènement ``pour tout $i$ et pour tous $z$, $w\in N_i$ tels que $d(z,w)$ soit de l'ordre de $s_i$, pour au moins la moitié des fonctions $f_i^k$,
\begin{eqnarray*}
|\sum_{j=1}^{\infty} (f_{j}^{k}(z)-f_{j}^{k}(w))|>s_{i}^{1-\eps}.
\end{eqnarray*}

\begin{lem}
On a $|F(x)-F(y)|\geq \mathrm{const.}(\frac{\eps}{d})^{2\theta} d(x,y)^{1-\eps}$ pourvu que l'évènement $E$ ci-dessus soit réalisé.
\end{lem}
En effet, choisir $i$ tel que $d(x,y)$ soit de l'ordre de $s_i$. Approcher $x$ et $y$ par $z$, $w\in N_i$. Utiliser le fait que $F$ est Hölder continue.%\pause

\smallskip

Dans la définition de $E$, on peut clairement introduire la modification suivante : $T(i,z,w)=$ ``pour au moins la moitié des fonctions $f_i^k$, 
\begin{eqnarray*}
|\sum_{j=1}^{i} (f_{j}^{k}(z)-f_{j}^{k}(w))|>2s_{i}^{1-\eps} ."
\end{eqnarray*}

\end{frame}

\begin{frame}
Comme le graphe de dépendance des évènements $T(i,z,w)$ a un degré borné par $(\frac{d}{\eps})^{O(d)}$ (c'est le nombre de points de $N_i$ dans une boule de rayon $s_i$), pour minorer la probabilité de $E$, on utilise le Lemme Local de Lov\'asz (en fait, la variante suivante).

\begin{lem}[\textcolor{red}{Abraham, Bartal, Neiman 2008}]
Soient $A_v$ des évènements indexés par les sommets d'un graphe $G$ de degré $\leq D$. Sur $G$, on se donne une fonction de niveau $V\to\N$ qui est constante sur les composantes connexes. On suppose qu'il existe $q$ tel que $q(D+1)e \leq 1$ et pour tout $v$ et tout ensemble $Q$ de sommets dont aucun n'est un voisin de $v$, et tous ont un niveau $\leq$ à celui de $v$,
\begin{eqnarray*}
\mathbb{P}(A_v^c \cap\bigcap_{u\in Q} A_u)\leq q\,\mathbb{P}(\bigcap_{u\in Q} A_u).
\end{eqnarray*}
Alors, avec une probabilité non nulle, les $A_v$ se produisent simultanément. 
\end{lem} %\pause

Ici, $v=(i,z,w)$, le niveau est $i$, $A_v =T(i,z,w)$. Il s'agit de montrer que $q=(\frac{\eps}{d})^{\theta N/2}$ convient. Si $G$ était vraiment un graphe de dépendance, ce serait simple.

\end{frame}

\end{document}

\begin{frame}


\end{frame}