\documentclass[8pt]{beamer}
\usepackage[ansinew]{inputenc}
\usepackage{amssymb, color}
\usepackage{graphicx}
\usepackage{beamerthemesplit}
\usepackage{pgf,tikz}
\usepackage{mathrsfs}
\usetikzlibrary{arrows}

\newtheorem{thm}{Th\'eor\`eme}
\newtheorem{lem}{Lemme}
\newtheorem{pro}[lem]{Proposition}
\newtheorem{cor}[lem]{Corollaire}
\newtheorem{dfi}[lem]{D\'efinition}
\newtheorem{rem}[lem]{Remarque}
\newtheorem{ntn}[lem]{Notation}
\newtheorem{que}[lem]{Question}
\newtheorem{pbm}[lem]{Probl\`eme}
\newtheorem{sol}[lem]{Solution}
\newtheorem{con}[lem]{Conclusion}
\newtheorem{coj}[lem]{Conjecture}
\newtheorem{exa}[lem]{Exemple}
\newtheorem{exs}[lem]{Exemples}
\newtheorem{res}[lem]{Resultats}
\newtheorem{fac}[lem]{Fait}
\newtheorem{pla}[lem]{Plan de l'expos\'e}
\newtheorem{sch}[lem]{Schéma de démonstration}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\C{\mathbb{C}}
\def\E{\mathbb{E}}
\def\P{\mathbb{P}}
\def\F{\mathbb{F}_2}
\def\k{\mathbf{k}}
\def\maprl#1#2{\stackrel{#1,#2}{\rightleftharpoons}}
\def\n#1{{|\hskip-1pt | #1 |\hskip-1pt |}}



\title{Distances entre complexes de cha{\^\i}nes normés}
\author{Pierre Pansu, Universit\'e Paris-Saclay}
\date{14 octobre 2022}


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

\begin{document}

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

\section{Presque-cohomologie}

\subsection{Qu'est-ce que la presque-cohomologie ?}


\begin{frame}

$X$ variété riemannienne. Sur les espaces $\Omega^k(X)$ de formes différentielles $C^\infty$, des normes $L^p$ sont définies. La différentielle extérieure $d$ est un complexe dont la cohomologie coïncide avec la cohomologie de $X$ à coefficients réels.


\medskip

\textbf{Exemple}. $X=$ intervalle de longueur $L$. Alors $H^1(X)=0$. Soit $f=\tanh$ une fonction sigmoïde, i.e. qui vaut presque $-1$ (resp. $1$) sur $X$ sauf sur un intervalle borné au milieu. Le cocycle $g=df$ satisfait
\begin{align*}
\|g\|_p\sim 1,\quad \|f\|_p\sim L^{1/p}.
\end{align*}\pause


Quand $L$ est grand, résoudre $df=g$ est coûteux. On dit que $g$ représente un élément non trivial en \emph{presque-cohomologie}.

\begin{dfi}
Le \textbf{seuil de presque-cohomologie en degré $k$}, noté $NH_k(X,p,\R)$, est la norme de l'inverse $\bar d^{-1}$ de $\bar d : \Omega^{k}(X,)/\mathrm{Ker}(d)\to dC^{k}(X)$. (Il dépend de $p$).
\end{dfi}\pause

\textbf{Exemple}. $X=$ intervalle de longueur $L$. Alors $NH_0(X)\sim L^{1/p}$.

\end{frame}

\begin{frame}


$X$ complexe simplicial, $\k=\F$ ou $\R$. Une $k$-cocha{\^\i}ne est une fonction antisymétrique à valeurs dans $\k$ sur l'ensemble des $k$-simplexes. Son \emph{cobord} $df$ is $df(\sigma)=f(\partial\sigma)$.

\medskip

Une valeur absolue sur $\k$ donne des normes $\ell^p$ sur les cocha{\^\i}nes : on tire les simplexes uniformément au hasard, et on pose $\|f\|_p=\E(|f|^p)^{1/p}$.\pause

\medskip

\textbf{Exemple}. Le graphe rectiligne de longueur $n$ satisfait $H^1=0$. La $1$-cha{\^\i}ne $g$ égale à $\bar 1$ sur l'arête centrale et $0$ ailleurs s'écrit $df$ où
\begin{align*}
\|g\|_p=\frac{1}{n^{1/p}},\quad \|f\|_p\sim 1.
\end{align*}

\begin{center}
\definecolor{qqzzqq}{rgb}{0.,0.6,0.}
\definecolor{ffqqqq}{rgb}{1.,0.,0.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.3cm,y=0.3cm]
\clip(-2.1578568610390616,3.1283691165789764) rectangle (33.81224865175817,9.076181839167461);
\draw (0.,6.)-- (14.,6.);
\draw [color=ffqqqq](0.39120573435601774,7.498190708684802) node[anchor=north west] {$0$};
\draw [color=ffqqqq](2.4547325972948912,7.457729397646785) node[anchor=north west] {$0$};
\draw [color=ffqqqq](4.3564142160816965,7.417268086608768) node[anchor=north west] {$0$};
\draw [color=ffqqqq](6.41994107902057,7.417268086608768) node[anchor=north west] {$1$};
\draw [color=ffqqqq](8.483467941959445,7.417268086608768) node[anchor=north west] {$0$};
\draw [color=ffqqqq](10.425610871784265,7.376806775570751) node[anchor=north west] {$0$};
\draw [color=ffqqqq](12.408215112647104,7.376806775570751) node[anchor=north west] {$0$};
\draw [color=qqzzqq] (18.,7.)-- (20.,7.);
\draw [color=qqzzqq] (20.,7.)-- (22.,7.);
\draw [color=qqzzqq] (22.,7.)-- (24.,7.);
\draw [color=qqzzqq] (24.,7.)-- (26.,8.);
\draw [color=qqzzqq] (26.,8.)-- (28.,8.);
\draw [color=qqzzqq] (28.,8.)-- (30.,8.);
\draw [color=qqzzqq] (30.,8.)-- (32.,8.);
\draw [color=ffqqqq] (6.,8.)-- (8.,8.);
\draw [color=ffqqqq](6.703170256286691,5.596509089898007) node[anchor=north west] {$g$};
\draw [color=qqzzqq](24.667992357166295,5.596509089898007) node[anchor=north west] {$f$};
\begin{scriptsize}
\draw [fill=black] (0.,6.) circle (2.5pt);
\draw [fill=black] (14.,6.) circle (2.5pt);
\draw [fill=black] (2.,6.) circle (2.5pt);
\draw [fill=black] (4.,6.) circle (2.5pt);
\draw [fill=black] (6.,6.) circle (2.5pt);
\draw [fill=black] (8.,6.) circle (2.5pt);
\draw [fill=black] (10.,6.) circle (2.5pt);
\draw [fill=black] (12.,6.) circle (2.5pt);
\draw [fill=black] (18.,6.) circle (2.5pt);
\draw [fill=black] (20.,6.) circle (2.5pt);
\draw [fill=black] (22.,6.) circle (2.5pt);
\draw [fill=black] (24.,6.) circle (2.5pt);
\draw [fill=black] (26.,6.) circle (2.5pt);
\draw [fill=black] (28.,6.) circle (2.5pt);
\draw [fill=black] (30.,6.) circle (2.5pt);
\draw [fill=black] (32.,6.) circle (2.5pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}\pause

Quand $n$ est grand, résoudre $df=g$ est coûteux. On dit que $g$ représente un élément non trivial en \emph{presque-cohomologie}.

\begin{dfi}
Le \textbf{seuil de presque-cohomologie en degré $k$}, noté $NH_k(X,p,\k)$, est la norme de l'inverse $\bar d^{-1}$ de $\bar d : C^{k}(X,\k)/\mathrm{Ker}(d)\to dC^{k}(X,\k)$. (Il dépend de $p$ et de $\k$).
\end{dfi}

\end{frame}

\begin{frame}

\begin{fac}[Gromov-Shubin]
Comme la cohomologie, la presque-cohomologie est un invariant topologique (et même homotopique) des variétés et des complexes simpliciaux. Pour les variétés et complexes non compacts, à géométrie bornée, c'est un  invariant de quasiisométrie
\end{fac}\pause

\medskip

À retenir : la cohomologie n'est pas la seule information intéressante qu'on puisse extraire d'un complexe de cocha{\^\i}nes. La presque-cohomologie l'est aussi.\pause

\begin{pla}
\begin{enumerate}
  \item Relier les divers seuils de presque cohomologie $\ell^p$ à l'isopérimétrie et à l'expansion.
  \item Ébaucher une étude géométrique des complexes de cha{\^\i}nes, en lien avec la presque-homologie. \end{enumerate}
\end{pla}

\end{frame}

\subsection{Isoperimétrie}

\begin{frame}[label=chee]

\begin{dfi}
La \textbf{constante de Cheeger} $h(X)$ d'une variété riemannienne $X$ est le plus grand $h$ tel que pour toute sous-variété $A$ de $X$ tel que $vol(A)\le \frac{1}{2}vol(X)$,
\begin{align*}
vol(\partial A)\ge h\,vol(A).
\end{align*}
\end{dfi}\pause

\begin{pro}
$$
h(X)=NH_0(X,1,\R)^{-1}=(\|d^{-1}\|_{1\to 1})^{-1}\text{ en de Rham}.
$$ 
\end{pro}\pause


Pour un graphe, les sous-variétés sont remplacées par des ensembles $A$ de sommets et le bord par l'ensemble des arêtes reliant $A$ à son complémentaire. 

\begin{pro}
$$
h(X)=NH_0(X,1,\F)^{-1}=(\|d^{-1}\|_{1\to 1})^{-1}\text{ sur }\F.\qquad\hyperlink{hnc<1>}{\beamergotobutton{Démonstration}}
$$ 
\end{pro}

\pause

\begin{exa}[de graphe de grande constante de Cheeger]
Pour le graphe complet $K_n$ à $n$ sommets, $h(K_n)=\frac{n}{n-1}$ ($n$ pair) ou $\frac{n+1}{n-1}$ ($n$ impair).
\end{exa}\hyperlink{isopnc<1>}{\beamergotobutton{Démonstration}}

\end{frame}


\subsection{Laplacien}

\begin{frame}[label=Laplacian]

\begin{pro}
Soit $\Delta$ l'opérateur auto-adjoint correspondant à la forme quadratique $f\mapsto \|df\|_2^2=\langle f,\Delta f \rangle$. Soient $\lambda_1\le \lambda_2\le\cdots$ ses valeurs propres. Si $X$ est connexe, alors $\lambda_1=0$ et
\begin{align*}
\lambda_2=NH_0(X,2,\R)^{-2}=(\|d^{-1}\|_{2\to 2})^{-2}.\qquad\qquad\hyperlink{lambda2<1>}{\beamergotobutton{Démonstration}}
\end{align*}
\end{pro}
\pause

\begin{dfi}
Désormais, on part d'une distribution de probabilité $\P_1$ sur les arêtes, et on définit la distribution $\P_0$ sur les sommets comme suit : on tire une arête selon $\P_1$ et on tire un de ses sommets au hasard. On l'appelle la \textbf{distribution de Garland}.
%Un complexe simplicial $X$ est de \textbf{dimension pure} $N$ si chaque sommet est contenu dans au moins un simplexe de dimension $N$. 

%Une famille de distributions de probabilité $\P_k$ sur les simplexes de dimension $k$ d'un complexe simplicial $X$ de dimension pure $N$ est \textbf{de Garland} si pour tout $k=0$, ..., $N-1$, il revient au même de tirer un $k$-simplexe au hasard selon $\P_k$ ou de tirer d'abord un $k+1$-simplexe $\sigma$ selon $\P_{k+1}$ puis de tirer uniformément un $k$-simplexe de $\sigma$.
\end{dfi}
Cela donne à chaque sommet un poids proportionnel à son degré.
\pause

\medskip

En utilisant $\P_1$ et $\P_0$, on définit des normes $\ell^p$ sur les $0$- et $1$-cocha{\^\i}nes, et donc des seuils de presque-cohomologie $NH_{0}(\P,1,\F)=(\|d^{-1}\|_{1\to 1})$ sur $\F$ et $NH_{0}(\P,2,\R)=\lambda_{2,\P}^{-1/2}=(\|d^{-1}\|_{2\to 2})$ sur $\R$.

\end{frame}

\begin{frame}[label=lambda2h]

\begin{thm}[Cheeger, Buser, Dodziuk, Alon-Milman]
Pour un graphe fini connexe muni d'une distribution de Garland $\P$,
\begin{align*}
\frac{1}{2}\lambda_{2,\P}\le NH_{0}(\P,1,\F)^{-1}\le 2\sqrt{\lambda_{2,\P}}.
\end{align*}
\end{thm}
\hyperlink{cheeger-buser<1>}{\beamergotobutton{Démonstration}}
\pause

Cet encadrement du seuil de presque-cohomologie $\ell^p$ $NH_{0}(\P,p,\F)$ se généralise à toutes les valeurs de  $p>1$.

\begin{pro}
Pour un graphe fini connexe muni d'une distribution de Garland $\P$, 
\begin{align*}
2^{1-p}NH_{0}(\P,p,\R)^{-p}\le NH_{0}(\P,1,\F)^{-1}\le \max\{p,2^{p-1}\}NH_{0}(\P,p,\R)^{-1}.
\end{align*}
\end{pro}

\medskip

\textbf{Moralité}. Le phénomène important ($NH_0$ borné) est finalement indépendant de $p$ et du corps $\k$. Ce n'est malheureusement pas vrai en dimensions supérieures. Cela rend la construction d'expanseurs de dimension supérieure ($NH_k(\P,1,\F)$ bornés pour $k= 0,1,\ldots$) plus difficile que celle de graphes expanseurs.

\end{frame}



\section{Distances entre complexes de cha{\^\i}nes}

\subsection{La distance de Banach-Mazur}

\begin{frame}

\textbf{Question}. Peut-on interpréter le seuil de presque-cohomologie $\|d^{-1}\|$ comme la distance entre certains complexes de cocha{\^\i}nes ?\pause

%\bigskip

%We consider vectorspaces over $\F$ or over $\R$. A \emph{norm} on an $\F$-vectorspace is a nonnegative subadditive real valued function such that $|e|\iff e=0$.

\medskip

Un \emph{complexe normé} est la donnée d'un espace vectoriel normé $B$ et d'un opérateur $d:B\to B$ tel que $d\circ d=0$. Un \emph{isomorphisme} de complexes normés $B_1\stackrel{d_1}{\to}B_1$ and $B_2\stackrel{d_2}{\to}B_2$ est une bijection linéaire $F:B_1\to B_2$ telle que $d_2f_1=f_1d_1$ and $F,F^{-1}$ sont bornés. Un \emph{isométrie} de complexes normés est un isomorphisme isométrique.\pause

\begin{dfi}
\label{defBMdist}
Soient $B_1\stackrel{d_1}{\to}B_1$ et $B_2\stackrel{d_2}{\to}B_2$ deux complexes normés. La \textbf{distance de Banach-Mazur} $\mathrm{BMDist}(B_1,B_2)$ est l'inf des $\log(|F||F^{-1}|)$ sur tous les isomorphismes $F:B_1\to B_2$.
\end{dfi}\pause

C'est trop restrictif : ne permet pas de comparer les complexes $L^p$ d'une variété riemannienne et d'un complexe simplicial, par exemple.

\end{frame}

\subsection{La distance homotopique}

\begin{frame}

\begin{dfi}
\label{defhomdist}
Soient $B_1\stackrel{d_1}{\to}B_1$ et $B_2\stackrel{d_2}{\to}B_2$ deux complexes normés. On considère toutes les homotopies bornées, i.e. 
\begin{itemize}
  \item des morphismes bornés $F_1:B_1\to B_2$ et $F_2:B_2\to B_1$ tels que 
  $$
  d_2F_1=F_1d_1,\quad d_1F_2=F_2d_2,
  $$
  \item des opérateurs bornés $Q_1:B_1\to B_1$ and $Q_2:B_2\to B_2$ tels que
  $$
1-F_2F_1=d_1Q_1+Q_1d_1, \quad 1-F_1F_2=d_2Q_2+Q_2d_2.
  $$
\end{itemize}
On note $\displaystyle
q=\max\{|Q_1|,|Q_2|\}$, $f=\max\{1,|F_1||F_2|\}$. La \textbf{distance homotopique} $\mathrm{HomDist}(B_1,B_2)$ est l'inf sur toutes les homotopies de $\displaystyle \min\{\frac{q}{f},1\}+\log f$.
\end{dfi}\pause

L'expression bizarre est là pour garantir l'inégalité triangulaire. \hyperlink{trihomdist<1>}{\beamergotobutton{Détails}}

\end{frame}

\subsection{Le seuil de presque-homologie}

\begin{frame}[label=homdist]

En dimension finie, 
\begin{align*}
\mathrm{HomDist}(B_1,B_2)<\infty &\iff \mathrm{dim}(H(B_1))=\mathrm{dim}(H(B_2)),\\
\mathrm{HomDist}(B_1,B_2)=0 &\iff (B_1,d_1)\text{ et }(B_2,d_2)\text{ sont isométriques.}
\end{align*}
Donc on obtient une distance sur l'ensemble des classes d'isométrie de complexes normés de dimension finie, de même homologie.\pause

\medskip

\begin{dfi}
Le \textbf{seuil de presque-homologie} $NH(B)$ est la norme de l'inverse $\bar d^{-1}$ de $\bar d : B/\mathrm{Ker}(d)\to \mathrm{Im}(d)$.
\end{dfi}\pause

\textbf{Remarque}. $\mathrm{NH}$ est un covariant d'homotopie : si deux complexes $B_1$ et $B_2$ sont homotopes, alors $\mathrm{NH}(B_1)\le \exp(\mathrm{HomDist}(B_1,B_2))(1+\mathrm{NH}(B_2))$. \hyperlink{nhhom<1>}{\beamergotobutton{Détails}}\pause

\begin{dfi}
On note $Null$ l'ensemble des complexes normés dont la différentielle est nulle.
\end{dfi}

\end{frame}

\begin{frame}[label=nh]

\begin{lem}
$HomDist(B,Null)\ge \min\{NH(B),1\}$. \hyperlink{dist0<1>}{\beamergotobutton{Détails}}
\end{lem}\pause

\begin{pro}
Si $B$ est un espace de Hilbert, $HomDist(B,Null)=\min\{NH(B),1\}$. 
\hyperlink{nhdetail<1>}{\beamergotobutton{Détails}}
\end{pro}\pause

Ça s'applique aux cocha{\^\i}nes sur les graphes. Pour lever l'obstruction homologique, on attache à un graphe $X$ les complexes
\begin{align*}
B_{X,\k,p}=H^0(X,\k)\oplus C^0(X,\k)\oplus dC^0(X,\k) \text{ munis de normes }\ell^p,
\end{align*}
où $d:H^0(X,\k)\to C^0(X,\k)$ consiste à voir les fonctions localement constantes comme des $0$-cochaines. Pour les graphes finis connexes, 
\begin{align*}
HomDist(B_{X,\R,2},0)=NH(B_{X,\R,2})=\lambda_2(X)^{1/2}.
\end{align*}\pause

Sur $\F$, ça se passe moins bien. \hyperlink{k3detail<1>}{\beamergotobutton{Détails}}
\begin{exa}
Soit $K_3$ le graphe complet à $3$ sommets. Alors 
\begin{align*}
HomDist(B_{K_3,\F,1},0)=1,\quad NH(B_{K_3,\F,1})=\frac{1}{2}.
\end{align*}
\end{exa}

\end{frame}

\subsection{La distance de Hausdorff}

\begin{frame}[label=Haus]

\begin{dfi}
Soit $B\stackrel{d}{\to}B$ un complexe normé, soient $B'$ et $B''$ des sous-complexes de $B$. On considère tous les morphismes bornés $F:B\to B$ tels que $F(B')\subset B''$ et les opérateurs bornés $Q:B\to B$ tels que, sur $B'$, $1-F=dQ+Qd$. On prend l'inf de $\min\{\frac{q}{f},1\}+\log(f)$ pour
$$
q=|Q|,\quad f=\max\{|F|,1\}.
$$ 
Ceci définit la distance de Hausdorff asymétrique $\mathrm{HausDist}_{B}(B'\to B'')$. On la rend symétrique en posant
\begin{align*}
\mathrm{HausDist}_{B}(B',B'')=\mathrm{HausDist}_{B}(B'\to B'')+\mathrm{HausDist}_{B}(B''\to B').
\end{align*}
%Let $B_1\stackrel{d_1}{\to}B_1$ and $B_2\stackrel{d_2}{\to}B_2$ be two normed complexes. Consider all normed complexes $B\stackrel{d}{\to}B$, containing subcomplexes $B'$ and $B''$ isometric to $B_1$ and $B_2$ respectively, and take the infimum of all embedded Hausdorff distances $\mathrm{HausDist}_{B}(B',B'')$. This defines the abstract \textbf{Hausdorff distance} $\mathrm{HausDist}(B_1,B_2)$.
\end{dfi}

Cette distance satisfait à l'inégalité triangulaire. \hyperlink{Hausdetail<1>}{\beamergotobutton{Détails}}


\end{frame}

\section{Compacité}

\subsection{Critère de compacité}

\begin{frame}

L'analogue d'un espace métrique compact est un complexe de cha{\^\i}nes normé qui peut être approximé par des sous-complexes de dimension finie.

\begin{dfi}
Soit $(B,d)$ un complexe de cha{\^\i}nes normé. Son \textbf{profil} est la plus petite fonction $\pi=(\pi_d,\pi_n):(0,+\infty)\to[0,+\infty]^2$ ayant la propriété suivante. Pour tout $\epsilon>0$, il existe un sous-complexe de dimension finie $B'\subset B$ tel que
$$
HausDist_B(B,B')<\epsilon, \quad \mathrm{dim}(B')\le \pi_d(\epsilon),\quad |d_{|B'}|\le \pi_n(\epsilon).
$$
\end{dfi}\pause

\begin{exa}
\label{exdiffforms}
Soit $M$ une variété riemannienne compacte lisse. Soit $E$ le complexe des formes différentielles lisses sur $M$ muni de la norme $L^2$. Alors le profil $\pi$ de $(E,d)$ est majoré par l'asymptotique des valeurs propres du laplacien de Hodge,
$$
\pi_d(\epsilon)\leq \mathrm{Card}\{\lambda\in\mathrm{spectre}(\Delta)\,;\,\lambda < \frac{1}{\epsilon^2}\},\quad \pi_n(\epsilon)\le \frac{1}{\epsilon}.
$$
\end{exa}
Cela donne une estimée du type $\pi_d(\epsilon)\le C\,\epsilon^{-N}$, où $N=\mathrm{dim}(M)$.

\end{frame}

\subsection{Distance de Gromov-Hausdorff ?}

\begin{frame}

On est tenté par la définition suivante.

\begin{dfi}
Soient $B_1\stackrel{d_1}{\to}B_1$ et $B_2\stackrel{d_2}{\to}B_2$ deux complexes de cha{\^\i}nes normés. On considère tous les complexes normés $B\stackrel{d}{\to}B$, contenant des sous-complexes $B'$ et $B''$ isométriques à $B_1$ et $B_2$ respectivement, et on prend l'inf des distances de Hausdorff $\mathrm{HausDist}_{B}(B',B'')$. Ceci definit la \textbf{distance de Gromov-Hausdorff} $\mathrm{GHDist}(B_1,B_2)$.
\end{dfi}\pause

Mauvaise idée !

\begin{pro}
Si un complexe de dimension finie $E$ satisfait $H(E)=0$, alors $\mathrm{GHDist}(E,0)=0$.

Il en résulte que $\mathrm{GHDist}=0$ sur l'ensemble des complexes de dimension finie d'homologie nulle.
\end{pro}\pause

En effet, si $B=E\oplus E$ muni de
\begin{align*}
d=\begin{pmatrix}
-d^E & 0 \\
a & d^E
\end{pmatrix},\quad F=\begin{pmatrix}
0 & 0 \\
0 &  0
\end{pmatrix},\quad Q=\frac{1}{ab+c}\begin{pmatrix}
-cQ^E &b \\
0 & c Q^E
\end{pmatrix},
\end{align*}
il vient $HausDist_B(0\oplus E,0)\le\max\{\frac{c|Q^E|}{ab+c},\frac{b}{ab+c}\}$ qui peut être rendu arbitrairement petit.

\end{frame}

\begin{frame}

\includegraphics[width=1.5in]{structures-metriques-pour-les-varietes-riemanniennes-de-mikhael-gromov-livre-875487804_ML.jpg}

\vskip-5cm

\includegraphics[width=3in]{Lafontaine-CIRM-1984}

\vskip-8cm

\hskip4cm \includegraphics[width=2.5in]{Holomorphic-curves.pdf}

\end{frame}

\section{Expanseurs}

\subsection{À quoi ça sert ?}

\begin{frame}[label=expander]

Un \emph{expanseur} est une famille infinie de graphes de degrés bornés et de constante de Cheeger bornée inférieurement. De façon équivalente, de \emph{trou spectraux} $\lambda_2$ bornés inférieurement. 

\begin{thm}[Pinsker 1973]
Les suites de graphes aléatoires $d$-reguliers sont des expanseurs.
\end{thm}\pause

\medskip

Il y a aussi des constructions déterministes d'expanseurs (à partir de groupes finis, de produit zig-zag,...).\pause

\bigskip

Les expanseurs servent 
\begin{itemize}
  \item à dérandomiser des algorithmes,
  \item à augmenter les performances de générateurs de bits aléatoires,
  \item à construire des exemples d'espaces et de groupes qui n'ont pas de plongements uniformes dans les espaces de Hilbert.
\end{itemize}

\medskip

\hyperlink{expanderdetail<1>}{\beamergotobutton{Détails}}



\end{frame}

\subsection{Parenthèse sur les graphes infinis}

\begin{frame}
%For infinite graphs, $\mathrm{Ker}(d)=\{0\}$ on $\ell^pC^0$, which simplifies matters.\pause

\begin{pro}
Soit $p\geq 1$. Soit $\Gamma$ un groupe discret de type fini. Fixons un système générateur fini, et le graphe de Cayley $G$ correspondant. Les propriétés suivantes sont équivalentes :
\begin{enumerate}
  \item $h(G)>0$.
  \item $d$ a un inverse borné $d\ell^pC^{0}(G)\to \ell^p C^{1}(G)/\mathrm{Ker}(d)$.
  \item La \emph{cohomologie $\ell^p$} $\ell^p H^1(G):=(\ell^p C^{1}(G)\cap\mathrm{Ker}(d))/d\ell^pC^{0}(G)$ est séparée.
  \item $\Gamma$ est non moyennable.
\end{enumerate}
\end{pro}\pause

\textbf{Exemples}. $\Z^d$ is moyennable. Il se comporte comme l'espace euclidien dont la constante de Cheeger vaut $0$. Sa cohomologie $\ell^p$ est non nulle et non séparée pour tout $p>1$.

Le groupe libre est non moyennable. Il se comporte comme l'espace hyperbolique dont la constante de Cheeger est non nulle. Sa cohomologie $\ell^p$ en degré $1$ est non nulle et séparée pour tout $p>1$.

\end{frame}

\subsection{Expanseurs de dimension supérieure}

\begin{frame}

\begin{dfi}
Un expanseur en dimension $n$ est une famille infinie de complexes simpliciaux de dimension pure $N$, de degrés bornés, munis de distributions de Garland, et de seuils de presque-cohomologie
\begin{align*}
h_k =(\|\bar d^{-1}\|_{1\to 1})^{-1},\quad \text{où} \quad \bar d:C^k(X,\F)/\mathrm{Ker}(d)\to dC^k(X,\F)
\end{align*}
bornés inférieurement pour $k=0,\ldots,n-1$. 
\end{dfi}\pause

\textbf{Exemple}
\label{complete}
Pour le $N$-squelette du $n$-simplexe, pour tout $k=0,\ldots,N-1$,
$\displaystyle h_k \ge \frac{n}{n-k-1}$.

\medskip

Dans cet exemple, le degré augmente avec $n$.\pause

\begin{thm}[Kaufman-Kazhdan-Lubotzky 2016]
Il existe un expanseur en dimension $2$, dont la construction est déterministe.
\end{thm}
Pour un $2$-complexe simplicial aléatoire, les garanties connues sur le degré sont un peu moins bonnes.

\end{frame}

\subsection{Expansion et papier froissé}

\begin{frame}[label=papier]

\textbf{Remarque}. Soit $X$ un graphe connexe et $F:X\to\R$ une fonction continue. Soit $m\in\R$ sa médiane. Alors $m$ appartient aux images d'une fraction $h(X)$ des arêtes de $X$.

\begin{center}
\definecolor{zzwwqq}{rgb}{0.6,0.4,0.}
\definecolor{qqqqff}{rgb}{0.,0.,1.}
\definecolor{qqzzqq}{rgb}{0.,0.6,0.}
\definecolor{qqqqcc}{rgb}{0.,0.,0.8}
\definecolor{ffqqqq}{rgb}{1.,0.,0.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.3cm,y=0.3cm]
\clip(-3.556524244306851,-5.620699961528273) rectangle (22.14068902288449,7.042292772063608);
\draw [domain=-3.556524244306851:22.14068902288449] plot(\x,{(-112.-0.*\x)/28.});
\draw (-2.,2.)-- (2.,0.);
\draw (2.,0.)-- (4.,4.);
\draw (4.,4.)-- (-2.,2.);
\draw (4.,4.)-- (8.,0.);
\draw (4.,4.)-- (8.,2.);
\draw (4.,4.)-- (8.,4.);
\draw (2.,0.)-- (8.,0.);
\draw (2.,0.)-- (8.,2.);
\draw (8.,4.)-- (10.,6.);
\draw [color=qqzzqq] (10.,6.)-- (14.,-2.);
\draw [color=qqzzqq] (8.,2.)-- (14.,0.);
\draw (8.,0.)-- (12.,4.);
\draw [color=qqzzqq] (12.,4.)-- (16.,2.);
\draw [color=qqzzqq] (10.,6.)-- (14.,4.);
\draw [color=qqzzqq] (8.,4.)-- (16.,2.);
\draw [color=qqzzqq] (8.,0.)-- (14.,-2.);
\draw (14.,-2.)-- (20.,0.);
\draw [color=qqzzqq] (12.,4.)-- (18.,-2.);
\draw (18.,-2.)-- (20.,0.);
\draw (14.,4.)-- (18.,2.);
\draw (16.,2.)-- (20.,4.);
\draw (14.,4.)-- (18.,-2.);
\draw (14.,0.)-- (18.,2.);
\draw (14.,0.)-- (18.,-2.);
\draw (18.,2.)-- (20.,4.);
\draw (18.,2.)-- (20.,0.);
\draw [color=zzwwqq] (13.020929355777671,-5.620699961528273) -- (13.020929355777671,7.042292772063608);
\draw [color=zzwwqq](11.4,-3.8) node[anchor=north west] {$m$};
\draw [->,color=zzwwqq] (0.,0.) -- (0.,-4.);
\draw [color=zzwwqq](-1.2,-0.8772336280980885) node[anchor=north west] {$F$};
\begin{scriptsize}
\draw [fill=ffqqqq] (-2.,2.) circle (1.5pt);
\draw [fill=ffqqqq] (2.,0.) circle (1.5pt);
\draw [fill=ffqqqq] (4.,4.) circle (1.5pt);
\draw [fill=ffqqqq] (8.,0.) circle (1.5pt);
\draw [fill=ffqqqq] (8.,2.) circle (1.5pt);
\draw [fill=ffqqqq] (8.,4.) circle (1.5pt);
\draw [fill=ffqqqq] (10.,6.) circle (1.5pt);
\draw [fill=qqqqcc] (14.,-2.) circle (1.5pt);
\draw [fill=qqqqcc] (14.,0.) circle (1.5pt);
\draw [fill=ffqqqq] (12.,4.) circle (1.5pt);
\draw [fill=qqqqff] (16.,2.) circle (1.5pt);
\draw [fill=qqqqff] (14.,4.) circle (1.5pt);
\draw [fill=qqqqff] (20.,0.) circle (1.5pt);
\draw [fill=qqqqff] (18.,-2.) circle (1.5pt);
\draw [fill=qqqqff] (18.,2.) circle (1.5pt);
\draw [fill=qqqqff] (20.,4.) circle (1.5pt);
\draw [fill=zzwwqq] (13.020929355777671,-4.) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}\pause

M. Gromov a trouvé une version multidimensionnelle de cette remarque : si un complexe simplicial de dimension pure $n$ suffisamment riche est envoyé continûment dans $\R^n$, il existe un point de $\R^n$ qui est atteint par une fraction substantielle des $n$-simplexes. 

\medskip

Suffisamment riche signifie expanseur en dimension $n$, plus d'autres hypothèses sur le degré et les \emph{cosystoles}. \hyperlink{gromov<1>}{\beamergotobutton{Détails}}

\end{frame}



\begin{frame}

\end{frame}














\begin{frame}[label=hnc]

\begin{lem}
$$
h(X)=(\|d^{-1}\|_{1\to 1})^{-1}\text{ over }\F.
$$ 
\end{lem}

The support $x\mapsto A=\{v\,;\,x(v)\not=\bar 0\}$ is a $1-1$ correspondence between $0$-cochains (resp. $1$-cochains) over $\F$ and subsets of vertices (resp. of edges). If $A$ is a subset of vertices and $x$ the corresponding $0$-cochain, then the subset of edges corresponding to $dx$ is $\partial A$. 

Furthermore, $\|x\|_1=\#A/n$ and $\|dx\|_1=\#\partial A/e$. 

\bigskip

Since $G$ is connected, the kernel of $d$ consists of the two $0$-cochains $x$ which are constant functions on the set of vertices.

\bigskip

If $y\in C^1$ belongs to $dC^0$, there exist exactly two $0$-cochains $x_1,x_2\in C^0$ such that $dx_1=dx_2=y$. One of them (let us denote it by $x$) has least $\ell^1$ norm. The support $A$ of $x$ satisfies $\#A\le \frac{n}{2}$ and $\partial A$ corresponds to $y$. Therefore the estimates 
$$
\|x\|_1\le h^{-1}\,\|y\|_1\quad \text{and}\quad \# \partial A/e\ge h\,\#A/n
$$ 
are equivalent.  
\medskip

\hyperlink{chee<3>}{\beamerreturnbutton{Back}}
\end{frame}


\begin{frame}[label=isopnc]

\begin{exa}
For the complete graph $K_n$ on $n$ vertices, $h(K_n)=\frac{n}{n-1}$ ($n$ even) or $\frac{n+1}{n-1}$ ($n$ odd).
\end{exa}

Indeed, for every subset $A$, every vertex of $A$ is connected to $n-\#A$ vertices of $A^c$, so
\begin{align*}
\P(\partial A)=\frac{\#\partial A}{e}
=\frac{\#A(n-\#A)}{n(n-1)/2}
=2\frac{n}{n-1}\P(A)(1-\P(A)).
\end{align*}
Since $\P(A)\le \frac{1}{2}$ (resp. $\frac{n-1}{2n}$),
\begin{align*}
\frac{\P(\partial A)}{\P(A)}\ge \frac{n}{n-1} \quad\text{(resp, }\frac{n+1}{n-1}\text{)},
\end{align*}
with equality if $n$ is even and $\#A=\frac{n}{2}$ or $n$ is odd and $\#A=\frac{n-1}{2}$.

\medskip

\hyperlink{chee<4>}{\beamerreturnbutton{Back}}
\end{frame}


\begin{frame}[label=lambda2]

\begin{pro}
$X$ connected, $\Delta$ defined by $\|df\|_2^2=\langle f,\Delta f \rangle$ with eigenvalues $\lambda_1\le \lambda_2\le\cdots$. Then 
\begin{align*}
\lambda_1=0\quad \text{and}\quad \lambda_2=(\|d^{-1}\|_{2\to 2})^{-2}.
\end{align*}
\end{pro}

Given $f\in C^0(G,\R)$, let $f=\sum f_\lambda$ be the decomposition of $f$ according to eigenspaces of $\Delta$. Then
\begin{align*}
\|f\|_2^2=\sum \|f_\lambda\|^2,\quad \|df\|_2^2=\langle df,df \rangle=\langle f,\Delta f \rangle=\sum \lambda \|f_\lambda\|^2.
\end{align*}
Since $G$ is connected, $df=0$ implies that $f$ is a constant function on vertices, so the kernel of $d$, which coincides with the $0$-eigenspace of $\Delta$, is $1$-dimensional.

\bigskip

If $f\in C^0(G,\R)$ and $f_0=0$, then
\begin{align*}
\|df\|_2^2 \ge \lambda_2 \|f\|_2^2.
\end{align*}
This shows that every $g\in dC^0$ has a primitive $f$ such that $\|f\|_2\le \lambda_2^{-1/2}\|g\|_2$. Equality holds if $g=df$ where $f$ belongs to the $\lambda_2$-eigenspace of $\Delta$, so $\|d^{-1}\|_{2\to 2}=\lambda_2^{-1/2}$.

\hyperlink{Laplacian<1>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=cheeger-buser]

\begin{thm}[Cheeger, Buser, Dodziuk, Alon-Milman]
Pour un graphe fini connexe muni d'une distribution de Garland $\P$,
\begin{align*}
\frac{1}{2}\lambda_{2,\P}\le h_\P\le 2\sqrt{\lambda_{2,\P}}.
\end{align*}
\end{thm}

L'inégalité de gauche consiste à associer une cocha{\^\i}ne réelle $f=|x|$ à une $\F$-cocha{\^\i}ne $x$ et à comparer $d^{-1}df$ et $d^{-1}dx$.
\pause

\medskip

L'inégalité de droite résulte de deux principes :
\begin{itemize}
  \item Isopérimetrie $\implies$ inégalité de Poincar\'e-Sobolev $\ell^1$. \\ En effet, toute fonction réelle $f$ à médiane nulle est l'intégrale de fonctions à valeurs dans $\{0,1\}$, les fonctions caractéristiques de ses ensembles de sur-niveaux.
  \item L'inégalité de Poincar\'e-Sobolev $\ell^1$ $\implies$ inégalité de Poincar\'e-Sobolev $\ell^2$. \\ Il suffit d'appliquer l'inégalité $\ell^1$ à $g=f|f|$, puis Cauchy-Schwartz.
\end{itemize}

\end{frame}

\begin{frame}

\begin{thm}
$h\ge \frac{1}{2}\lambda_2.$
\end{thm}

If $x$ is an $\F$-cochain, $f=|x|$ is a real cochain, and $\|x\|_1=\|f\|_2^2$, $\|dx\|_1=\|df\|_2^2$. 

\medskip

The real number $m$ which minimizes $\E((f-m)^2)$, is $m=\E(f)$. Thus $d^{-1}df=f-\E(f)$,
and 
$$
\|f-\E(f)\|_2^2 \leq (|d^{-1}|_{2\to 2})^2\|f\|_2^2.
$$

\medskip

On the other hand,
$$
\|f-\E(f)\|_2^2=\P(x\not=0)(1-\E(f))^2+\P(x=0)\E(f)^2=\|x\|_1(1-\|x\|_1)\ge \frac{1}{2}\|d^{-1}dx\|_1.
$$
so
$$
\|d^{-1}dx\|_1\le 2(|d^{-1}|_{2\to 2})^2\|x\|_1,
$$
and
$$
\|d^{-1}\|_{1\to 1}\le 2(|d^{-1}|_{2\to 2})^2.
$$
\hyperlink{lambda2h<2>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=buser-cheeger]

\begin{thm}
$h\le 2\sqrt{\lambda_2}.$
\end{thm}

\textbf{First step}.
\begin{align*}
\|d_{\R}^{-1}\|_{1\to 1}\le \|d_{\F}^{-1}\|_{1\to 1},
\end{align*}
i.e. the isoperimetric inequality (expressed in terms of $\F$ cochains) implies the Poincar\'e-Sobolev inequality (expressed in terms of $\R$ cochains).

Let $f\in C^0(G,\R)$ be a function whose median vanishes. For $t\not=0$, define $x_t\in C^0(G,\F)$ by
\begin{align*}
x_t(v)=\begin{cases}
\bar 1 & \text{if }\frac{f(v)}{t}>1, \\
\bar 0 & \text{otherwise},
\end{cases}
\end{align*} 
and set $f_t=|x_t|$. Then $\displaystyle |f|=\int_{\R}f_t \,dt$.
Since the $\ell^1$ norm is a norm,
\begin{align*}
\|f\|_1&=\||f|\|_1\le \int_{\R}\|f_t\|_1\,dt = \int_{\R}\|x_t\|_1\,dt\le h^{-1}\int_{\R}\|dx_t\|_1\,dt=h^{-1}\int_{\R}\|df_t\|_1\,dt\\
&\le h^{-1}\|df\|_1.
\end{align*}
\end{frame}

\begin{frame}

\textbf{Second step}.
The $\ell^1$ Poincar\'e-Sobolev inequality implies its $\ell^2$ version. 

\medskip

Let $g=f|f|$. Then the median of $g$ is equal to $0$ as well. One can apply the $\ell^1$ Poincar\'e-Sobolev inequality to $g$ and get
\begin{align*}
\|g\|_1\le h^{-1}\|dg\|_1.
\end{align*}
One checks that $\|dg\|_1\le 2\|f\|_2\|df\|_2$, hence
\begin{align*}
\|f\|_2^2=\|g\|_1\le h^{-1}2\|f\|_2\|df\|_2,
\end{align*}
so
\begin{align*}
\|f\|_2\le 2h^{-1}\|df\|_2
\end{align*}
and
$$
\lambda_2^{-1/2}=\|d^{-1}\|_{2\to 2}\le 2h^{-1}.
$$

\hyperlink{lambda2h<3>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=expanderdetail]

\begin{center}
\textbf{What are expanders good for}
\end{center}

\bigskip

The uniform spectral gap says that spectrally, an expander behave as a complete graph. Therefore, in a problem where one should check all pairs of points (e.g. find the minimal distance between two points of a cloud), one can pick an expander and check only its edges. Hence expanders are used to \emph{derandomize} algorithms. Fortunately, there are (several) deterministic constructions of expanders.\pause

\bigskip

The spectral gap measures the exponential speed at which the simple random walk on the graph is mixing (i.e. pushes forward any distribution close to the uniform distribution). For instance, the art of cards shuffling is closely related to expansion in the symmetric group.\pause

\bigskip

The spectral gap also controls coarse embeddings to Hilbert spaces. For instance, planar graphs cannot be expanders. Examples of finitely generated groups that cannot be coarsely embedded in Hilbert spaces (Gromov monsters) have been constructed by arranging that an expander embeds in their Cayley graphs.

\medskip

\hyperlink{expander<1>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=seidel]

A \emph{Seidel switch} on a graph consists in picking a vertex, removing all edges that contain it and insert edges to all vertices that were not previously its neighbours. 

\begin{center}
\definecolor{ffqqqq}{rgb}{1.,0.,0.}
\definecolor{qqqqcc}{rgb}{0.,0.,0.8}
\definecolor{qqqqff}{rgb}{0.,0.,1.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.1cm,y=0.1cm]
\clip(-9.049378759324258,-22.356437343822005) rectangle (48.19430081075812,2.524184275905502);
\draw [color=qqqqcc] (0.,-10.)-- (-5.,-10.);
\draw [color=qqqqcc] (0.,-10.)-- (-5.,-5.);
\draw [color=qqqqcc] (-5.,0.)-- (0.,-10.);
\draw [color=qqqqcc] (0.,-10.)-- (-5.,-20.);
\draw [color=qqqqcc] (0.,-10.)-- (-5.,-15.);
\draw [color=ffqqqq] (35.,-10.)-- (45.,0.);
\draw [color=ffqqqq] (45.,-5.)-- (35.,-10.);
\draw [color=ffqqqq] (35.,-10.)-- (45.,-10.);
\draw [color=ffqqqq] (35.,-10.)-- (45.,-15.);
\draw (-5.,0.)-- (10.,0.);
\draw (-5.,-5.)-- (10.,-10.);
\draw (10.,-5.)-- (-5.,-20.);
\draw (10.,-15.)-- (-5.,-20.);
\draw (10.,0.)-- (10.,-5.);
\draw [shift={(0.,-5.)}] plot[domain=-0.46364760900080615:0.4636476090008061,variable=\t]({1.*11.180339887498949*cos(\t r)+0.*11.180339887498949*sin(\t r)},{0.*11.180339887498949*cos(\t r)+1.*11.180339887498949*sin(\t r)});
\draw [shift={(20.,-10.)}] plot[domain=2.677945044588987:3.6052402625905993,variable=\t]({1.*11.180339887498949*cos(\t r)+0.*11.180339887498949*sin(\t r)},{0.*11.180339887498949*cos(\t r)+1.*11.180339887498949*sin(\t r)});
\draw [shift={(55.,-10.)}] plot[domain=2.677945044588987:3.6052402625905993,variable=\t]({1.*11.180339887498949*cos(\t r)+0.*11.180339887498949*sin(\t r)},{0.*11.180339887498949*cos(\t r)+1.*11.180339887498949*sin(\t r)});
\draw [shift={(35.,-5.)}] plot[domain=-0.46364760900080615:0.4636476090008061,variable=\t]({1.*11.180339887498949*cos(\t r)+0.*11.180339887498949*sin(\t r)},{0.*11.180339887498949*cos(\t r)+1.*11.180339887498949*sin(\t r)});
\draw (45.,-5.)-- (30.,-20.);
\draw (45.,-15.)-- (30.,-20.);
\draw (45.,0.)-- (30.,0.);
\draw (45.,-10.)-- (30.,-5.);
\draw (45.,0.)-- (45.,-5.);
\draw (-5.,0.)-- (-5.,-5.);
\draw (30.,0.)-- (30.,-5.);
\draw [shift={(10.,-15.)}] plot[domain=2.819842099193151:3.4633432079864352,variable=\t]({1.*15.811388300841898*cos(\t r)+0.*15.811388300841898*sin(\t r)},{0.*15.811388300841898*cos(\t r)+1.*15.811388300841898*sin(\t r)});
\draw [shift={(45.,-15.)}] plot[domain=2.819842099193151:3.4633432079864352,variable=\t]({1.*15.811388300841898*cos(\t r)+0.*15.811388300841898*sin(\t r)},{0.*15.811388300841898*cos(\t r)+1.*15.811388300841898*sin(\t r)});
\begin{scriptsize}
\draw [fill=qqqqff] (0.,-10.) circle (0.5pt);
\draw [fill=qqqqff] (-5.,0.) circle (0.5pt);
\draw [fill=qqqqff] (-5.,-5.) circle (0.5pt);
\draw [fill=qqqqff] (-5.,-15.) circle (0.5pt);
\draw [fill=qqqqff] (-5.,-20.) circle (0.5pt);
\draw [fill=qqqqff] (-5.,-10.) circle (0.5pt);
\draw [fill=qqqqff] (10.,0.) circle (0.5pt);
\draw [fill=qqqqff] (10.,-5.) circle (0.5pt);
\draw [fill=qqqqff] (10.,-10.) circle (0.5pt);
\draw [fill=qqqqff] (10.,-15.) circle (0.5pt);
\draw [fill=qqqqff] (30.,0.) circle (0.5pt);
\draw [fill=qqqqff] (30.,-5.) circle (0.5pt);
\draw [fill=qqqqff] (30.,-10.) circle (0.5pt);
\draw [fill=qqqqff] (30.,-15.) circle (0.5pt);
\draw [fill=qqqqff] (30.,-20.) circle (0.5pt);
\draw [fill=qqqqff] (35.,-10.) circle (0.5pt);
\draw [fill=qqqqff] (45.,0.) circle (0.5pt);
\draw [fill=qqqqff] (45.,-5.) circle (0.5pt);
\draw [fill=qqqqff] (45.,-10.) circle (0.5pt);
\draw [fill=qqqqff] (45.,-15.) circle (0.5pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}


Two graphs on the same vertex set are \emph{Seidel equivalent} if they can be obtained one from the other after a finite number of Seidel switches.

\begin{exa}
Seidel equivalence is $(3,1)$-testable.
\end{exa}
Indeed, a graph with vertex set $\{1,\ldots,n\}$ can be viewed as a $1$-cochain on the complete graph $K_n$. A Seidel switch at vertex $v$ amounts to adding $d\chi_v$, where $\chi_v(v)=\bar 1$ and $\chi_v=\bar 0$ elsewhere. Therefore two graphs with vertex set $\{1,\ldots,n\}$ are Seidel equivalent if and only if the corresponding $1$-cochains are cohomologous, and we have a $(3,1)$-tester for that, since $H^1(K_n,\F)=0$ and $h_1(K_n)\ge 1$.

\medskip

\hyperlink{testing<3>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=gromov]

Let $X$ be a simplicial complex. Fix a Garland probability distribution on simplices $\sigma$ of $X$. The \emph{local sparsity} of $X$ controls the fraction of simplices of all dimensions that can meet at a vertex,
\begin{align*}
\mathrm{spar}(X)=\max_{v\in X^0}\P(v\in\sigma).
\end{align*}\pause

When $H^k(X,\F)\not=0$, the \emph{$k$-cosystole} of $X$ is the length of its shortest nonzero vector,
\begin{align*}
\theta_k(X):=\min\{\|\kappa\|_1\,;\,\kappa\in C^k(X,\F)\setminus dC^{k-1}(X,\F)\}.
\end{align*}\pause

\begin{thm}[Gromov 2010]
For every $h>0,\theta>0$ and $N$, for all sufficiently small $\epsilon>0$, there exists $c(\epsilon,h,\theta,N)>0$ such that for every simplicial complex $X$ of pure dimension $N$, and every continuous map $F:X\to\R^N$, there exists a point in $\R^N$ which belongs to the images by $F$ of at least a fraction 
$$
c(\mathrm{spar}(X),\min_{k=0,\ldots,N-1}h_k(X),\min_{k=0,\ldots,N-1}\theta_k(X),N)
$$
of the $N$-simplices of $X$.
\end{thm}

\hyperlink{papier<2>}{\beamerreturnbutton{Back}}

\end{frame}


\begin{frame}[label=trihomdist]

\begin{lem}
$HomDist(B_1,B_3)\le HomDist(B_1,B_2)+HomDist(B_2,B_3)$.
\end{lem}

Let $\displaystyle (B_1,d_1,Q_1) \maprl{F_1}{F_2} (B_2,d_2,Q_2)$ and $\displaystyle (B_2,d_2,Q'_2) \maprl{G_2}{G_3} (B_3,d_3,Q_3)$ be homotopies. Let 
$q=\max\{|Q_1|,|Q_2|\}$, $f=\max\{1,{|F_1||F_2|}\}$, $q'=\max\{|Q'_2|,|Q_3|\}$, $f'=\max\{1,{|G_2||G_3|}\}$. Then
$\displaystyle (B_1,d_1,Q'_1) \maprl{G_2F_1}{F_2G_3} (B_3,d_3,Q'_3)$
is a homotopy, where
\begin{align*}
Q'_1=Q_1+F_2Q'_2 F_1,\quad Q'_3=Q_3+G_2Q_2G_3.
\end{align*}

\medskip

Thus $q''=\max\{|Q'_1|,|Q'_3|\}$ and $f''=\max\{1,{|G_2F_1||F_2G_3|}\}$ satisfy
\begin{align*}
q''\le f'q+fq',\quad f'' \le ff',
\end{align*}
so $\displaystyle \frac{q''}{f''}+\log(f'')\le \frac{q}{f}+\log(f)+\frac{q'}{f'}+\log(f')$.

\medskip

The expression $\displaystyle \max\{\frac{q}{f}+\log f,1\}$ is necessary in order for this function to be nondecreasing in $q$ and in $f$.

\medskip

\hyperlink{homdist<1>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=dist0]

\begin{lem}
$HomDist(B,0)\ge \|\bar d^{-1}\|$.
\end{lem}

Let 
\begin{align*}
(B,d,Q)\maprl{0}{0} (0,0,0)
\end{align*}
be a homotopy to the trivial complex. This simply means that $1=dQ+Qd$. If $y\in \mathrm{Im}(d)$, $y=dx$, then 
\begin{align*}
y=dx=d(dQx+Qdx)=dQdx=dQy,
\end{align*} 
thus $|Qy|\ge |\bar d^{-1}y|$, and $|Q|\ge|\bar d^{-1}|$, so
\begin{align*}
HomDist(B,0)\ge \max\{|Q|,\frac{1}{|Q|}+\log(|Q|)\}\ge |\bar d^{-1}|=NH(B).
\end{align*}

\hyperlink{nh<1>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=nhhom]

\begin{lem}
$\mathrm{NH}(B_1)\le \exp(\mathrm{HomDist}(B_1,B_2))(1+\mathrm{NH}(B_2))$.
\end{lem}
Let $(B_1,d_1,Q_1)\maprl{F_1}{F_2}(B_2,d_2,Q_2)$ be a homotopy of complexes. Let $c_2=\mathrm{NH}(B_2)$. 

\medskip

If $y_1\in d_1B_1$, $y_2=f_1(y_1)\in d_2B_2$, so there exists $x_2\in B_2$ such that $dx_2=y_2$ and $|x_2|\le c_2|y_2|$. Let $x_1=Q_1y_1+F_2(x_2)$. Then $dx_1=y_1$ and
\begin{align*}
|x_2|\le |Q_1||y_1|+|F_2|c_2|F_1||y_1|\le (q+fc_2)|y_2|.
\end{align*}
Therefore $\mathrm{NH}(B_1)\le q+fc_2$. 

\medskip

Remember that $D=\mathrm{HomDist}(B_1,B_2)=\max\{\frac{q}{f}+\log f,\frac{f}{q}+\log q\}$. 

If $q\le f$, $D=\frac{q}{f}+\log f$ and $q+fc_2\le f+fc_2\le e^D(1+c_2)$. 

If $q\ge f$, $D=\frac{f}{q}+\log q$ and $q+fc_2\le q+qc_2\le e^D(1+c_2)$ again.

\medskip

\hyperlink{homdist<4>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=nhdetail]

\begin{pro}
If $B$ is a Hilbert space, $HomDist(B,0)= NH(B)\iff H(B)=0$. 
\end{pro}
Indeed, homotopic complexes has the same homology, so $HomDist(B,0)<\infty\implies H(B)=0$.

\medskip

Conversely, assume that $H(B)=0$. The orthogonal projection $\pi:B\to \mathrm{Im}(d)$ has norm $\le 1$. The section $\sigma$ of the projection $p:B\to B/\mathrm{Ker}(d)$ whose image is the orthogonal complement of $\mathrm{Ker}(d)$ has norm $\le 1$. Therefore $Q=\sigma\bar d^{-1}\pi$ satisfies $|Q|\le|\bar d^{-1}|$. Since $H(B)=0$, $\mathrm{Im}(\sigma)=\mathrm{Ker}(\pi)$, and $B$ is the orthogonal direct sum $B=\mathrm{Im}(\sigma)\oplus \mathrm{Im}(d)$. In this decomposition,
\begin{align*}
Qd=\begin{pmatrix}
1 & 0  \\
0  & 0
\end{pmatrix}\quad \text{and} \quad dQ=\begin{pmatrix}
0 & 0  \\
0  & 1
\end{pmatrix},
\end{align*}
so $dQ+Qd=1$, $HomDist(B,0)\le NH(B)$.

\hyperlink{nh<2>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=k3detail]

\begin{exa}
$HomDist(B_{K_3,\F,1},0)=1 $, $NH(B_{K_3,\F,1})=\frac{1}{2}$.
\end{exa}
The assertion $NH(B_{K_3,\F,1})=\frac{1}{2}$ is a special case of $h(K_n)=\frac{n+1}{n-1}$ for $n$ odd.

\medskip

Let $Q:B\to B$ satisfy $1=dQ+Qd$. Let $e_1,e_2,e_3$ be the natural basis of $C^0(K_3,\F)$. Then $|de_1|=|de_2|=|de_3|=\frac{2}{3}$, and $d(e_1+e_2+e_3)=\bar 0$. 

If $Qde_1$ has norm $<\frac{2}{3}$, then $Qde_1=e_1$. If furthermore $Qde_2$ has norm $<\frac{2}{3}$, then $Qde_2=e_2$. Then $Qd(e_3)=Qde_1+Qde_2=e_1+e_2$ has norm $\frac{2}{3}$. Thus one of the $Qde_i$ must have norm $\frac{2}{3}$, thus $|Q|\ge 1$.

\medskip

Conversely, let us denote by $e_0$ the nonzero element of $H^0(K_3,\F)$, so that $de_0=e_1+e_2+e_3$ and $e_0,e_1,e_2,e_3,de_1,de_2$ is a basis of $B_{K_3,\F,1}$. If $x=x_0e_0+x_1e_1+x_2e_2+x_3e_3+x_4de_1+x_5de_2$, 
\begin{align*}
|x|=\frac{1}{3}(|x_0|+|x_1|+|x_2|+|x_3)+\frac{2}{3}\max\{|x_4|,|x_5|,|x_4+x_5|\}.
\end{align*}
Let us set $Q(x)=x_3e_3+x_4e_1+x_5e_2$. Then $dQ+Qd=1$, and
\begin{align*}
|Q(x)|=\frac{1}{3}(|x_3|+|x_4|+|x_5|)\le \frac{1}{3}|x_3|+\frac{2}{3}\max\{|x_4|,|x_5|\}\le|x|.
\end{align*}

\hyperlink{nh<4>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}[label=Hausdetail]

\begin{lem}
\label{triembedded}
Let $(B,d)$ be a normed complex. The embedded Hausdorff distance $\mathrm{HausDist}_{B}$ between subcomplexes of $B$ satisfies the triangle inequality.
\end{lem}

Let $B_1,B_2,B_3$ be subcomplexes of $B$. Let
operators $F_1,F_2, Q_1, Q_2:B\to B$ satisfy 
\begin{align*}
F_1(B_1)\subset B_2,\quad &F_2(B_2)\subset B_3,\\
1-F_1=d_1Q_1+Q_1d_1,\quad &1-F_2=d_2Q_2+Q_2d_2.
\end{align*}
Then $F_3=F_2F_1$ maps $B_1$ to $B_3$ and satisfies $1-F_3=dQ_3+Q_3d$ for
$$
Q_3=Q_1+Q_2 F_1.
$$
Since
$$
|Q_3| \le |Q_1|\max\{|F_2|,1\}+|Q_2||F_1|\quad\text{and}\quad |F_3|\le|F_1||F_2|,
$$
\begin{align*}
\frac{|Q_3|}{\max\{|F_3|}+\log(\max\{|F_3|,1\}) &\le \frac{|Q_1|}{|F_1|}+\log(|F_1|)+\frac{|Q_2|}{\max\{|F_2|,1\}}+\log(\max\{|F_2|,1\}) . 
\end{align*}

\hyperlink{Haus<1>}{\beamerreturnbutton{Back}}

\end{frame}

\begin{frame}

\begin{cor}
Let $r>0$. The Hausdorff distance $\mathrm{HausDist}_r$ between complete normed complexes $B\stackrel{d}{\to}B$ such that $|d|\leq r$ satisfies the triangle inequality.
\end{cor}

Given isometries of $B_1,B_2$ to subcomplexes of $B$ and isometries of $B_2,B_3$ to subcomplexes of $\bar B$, one constructs a complex $\bar{\bar B}$ that contains isometric copies of $B$ and $\bar B$ which intersect along a common subcomplex $B''$ isometric to $B_2$. One starts with $B\oplus \bar{B}$ with the norm $|(x,\bar x)|=|x|+|\bar x|$. By completeness, the subspace
\begin{align*}
D=\{(-x'',i(x''))\,;\,x''\in B''\}
\end{align*}
of $B\oplus \bar{B}$ is closed. Let $\bar{\bar B}=(B\oplus \bar{B})/D$, equipped with the quotient norm and the quotient operator $\bar{\bar d}$. 

\medskip

The embedded Hausdorff distances in $\bar{\bar B}$ are less that those in $B$ and $\bar B$, so one can apply the previous Lemma.

\medskip

\hyperlink{Haus<1>}{\beamerreturnbutton{Back}}

\end{frame}

\end{document}