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

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{pro}[lem]{Proposition}
\newtheorem{cor}[lem]{Corollary}
\newtheorem{dfi}[lem]{Definition}
\newtheorem{rem}[lem]{Remark}
\newtheorem{ntn}[lem]{Notation}
\newtheorem{que}[lem]{Question}
\newtheorem{pbm}[lem]{Problem}
\newtheorem{sol}[lem]{Solution}
\newtheorem{con}[lem]{Conclusion}
\newtheorem{coj}[lem]{Conjecture}
\newtheorem{exa}[lem]{Example}
\newtheorem{exs}[lem]{Examples}
\newtheorem{res}[lem]{Results}
\newtheorem{fac}[lem]{Fact}
\newtheorem{pla}[lem]{Plan of lecture}
\newtheorem{sch}[lem]{Scheme of proof}
\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{Near-homology}
\author{Pierre Pansu, Universit\'e Paris-Saclay}
\date{May 12th, 2022}


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

\begin{document}

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

\section{Near-cohomology}
\subsection{What is cohomology?}

\begin{frame}

$X$ simplicial complex, $\k$ a field. A $k$-cochain is a (skew-symmetric) $\k$-valued function $f$ on the set of $k$-simplices. Its \emph{coboundary} $df$ is $df(\sigma)=f(\partial\sigma)$, e.g.,
\begin{itemize}
  \item $k=0$, $e=vv'$ edge, $df(e)=f(v)-f(v')$.
  \item $k=1$, $\sigma=vv'v''$ triangle, $df(\sigma)=f(vv')+f(v'v'')+f(v''v)=f(vv')-f(vv'')+f(v'v'')$.
\end{itemize}
Cohomology is $H^\cdot(X,\k)=\mathrm{Ker}(d)/\mathrm{Im}(d)$ in each degree.\pause

\begin{minipage}{6cm}

\begin{center}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.3cm,y=0.3cm]
\clip(-2.536661241390902,5.346267276405821) rectangle (17.527039105908948,9.128768161552495);
\draw (0.,6.)-- (14.,6.);
\begin{scriptsize}
\draw [fill=black] (0.,6.) circle (2.5pt);
\draw[color=black] (-0.06981283803436303,7.) node {$A$};
\draw [fill=black] (14.,6.) circle (2.5pt);
\draw[color=black] (13.941886093030778,7.) node {$H$};
\draw [fill=black] (2.,6.) circle (2.5pt);
\draw[color=black] (1.936557196695622,7.) node {$B$};
\draw [fill=black] (4.,6.) circle (2.5pt);
\draw[color=black] (3.910035919380853,7.) node {$C$};
\draw [fill=black] (6.,6.) circle (2.5pt);
\draw[color=black] (5.9164059541108385,7.) node {$D$};
\draw [fill=black] (8.,6.) circle (2.5pt);
\draw[color=black] (7.988558612930331,7.) node {$E$};
\draw [fill=black] (10.,6.) circle (2.5pt);
\draw[color=black] (9.962037335615562,7.) node {$F$};
\draw [fill=black] (12.,6.) circle (2.5pt);
\draw[color=black] (11.869733434211286,7.) node {$G$};
\end{scriptsize}
\end{tikzpicture}
\end{center}

\end{minipage}\begin{minipage}{4cm}

\begin{exa}
$X=n$-stick. $H^0=$ constant functions $\simeq\k$. 

$H^1=0$.
\end{exa}

\end{minipage}\pause

\begin{minipage}{6cm}
\begin{exa}
$X=n$-cycle. $H^0=$constant functions $\simeq\k$. 

$H^1\simeq\k$ by $f\mapsto \sum_{\mathrm{edges}\,e}f(e)$.
\end{exa}
\end{minipage}\begin{minipage}{4cm}

\begin{center}
\definecolor{uuuuuu}{rgb}{0.26666666666666666,0.26666666666666666,0.26666666666666666}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.2cm,y=0.2cm]
\clip(-2.898465673883194,-7.6458009812719006) rectangle (12.790690171464394,7.451311247270104);
\draw (1.9365571966956214,-6.3959311235712555)-- (7.856993364751315,-6.363039811526502);
\draw (7.856993364751315,-6.363039811526502)-- (11.52260947483337,-1.7137490277685223);
\draw (11.52260947483337,-1.7137490277685223)-- (10.173121831108162,4.050930439284523);
\draw (10.173121831108162,4.050930439284523)-- (4.824722153832029,6.590077372910569);
\draw (4.824722153832029,6.590077372910569)-- (-0.4951355125351853,3.991662342930953);
\draw (-0.4951355125351853,3.991662342930953)-- (-1.7804898398989701,-1.7876551350725864);
\draw (-1.7804898398989701,-1.7876551350725864)-- (1.9365571966956214,-6.3959311235712555);
\begin{scriptsize}
\draw [fill=black] (1.9365571966956214,-6.3959311235712555) circle (2.5pt);
\draw[color=black] (2.495709501456438,-4.817148145423072) node {$A$};
\draw [fill=black] (7.856993364751315,-6.363039811526502) circle (2.5pt);
\draw[color=black] (7.166275811811484,-4.981604705646841) node {$B$};
\draw [fill=uuuuuu] (11.52260947483337,-1.7137490277685223) circle (2.5pt);
\draw[color=uuuuuu] (10.19227651992884,-1.396451692768674) node {$C$};
\draw [fill=uuuuuu] (10.173121831108162,4.050930439284523) circle (2.5pt);
\draw[color=uuuuuu] (9.073971910407208,3.274114617586369) node {$D$};
\draw [fill=uuuuuu] (4.824722153832029,6.590077372910569) circle (2.5pt);
\draw[color=uuuuuu] (4.830992656633962,5.116028092092583) node {$E$};
\draw [fill=uuuuuu] (-0.4951355125351853,3.991662342930953) circle (2.5pt);
\draw[color=uuuuuu] (0.8182525871739914,2.912310185094077) node {$F$};
\draw [fill=uuuuuu] (-1.7804898398989701,-1.7876551350725864) circle (2.5pt);
\draw[color=uuuuuu] (-0.16848677416862412,-1.1991038205001512) node {$G$};
\end{scriptsize}
\end{tikzpicture}
\end{center}

\end{minipage}

\end{frame}

\subsection{What is near-cohomology?}

\begin{frame}

Pick an absolute value on $\k$. Get norms on cochains: picking simplices uniformly at random, set $\|f\|_p=\E(|f|^p)^{1/p}$.\pause

\medskip

Let $n=2m+1$ be odd. In the $n$-stick with vertices $v_0,\ldots,v_n$, the $1$-chain $g$ equal to $\bar 1$ on the middle edge $v_m v_{m+1}$ and $0$ elsewhere is $df$ where $f(v_i)=\bar 0$ for $i\le m$ and $f(v_i)=\bar 1$ for $i\ge m+1$. Then
\begin{align*}
\|g\|_p=\frac{1}{n^{1/p}},\quad \|f\|_p\sim \frac{1}{2^{1/p}}.
\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

When $\k=\F$, the only other choice for $f$ is $\bar 1+f$ which has the same norm. When $\k=\R$, the optimal choice is $f(v_i)=\pm \frac{1}{2}$ which has norm $\frac{1}{2}$.\pause

When $n$ is large, it is costly to solve $df=g$. We say that $g$ is nontrivial in \emph{near-cohomology}.

\begin{dfi}
The \textbf{near-cohomology threshold in degree $k$} is the norm of the inverse $\bar d^{-1}$ of $\bar d : C^{k}(X,\k)/\mathrm{Ker}(d)\to dC^{k}(X,\k)$. (It depends on $p$, i.e. on a choice of norm).
\end{dfi}

\end{frame}

\begin{frame}

\begin{fac}
Like cohomology, near-cohomology is a topological (even homotopy) invariant of simplicial complexes. Respectively, a quasiisometry invariant (for infinite complexes of locally bounded geometry).
\end{fac}\pause

\medskip

Remember: cohomology is not the only interesting information one can extract from cochain complexes. Apparently, near-cohomology is significant too.\pause

\begin{pla}
\begin{enumerate}
  \item Relate the various $\ell^p$ near-cohomology thresholds for graphs to expansion.
  \item Survey the theory of higher dimensional expanders.
  \item Briefly mention one other instance where near-cohomology is relevant.
  \item Start a more general discussion of normed chain complexes and the role played by near-homology.
\end{enumerate}
\end{pla}

\end{frame}

\subsection{Isoperimetry}

\begin{frame}

\begin{dfi}
The \textbf{near-cohomology threshold in degree $k$} is the norm of the inverse $\bar d^{-1}$ of $\bar d : C^{k}(X,\k)/\mathrm{Ker}(d)\to dC^{k}(X,\k)$.
\end{dfi}

For the $n$-stick or the $n$-cycle, $\|d^{-1}\|_{p\to p}\sim n^{1/p}$. \pause

\begin{que}
Are there large graphs without near-cohomology (i.e. bounded near-cohomology threshold)?
\end{que}\pause

\begin{minipage}{5cm}

This is a geometric question. In a graph $X$ with $n$ vertices and $e$ edge, $A$ a subset of vertices, the \textbf{edge-boundary $\partial A$} of $A$ is the set of edges that join $A$ to its complement.

\end{minipage}\begin{minipage}{5cm}

\begin{center}
\definecolor{qqzzqq}{rgb}{0.,0.6,0.}
\definecolor{ffqqqq}{rgb}{1.,0.,0.}
\definecolor{qqqqff}{rgb}{0.,0.,1.}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.07cm,y=0.07cm]
\clip(-5.76000982177678,-18.30258608377214) rectangle (29.20345488179657,6.629028446151257);
\draw (-2.997139610017456,4.32663660301849)-- (-3.918096347270564,0.4125704696927845);
\draw (-3.918096347270564,0.4125704696927845)-- (1.377404891934806,0.5112444058270478);
\draw (1.377404891934806,0.5112444058270478)-- (-2.997139610017456,4.32663660301849);
\draw (-2.997139610017456,4.32663660301849)-- (2.758839997814468,2.9780928091835848);
\draw (2.758839997814468,2.9780928091835848)-- (1.377404891934806,0.5112444058270478);
\draw (1.377404891934806,0.5112444058270478)-- (5.094123152991991,0.6099183419613093);
\draw (2.758839997814468,2.9780928091835848)-- (5.094123152991991,0.6099183419613093);
\draw (-3.918096347270564,0.4125704696927845)-- (-4.740379148389411,-4.751365521333566);
\draw (-4.740379148389411,-4.751365521333566)-- (1.377404891934806,0.5112444058270478);
\draw [color=qqzzqq] (1.377404891934806,0.5112444058270478)-- (0.5222307787712068,-6.231474563347488);
\draw [color=qqzzqq] (0.5222307787712068,-6.231474563347488)-- (-4.740379148389411,-4.751365521333566);
\draw [color=qqzzqq] (0.5222307787712068,-6.231474563347488)-- (5.094123152991991,0.6099183419613093);
\draw (5.094123152991991,0.6099183419613093)-- (6.047971202289853,-2.2845171179770274);
\draw [color=qqzzqq] (6.047971202289853,-2.2845171179770274)-- (0.5222307787712068,-6.231474563347488);
\draw (2.758839997814468,2.9780928091835848)-- (5.192797089126253,5.116028092092583);
\draw (5.192797089126253,5.116028092092583)-- (5.094123152991991,0.6099183419613093);
\draw (5.094123152991991,0.6099183419613093)-- (9.567341591078517,2.747853624870308);
\draw (9.567341591078517,2.747853624870308)-- (5.192797089126253,5.116028092092583);
\draw (9.567341591078517,2.747853624870308)-- (6.047971202289853,-2.2845171179770274);
\draw (6.047971202289853,-2.2845171179770274)-- (11.507929001718995,-4.488235024975535);
\draw (11.507929001718995,-4.488235024975535)-- (9.567341591078517,2.747853624870308);
\draw (9.567341591078517,2.747853624870308)-- (16.079821375939783,5.839636957077166);
\draw (16.079821375939783,5.839636957077166)-- (11.507929001718995,-4.488235024975535);
\draw (11.507929001718995,-4.488235024975535)-- (21.210866054921386,1.4979837671696608);
\draw (16.079821375939783,5.839636957077166)-- (21.210866054921386,1.4979837671696608);
\draw (21.210866054921386,1.4979837671696608)-- (21.441105239234663,-5.376300450183889);
\draw (21.441105239234663,-5.376300450183889)-- (11.507929001718995,-4.488235024975535);
\draw (11.507929001718995,-4.488235024975535)-- (15.520669071178967,-9.882410200315162);
\draw (15.520669071178967,-9.882410200315162)-- (21.441105239234663,-5.376300450183889);
\draw [color=qqzzqq] (15.520669071178967,-9.882410200315162)-- (6.34399301069264,-7.349779172869118);
\draw [color=qqzzqq] (6.34399301069264,-7.349779172869118)-- (11.507929001718995,-4.488235024975535);
\draw [color=qqzzqq] (6.047971202289853,-2.2845171179770274)-- (6.34399301069264,-7.349779172869118);
\draw (6.34399301069264,-7.349779172869118)-- (0.5222307787712068,-6.231474563347488);
\draw [color=qqzzqq] (0.5222307787712068,-6.231474563347488)-- (-3.4247266665992564,-10.441562505075977);
\draw (-3.4247266665992564,-10.441562505075977)-- (-4.740379148389411,-4.751365521333566);
\draw [color=qqzzqq] (-3.4247266665992564,-10.441562505075977)-- (6.34399301069264,-7.349779172869118);
\draw (6.34399301069264,-7.349779172869118)-- (13.612972972583243,-13.105758780701038);
\draw [color=qqzzqq] (13.612972972583243,-13.105758780701038)-- (15.520669071178967,-9.882410200315162);
\draw (26.539258606171508,-12.217693355492685)-- (21.441105239234663,-5.376300450183889);
\draw (21.210866054921386,1.4979837671696608)-- (25.68408449300791,2.682071000780798);
\draw (25.68408449300791,2.682071000780798)-- (26.539258606171508,-12.217693355492685);
\draw (-3.4247266665992564,-10.441562505075977)-- (-4.773270460434165,-16.263324736997404);
\draw [color=qqzzqq] (-4.773270460434165,-16.263324736997404)-- (3.8771446073361004,-12.678171724119238);
\draw [color=qqzzqq] (3.8771446073361004,-12.678171724119238)-- (-3.4247266665992564,-10.441562505075977);
\draw (6.34399301069264,-7.349779172869118)-- (3.8771446073361004,-12.678171724119238);
\draw (3.8771446073361004,-12.678171724119238)-- (8.942406662228194,-14.256954702267421);
\draw (8.942406662228194,-14.256954702267421)-- (6.34399301069264,-7.349779172869118);
\draw (8.942406662228194,-14.256954702267421)-- (13.612972972583243,-13.105758780701038);
\draw [color=qqzzqq] (13.612972972583243,-13.105758780701038)-- (17.79016960226698,-17.217172786295265);
\draw (26.539258606171508,-12.217693355492685)-- (26.243236797768724,-17.151390162205757);
\draw (26.243236797768724,-17.151390162205757)-- (17.79016960226698,-17.217172786295265);
\draw (17.79016960226698,-17.217172786295265)-- (11.080341945137196,-17.381629346519034);
\draw [color=qqzzqq] (11.080341945137196,-17.381629346519034)-- (8.942406662228194,-14.256954702267421);
\draw (11.080341945137196,-17.381629346519034)-- (2.3312529412326692,-17.34873803447428);
\draw [color=qqzzqq] (2.3312529412326692,-17.34873803447428)-- (3.8771446073361004,-12.678171724119238);
\draw (2.3312529412326692,-17.34873803447428)-- (-4.773270460434165,-16.263324736997404);
\draw (21.441105239234663,-5.376300450183889)-- (17.79016960226698,-17.217172786295265);
\begin{scriptsize}
\draw [fill=qqqqff] (-2.997139610017456,4.32663660301849) circle (1.0pt);
\draw [fill=qqqqff] (-3.918096347270564,0.4125704696927845) circle (1.0pt);
\draw [fill=qqqqff] (1.377404891934806,0.5112444058270478) circle (1.0pt);
\draw [fill=qqqqff] (2.758839997814468,2.9780928091835848) circle (1.0pt);
\draw [fill=qqqqff] (5.094123152991991,0.6099183419613093) circle (1.0pt);
\draw [fill=qqqqff] (-4.740379148389411,-4.751365521333566) circle (1.0pt);
\draw [fill=ffqqqq] (0.5222307787712068,-6.231474563347488) circle (1.0pt);
\draw [fill=qqqqff] (6.047971202289853,-2.2845171179770274) circle (1.0pt);
\draw [fill=qqqqff] (5.192797089126253,5.116028092092583) circle (1.0pt);
\draw [fill=qqqqff] (9.567341591078517,2.747853624870308) circle (1.0pt);
\draw [fill=qqqqff] (11.507929001718995,-4.488235024975535) circle (1.0pt);
\draw [fill=qqqqff] (16.079821375939783,5.839636957077166) circle (1.0pt);
\draw [fill=qqqqff] (21.210866054921386,1.4979837671696608) circle (1.0pt);
\draw [fill=qqqqff] (21.441105239234663,-5.376300450183889) circle (1.0pt);
\draw [fill=qqqqff] (15.520669071178967,-9.882410200315162) circle (1.0pt);
\draw [fill=ffqqqq] (6.34399301069264,-7.349779172869118) circle (1.0pt);
\draw [fill=qqqqff] (-3.4247266665992564,-10.441562505075977) circle (1.0pt);
\draw [fill=ffqqqq] (13.612972972583243,-13.105758780701038) circle (1.0pt);
\draw [fill=qqqqff] (26.539258606171508,-12.217693355492685) circle (1.0pt);
\draw [fill=qqqqff] (25.68408449300791,2.682071000780798) circle (1.0pt);
\draw [fill=qqqqff] (-4.773270460434165,-16.263324736997404) circle (1.0pt);
\draw [fill=ffqqqq] (3.8771446073361004,-12.678171724119238) circle (1.0pt);
\draw [fill=ffqqqq] (8.942406662228194,-14.256954702267421) circle (1.0pt);
\draw [fill=qqqqff] (17.79016960226698,-17.217172786295265) circle (1.0pt);
\draw [fill=qqqqff] (26.243236797768724,-17.151390162205757) circle (1.0pt);
\draw [fill=qqqqff] (11.080341945137196,-17.381629346519034) circle (1.0pt);
\draw [fill=qqqqff] (2.3312529412326692,-17.34873803447428) circle (1.0pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}

\end{minipage}\pause

\begin{dfi}
The \textbf{Cheeger constant} $h(X)$ of $X$ is the largest $h$ such that for every set $A$ of vertices such that $\P(A)<\frac{1}{2}$, 
\begin{align*}
\frac{\# \partial A}{e}=\P(\partial A) \ge h\,\P(A)=\frac{\# A}{n}.
\end{align*}
\end{dfi}

\end{frame}

\begin{frame}[label=chee]

\begin{dfi}
The \textbf{Cheeger constant} $h(X)$ of $X$ is the largest $h$ such that for every set $A$ of vertices such that $\P(A)<\frac{1}{2}$, 
$\displaystyle\frac{\# \partial A}{e}=\P(\partial A) \ge h\,\P(A)=\frac{\# A}{n}$.
\end{dfi}

\begin{lem}
$$
h(X)=(\|d^{-1}\|_{1\to 1})^{-1}\text{ over }\F.
$$ 
\end{lem}
So near-cohomology is present iff the Cheeger constant is small, i.e. the isoperimetry is poor. \hyperlink{hnc<1>}{\beamergotobutton{Proof}}\pause

\medskip

Here is an example of graph without near-cohomology.

\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}\hyperlink{isopnc<1>}{\beamergotobutton{Proof}}



\end{frame}


\subsection{Laplacian}

\begin{frame}[label=Laplacian]

The $\ell^2$ near-cohomology threshold $(\|d^{-1}\|_{2\to 2})^{-1}$ over $\R$ has an interpretation too.

\begin{pro}
Let $\Delta$ be the self-adjoint operator corresponding to the quadratic form $f\mapsto \|df\|_2^2=\langle f,\Delta f \rangle$. Let $\lambda_1\le \lambda_2\le\cdots$ denote its eigenvalues. If the graph $X$ is connected, then $\lambda_1=0$ and
\begin{align*}
\lambda_2=(\|d^{-1}\|_{2\to 2})^{-2}.
\end{align*}
\end{pro}\hyperlink{lambda2<1>}{\beamergotobutton{Proof}}

\pause

This suggests a slight generalization: replacing graphs (resp. simplicial complexes) with weighted graphs (resp. weighted simplicial complexes).

\begin{dfi}
Say a simplicial complex $X$ has \textbf{pure dimension} $N$ if every vertex is contained in at least one $N$-simplex. 

A probability distribution on the simplices of a simplicial complex $X$ of pure dimension $N$ is \textbf{Garland} if for every $k=0,\ldots,N-1$, it is the same to pick a $k$-simplex at random, or to first pick a $k+1$-simplex $\sigma$ at random and then a $k$-simplex of $\sigma$ uniformly at random.
\end{dfi}
For a graph, the uniform distribution on edges gives rise to the distribution on vertices which is proportional to degree.

\end{frame}

\begin{frame}[label=lambda2h]

$\ell^p$ norms on cochains are defined accordingly. Whence $h_\P=(\|d^{-1}\|_{1\to 1})^{-1}$ over $\F$ and $\lambda_{2,\P}=(\|d^{-1}\|_{2\to 2})^{-2}$ over $\R$.

\begin{thm}[Cheeger, Buser, Dodziuk, Alon-Milman]
For a finite connected graph equipped with a Garland distribution $\P$,
\begin{align*}
\frac{1}{2}\lambda_{2,\P}\le h_\P\le 2\sqrt{\lambda_{2,\P}}.
\end{align*}
\end{thm}\pause

The left-hand inequality amounts to associating a real cochain $f=|x|$ to an $\F$-cochain $x$ and comparing $d^{-1}df$ and $d^{-1}dx$.
\hyperlink{cheeger-buser<1>}{\beamergotobutton{Details}}\pause

\medskip

The right-hand inequality follows from two principles:
\begin{itemize}
  \item Isoperimetry $\implies \ell^1$-Poincar\'e-Sobolev inequality. \\ For this, write any real function $f$ with vanishing median as an integral of $\{0,1\}$-valued functions, the characteristic functions of its superlevel sets.
  \item $\ell^1$-Poincar\'e-Sobolev inequality $\implies \ell^2$-Poincar\'e-Sobolev inequality. \\ For this, apply the $\ell^1$ inequality to $g=f|f|$, and then Cauchy-Schwartz.
\end{itemize}
\hyperlink{buser-cheeger<1>}{\beamergotobutton{Details}}

\end{frame}

\section{Expanders}

\subsection{What are expanders good for}

\begin{frame}

An \emph{expander} is an infinite family of finite graphs with uniformly bounded degree and Cheeger constant uniformly bounded below. Equivalently, with \emph{spectral gaps} $\lambda_2$ uniformly bounded below. 

\begin{thm}[Pinsker 1973]
Random $d$-regular graphs are expanders.
\end{thm}\pause

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.


\end{frame}

\subsection{Infinite graphs}

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

\begin{pro}
Let $p\geq 1$. Let $\Gamma$ be a discrete finitely generated group. Fix a finite generating system. There is an associated graph, the Cayley graph $G$. Then the following are equivalent:
\begin{enumerate}
  \item $h(G)>0$.
  \item $d$ has a bounded inverse $d\ell^pC^{0}(G)\to \ell^p C^{1}(G)/\mathrm{Ker}(d)$.
  \item The \emph{$\ell^p$ cohomology} $\ell^p H^1(G):=(\ell^p C^{1}(G)\cap\mathrm{Ker}(d))/d\ell^pC^{0}(G)$ is Hausdorff.
  \item $\Gamma$ is non-amenable.
\end{enumerate}
\end{pro}\pause

Amenability is a property of groups that has emerged from ergodic theory and operator algebras (von Neumann). It has hundreds of equivalent characterizations.\pause

\medskip

\begin{minipage}{3cm}

The free abelian group $\Z^d$ is amenable. It behaves like Euclidean space, which has vanishing Cheeger constant. Its $\ell^p$ cohomology is nonzero and non-Hausdorff for all $p>1$.

\end{minipage}\begin{minipage}{5cm}

\begin{center}
\definecolor{ttffqq}{rgb}{0.2,1.,0.}
\definecolor{ffqqqq}{rgb}{1.,0.,0.}
\definecolor{uuuuuu}{rgb}{0.26666666666666666,0.26666666666666666,0.26666666666666666}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=0.1cm,y=0.1cm]
\clip(-21.321804244784126,-14.883554420718598) rectangle (19.45693282169477,3.164654886365931);
\draw (0.,-6.)-- (16.,-6.);
\draw (8.,2.)-- (8.,-14.);
\draw (5.139926682871062,-1.9625794616877066)-- (10.964530097651974,-1.9625794616877066);
\draw (5.002337625828993,-9.942744770127693)-- (11.193845192722089,-10.034470808155739);
\draw (3.9933512075204884,-3.0632919180242566)-- (3.9933512075204884,-9.025484389847236);
\draw (11.973516515960478,-3.200880975066325)-- (12.019379534974501,-9.025484389847236);
\draw (3.030227808226007,-4.026415317318738)-- (5.002337625828993,-4.026415317318738);
\draw (5.965461025123474,-0.8160039863371338)-- (6.011324044137497,-2.879839841968165);
\draw (10.001406698357492,-0.9077300243651796)-- (10.001406698357492,-2.788113803940119);
\draw (3.121953846254053,-8.016497971538731)-- (5.139926682871062,-8.016497971538731);
\draw (11.147982173708066,-8.016497971538731)-- (13.028365953283005,-7.970634952524708);
\draw (7.157899519488071,0.835064698167691)-- (9.130009337091057,0.835064698167691);
\draw (7.112036500474048,-13.015567044067229)-- (9.130009337091057,-13.015567044067229);
\draw (5.919598006109451,-8.93375835181919)-- (5.965461025123474,-11.135183264492289);
\draw (9.955543679343469,-9.025484389847236)-- (10.001406698357492,-11.043457226464243);
\draw (1.1039810096370442,-4.989538716613219)-- (1.0581179906230214,-7.007511553230227);
\draw (1.0581179906230214,-7.007511553230227)-- (1.1039810096370442,-4.989538716613219);
\draw (11.102119154694043,-3.934689279290692)-- (13.074228972297028,-3.934689279290692);
\draw (15.046338789900014,-5.035401735627242)-- (15.092201808914037,-6.961648534216204);
\draw (-18.895511955860016,-5.987149361330235)-- (-8.89237708047114,-5.987149361330235);
\draw (-18.93807848724465,-3.986522386252468)-- (-8.934943611855775,-3.986522386252468);
\draw (-18.895511955860016,-1.9858954111747016)-- (-8.89237708047114,-2.0284619425593347);
\draw (-18.938078487244653,-8.030342867792633)-- (-8.934943611855777,-8.030342867792633);
\draw (-18.93807848724465,-9.988403311485767)-- (-8.89237708047114,-9.988403311485767);
\draw (-18.00161479678271,-0.9217321265588683)-- (-18.00161479678271,-11.0525665961016);
\draw (-15.915854758935673,-1.0494317207127686)-- (-15.958421290320306,-11.137699658870869);
\draw (-13.957794315242529,-0.9642986579435016)-- (-13.957794315242529,-10.967433533332335);
\draw (-12.042300402934021,-1.0494317207127684)-- (-11.999733871549386,-10.967433533332335);
\draw (-9.999106896471613,-1.134564783482035)-- (-10.041673427856246,-11.010000064716968);
\draw [line width=2.pt,color=ttffqq] (-11.999733871549386,-9.562737997639433)-- (-11.999733871549386,-8.2431755247158);
\draw [line width=2.pt,color=ttffqq] (-12.042300402934021,-3.6034236037907683)-- (-12.042300402934021,-2.2838611308671353);
\draw [line width=2.pt,color=ttffqq] (-13.957794315242529,-5.604050578868534)-- (-13.957794315242529,-4.284488105944901);
\draw [line width=2.pt,color=ttffqq] (-15.91585475893567,-7.562111022561668)-- (-15.91585475893567,-6.242548549638035);
\draw [line width=2.pt,color=ttffqq] (-15.91585475893567,-5.731750173022435)-- (-15.91585475893567,-4.412187700098802);
\draw [line width=2.pt,color=ttffqq] (-13.957794315242527,-7.604677553946301)-- (-13.957794315242527,-6.285115081022668);
\draw [line width=2.pt,color=ttffqq] (10.390261636767836,-3.9013893234832007)-- (11.792810118776796,-3.914239962152965);
\draw [line width=2.pt,color=ttffqq] (-12.02969486359694,-3.986522386252468)-- (-10.627146381587972,-3.9993730249222335);
\draw [line width=2.pt,color=ttffqq] (-12.021108481729653,-5.987149361330236)-- (-10.618559999720684,-6.);
\draw [line width=2.pt,color=ttffqq] (-17.661082545705643,-5.987149361330235)-- (-16.258534063696676,-6.);
\draw [line width=2.pt,color=ttffqq] (-12.,-8.)-- (-10.597451517991033,-8.012850638669764);
\draw [line width=2.pt,color=ttffqq] (6.261308092458386,-5.987149361330235)-- (7.663856574467357,-6.);
\draw [line width=2.pt,color=ttffqq] (11.995556823243419,-6.)-- (13.398105305252376,-6.012850638669765);
\draw [line width=2.pt,color=ttffqq] (11.979294534103975,-3.934689279290692)-- (13.38184301611294,-3.9475399179604573);
\draw [line width=2.pt,color=ttffqq] (11.965223297999277,-3.688556666560034)-- (11.965223297999277,-3.0500586957905345);
\draw [line width=2.pt,color=ttffqq] (7.963969347843726,-5.6466171102531675)-- (7.963969347843726,-4.327054637329534);
\draw [line width=2.pt,color=ttffqq] (7.963969347843726,-7.562111022561668)-- (7.963969347843726,-6.242548549638035);
\draw [line width=2.pt,color=ttffqq] (12.00778982938391,-7.519544491177035)-- (12.00778982938391,-6.199982018253402);
\begin{scriptsize}
\draw [fill=uuuuuu] (1.081015980469163,-6.) circle (1.5pt);
\draw [fill=uuuuuu] (3.993351207520489,-6.) circle (1.5pt);
\draw [fill=uuuuuu] (3.993351207520489,-4.0264153173187385) circle (1.5pt);
\draw [fill=uuuuuu] (3.993351207520489,-8.01649797153873) circle (1.5pt);
\draw [fill=uuuuuu] (5.990940480131265,-1.9625794616877068) circle (1.5pt);
\draw [fill=uuuuuu] (8.,0.835064698167691) circle (1.5pt);
\draw [fill=uuuuuu] (8.,-1.9625794616877068) circle (1.5pt);
\draw [fill=uuuuuu] (10.00140669835749,-1.9625794616877068) circle (1.5pt);
\draw [fill=ffqqqq] (11.979294534103975,-3.934689279290692) circle (1.5pt);
\draw [fill=ffqqqq] (11.995556823243419,-6.) circle (1.5pt);
\draw [fill=uuuuuu] (15.069305415242221,-6.) circle (1.5pt);
\draw [fill=uuuuuu] (12.01126896651983,-7.9954421961043) circle (1.5pt);
\draw [fill=uuuuuu] (5.940908238778829,-9.956649519949172) circle (1.5pt);
\draw [fill=uuuuuu] (8.,-9.987154583078373) circle (1.5pt);
\draw [fill=uuuuuu] (9.978065835531563,-10.016459262123286) circle (1.5pt);
\draw [fill=uuuuuu] (8.,-13.015567044067225) circle (1.5pt);
\draw [fill=ffqqqq] (8.,-6.) circle (1.5pt);
\draw [fill=uuuuuu] (-18.001614796782714,-1.9896992288729032) circle (1.5pt);
\draw [fill=uuuuuu] (-18.00161479678271,-3.986522386252468) circle (1.5pt);
\draw [fill=uuuuuu] (-18.001614796782714,-5.9871493613302365) circle (1.5pt);
\draw [fill=uuuuuu] (-18.001614796782714,-8.030342867792633) circle (1.5pt);
\draw [fill=uuuuuu] (-18.001614796782714,-9.988403311485765) circle (1.5pt);
\draw [fill=uuuuuu] (-15.953571938643574,-9.988403311485765) circle (1.5pt);
\draw [fill=uuuuuu] (-15.945310080231366,-8.030342867792632) circle (1.5pt);
\draw [fill=ffqqqq] (-15.936689010583846,-5.987149361330235) circle (1.5pt);
\draw [fill=uuuuuu] (-15.928247546553983,-3.9865223862524686) circle (1.5pt);
\draw [fill=uuuuuu] (-15.919859510164763,-1.9985577620074473) circle (1.5pt);
\draw [fill=uuuuuu] (-13.957794315242527,-2.006906975602861) circle (1.5pt);
\draw [fill=ffqqqq] (-13.957794315242527,-5.987149361330236) circle (1.5pt);
\draw [fill=uuuuuu] (-13.957794315242527,-8.030342867792633) circle (1.5pt);
\draw [fill=uuuuuu] (-13.957794315242527,-9.988403311485765) circle (1.5pt);
\draw [fill=uuuuuu] (-12.00393571799508,-9.988403311485765) circle (1.5pt);
\draw [fill=ffqqqq] (-12.012339410886465,-8.030342867792633) circle (1.5pt);
\draw [fill=ffqqqq] (-12.021108481729653,-5.987149361330236) circle (1.5pt);
\draw [fill=ffqqqq] (-12.02969486359694,-3.986522386252468) circle (1.5pt);
\draw [fill=uuuuuu] (-12.038156008390947,-2.015075649249038) circle (1.5pt);
\draw [fill=uuuuuu] (-10.002939531650116,-2.0237361448947433) circle (1.5pt);
\draw [fill=uuuuuu] (-10.01139981717321,-3.9865223862524677) circle (1.5pt);
\draw [fill=uuuuuu] (-10.020023209307166,-5.987149361330236) circle (1.5pt);
\draw [fill=uuuuuu] (-10.028830077869504,-8.030342867792633) circle (1.5pt);
\draw [fill=uuuuuu] (-10.037269993575077,-9.988403311485765) circle (1.5pt);
\draw [fill=uuuuuu] (-13.957794315242527,-3.986522386252468) circle (1.5pt);
\end{scriptsize}
\end{tikzpicture}
\end{center}

\end{minipage}\begin{minipage}{3cm}

The free group on at least $2$ generators is non-amenable. It behaves like hyperbolic plane, which has positive Cheeger constant. Its $\ell^p$ cohomology is nonzero and Hausdorff for all $p>1$. 

\end{minipage}

\end{frame}

\subsection{Computing the Cheeger constant}

\begin{frame}

Computing the Cheeger constant of a graph is known as the \textsf{SPARSEST CUT} problem in computer science. It is NP-hard (F. Shahrokhi and D. W. Matula 1990).\pause

\bigskip

Approximating the Cheeger constant up to a multiplicative factor of $\sqrt{\log n}$, where $n$ is the number of vertices, can be done in quadratic time (S. Arora, E. Hazan and S. Kale 2010).\pause

\bigskip

Conjecturally, this approximation factor cannot be improved. Some evidence is provided by a decade of work by A. Naor with various coauthors, showing that the integrality gap of the Goemans-Linial relaxation for \textsf{SPARSEST CUT} is at least $\sqrt{\log n}$ (2006-2018).

\end{frame}

\subsection{Computing Laplacian eigenvalues}

\begin{frame}

On the other hand, computing eigenvalues of graph Laplacians can be done very efficiently: in linear time. \pause

\medskip

Indeed, say two graphs $G$ and $H$ on the same vertex set are $\epsilon$-close if the Laplacian quadratic forms $Q_G:f\mapsto \E(|df|^2)$ satisfy
\begin{align*}
\frac{1}{1+\epsilon}Q_G \le Q_H \le (1+\epsilon)Q_G.
\end{align*}
Then every graph $G$ is $\epsilon$-close to a graph with less than $n(2+\epsilon)^2/\epsilon^2$ edges (J. Batson, D. Spielman and N. Srivastava 2014).\pause

Such a sparsification can be computed in nearly linear time. It follows that spectra are $\epsilon$-close as well. 

\bigskip

For a graph with few edges, eigenvalues can be fast computed using powers: solving $\Delta f_1=f_0$ on functions with vanishing $\E(f)$ and iterating gives a sequence $f_j$ such that $\|f_j\|\sim \lambda_2^{-j}\|f_0\|$, from which one can extract $\lambda_2$.\pause

\bigskip

The sparsification procedure relies on the concept of expansion. An expander is a graph which behaves spectrally like a complete graph, but with far less edges. Random $d$-regular graphs are expanders, so one expects that decimating edges locally randomly does not disturb $Q_G$ too much. 

\end{frame}

\section{High dimensional expanders}

\subsection{Cocycle expansion}

\begin{frame}

\begin{dfi}
Let $X$ be a finite simplicial complex of pure dimension $N$. Fix a Garland distribution on simplices of $X$, and the corresponding $\ell^p$ norms on cochains. For $k=0,\ldots,n-1$, the \emph{$k$-th cocycle expansion constant} of $X$ is
\begin{align*}
h_k =(\|\bar d^{-1}\|_{1\to 1})^{-1},
\end{align*}
where $\bar d:C^k(X,\F)/\mathrm{Ker}(d)\to dC^k(X,\F)$ is induced by the coboundary operator $d:C^k(X,\F) \to C^{k+1}(X,\F)$.
\end{dfi}\pause

\textbf{Example}
\label{complete}
For the complete $N$-dimensional complex on $n$ vertices, let us use uniform distributions. Then for all $k=0,\ldots,N-1$,
$\displaystyle h_k \ge \frac{n}{n-k-1}$.

\medskip

In this example, the degree, i.e. the number of simplices containing a given vertex, increases with $n$.\pause

\begin{thm}[Kaufman-Kazhdan-Lubotzky 2016]
There exists an infinite family of $2$-dimensional simplicial complexes with uniformly bounded degree such that $h_0$ and $h_1$ are bounded away from $0$.
\end{thm}
The construction is explicit. A simpler result is the fact that random $2$-dimensional simplicial complexes have $h_0$ and $h_1$ are bounded away from $0$ and edge-degree (number of simplices containing an edge) bounded.

\end{frame}

\subsection{Expansion and property testing}

\begin{frame}[label=testing]

A \emph{tester} is a randomized algorithm that recognizes strings satisfying a property among a larger set of strings, by examining only a few bits, with a significant probability of being right.

The probability of rejecting a string should increase with the distance of the string to the subset of strings having the required property. It should vanish when this distance is $0$. We use the normalized Hamming distance between strings, $d(f,g)=\P(f_i\not=g_i)$.

\begin{dfi}
Let $A, B$ be finite sets, $W\subset A^B$ a set of strings, and $P\subset W$ a subset. A $(q,\epsilon)$-tester for $P$ is a randomized algorithm that queries only $q$ bits of a string $f$ and rejects it with probability at least $\epsilon\, d(f,P)$.
\end{dfi}\pause

\textbf{Example}. \emph{Linearity testing}. Let $V$ be a finite dimensional $\F$-vectorspace. Strings are $\F$-valued functions on $V$, with $P$ the subset of linear functions. The tester pick uniformly at random two elements $x,y\in V$, it rejects $f$ if $f(x+y)\not=f(x)+f(y)$. This is a $(3,1)$-tester for linearity.\pause

\begin{thm}[Kaufman-Lubotzky 2014]
\label{KF}
Let $X$ be a finite simplicial complex. Let strings be $\F$-valued $k$-cochains on $X$. The $k$-cocycle tester picks a $k+1$-simplex $\sigma$ at random and rejects a cochain $f$ if and only if $df(\sigma)\not=0$. This is a $(k+2,\epsilon)$-tester if and only if $\epsilon\ge h_k(X)$.
\end{thm}

\hyperlink{seidel<1>}{\beamergotobutton{Application to Seidel equivalence}}

\end{frame}

\subsection{Expansion and topological overlap}

\begin{frame}

\textbf{Remark}. Let $X$ be a connected graph and $F:X\to\R$ a continuous map. Let $m\in\R$ denote the median of $F$. Then $m$ belongs to the images of at least a fraction $h(X)$ of the edges of $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 has given a multidimensional extension of this remark: if a sufficiently rich simplicial $N$-complex is continuously mapped to $\R^N$, then some point needs be hit by a lot of $N$-simplices. 

\medskip

Sufficiently rich is expressed by \emph{cocycle expansion constants}, plus \emph{sparsity}, and also \emph{cosystoles} in case the cohomology does not vanish.

\end{frame}

\begin{frame}

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}

\end{frame}

\subsection{Expansion and curvature pinching}

\begin{frame}

Now comes a multidimensional extension of the above discussion of expansion in infinite groups.\pause

\medskip

\textbf{Curvature pinching}. Let $-1\le\delta<0$. Say a Riemannian manifold is $\delta$-pinched if its sectional curvature satisfies $-1\le \mathrm{SecCurv}\le \delta$.\pause

\begin{thm}[Pansu 2008]
For every $n$, $k=1,\ldots, n-1$ and $\delta\in[-1,0)$, there exists a $\mathbf{p}(n,\delta,k)$ such that if a simply connected complete Riemannian $n$-manifold is $\delta$-pinched and $1<p<\mathbf{p}(n,\delta,k)$, then $h_k>0$ in $\ell^p$ cohomology.  

\smallskip

This is sharp: for every $n$, $k=1,\ldots, n-1$ and $\delta\in[-1,0)$, there exists a Riemannian homogeneous space $M_{n,\delta,k}$ which is $\delta$-pinched and has $h_k=0$ in $\ell^p$ cohomology for $p$ in an interval starting at $\mathbf{p}(n,\delta,k)$.
\end{thm}\pause

It follows that $M_{n,\delta,k}$ is not quasiisometric to any $\delta'$-pinched Riemannian manifold, for $\delta'<\delta$.\pause

\medskip

There is a comparison theorem for the vanishing of $\ell^p$ cohomology, but it is not sharp. 

\end{frame}



\section{Distances between chain complexes}

\subsection{The homotopy distance}

\begin{frame}

\textbf{Question}. Can one interpret the near-cohomology threshold $\|d^{-1}\|$ as a distance between certain chain complexes?\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

A \emph{normed complex} is the data of a normed vectorspace and a bounded linear map $d:B\to B$ such that $d\circ d=0$. An \emph{isomorphism} of normed complexes $B_1\stackrel{d_1}{\to}B_1$ and $B_2\stackrel{d_2}{\to}B_2$ is a bijection $f:B_1\to B_2$ such that $d_2f_1=f_1d_1$ and $f,f^{-1}$ are bounded. An \emph{isometry} of normed complexes is an isometric isomorphism.\pause

\begin{dfi}
\label{defhomdist}
Let $B_1\stackrel{d_1}{\to}B_1$ and $B_2\stackrel{d_2}{\to}B_2$ be two normed complexes. Consider all bounded homotopies, i.e. 
\begin{itemize}
  \item bounded morphisms $F_1:B_1\to B_2$ and $F_2:B_2\to B_1$ such that 
  $$
  d_2F_1=F_1d_1,\quad d_1F_2=F_2d_2,
  $$
  \item bounded linear maps $Q_1:B_1\to B_1$ and $Q_2:B_2\to B_2$ such that
  $$
1-F_2F_1=d_1Q_1+Q_1d_1, \quad 1-F_1F_2=d_2Q_2+Q_2d_2.
  $$
\end{itemize}
Denote by $\displaystyle
q=\max\{|Q_1|,|Q_2|\}$, $f=\max\{1,|F_1||F_2|\}$. The \textbf{homotopy distance} $\mathrm{HomDist}(B_1,B_2)$ is the infimum over all homotopies of $\displaystyle \max\{\frac{q}{f}+\log f,\frac{f}{q}+\log q\}$.
\end{dfi}

\end{frame}

\subsection{The near-homology threshold}

\begin{frame}[label=homdist]

\begin{dfi}
$\mathrm{HomDist}(B_1,B_2)=\inf\displaystyle \max\{\frac{q}{f}+\log f,\frac{f}{q}+\log q\}$.
\end{dfi}
The purpose of the weird formula is to have a triangle inequality. \hyperlink{trihomdist<1>}{\beamergotobutton{Details}}\pause

\medskip

When $B_1$ and $B_2$ are finite dimensional, 
\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{ and }(B_2,d_2)\text{ are isometric.}
\end{align*}
Therefore one gets a distance on the set of isometry classes of finite dimensional normed complexes with the same homology.\pause

\medskip

\begin{dfi}
The \textbf{near-homology threshold} $NH(B)$ is the norm of the inverse $\bar d^{-1}$ of $\bar d : B/\mathrm{Ker}(d)\to \mathrm{Im}(d)$.
\end{dfi}\pause

\textbf{Remark}. $\mathrm{NH}$ is a homotopy covariant: if two chain complexes $B_1$ and $B_2$ are homotopic, then $\mathrm{NH}(B_1)\le \exp(\mathrm{HomDist}(B_1,B_2))(1+\mathrm{NH}(B_2))$. \hyperlink{nhhom<1>}{\beamergotobutton{Details}}

\end{frame}

\begin{frame}[label=nh]

\begin{lem}
$HomDist(B,0)\ge NH(B)$. \hyperlink{dist0<1>}{\beamergotobutton{Details}}
\end{lem}\pause

\begin{pro}
If $B$ is a Hilbert space, $HomDist(B,0)=NH(B)\iff H(B)=0$. 
\hyperlink{nhdetail<1>}{\beamergotobutton{Details}}
\end{pro}\pause
This applies to the $\ell^2$ norm on cochains on graphs. In order to remove the homology obstruction, we attach to a graph $X$ the following complexes
\begin{align*}
B_{X,\k,p}=H^0(X,\k)\oplus C^0(X,\k)\oplus dC^0(X,\k) \text{ equipped with }\ell^p\text{ norms}.
\end{align*}
where $d:H^0(X,\k)\to C^0(X,\k)$ embeds locally constant functions as $0$-cochains. Then for all finite connected graphs, 
\begin{align*}
HomDist(B_{X,\R,2},0)=NH(B_{X,\R,2})=\lambda_2(X)^{-1/2}.
\end{align*}\pause

Over $\F$, things are not as nice. \hyperlink{k3detail<1>}{\beamergotobutton{Details}}
\begin{exa}
Let $K_3$ be the complete graph on $3$ vertices. Then 
\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{The Hausdorff distance}

\begin{frame}[label=Haus]

\begin{dfi}
Let $r>0$. Let $B\stackrel{d}{\to}B$ be a normed complex such that $|d|\le r$, let $B'$ and $B''$ be subcomplexes of $B$. Consider all bounded morphisms $f:B\to B$ such that $f(B')\subset B''$ and bounded maps $Q:B\to B$ such that, on $B'$, $1-f=dQ+Qd$. Take the infimum of $\log(1+2r|Q|)$. This defines the asymmetric embedded Hausdorff distance $\mathrm{HausDist}_{B,r}(B'\to B'')$. Make it symmetric by setting
\begin{align*}
\mathrm{HausDist}_{B,r}(B',B'')=\mathrm{HausDist}_{B,r}(B'\to B'')+\mathrm{HausDist}_{B,r}(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$ such that $|d|\le r$, containing subcomplexes $B'$ and $B''$ isometric to $B_2$ and $B_2$ respectively, and take the infimum of all embedded Hausdorff distances $\mathrm{HausDist}_{B,r}(B',B'')$. This defines the abstract \textbf{Hausdorff distance} 
$\mathrm{HausDist}_r(B_1,B_2)$.
\end{dfi}

Again, the role of the log is to achieve the triangle inequality. \hyperlink{Hausdetail<1>}{\beamergotobutton{Details}}


\end{frame}

\subsection{The near-homology distance}

\begin{frame}

Here is an other suggestion in order to bypass the homology obstruction. A \emph{null complex} is a normed complex whose boundary operator is zero. If $B\maprl{H}{K} N$ is a bounded homotopy to a null complex, then 
$$
B=\mathrm{Im}(K)\oplus\mathrm{Ker}(H),
$$
where $\mathrm{Im}(K)$ is a null subcomplex of $B$ which has the same homology as $B$ and $N$, and $\mathrm{Ker}(h)$ is a subcomplex of $B$ whose homology vanishes. Therefore one can think of $\mathrm{Ker}(H)$ as $B$ with its homology removed.

\begin{dfi}
Let $B_1\maprl{H_1}{K_1} N_1$ and $B_2\maprl{H_2}{K_2} N_2$ be normed complexes coming with homotopies to null-complexes. Define the \emph{near-homology distance} between pairs as
\begin{align*}
\mathrm{NHDist}((B_1,N_1),(B_2,N_2)):=\mathrm{HomDist}(\mathrm{Ker}(H_1),\mathrm{Ker}(H_2)).
\end{align*}
\end{dfi}
Then, in finite dimensions, $\mathrm{NHDist}$ is finite, and $\mathrm{NHDist}((B_1,N_1),(B_2,N_2))=0 \iff B_1$ and $B_2$ are isometric, up to direct sums with null complexes isomorphic to $N_1$ and $N_2$.

\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<1>}{\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<2>}{\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}
$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=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=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,\frac{f}{q}+\log q\}$ 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<1>}{\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. Let $r\geq |d|$. The embedded Hausdorff distance $\mathrm{HausDist}_{B,r}$ 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+Q_2dQ_1+Q_2Q_1d.
$$
Since
$$
|Q_3| \le |Q_1|+|Q_2|+2|d||Q_1||Q_2|\le |Q_1|+|Q_2|+2r|Q_1||Q_2|,
$$
\begin{align*}
1+2r|Q_3| &\le 1+2r|Q_1|+2r|Q_2|+4r^2|Q_1||Q_2|\\
&=(1+2r|Q_1|)(1+2r|Q_2|),
\end{align*}

\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}