\documentclass[a4paper, 10.9pt]{book} 

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{pdfpages}
\usepackage{tikz}
\usetikzlibrary{trees}
\usetikzlibrary{arrows}
\usepackage{qtree}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{psl-cover}
\usepackage[french]{babel}     %       Babel
\usepackage{epsfig}
\usepackage{psfrag}
%\textwidth 16.5cm \textheight 25cm \oddsidemargin -0.3cm
%\evensidemargin -0.3cm \topmargin -1.5cm
%\parindent 1cm
\usepackage{graphicx}
\usepackage{dsfont}

\usepackage{multibib}
\newcites{me}{Articles}
%\usepackage{xcolor}

\DeclareMathOperator\supp{supp}
\DeclareMathOperator\rang{rang}
\DeclareMathOperator\Fol{Føl}
\DeclareMathAlphabet{\mymathbb}{U}{BOONDOX-ds}{m}{n}

\newfont{\bbf}{msbm10 scaled\magstep1}

\let\OldOddSideMargin\oddsidemargin
\let\oddsidemargin\evensidemargin
\let\evensidemargin\OldOddSideMargin
\reversemarginpar

\def\arxivprefix{https://arxiv.org}
\newcommand*\arXiv[1]{\href{\arxivprefix/abs/#1}{arXiv:#1}}

\newcounter{glob}
\newcounter{me}
\renewcommand\theme{\Alph{me}}
%\renewcommand\theglob{%
%	\ifnum\arabic{section}=0\else\arabic{section}.\fi %
%	\ifnum\arabic{subsection}=0\else\arabic{subsection}.\fi %
%	\arabic{glob}}

\theoremstyle{plain}
\newtheorem{thm}[glob]{Théorème}
\newtheorem*{thm*}{Théorème}
\newtheorem{thmme}[me]{Théorème}
\newtheorem{lemma}[glob]{Lemme}
\newtheorem{cor}[glob]{Corollaire}
\newtheorem{corme}[me]{Corollaire}
\newtheorem*{cor*}{Corollaire}
\newtheorem{prop}[glob]{Proposition}
\newtheorem{propme}[me]{Proposition}
\newtheorem*{prop*}{Proposition}

\theoremstyle{definition}
\newtheorem{defi}[glob]{Définition}
\newtheorem{pbm}[glob]{Problème}
\newtheorem{ex}[glob]{Exemple}
\newtheorem{question}[glob]{Question}
\newtheorem*{question*}{Question}

\theoremstyle{remark}
\newtheorem{remark}[glob]{Remarque}
\newtheorem*{remark*}{Remarque}

\def\Z{\mathbb{Z}}
\def\A{\mathcal{A}}
\def\C{\mathbb{C}}
\def\R{\mathbb{R}}
\def\Q{\mathbb{Q}}
\def\N{\mathbb{N}}
\def\K{\mathbf{K}}
\def\P{\mathbb{P}^1}


\usetikzlibrary{lindenmayersystems,arrows.meta}
\newcount\quadrant
\pgfdeclarelindenmayersystem{cayley}{
	\rule{A -> B [ R [A] [+A] [-A] ]}
	\symbol{R}{ \pgflsystemstep=0.5\pgflsystemstep } 
	\symbol{-}{
		\pgfmathsetcount\quadrant{Mod(\quadrant+1,4)}
		\tikzset{rotate=90}
	}
	\symbol{+}{
		\pgfmathsetcount\quadrant{Mod(\quadrant-1,4)}
		\tikzset{rotate=-90}
	}
	\symbol{B}{
		\draw [line width=1.5, dot-cayley] (0,0) -- (\pgflsystemstep,0) 
		node [font=\footnotesize, midway, 
		anchor={270-mod(\the\quadrant,2)*90}, inner sep=.5ex] 
		{\ifcase\quadrant$a$\or$b$\or$a^{-1}$\or$b^{-1}$\fi};
		\tikzset{xshift=\pgflsystemstep}
	}
}
\newcount\quadrant
\pgfdeclarelindenmayersystem{cayleyred}{
	\rule{A -> B [ R [A] [+A] [-A] ]}
	\symbol{R}{ \pgflsystemstep=0.5\pgflsystemstep } 
	\symbol{-}{
		\pgfmathsetcount\quadrant{Mod(\quadrant+1,4)}
		\tikzset{rotate=90}
	}
	\symbol{+}{
		\pgfmathsetcount\quadrant{Mod(\quadrant-1,4)}
		\tikzset{rotate=-90}
	}
	\symbol{B}{
		\draw [line width=1.5, color=red, dashed, dot-cayley] (0,0) -- (\pgflsystemstep,0) 
		node [font=\footnotesize, midway, 
		anchor={270-mod(\the\quadrant,2)*90}, inner sep=.5ex] 
		{\ifcase\quadrant$a$\or$b$\or$a^{-1}$\or$b^{-1}$\fi};
		\tikzset{xshift=\pgflsystemstep}
	}
}
\newcount\quadrant
\pgfdeclarelindenmayersystem{cayleyblue}{
	\rule{A -> B [ R [A] [+A] [-A] ]}
	\symbol{R}{ \pgflsystemstep=0.5\pgflsystemstep } 
	\symbol{-}{
		\pgfmathsetcount\quadrant{Mod(\quadrant+1,4)}
		\tikzset{rotate=90}
	}
	\symbol{+}{
		\pgfmathsetcount\quadrant{Mod(\quadrant-1,4)}
		\tikzset{rotate=-90}
	}
	\symbol{B}{
		\draw [line width=1.5, color=blue, densely dotted, dot-cayley] (0,0) -- (\pgflsystemstep,0) 
		node [font=\footnotesize, midway, 
		anchor={270-mod(\the\quadrant,2)*90}, inner sep=.5ex] 
		{\ifcase\quadrant$a$\or$b$\or$a^{-1}$\or$b^{-1}$\fi};
		\tikzset{xshift=\pgflsystemstep}
	}
}
\tikzset{
	dot/.tip={Circle[sep=-1.5pt,length=3pt]}, cayley/.tip={Stealth[]dot[]}
}

\renewcommand{\tan}{{\rm tg}\,}
\renewcommand{\cot}{{\rm ctg}\,}
\renewcommand{\arctan}{{\rm arctg}\,}
\pagestyle{plain}
%% commande à remplir obligatoirement
%% (sinon la compilation plante)
\title{\bf Bord de Poisson de marches aléatoires sur les groupes et profils isopérimétriques}

%% commandes avec des valeurs par défaut non nulles
\institute{École Normale Supérieure}
\doctoralschool{\bf Mathématique Hadamard}{574}
\specialty{\bf Mathématiques fondamentales}

%% commandes avec des valeurs par défaut nulles (vides)
\author{\bf Bogdan STANKOV}
\date{27 Mai 2021}

\hypersetup{
pdftitle={Bord de Poisson de marches aléatoires sur les groupes et profils isopérimétriques},
pdfsubject={Thèse de Doctorat},
pdfauthor={Bogdan STANKOV},
pdfkeywords={Marches aléatoires sur les groupes, bord de Poisson, graphe de Schreier, espace des bouts, groupe $F$ de Thompson, groupes d'homéomorphismes projectifs par morceaux, groupes resolubles, groupes localement resolubles, auto-similarité, fonction de Følner, groupe d'allumeur de réverbères, produits en couronnes, produits en couronnes permutationnels, groupe de Baumslag-Solitar, inégalité de Coulhon et Saloff-Coste, fonction de croissance},
pdflang={fr-FR}
}

%\jurymember{1}{Prénom NOM}{Titre, établissement}{Président}
\jurymember{3}{Anders KARLSSON}{Pr, Uppsala universitet}{Rapporteur}
\jurymember{4}{Christophe PITTET}{Pr, Aix-Marseille Université}{Rapporteur}
\jurymember{5}{Peter HAISSINSKY}{Pr, Aix-Marseille Université}{Examinateur}
\jurymember{1}{Pierre PANSU}{Pr, Université Paris-Saclay}{Président}
%\jurymember{6}{Prénom NOM}{Titre, établissement}{Examinateur}
%\jurymember{7}{Prénom NOM}{Titre, établissement}{Examinateur}
\jurymember{2}{Anna ERSCHLER}{DR, École Normale Supérieure}{Directeur de thèse}
% \jurymember{9}{Prénom NOM}{Titre, établissement}{Invité}
% \jurymember{10}{Prénom NOM}{Titre, établissement}{Invité}

\frabstract{
On étudie les marches aléatoires sur les groupes, et plus généralement les marches induites par des mesures sur des groupes. On cherche à comprendre leur comportement à l'infini, surtout en terme du non-trivialité de leur bords de Poisson. On s'intéresse en particulier aux sous-groupes de $H(\mathbb{Z})$, y compris le groupe de Thompson $F$. Le groupe $H(\mathbb{Z})$ est le groupe des homéomorphismes projectifs par morceaux sur les entiers défini par Monod. Pour un sous-groupe $H$ de $H(\mathbb{Z})$ de type fini, on montre que soit $H$ est résoluble, soit pour tout mesure sur $H$ dont le premier moment est fini et le support engendre $H$ en tant que semi-groupe, le bord de Poisson de la marche aléatoire sur $H$ est non-trivial. En particulier, on démontre la non-trivialité du bord de Poisson des marches aléatoires sur le groupe de Thompson $F$ pour les mesures sur $F$ dont le support l'engendre en tant que semi-groupe et qui sont de premier moment fini. Cela réponde à une question de Kaimanovich.

Considérons une action transitive d'un groupe $G$ de type fini, et le graphe de Schreier $\Gamma$ que cette action définit pour un ensemble générateur fixé. Pour une mesure de probabilité $\mu$ sur $G$ de premier moment fini, on prouve que si la marche aléatoire induite sur $\Gamma$ est transiente, alors elle converge vers un bout de $\Gamma$. On obtient comme corollaire que pour une mesure de probabilité de premier moment fini sur le groupe de Thompson $F$, dont le support engendre $F$ en tant que semi-groupe, la marche aléatoire induite sur les nombres dyadiques a un bord de Poisson non-trivial. Il est nécessaire d'avoir une hypothèse sur le moment de la mesure d'après un résultat de Juscheno et Zheng.

En outre, on calcule les valeurs exactes des fonctions de Følner sur le groupe d'allumeur de réverbères ${\mathbb{Z}\wr\mathbb{Z}/2\mathbb{Z}}$ pour l'ensemble générateur standard et l'ensemble générateur «switch-walk-switch». Les fonctions de Følner encodent les propriétés isopérimétriques des groupes moyennables et ont été auparavant étudiées à équivalence asymptotique prêt (autrement dit, de façon indépendante du choix d'ensemble générateur fini). On obtient aussi une borne inférieure pour les fonctions de Følner d'une classe de produits en couronnes permutationnels (avec certains ensembles générateurs). On l'utilise pour construire un exemple de groupe dont la fonction de Følner a la même exponente que sa fonction de croissance. De plus, on démontre un résultat isopérimétrique par rapport au bord sur les arrêtes sur le groupe de Baumslag-Solitar $BS(1,2)$ avec l'ensemble générateur standard.
}
\enabstract{
We study random walks on groups, and more generally walks induced by measures on groups. We seek to understand their limit behaviour, in particular in terms of whether their Poisson boundary is trivial or not. We are specifically interested in measures on subgroups of $H(\mathbb{Z})$, including Thompson's group $F$. The group $H(\mathbb{Z})$ is the group of piecewise projective homeomorphisms over the integers defined by Monod. For a finitely generated subgroup $H$ of $H(\mathbb{Z})$, we prove that either $H$ is solvable, or for every measure on $H$ with finite first moment and support that generates $H$ as a semigroup, the random walk on $H$ has non-trivial Poisson boundary. In particular, we prove the non-triviality of the Poisson boundary of walks on Thompson's group $F$ induced by measures, the support of which generates $F$ as a semigroup and which have finite first moments. This answers a question by Kaimanovich.

Consider a transitive action of a finitely generated group $G$ and the Schreier graph $\Gamma$ defined by this action for some fixed generating set. For a probability measure $\mu$ on a group with a finite first moment we show that if the induced random walk on $\Gamma$ is transient, it converges towards the space of ends of $\Gamma$. As a corollary we obtain that for a probability measure with a finite first moment on Thompson's group $F$, the support of which generates $F$ as a semigroup, the induced random walk on the dyadic numbers has a non-trivial Poisson boundary. Some assumption on the moment of the measure is necessary as follows from an example by Juschenko and Zheng.

Additionally, we calculate the exact values of the Følner function of the lamplighter group $\mathbb{Z}\wr\mathbb{Z}/2\mathbb{Z}$ for the standard and the switch-walk-switch generating sets. Følner functions encode the isoperimetric properties of amenable groups and have previously been studied up to asymptotic equivalence (that is to say, independently of the choice of finite generating set). We also obtain a lower bound for the Følner function for a class of permutational wreath products (with certain generating sets). We use that bound to construct an example of a group, the Følner function of which has the same exponent as its growth function. What is more, we prove an isoperimetric result concerning the edge boundary on the Baumslag-Solitar group $BS(1,2)$ with the standard generating set.
}
\frkeywords{Marches aléatoires sur les groupes, bord de Poisson, graphe de Schreier, espace des bouts, groupe $F$ de Thompson, groupes d'homéomorphismes projectifs par morceaux, groupes resolubles, groupes localement resolubles, auto-similarité, fonction de Følner, groupe d'allumeur de réverbères, produits en couronnes, produits en couronnes permutationnels, groupe de Baumslag-Solitar, inégalité de Coulhon et Saloff-Coste, fonction de croissance}
\enkeywords{Random walks on groups, Poisson boundary, Schreier graph, end space, Thompson's group $F$, groups of piecewise projective homeomorphisms, solvable group, locally solvable group, self-similarity, Følner function, lamplighter group, wreath products, permutational wreath products, Baumslag-Solitar groups, Coulhon and Saloff-Coste inequality, growth function}

\begin{document}
\fontsize{10.9}{12.5}\selectfont
\maketitle

%\chapter*{Résumé}
%\thefrabstract{}
%\vfill
%\textbf{Mots clés :} \thefrkeywords{}

\chapter*{Remerciements}
Je tiens surtout à remercier de tout cœur ma directrice de thèse, Anna Erschler. Des le début de cette expérience extraordinaire elle m'a guidé vers des questions inspirantes, garantissant une entrée exceptionnelle dans le monde de la recherche. Mais ce n'est pas juste les discussions mathématiques - elle a aussi veillé à ce que j’interagisse avec d’autres mathématiciennes et mathématiciens, et que je participe aux événements variés dont elle me faisait découvrir l’existence.

Je voudrai aussi adresser des remerciements spéciaux à Vadim Kaimanovich, qui a joué un rôle important dans mes premiers pas en tant que chercheur. Il a notamment su saisir l’intérêt d’un résultat de mon premier article, et me suggérer de le développer. Sa suggestion s’est prouvée extrêmement bien venue puisqu’elle a aboutit à mon deuxième article.

Mes sincères remerciements vont à Anders Karlsson et Christophe Pittet pour avoir accepté d’être rapporteurs ainsi que pour les suggestions de corrections détaillées, et à Peter Haïssinsky et Pierre Pansu pour m’avoir fait l’honneur de faire parti du jury.

Merci bien aussi à l'équipe administrative du DMA. Les efforts de Fabienne Renia, Zaïna Elmir, Amélie Castelian, Francoise Dessalle, Laurence Gareaux, Anna Arato, Albane Trémeau, Bénédicte Auffray ont été essentiels pour le bon déroulement de tout ce qu'on a fait pendant ces années.

Mes camarades de bureau ont joué un rôle très important. Un grand merci à Yanis Amirou, Markus Steenbock, Arman Darbinyan et Nima Hoda pour leurs discussions et leurs amitiés.

Beaucoup d’individus m'ont enseigné les mathématiques durant mon parcours, mais je tiens en particulier à exprimer ma gratitude envers Lionel Nguyen Van Thé, qui m'a encadré pour un stage passionnant, mes professeurs de mathématiques de prépa : Roger Mansuy et Nicolas Tosel, et ma professeur de mathématiques pour tout mon enseignement secondaire : Iliana Tzvetkova. Je voudrais aussi remercier ma famille. Ma mère Nadezhda Ribarska, qui est professeur de mathématiques à l'Université de Sofia, et la personne qui a éveillé ma passion envers les mathématiques.

Finalement, je voudrais remercier le professeur Minko Balkanski et tout le monde de la Fondation Balkanski, sans qui je n'aurais jamais eu l’idée de venir en France et découvrir toutes ces possibilités.

\tableofcontents

\chapter{Présentation des résultats}

Mes deux premiers résultats portent sur les marches aléatoires induites par des mesures sur des groupes (voir Section~\ref{defwalk}). On étudie leur comportements asymptotiques, surtout en terme de leurs bords de Poisson (voir Définition~\ref{poissondef}, Section~\ref{poisson}). Dans~\citeme{hz} (voir Chapitre~\ref{hz}), on considère les sous-groupes du groupe des homéomorphismes projectifs par morceaux sur les entiers $H(\Z)$, présenté dans un article de Monod~\cite{h-main}. On va expliquer les résultats de Monod et définir ce groupe dans la Section~\ref{monodsection}. On aborde la question si des mesures sur les sous-groupes de $H(\Z)$ sont Liouvilles, c'est-à-dire si la marche induite sur le sous-groupe a un bord de Poisson trivial.

\begin{thmme}\label{thmhz}
	Pour tout sous-groupe $H$ de $H(\Z)$ qui n'est pas localement résoluble et toute mesure $\mu$ sur $H$ avec une espérance fini du nombre de fins de morceaux (voir la définition de $H(\Z)$ dans Section~\ref{monodsection}) et dont le support engendre $H$ comme semi-groupe, $(H,\mu)$ n'est pas Liouville.
\end{thmme}

Comme $H(\Z)$ contient le groupe $F$ de Thompson comme sous-groupe, cela répond en particulier à une question de Kaimanovich~\cite[7.A]{kaimanovichthompson}.

Dans~\citeme{convend} (voir Chapitre~\ref{conved}), on s'intéresse aux questions qui sont, comme dans~\citeme{hz}, relatifs aux marches aléatoires induites par des mesures sur des groupes, mais cette fois on considère les marches induites par une action du groupe. Le bord de Poisson de cette marche est toujours un quotient du bord de Poisson de la marche sur le groupe (voir Section~\ref{schreierwalk}). On obtient des résultats sur les comportements asymptotiques des marches provenant d'une classe de mesures de premier moment fini :

\begin{thmme}\label{themschreier}
	Considérons une action transitive d'un groupe $G$. Soit $S$ un ensemble générateur et $\Gamma$ le graphe de Schreier associé. Soit $\mu$ une mesure sur $G$ avec premier moment fini tel que la marche aléatoire induite sur $\Gamma$ est transiente. Alors elle converge presque surement vers un bout (aléatoire) du graphe.
\end{thmme}

On y trouve un corollaire qui s'applique en particulier au groupe $F$ de Thompson.

\begin{corme}\label{corschreier}
	Considérons une action transitive d'un groupe $G$. Soit $S$ un ensemble générateur et $\Gamma$ le graphe de Schreier associé. Supposons que $\Gamma$ est transient. Alors pour tout mesure $\mu$ sur $G$ dont le support engendre $G$ en tant que semi groupe et qui a un premier moment fini, la marche aléatoire induite converge presque surement vers un bout du graphe.
\end{corme}

On peut appliquer ce corollaire à l'action de $F$ sur les nombres dyadiques. Il n'est pas difficile d'obtenir que la convergence vers les bouts implique que les bords de Poisson des marches induites par ces mesures ne sont pas triviaux.

Dans~\citeme{lampl} (voir Chapitre~\ref{lampl}) on s'intéresse aux profils isopérimétriques des groupes, encodés par la fonction de F\o lner (voir Sections~\ref{foldefsect}~et~\ref{folfunct}). Cette fonction a été auparavant étudiée à équivalence asymptotique près (autrement dit, de façon indépendante du choix de l'ensemble générateur fini (voir Section~\ref{quasisect})). On obtient ses valeurs exactes pour deux exemples classiques :

\begin{thmme}\label{thmfollamp}
	La fonction de F\o lner sur le groupe $\Z\wr\Z/2\Z$ est, pour $n\geq2$, $\Fol(n)=2n2^{2(n-1)}$ pour l'ensemble générateur standard et $\Fol_{sws}(n)=2n2^{2n}$ pour l'ensemble générateur «switch-walk-switch».
\end{thmme}

On donne aussi une description des ensembles de F\o lner pour lesquels on obtient une égalité.

On obtient de plus un résultat isopérimétrique sur le groupe de Baumslag-Solitar $BS(1,2)={\langle a,b|bab^{-1}=a^2\rangle}$ en terme du bord par rapport aux arêtes.

\begin{thmme}\label{bs}
	Considérons le groupe de Baumslag-Solitar $BS(1,2)$ avec l'ensemble générateur $\{a,b\}$. Alors pour tout $n\in\N$ et tout $F\subset BS(1,2)$ fini tel que $|F|\leq|F_n|$, on a $\frac{|\partial F|}{|F|}\geq\frac{|\partial F_n|}{|F_n|}$, où $F_n$ sont les ensembles de F\o lner standards (voir Équation~\ref{bsstand}), et si $|F|<|F_n|$, l'inégalité est stricte.
\end{thmme}

\chapter{Contexte historique}

\section{Moyennabilité}

\subsection{Définitions}

L'origine de la notion de moyennabilité vient du paradoxe de Banach-Tarski (ou Hausdorff-Banach-Tarski). En 1924, Banach et Tarski~\cite{Banach-Tarski-original} découpent la boule de $\R^3$ en un nombre fini de parties, puis, en y appliquant des isométries, ils reconstruisent deux boules chacune identique à la première. Leur preuve est inspiré par un résultat similaire de Hausdorff sur la sphère. Cela est contraire à l'idée intuitive de volume, et, clairement, les morceaux ne sont pas Lebesgue-mesurables. Pour comprendre la structure qui permet cela, étant donnée une action (à droite) d'un groupe sur un espace, on définit :

\begin{defi}
	Soit un groupe $G$ qui agit sur un ensemble $X$. On dit que l'action est \textbf{paradoxale} s'ils existent deux entiers positifs $m$ et $n$ et des sous-ensembles $A_1,A_2,\dots,A_m,B_1,\dots,B_n$ de $X$ deux-à-deux disjoints, ainsi que $g_1,g_2,\dots,g_m,h_1,\dots,h_n\in G$ tels que $X=\bigcup(A_i)g_i=\bigcup(B_i)h_i$.
\end{defi}

Avec cette notation, le paradoxe de Banach-Tarski dit que l'action des isométries de $\R^3$ sur une boule est paradoxale. Cette propriété est reliée à la structure du groupe des isométries de $\R^3$. En effet, définissons qu'un groupe est paradoxal si l'action sur lui-même par multiplication à droite l'est. Alors pour une action paradoxale de $G$ sur $X$, pour un point $x\in X$, en prenant des ensembles obtenus comme images inverses d'un décomposition paradoxale sur $X$ par $g\rightarrow x.g$ on obtient une décomposition paradoxale sur $G$. Le groupe est donc paradoxal, et on peut aussi obtenir un résultat inverse partiel (voir~\cite{Banach-Tarski}):

\begin{prop}
	Si $G$ est paradoxal et agit librement sur $X$, alors cette action est paradoxale.
\end{prop}

On peut donc, comme remarqué par John von Neumann, chercher une explication du paradoxe dans les propriétés du groupe des isométries de $\R^3$. Cela donne une première définition de moyennabilité :

\begin{defi}\label{paradoxmoy}
	Un groupe est \textbf{moyennable} si et seulement s'il n'est pas paradoxal.
\end{defi}

Remarquons qu'on parle ici de moyennabilité des groupes dénombrables. Des notions plus générales existent pour les groupes topologiques.

Plus généralement, une action est moyennable si et seulement si elle n'est pas paradoxale. Aujourd'hui il existe des nombreuses caractérisations de la moyennabilité (voir~\cite{bartholdi},\cite{MR1721355},\cite{greenleaf},\cite{Banach-Tarski}). Commençons par la définition canonique de moyennabilité, donnée (sur les groupes) par John von Neumann. Les notations qu'on utilisera sont inspirées par le livre de Juschenko en préparation~\cite{jus} et le survol de Bartholdi~\cite{bartholdi}. Soit $G$ un groupe agissant à droite sur $X$. Une \textbf{moyenne} (ou moyenne $l^\infty$; «mean» en anglais) sur $X$ est une fonctionnelle linéaire $\mu$ sur $l^\infty(X)$ qui vérifie $\mu(\chi_X)=1$, $\mu(0)=0$ et $\mu(f)\geq0$ pour chaque $f\geq0$. Pour une fonction $f$ sur $X$ et $g\in G$, on dénote par $T_g(f)$ la fonction $x\mapsto f(x.g^{-1})$ pour tout $g\in G$. Une moyenne sur $X$ est invariante (à droite) si pour chaque $f\in l^\infty(X)$, $g\in G$,

$$\mu(T_gf)=\mu(f).$$

\begin{defi}\label{defmoy}
	Un groupe $G$ (respectivement une action $G\curvearrowright X$) est moyennable s'il (respectivement elle) admet une moyenne invariante sur $G$ (respectivement sur $X$).
\end{defi}

Remarquons qu'en considérant l'action à gauche par $g^{-1}$, une moyenne invariante à droite devient invariante à gauche. Le choix de coté est donc une convention que chaque auteur choisit. En passant par la dualité entre fonctionnelles et mesures, on a de manière équivalente :

\begin{defi}
	Un action $G\curvearrowright X$ est moyennable si et seulement s'il existe $\mu:\mathcal{P}(X)\rightarrow[0,1]$ qui vérifie $\mu(X)=1$, $\mu(\emptyset)=0$,
	
	$$\mu(A\cup B)=\mu(A)+\mu(B)$$
	pour $A\cap B=\emptyset$ et
	
	$$\mu(E.g)=\mu(E)$$
	pour tout $g\in G$, $E\in\mathcal{P}(X)$.
	
\end{defi}

Une telle «mesure» est dite moyenne sur les sous-ensembles de $X$. Il est assez claire que l'existence d'une décomposition paradoxale implique la non-moyennabilité. Le sens inverse a été montré pour une action de groupe sur lui-même par multiplication par Tarski~\cite{Tarski1938}. Cela montre l'équivalence entre Définition~\ref{defmoy} et Définition~\ref{paradoxmoy} pour les groupes. On présente maintenant plusieurs définitions équivalentes :

\begin{thm}\label{moyeq}
	Considérons une action $G\curvearrowright X$. Alors on a une équivalence entre:
	\begin{enumerate}
		\item $G\curvearrowright X$ est moyennable.
		\item (\textbf{Condition de Reiter}~\cite[Chapitre~8]{MR0306811}) Pour chaque $E\subset G$ fini et $\varepsilon>0$, et pour $p\geq1$ ($p=1$), il existe $\phi\in l^p(X)$ tel que $\|T_s\phi-\phi\|_p\leq\varepsilon\|\phi\|_p$ pour tout $s\in E$.
		\item (\textbf{Condition de Følner}~\cite{Folner1955}) Pour chaque $E\subset G$ fini et $\varepsilon>0$, il existe un ensemble fini $F\subset X$ (appelé ensemble de Følner) qui vérifie :
		
		$$|F.s\bigtriangleup F|\leq\varepsilon|F|\mbox{ pour tout }s\in E.$$
	\end{enumerate}
\end{thm}

Remarquons que pour un groupe de type fini, il suffit de fixer un ensemble générateur fini pour $E$. Remarquons aussi que pour ces deux définitions on n'a pas besoin de l'axiome du choix. Par contre, la Définition~\ref{defmoy} avec les moyennes ne serait pas équivalente sans cet axiome. Même sur le groupe infini le plus simple, $\Z$, on ne peut pas construire une moyenne invariante sans utiliser des ultrafiltres. Remarquons les exemples de groupes moyennables qu'on voit ici : les groupes finis et les groupes cycliques (c'est immédiat par exemple en utilisant la condition de F\o lner).

\begin{prop}[Critère de Kesten~\cite{kesten}]\label{kesten}
Une action $G\curvearrowright X$ est moyennable si et seulement si pour une (toute) mesure symétrique non-dégénérée $\mu$ sur $G$, le \textbf{rayon spectral}
$$\rho(p,x)=\limsup_{n\rightarrow\infty}\sqrt[n]{p_n(x,x)}$$
de la marche induite sur $X$ est $1$.
\end{prop}

Ici $p_n(x,x)$ est la probabilité d'être au point $x$ après $n$ pas en commençant de $x$. On va préciser les termes relatifs aux marches aléatoires dans la Section~\ref{defwalk}.

A partir d'ici on va se concentrer sur les groupes moyennables plutôt que les actions moyennables. On y retrouve une critère très utilisé. Considérons un groupe $G$ de type fini. Soit $S$ une ensemble générateur qui ne contient ni l'élément neutre, ni deux éléments qui sont mutuellement inverses. On s'intéresse aux mots sur l'alphabet $S\cup S^{-1}$. Comme on s'intéresse aux propriétés de groupe, on se permet de supprimer des combinaisons $xx^{-1}$ ou $x^{-1}x$, ce qui est notre action de réduction. On dit qu'un mot qui ne contient pas de tels combinaisons est un mot réduit. On dénote $\gamma_n$ le nombre de mots réduits de longueur au plus $n$ sur $S\cup S^{-1}$ qui sont égaux à l'élément neutre comme éléments de $G$.

Une autre façon équivalente de définir cela est de considérer le groupe libre $F_{|S|}$ sur $S$ (voir Section~\ref{libre}). Il y a un morphisme de groupes naturel de $F$ vers $G$ - il suffit d'associer à chaque élément de $S$ dans $F$ le même élément de $S$ dans $G$. Si $N$ est son noyau, $\gamma_n$ est la taille de la boule de rayon $n$ dans $N$.

\begin{prop}[Critère de co-croissance de Grigorchuk~\cite{Gri77}]\label{grigcrit}
$G$ est moyennable si et seulement si

$$\lim_{n\rightarrow\infty}\sqrt[n]{\gamma_n}=2|S|-1.$$
\end{prop}

Ce critère n'est pas difficile à prouver en utilisant le critère de Kesten, mais sa formulation algébrique le rend très utilisable. On va approfondir sur ses applications dans la Section~\ref{libre}.

\subsection{Groupes élémentairement moyennables}

Il suit directement des définitions que la moyennabilité est préservée par plusieurs opérations :

\begin{prop}\label{stabsubgr}
	Tout sous-groupe $H$ d'un groupe moyennable $G$ est moyennable.
\end{prop}

\begin{prop}\label{stabunion}
	Soit $G_i$ une suite de groupes moyennables telle que $G_i\subset G_{i+1}$ pour chaque $i$. Alors $G=\bigcup_{i=0}^\infty G_i$ est moyennable.
\end{prop}

\begin{cor}\label{crofin}
	Un groupe est moyennable si et seulement si chaque sous-groupe de type fini l'est.
\end{cor}

\begin{prop}
	Si $G$ est moyennable et $N$ est un sous-groupe normal, alors $G/N$ est moyennable.
\end{prop}

\begin{prop}
	Si $N$ est un sous-groupe normal de $G$, et $N$ et $G/N$ sont moyennables, alors $G$ est moyennable.
\end{prop}

Avec le fait que les groupes cycliques sont moyennables, on obtient déjà que les groupes résolubles sont moyennables. De façon générale, les groupes qu'on peut obtenir à partir des groupes cycliques en appliquant ces propositions forment la classe des groupes \textbf{élémentairement moyennables}. Comme on verra dans la Section~\ref{growthsect}, les groupes de croissance sous-exponentielle sont moyennables. On obtient une classe plus grande de groupes moyennables : c'est les groupes \textbf{sous-exponentiellement moyennables}, qui sont les groupes obtenus à partir des groupes de croissance sous-exponentielle en appliquant ces opérations. Ce ne sont encore tous les groupes moyennables comme montré par Bartholdi et Virág~\cite{Bartholdi2005}. On discutera sur leur résultat dans la Section~\ref{poisson} (le groupe qu'ils utilisent comme exemple est définit dans la Section~\ref{autosim}).

\subsection{Sous-groupes libres}\label{libre}

Considérons le groupe engendré par deux éléments $a$ et $b$ tel que chaque mot réduit non-trivial sur ces deux éléments ne donne pas l'identité. De façon équivalente, on peut le considérer comme l'ensemble de mots réduits muni de la concaténation (puis réduction). On appelle cela le groupe~\textbf{libre non-abélien} à deux générateurs, et on le dénote $F_2$.

\begin{lemma}
	Le groupe $F_2$ est paradoxal.
\end{lemma}

On va exhiber une décomposition associée. Prenons les quatre ensembles $A_1,\dots,A_4$ des mots réduits qui commencent par $a$, $a^{-1}$, $b$ et $b^{-1}$ respectivement. Autrement dit, $A_1=\{ax_0x_1\dots x_n \text{ sous forme réduite},n\in\N,x_i\in\{a,a^{-1},b,b^{-1}\}\}$, etc. Alors $A_1\cup a.A_2=F_2$. Voir sur Figure~\ref{calf2} son graphe de Cayley (voir Définition~\ref{defcayley}) avec $A_1$ représenté par des lignes en tirets (et en rouge si vous avez imprimé en couleur) et $A_2$ par des lignes pointillées (bleus).

\begin{figure}[!ht]\centering\resizebox{.9\linewidth}{!}{
\begin{tikzpicture}
	\draw l-system [l-system={cayleyblue, axiom=[++A], step=4cm, order=4}];
	\draw l-system [l-system={cayleyred, axiom=[A], step=4cm, order=4}];
	\draw l-system [l-system={cayley, axiom=[+A] [-A], step=4cm, order=4}];
\end{tikzpicture}
}
\caption{Graphe de Cayley de $F_2$}
\label{calf2}
\end{figure}

De manière similaire, $A_3\cup b.A_4$ donne aussi le groupe tout entier. En ajoutant l'élément neutre dans un de ces ensembles, on obtient une décomposition paradoxale. D'après Proposition~\ref{stabsubgr}, cela implique que chaque groupe qui contient un sous-groupe libre est non-moyennable. Cela donne la classe  la plus évidente d'exemples de groupes non-moyennables (on peut en penser comme des groupes élémentairement non-moyennables). Le groupe des isomorphismes de $\R^3$ appartient à celle-ci, c'est-à-dire qu'il contient un sous-groupe libre. Par contre, trouver un exemple de groupe non-moyennable en-dehors de cette classe n'est pas facile - la question de leur existence est restée ouverte pendant 30 ans. Elle a été formulée par Day dans les années 1950, ce qui était appelé le «problème de von Neumann-Day». Le premier exemple a été donné en 1980 et on en parlera en détail dans la prochaine Section~\ref{torsion}. Malgré le quantité énorme de définitions équivalentes, à notre connaissance, jusqu'à récemment, toutes les (premières) preuves de non-moyennabilité de groupes sans sous-groupe libre sont faites avec le critère de co-croissance (voir Proposition~\ref{grigcrit}). Dans la Section~\ref{monodsection} on va présenter des résultats autour d'un article qui change cela.

Plus généralement, on ne sait même pas si avoir un sous-groupe libre est une condition géométrique (on expliquera ce que cela veut dire dans la Section~\ref{quasisect}). Cela conduit à une des grandes questions ouvertes dans le domaine - donner une condition de moyennabilité algébrique.

Les deux approches les plus connues pour chercher des sous-groupes libres sont le lemme du ping-pong et l'alternative de Tits~\cite{tits} :

\begin{thm}[Alternative de Tits]
	Soit $G$ un sous-groupe de $GL_n(\K)$ pour $n\geq1$ et $K$ un corps de caractéristique zéro. Alors soit $G$ a un sous-groupe libre non-abélien, soit $G$ a
	un sous-groupe résoluble d'indice fini.
\end{thm}

Plus généralement, il y a une fonction $n\mapsto\lambda(n)$ telle que, indépendamment de $\K$, si $G$ n'a pas de sous-groupe libre, il a un sous-groupe résoluble d'indice $\lambda(n)$. Le résultat est aussi correct si $K$ est de caractéristique fini, mais seulement pour les sous-groupes de type fini. Des théorèmes similaires ont été démontrés pour d'autres groupes, et on dit qu'une classe de groupes $\mathcal{C}$ satisfait l'alternative de Tits si tout groupe de la classe possède soit un sous-groupe libre, soit un sous-groupe résoluble d'indice fini. Par exemple, Karrass et Solitar~\cite[Théorème~3]{Karrass1971} ont montré que pour un groupe $G$ défini par une seule relation, soit il contient un sous-groupe libre, soit il est résoluble. Explicitons ce que signifie être défini par une seule relation. Pour cela, on a besoin d'un lemme. Considérons un groupe $G$ engendré par un ensemble $S$. Il y a un morphisme naturel du groupe libre non-abélien $F_{|S|}$ sur $S$ vers $G$. On peut donc écrire $G$ comme un quotient de ce groupe (par le noyau du morphisme). On a donc :

\begin{lemma}
	Tout groupe $G$ est un quotient d'un groupe libre. De plus, si $G$ est de type fini, il est quotient d'un groupe libre sur un nombre fini de générateurs.
\end{lemma}

On considère alors un groupe comme le quotient $F_k/N$ d'un groupe libre $F_k$ par un sous-groupe normal $N$. Si dans une telle représentation, $N$ est engendré par un nombre fini d'éléments comme sous-groupe normal, alors on dit que $F_k/N$ est \textbf{de présentation finie}. Si de plus il est engendré comme sous-groupe normal par un seul générateur $A$, on dit que $F_k/N$ est défini par une relation. On écrit $F_k/N=\langle x_1,\dots,x_k|A\rangle$ (où $S=\{x_1,\dots,x_k\}$). Plus généralement, si $A_1,\dots,A_n$ sont des éléments de $F_k$ (dites aussi relations sur $F_k$), on dénote par $\langle x_1,\dots,x_k|A_1,\dots,A_n\rangle$ le groupe $F_k/N'$ où $N'$ est le sous-groupe normal engendré par $A_1,\dots,A_n$. On les écrit parfois comme des égalités : par exemple pour le Théorème~\ref{bs} on a défini $BS(1,2)=\langle a,b|bab^{-1}=a^2\rangle$. Cela veut dire que c'est le groupe $\langle a,b|bab^{-1}a^{-2}\rangle$.

Un autre exemple d'alternative de Tits est donné par les sous-groupes des groupes modulaires des surfaces de Riemann~\cite{ivanov84,The1985} (c'est-à-dire les classes d'isotopie des difféomorphismes). C'est aussi vrai~\cite{Parry1992} pour les groupes fondamentaux des variétés $M$ fermées, orientables et irréductibles de dimension $3$ telles que $H_1(M,\Z/p\Z)\geq3$ pour un $p$ premier, ainsi que pour~\cite[8.2.F]{gromov87} les sous-groupes de groupes Gromov hyperboliques. Pour une liste plus complète, voir le livre de Pierre de la Harpe~\cite[II.42]{harpebible}.

\subsection{Groupes de torsion bornée}\label{torsion}

En 1902 William Burnside demande si chaque groupe de type fini de torsion est fini, c'est-à-dire s'il existe un groupe $G$ infini de type fini tel que pour chaque $g\in G$ il existe $p>0$ tel que $g^p=Id$. En 1964 la conjecture est réfutée. Ici on s'intéressera au problème de Burnside \textbf{borné} : existe-t-il un nombre entier $p$ et un groupe infini de type fini $G$ tel que $g^p=Id$ pour chaque $g\in G$ ? Cette question se ramène aux groupes de Burnside libres, qui sont des objets universels (dans un certain sens). On définit $B(m,n)$ comme le quotient de $F_m$ par le sous-groupe normal engendré par les $g^n$ pour $g\in F_m$. C'est un groupe de torsion $n$ qui est universel pour tous les groupes de torsion $n$ engendrés par au plus $m$ éléments. Le problème de Burnside borné demande alors s'il y a des groupes de Burnside libres infinis, et lesquels. En 1968, Adyan et Novikov~\cite{adyannovakov} démontrent que $B(m,n)$ est infini pour $m\geq 2$ et $n\geq4381$ impaire.

Ol'shanskii développe leur méthode et en 1980~\cite{0036-0279-35-4-L13} donne le premier exemple de groupe \textbf{non-moyennable sans sous-groupe libre}. Plus tard dans la même année, il présente aussi des groupes de torsion non-moyennables~\cite{Olshanskii1980}. On obtient même une propriété plus forte : tous leurs sous-groupes sont cycliques. C'est ce qu'on appelle les monstres de Tarski. Puisqu'un groupe non-moyennable est toujours infini, cela implique qu'un nombre infini de groupes de Burnside sont infinis.

En 1983 Adyan~\cite{0025-5726-21-3-A01} montre que $B(m,n)$ pour $m\geq2$ et $n\geq655$ impaire est non-moyennable (et donc aussi infini). Dans~\cite{grigorchuk} Grigorchuk décrit un groupe de torsion infini moyennable (voir Section~\ref{grigsect}). Mais c'est une question ouverte~\cite{Shalom2007} de savoir si un groupe de Burnside peut être infini et moyennable. Plus généralement, on ne sait pas si un groupe peut être infini, moyennable et de torsion bornée.

Un autre exemple connu de groupe non-moyennable sans sous-groupe libre est donné par Ol'shanskii et Sapir~\cite{finpresnonam} quand ils décrivent pour la première fois un groupe non-moyennable sans sous-groupe libre de présentation finie.

\subsection{La classe de groupes $H(A)$ d'un article de Monod}\label{monodsection}

Monod~\cite{h-main} construit une classe de groupes non-moyennables sans sous-groupe libre d'homéomorphismes projectifs par morceaux $H(A)$, où $A$ est un sous-anneau de $\R$. Considérons l'action de $PSL_2(\R)$ sur la ligne projective réelle $\P=\P(\R)$. Cette dernière peut être muni d'une topologie canonique qui fait d'elle un cercle : par exemple, en la décrivant comme le quotient de $\mathbb{S}^1$ par la relation d'équivalence $x\sim-x$. On dénote $G$ le groupe des homéomorphismes de $\P$ qui sont dans $PSL_2(\R)$ par morceaux, avec un nombre fini de morceaux et $H$ la sous-groupe de $G$ des éléments qui fixent $\begin{pmatrix}1\\0\end{pmatrix}\in\R^2$. Ce point devient le point $\infty$ si on considère la description de $\P$ comme $\R\cup\{\infty\}$, et l'action comme $\begin{pmatrix}a&b\\c&d\end{pmatrix}.x=\frac{ax+b}{cx+d}$ (avec les conventions naturelles pour l'infini).

Soit $A$ un sous-anneau de $\R$. En particulier, on s'intéresse au cas où $A$ est dénombrable et dense. Soit $P_A\subset\P$ l'ensemble des points fixes d'éléments hyperboliques de $PSL_2(A)$. On définit $G(A)$ comme le sous-ensemble de $G$ des éléments qui sont dans $PSL_2(A)$ par morceaux, avec les extrémités des morceaux dans $P_A$. On obtient le groupe $H(A)=G(A)\cap H$, c'est-a-dire les éléments de $G(A)$ qui fixent le point infini. Ils fixent donc la ligne réelle, et on peut y penser comme des homéomorphismes de $\R$ projectifs par morceaux. Monod obtient :

\begin{thm}\label{monodnonmoy}
	Le groupe $H(A)$ n'est pas moyennable si $A\neq\Z$.
\end{thm}

\begin{thm}
	Le groupe $H$ ne contient pas des sous-groupes libres non-abéliens. Alors $H(A)$, comme sous-groupe, n'en contient pas non plus pour chaque $A$.
\end{thm}

Il vaut de noter que le Théorème~\ref{monodnonmoy} est obtenu en comparant l'action de $H(A)$ avec celle de $PSL_2(A)$. Pour $H(\Z)$, il est une question ouverte s'il est moyennable, et il contient le groupe de Thompson $F$ (voir Définition~\ref{defthomp}) comme sous-groupe (voir~\cite{chainhomeo}).

On retrouve des autres groupes intéressants dans cette classe. Lodha~\cite{Lodha2014} montre qu'un certain sous-groupe de $H(\Z[\frac{\sqrt{2}}{2}])$ est de type $F_\infty$ (c'est-a-dire, il existe un CW-complexe $X$ connexe asphérique dans chaque dimension avec un nombre fini de cellules dans chaque dimension tel que $\pi_1(X)$ est isomorphe au sous-groupe). Ce sous-groupe était construit avant par Moore et Lodha~\cite{lhodafinpres} comme un exemple de groupe de présentation finie non-moyennable sans sous-groupe libre. Il n'a que trois générateurs et $9$ relations, bien moins que l'exemple de Ol'shanskii-Sapir~\cite{finpresnonam}. Il est le premier exemple de groupe de type $F_\infty$ non-moyennable sans sous-groupe libre. Plus tard, Lodha~\cite{lhoda-tarski} montre aussi que les nombres de Tarski (le nombre minimal de pièces dans une décomposition paradoxale) des groupes $H(A)$ sont bornées par $25$.

\subsection{Produits en couronnes}\label{lamplsect}

On présente ici une construction commune de groupes. On s'en intéresse en particulier dans~\citeme{lampl} (voir Chapitre~\ref{lampl}). Pour deux groupes $A$ et $B$, notons $B^{(A)}$ les fonctions de $A$ sur $B$ tels que tout sauf un nombre fini de points valent $Id_B$.

\begin{defi}
	Le \textbf{produit en couronne} $A\wr B$ est le produit semi-directe de $A$ sur $B^{(A)}$ où $A$ agit sur $B^{(A)}$ par translations.
\end{defi}

Si on écrit les éléments comme $(a,f)$ où $a\in A$ et $f\in B^{(A)}$, le produit est donc $(a,f)(a',f')=(aa',x\mapsto f(x)f'(xa^{-1}))$.

Pour un ensemble générateur $S$ de $A$ et $S'$ de $B$, on a un ensemble générateur standard de $A\wr B$. Il est formé des $(s,\mathbb{Id_B})$ pour $s\in S$ (où $\mathbb{Id_B}(x)=Id_B$ pour tout $x\in A$), ainsi que les $(Id_A,\delta_{Id_A}^{s'})$ pour $s'\in S'$ où $\delta_{Id_A}^{s'}(Id_A)=s'$ et $\delta_{Id_A}^{s'}(x)=Id_B$ sinon. On peut vérifier que quand on multiplie $(a,f)$ à droite avec le première type d'élément, on obtient $(as,f)$, et avec le deuxième type, on change le valeur de $f$ au point $a$ par $s'$.

Similairement, étant donne des ensembles de F\o lner $F_A$ et $F_B$ sur $A$ et $B$, cela donne des ensembles de F\o lner standards pour $A\wr B$. Soit 
$$F=\{(a,f)|a\in F_A,\supp(f)\subset F_A,\forall x:f(x)\in F_B\}.$$

Alors (voir Section~\ref{foldefsect} pour la définition de $\partial F$) :

\begin{equation*}
\begin{split}
\partial F= & \{(a,f)|a\in\partial F_A,\supp(f)\subset F_A,\forall x:f(x)\in F_B\}\\
& \bigcup\{(a,f)|a\in F_A,\supp(f)\subset F_A,f(a)\in\partial F_B\}.
\end{split}
\end{equation*}

On a $|F|=|F_A||F_B|^{|F_A|}$ et $|\partial F|=|\partial F_A||F_B|^{|F_A|}+|F_A||F_B|^{|F_A|-1}|\partial F_B|$. Donc

$$\frac{|\partial F|}{|F|}=\frac{|\partial F_A|}{|F_A|}+\frac{|\partial F_B|}{|F_B|}.$$

\section{Graphes de Cayley et Schreier}

\subsection{Définitions et résultats généraux}

\begin{defi}\label{defcayley}
	Soit $G$ un groupe de type fini et $S$ un ensemble générateur. Son \textbf{graphe de Cayley} est $\Gamma=(V,E)$ avec $V=G$ et $E=\{(g,gs):g\in G,s\in S\}$.
\end{defi}

\begin{defi}\label{defschreier}
Soit $G$ un groupe de type fini et $S$ un ensemble générateur.
\begin{enumerate}
	\item Un graphe de «coset» de Schreier est défini par rapport à un sous-groupe $H$. Ces sommets sont les classes $Hg$, $g\in G$, et ces arrêtes sont les couples de la forme $(Hg,Hgs)$ pour $g\in G$, $s\in S$.
	\item Un graphe d'action de Schreier est défini par rapport à une action transitive à droite de $G$, soit sur $X$. L'ensemble de sommets est $X$, et les arrêtes sont les couples de la forme $(x,xs)$ pour $x\in X$, $s\in S$.
	\item L'ensemble de graphes de coset de Schreier et les graphes d'action de Schreier sont les mêmes. On appelle un tel graphe un graphe de Schreier.
\end{enumerate}
\end{defi}

Il y a une application évidente des graphes de coset de Schreier avec un sommet marqué vers les graphes d'action de Schreier avec un sommet marqué. Il suffit de considérer l'action de $G$ sur les classes de $H$ par multiplication (à droite). Son inverse n'est pas compliqué non plus : il suffit de considérer le sous-groupe des éléments qui fixent le sommet marqué $\mathfrak{o}$, dit stabilisateur et noté $St(\mathfrak{o})$.

Les graphes de Schreier généralisent les graphes de Cayley. Effectivement, le graphe de Cayley d'un groupe $G$ est juste le graphe de Schreier par rapport au sous-groupe trivial $\{e\}$, où par rapport à l'action du groupe sur lui-même par multiplication.

Il est connu que chaque graphe régulier de degré paire est un graphe de Schreier~\cite{MR0450121}. Pour une preuve détaillée du cas infini, voir~\cite[Theorem~3.2.5]{thesis}. Ce n'est pas le cas pour les graphes de Cayley. Comme on verra dans la Section~\ref{growthsect}, les graphes de croissance $n^d$ où $d$ n'est pas entier ne sont pas des graphes da Cayley.

\subsection{Bouts des graphes}

\begin{defi}\label{end}
Considérons une espace topologique $X$. Pour un ensemble compact $K\subset X$ on dénote $\pi_0(X\setminus K)$ l'ensemble des composantes connexes de $X\setminus K$. Il y a un ordre naturelle défini par $K_1\leq K_2$ si et seulement si $K_1\subseteq K_2$. On en obtient un morphisme $\pi_{1,2}:\pi_0(X\setminus K_2)\mapsto \pi_0(X\setminus K_1)$ qui envoi chaque composante connexe dans une composante connexe qui la contient. Cela forme une système inverse indexé par $K\subset X$ (voir~\cite[Section~3.1.2]{qtheory}). \textbf{L'espace des bouts} est la limite inverse :
	
$$\underset{compact}{\varprojlim_{K\subset X}}\pi_0(X\setminus K)=\{(x_K)\in\underset{compact}{\prod_{K\subset X}}\pi_0(X\setminus K)|\pi_{\alpha,\beta}x_\beta=x_\alpha,\ K_\alpha\subset K_\beta\}.$$

Dans le cas d'un graphe, de façon équivalent, si on prends une suite exhaustive croissante pour l'inclusion d'ensembles finis $K_1\subset K_2\subset\dots$, un \textbf{bout} est représenté par une suite décroissante $U_1\supseteq U_2\supseteq\dots$ de composantes connexes de $X\setminus K_i$.
\end{defi}

Par exemple, dans un arbre l'ensemble des bouts est représentable par les branches infinies. Les graphes de Cayley de $\Z$ et $F_2$ sont des arbres, et ils ont donc deux bouts et un nombre infini de bouts respectivement. Par contre, considérons le graphe de Cayley $\Z^d$ pour $d\geq2$. Pour chaque $K$ fini, $\Z^d\setminus K$ a exactement une composante connexe infini. Ce graphe a donc un seul bout.

Dans le cas des graphes de Cayley, le nombre de bouts est bien classifié par Stallings~\cite{stallingstosionfree,stallings1972group} (voir~\cite[Sections~13.5~et~13.6]{Geoghegan2008}). Il était connu avant lui que le nombre des bouts est $0,1,2$ ou $\infty$, et que les groupes avec $0$ bouts sont les groupes finis, et les groupes avec $2$ bouts sont les groupes virtuellement $\Z$. Il démontre qu'un groupe a un nombre infini de bouts si et seulement s'il peut être écrit comme  produit libre amalgamé ou comme une extension HNN sur un groupe fini. 

\subsection{Exemples}

\subsubsection{Le groupe de la Basilique}\label{autosim}

\begin{figure}[!h]\centering\resizebox{.9\linewidth}{!}{
		\psfrag{00000}{\tiny$00000$} \psfrag{10000}{\tiny$10000$} \psfrag{01000}{\tiny$01000$}
		\psfrag{11000}{\tiny$11000$} \psfrag{00100}{\tiny$00100$} \psfrag{10100}{\tiny$10100$}
		\psfrag{01100}{\tiny$01100$} \psfrag{11100}{\tiny$11100$} \psfrag{00010}{\tiny$00010$}
		\psfrag{10010}{\tiny$10010$} \psfrag{01010}{\tiny$01010$} \psfrag{11010}{\tiny$11010$}
		\psfrag{00110}{\tiny$00110$} \psfrag{10110}{\tiny$10110$} \psfrag{01110}{\tiny$01110$}
		\psfrag{11110}{\tiny$11110$} \psfrag{00001}{\tiny$00001$} \psfrag{10001}{\tiny$10001$}
		\psfrag{01001}{\tiny$01001$} \psfrag{11001}{\tiny$11001$} \psfrag{00101}{\tiny$00101$}
		\psfrag{10101}{\tiny$10101$} \psfrag{01101}{\tiny$01101$} \psfrag{11101}{\tiny$11101$}
		\psfrag{00011}{\tiny$00011$} \psfrag{10011}{\tiny$10011$} \psfrag{01011}{\tiny$01011$}
		\psfrag{11011}{\tiny$11011$} \psfrag{00111}{\tiny$00111$} \psfrag{10111}{\tiny$10111$}
		\psfrag{01111}{\tiny$01111$} \psfrag{11111}{\tiny$11111$} \epsfig{file=1601.07687/Graph_Basilica.eps,height=230pt}
	}
	\centering\epsfig{file=1601.07687/BasilicaLimitSpace.eps,width=.9\linewidth}
	\caption{Le graphe de Schreier à niveau $5$ du groupe de la Basilique et son espace limite par Bondarenko, D'Angeli et Nagnibeda}
	\label{basil}
\end{figure}

Notons $\mathcal{T}$ l'arbre infini binaire. Ses sommets sont les suites finies de $\{0,1\}$, la suite vide étant la racine. On considère des automorphismes sur lui. Comme ils préservent la racine (car il est le seul sommet de degré $2$), ils préservent - et donc permutent - chaque niveau. Un automorphisme est donc défini de façon unique par le choix, sur chaque sommet, de permuter ou non les deux fils. Un sous-groupe de $Aut(\mathcal{T})$ est appelé un groupe agissant sur un arbre enraciné binaire. On s'intéressera à un tel groupe, le groupe de la Basilique. Il est défini comme le groupe engendré par deux éléments $a$ et $b$ définis par récurrence sur le longueur $k$ de la suite :

\begin{equation*}
	%\begin{columns}
	\begin{minipage}{0.52\linewidth}
		\[\begin{cases}&a(0,j_2,\dots,j_k)=(0,j_2,\dots,j_k)\\
			&a(1,j_2,\dots,j_k)=(1,b(j_2,\dots,j_k))\\
		\end{cases}\]
	\end{minipage}
	\begin{minipage}{0.52\linewidth}
		\[\begin{cases}&b(0,j_2,\dots,j_k)=(1,a(j_2,\dots,j_k))\\
			&b(1,j_2,\dots,j_k)=(0,j_2,\dots,j_k)\\
		\end{cases}\]
	\end{minipage}
	%\end{columns}
\end{equation*}

Il est aussi le groupe des monodromies itérées du polynôme $z^2-1$ (voir le survol par Bartholdi, Grigorchuk et Nekrashevych~\cite{itermonod}; livre de Nekrashevych~\cite[Chapitres~3~et~5]{Nekrashevych2005}); les graphes de Schreier induits au niveau $n$ convergent, quitte à normaliser la distance, vers l'ensemble de Julia du polynôme. Le groupe doit son nom à cet ensemble : il ressemble la Basilique de San Marco à Venise. Une visualisation de Bondarenko, D'Angeli et Nagnibeda~\cite{schreierbandarenkoangelinagnibeda} est présenté dans Figure~\ref{basil}.

\subsubsection{Le groupe $D_\infty\wr_a\Z_2$}\label{dihedsect}

On présente ici un exemple auquel on s'intéresse dans~\citeme{lampl} (voir Chapitre~\ref{lampl}). On commence par définir une généralisation du produit en couronne (voir Section~\ref{lamplsect}) :

\begin{defi}\label{deflampact}
Considérons un groupe $A$ qui agit sur un ensemble $X$. Notons cette action $a$. Le \textbf{produit en couronne permutationnel} (restreint) $A\wr_aB$ est le produit semi-direct de $A$ sur $B^{(X)}$ où $A$ agit sur $B^{(X)}$ par translation.
\end{defi}

Remarquons qu'un produit en couronne est un produit en couronne permutationnel pour l'action du groupe sur lui même par multiplication.

Considérons le groupe diédral infini $D_\infty$, défini par
$$D_\infty=\langle a,x|x^2=e,xax=a^{-1}\rangle.$$
De façon équivalent, il est le produit semi-direct de $\Z_2=\Z/2\Z$ sur $\Z$, avec l'élément non-neutre de $\Z_2$ agissant en tant que l'inversion sur $\Z$. Tout élément s'écrit soit $a^n$, soit $xa^n$. On considère un autre ensemble générateur :  $\{x,y\}$ avec
$$y=xa.$$
Alors $xax=a^{-1}$ devient $(xa)^2=e$ et donc $D_\infty$ est aussi le produit libre de $\Z_2$ avec lui-même.

\begin{figure}[!h]\centering\resizebox{.9\linewidth}{!}{
	\begin{tikzpicture}[shorten >=1pt, auto, node distance=3cm, ultra thick]
		\begin{scope}[every node/.style={circle,draw=blue,fill=blue!20!,font=\sffamily\Large\bfseries}]
			\node (p1) at (-2,2) {1};
			\node (p2) at (1,2) {2};
			\node (p3) at (4,2) {3};
			\node (m1) at (-2,-2) {-1};
			\node (m2) at (1,-2) {-2};
			\node (m3) at (4,-2) {-3};
			\node (r) at (-4,0) {0};
		\end{scope}
		\begin{scope}[every loop/.style={min distance=25mm,in=250,out=290}]
			\tikzset{edge/.style = {->,> = latex'}}
			\draw[edge,draw=black,very thick,dashed] (p1) to[bend right] (m1);
			\draw[edge,draw=black,very thick,dashed] (m1) to[bend right] (p1);
			\draw[edge,draw=black,very thick,dashed] (p2) to[bend right] (m2);
			\draw[edge,draw=black,very thick,dashed] (m2) to[bend right] (p2);
			\draw[edge,draw=black,very thick,dashed] (p3) to[bend right] (m3);
			\draw[edge,draw=black,very thick,dashed] (m3) to[bend right] node[right] {\scalebox{2}{$\mathbf{\dots}$}} (p3);
			\draw[edge,draw=black,very thick,dashed] (r) to[loop above] (r);
			\draw[edge,draw=blue,very thick] (p2) to[bend right] (m1);
			\draw[edge,draw=blue,very thick] (m1) to[bend right] (p2);
			\draw[edge,draw=blue,very thick] (p3) to[bend right] (m2);
			\draw[edge,draw=blue,very thick] (m2) to[bend right] (p3);
			\draw[edge,draw=blue,very thick] (p1) to[bend right] (r);
			\draw[edge,draw=blue,very thick] (r) to[bend right] (p1);
			\draw[edge,draw=red,very thin] (m3) to (m2);
			\draw[edge,draw=red,very thin] (m2) to (m1);
			\draw[edge,draw=red,very thin] (m1) to (r);
			\draw[edge,draw=red,very thin] (r) to (p1);
			\draw[edge,draw=red,very thin] (p1) to (p2);
			\draw[edge,draw=red,very thin] (p2) to (p3);
		\end{scope}
	\end{tikzpicture}}
\caption{(Une partie du) Graphe de Schreier de $D_\infty$ pour le sous-groupe $\{e,x\}$ avec $x$ (pointillée, noire), $y$ (bleue) et $a$ (fine, rouge). On va considérer l'ensemble générateur $\{x,y\}$ (sans les lignes rouges)}
\label{dinf}
\end{figure}

Considérons le sous-groupe $\{e,x\}$ et le graphe de Schreier de coset qu'il définit (avec ensemble générateur $\{x,y\}$). Chaque sommet est de la forme $\{g,xg\}$, et il peut donc s'écrire comme $\{xa^n,a^n\}$ pour un $n\in\Z$. Si on représente les sommets avec ces entiers, le graphe est dessiné dans la Figure~\ref{dinf}. Avec l'ensemble générateur $\{x,y\}$, il est un rayon : $0,1,-1,2,-2,3,-3,\dots$.

On s'intéressera à l'action $a$ de $D_\infty$ que cela définit (voir Définition~\ref{defschreier}), et le produit en couronne permutationnel $D_\infty\wr_a\Z_2$ qu'on y obtient. On expliquera dans la Section~\ref{folfunct} que cela donne un exemple où la fonction de F\o lner est similaire à la fonction de croissance.

\section{Profiles géométriques}

\subsection{Croissance des groupes}\label{growthsect}

Pour un groupe $G$ de type fini, et un ensemble $S$ fini générateur, on dénote $V(k)=V(G,S,k)$ la taille de la boule autour de l'identité dans le graphe de Cayley associé. On dénote $\omega(G,S)=\limsup_k\sqrt[k]{V(G,S,k)}$. Si $\omega(G,S)>1$, on dit que $G$ est de \textbf{croissance exponentielle} (remarquons que cela ne dépend pas du choix de $S$ fini; par contre le valeur exact de $\omega(G,S)$ si). Si $V(G,S,k)$ est majorée par un polynôme, on dit que $G$ est de \textbf{croissance polynomiale}. Sinon, si $V$ croît plus vite que chaque polynôme mais plus lentement que chaque exponentielle, on dit que le groupe est de \textbf{croissance intermédiaire}. Il n'est pas évident de construire un tel groupe. On exprimera un exemple dans la prochaine Section~\ref{grigsect}.

Les groupes de croissance polynomiale sont bien classifiés par un résultat célèbre de Gromov~\cite{polynilp}. Il obtient qu'ils sont exactement les groupes virtuellement nilpotents. En particulier, leur croissance vérifie que $V(n)n^{-d}$ converge pour l'entier $d=\sum_{i\geq1}i\rang(G_i/G_{i+1})$ où $(G_i)$ est la suite centrale descendante. Voir Bass~\cite{Bass1972}, Guivarc'h~\cite{Guivarch1973} pour $V(n)$ entre $C_1n^d$ et $C_2n^d$ et Pansu~\cite{Pansu1983} pour la convergence.

Si un groupe n'est pas de croissance exponentielle, on peut montrer qu'une sous-suite de boules autour de l'identité forme des ensembles de Følner. En effet, si $\omega(G,S)<1+\epsilon$, alors à partir d'un certain $k$, $V(G,S,k)<(1+\epsilon)^k$. Cela implique que l'on peut en extraire une sous-suite de boules telle que le bord est toujours plus petit que $\epsilon$ fois l'intérieur. En procédant par extraction diagonale, on obtient le résultat. Il est donc moyennable. Par contre, l'inverse n'est pas vrai. Considérons par exemple le produit en couronne $\Z\wr\Z_2$ (où $\Z_2=\Z/2\Z)$. Il n'est pas difficile de voir que les éléments $(1,\mymathbb{0})$ et $(1,\delta_0^1)$ (avec les notations de Section~\ref{lamplsect}) forment un sous-semi-groupe libre. La croissance de $\Z\wr\Z_2$ est donc au moins $2^n$ pour un ensemble générateur qui les contient. On a donc une croissance exponentielle. Par contre il est moyennable, et même résoluble. Comme on a vu dans la Section~\ref{lamplsect}, un exemple d'ensembles de Følner pour ce groupe est l'ensemble $F_n$ des $(k,f)$ tels que $\supp(f)\subset[\![1\dots n]\!]$ et $k\in[\![1\dots n]\!]$. Ils vérifient $\frac{|\partial F_n|}{|F_n|}=\frac{2}{n}$. La question suivante reste ouverte. Peut-on choisir pour chaque groupe moyennable certaines boules comme ensembles de Følner ? Si l'on sait que la croissance est intermédiaire ou polynomiale, c'est vrai, mais dans ce cas la question se pose de savoir si on peut choisir toutes les boules comme des ensembles de Følner.

\subsection{Groupe de Grigorchuk}\label{grigsect}

Pour plus de références sur cette section, voir le livre de Pierre de la Harpe~\cite[Ch.~VIII]{harpebible}. On rappelle quelques définitions de la Section~\ref{autosim}. Notons $\mathcal{T}$ l'arbre infini binaire. Ses sommets sont les suites finies de $\{0,1\}$, la suite vide étant la racine. On considère des automorphismes sur lui. Comme ils préservent la racine (car il est le seul sommet de degré $2$), ils préservent - et donc permutent - chaque niveau. Un automorphisme est donc défini de façon unique par le choix, sur chaque sommet, de permuter ou non ses deux fils. Notons $a$ l'automorphisme qui permute les deux branches principales et rien d'autre. Autrement dit, 

$$a(j_1,j_2,\dots,j_k)=(\bar{j_1},j_2,j_3,\dots,j_k)$$
où $\bar{j}=1-j$. On définit aussi $b,c$ et $d$ par récurrence. L'automorphisme $b$ va agir comme $a$ sur le sous-arbre à gauche (celui dont les sommets sont de la forme $(0,j_2,j_3,\dots,j_k)$) et comme $c$ à droite. De même, $c=(a,d)$, mais $d=(1,b)$. Formellement :

\[\begin{cases}& b(0,j_2,j_3,\dots,j_k)=(0,\bar{j_2},j_3,\dots,j_k) \\
& b(1,j_2,j_3,\dots,j_k)=(1,c(j_2,j_3,\dots,j_k)) \\
\end{cases}\]

\[\begin{cases}& c(0,j_2,j_3,\dots,j_k)=(0,\bar{j_2},j_3,\dots,j_k) \\
& c(1,j_2,j_3,\dots,j_k)=(1,d(j_2,j_3,\dots,j_k)) \\
\end{cases}\]

\[\begin{cases}& d(0,j_2,j_3,\dots,j_k)=(0,j_2,j_3,\dots,j_k) \\
& d(1,j_2,j_3,\dots,j_k)=(1,b(j_2,j_3,\dots,j_k)). \\
\end{cases}\]

Le \textbf{groupe de Grigorchuk} (ou première groupe de Grigorchuk) est alors $\Gamma=\langle a,b,c,d\rangle$ (le sous-groupe de $Aut(\mathcal{T})$ engendré par ces quatre éléments). Notons qu'on a $a^2=b^2=c^2=d^2=1$ et aussi $bc=cb=d$. Cela veut dire que pour chaque mot sur $a,b,c,d$ qui est de longueur minimale pour l'élément du groupe qu'elle représente, elle est de la forme $ax_1ax_2\dots x_ka$, $ax_1\dots x_k$, $x_1a\dots x_ka$ ou $x_1a\dots x_k$ pour $x_1,\dots,x_k$ parmi $b,c,d$. Notons $St_\Gamma(k)$ le sous-groupe qui fixe les $k$ premiers niveaux. Il agit séparément sur chaque sous-arbre défini en prenant un sommet de profondeur $k$ comme racine. On peut vérifier que la restriction donne aussi un élément de $\Gamma$. On a donc des morphismes naturels $St_\Gamma(k)\mapsto\Gamma^{2^k}$. Considérons en particulier $St_\Gamma(3)$. D'après les définitions on peut voir que pour chaque élément parmi $b,c,d$, on peut trouver une branche sur laquelle cet élément agit trivialement jusqu'à cette profondeur. On peut utiliser cela et l'écriture ci-dessus pour démontrer :

\begin{lemma}\label{majorgrigo}
	Considérons $\gamma\in St_\Gamma(3)$ et soient $\gamma_1,\dots,\gamma_8$ les restrictions de $\gamma$ sur les sous-arbres. On a donc :
	
	$$\sum_{i=1}^8|\gamma_i|\leq\frac{3}{4}|\gamma|+8.$$
\end{lemma}

On sait que, pour tout $\varepsilon>0$, $V(k)=V(\Gamma,\{a,b,c,d\},k)\leq(\omega(\Gamma,\{a,b,c,d\})+\varepsilon)^k$ à partir d'un certain rang (par définition de limite supérieure). Si on applique à cela ce Lemme~\ref{majorgrigo} et le fait que $St_\Gamma(3)$ est d'indice $2^7$ (voir~\cite[VIII.22]{harpebible}), on obtient

$$V(k)\leq DP(k)(\omega+\varepsilon)^{\frac{3}{4}(k+2^7-1)+8}$$
pour une constante $D$ et un polynôme $P$. Cela implique que $\omega\leq(\omega+\varepsilon)^{\frac{3}{4}}$. On a donc $\omega(\Gamma,\{a,b,c,d\})=1$ et le groupe de Grigorchuk n'est pas de croissance exponentielle (il est donc moyennable). On peut montrer aussi qu'il n'est pas de croissance polynomiale \cite[VIII.63]{harpebible}. Il est le premier tel exemple. Cela ne résout pas encore la question sur la classification des croissances : il reste ouvert le Growth Gap Conjecture~\cite[Conjecture~2]{grigsurvey}, qui conjecture que la croissance en volume doit être soit polynomiale, soit plus grande que $\exp(\sqrt{n})$. Plus généralement, la version faible de cette conjecture est qu'il existe un $0<\beta<1$ tel que la croissance en volume doit être soit polynomiale, soit plus grande que $\exp(n^\beta)$.

On peut aussi montrer que ce groupe est de torsion, mais pas de torsion fini: plus précisément, pour chaque $\gamma\in\Gamma$ il existe $N$ tel que $\gamma^{2^N}=1$, mais pour chaque $n$ il existe $\gamma$ tel que $\gamma^{2^n}\neq1$.

\subsection{Définition de la fonction de Følner}\label{foldefsect}

Fixons un groupe $G$ moyennable de type fini et un ensemble générateur $S$ et soit $\Gamma$ son graphe de Cayley. Rappelons la condition de Følner : Théorème~\ref{moyeq}(3). On rappelle que pour un groupe de type fini, on peut considérer $E$ comme n'importe quel ensemble générateur fixé. On s'intéressera en particulier à $E=S\bigcup S^{-1}\bigcup\{Id\}$. Alors pour un ensemble $F$, $F.E\bigtriangleup F$ est l'ensemble des éléments $g$ qui ne sont pas dans $F$ mais pour lesquels il existe un $s=s(g)\in S$ tel que $s.g$ où $s^{-1}.g$ est dans $F$. Autrement dit, ce sont les éléments dans le complémentaire de $F$ qui sont à distance $1$ de $F$ dans $\Gamma$. On appellera cet ensemble $\partial_{out}F$ (définition valable de façon générale pour tout graphe). Similairement, $\partial_{in}F$ sera l'ensemble des éléments de $F$ à distance $1$ de l'extérieur. Finalement, $\partial F$ est l'ensemble d'arrêtes entre $F$ et son complémentaire. La fonction de Følner est alors :

\begin{equation}\label{foldef}
\Fol(n)=\min\left\{|F|: F\subset G,\frac{|\partial_{in}F|}{|F|}\leq\frac{1}{n}\right\}.
\end{equation}

Remarquons que $\Fol(1)=1$ pour tout groupe et tout ensemble générateur.

\subsection{Quasi-isométries et équivalence asymptotique}\label{quasisect}

Soient $X$ et $X'$ deux espaces métriques. Une fonction $\phi:X\mapsto X'$ est appelée un \textbf{plongement quasi-isométrique} s'il existe des constantes $\lambda\geq1$ et $C\geq0$ telles que pour tout $x,y$ :

$$\frac{1}{\lambda}d(x,y)-C\leq d'(\phi(x),\phi(y))\leq\lambda d(x,y)+C.$$

C'est une \textbf{quasi-isométrie} si de plus il existe $D\geq0$ tel que chaque point de $X'$ est à distance plus petite que $D$ d'un point de $\phi(X)$. On le considère dans le cas des groupes de type fini avec la métrique de longueur de mots.

\begin{prop}
	Soit $G$ un groupe de type fini et $S$ et $S'$ deux ensembles générateurs. Alors $G$ avec la métrique de longueur de mots sur $S$ est quasi-isométrique à $G$ avec la métrique de longueur de mots sur $S'$.
\end{prop}

On a donc une notion de quasi-isométrie de groupes bien définie pour les groupes de type fini. Les propriétés préservées par quasi-isométrie sont considérées comme des propriétés géométriques. La moyennabilité en est une. Une façon simple de voir cela est d'utiliser la condition de Følner. 

Il existe plusieurs propriétés pour lesquelles on ne sait pas si elles sont géométriques. Par exemple, on ne sait pas si deux groupes, l'un avec un sous-groupe libre et l'autre sans, peuvent être quasi-isométriques. Être de torsion aussi, on ne sait pas si cette propriété est préservé par quasi-isométrie.

Le type de croissance (comme défini dans la Section~\ref{growthsect}) est préservé par quasi-isométries. Par rapport aux fonctions de F\o lner, les quasi-isométries les préservent à \textbf{équivalence asymptotique} prês. Deux fonctions sont asymptotiquement équivalentes s'il existe des constantes $A$ et $B$ tels que $f(x/A)/B<g(X)<f(xA)B$. L'approche standard pour décrire la fonction de F\o lner d'un groupe est ainsi de donner sa classe d'équivalence asymptotique. Il vaut de noter aussi que la classe d'équivalence asymptotique de la probabilité de retour après $2n$ pas est préservé par quasi-isométrie pour les graphes de Cayley (voir Pittet et Saloff-Coste~\cite{Pittet2000a}). 

\subsection{Fonctions de Følner}\label{folfunct}

Comme on l'a mentionné dans la Section~\ref{quasisect}, généralement, on cherche à classifier les fonctions de Følner à équivalence asymptotique près. Le Théorème isopérimétrique classique dit que le compact dans $\R^n$ qui minimise le bord pour un volume fixé est la boule (voir le survol d'Osserman~\cite[Section~2]{Osserman1978}). Car $\Z^n$ est quasi-isométrique à $\R^n$, cela est aussi un première résultat pour les groupes discrets. Le fait que si un minimum existe, il est réalisé uniquement sur la boule est obtenu (dans $\R^2$) par Steiner au XIX\textsuperscript{e} siècle, en utilisant ce qui est maintenant appelé symétrisation de Steiner (voir Hehl~\cite{hehl13}, Hopf~\cite{hopf40}, Froehlich~\cite{froehlich09}). L'existence du minimum est prouvé, dans $\R^3$, par Schwarz~\cite{Schwarz1884}. Varopoulos~\cite{Varopoulis1985} démontre plus généralement une inégalité isopérimétrique pour les produits directs. Pansu~\cite{pansu83} (voir aussi~\cite{pansu82}) en obtient dans le groupe de Heisenberg $H_3$. Un résultat central est l'inégalité de Coulhon et Saloff-Coste~\cite{Coulhon1993}, qui relie la croissance en volume et la fonction de F\o lner :

\begin{thm}[Inégalité de Coulhon et Saloff-Coste]\label{cscthm}
	Soit $G$ un groupe infini engendré par un ensemble $S$ fini et soit $\phi(\lambda)=\min(n|V(n)>\lambda)$, où $V(n)$ est la taille de la balle de rayon $n$ dans le graphe de Cayley. Alors pour tout ensemble $F$ fini on a
	
	$$\frac{|\partial_{in}F|}{|F|}\geq\frac{1}{8|S|\phi(2|F|)}.$$
\end{thm}

Les constantes multiplicatives peuvent être améliorées (voir G. Pete~\cite[Theorem~5.11]{pete}, B. L. Santos Correia~\cite{csc2020}):

\begin{equation}\label{csceq}
	\frac{|\partial_{in}F|}{|F|}\geq\frac{1}{2\phi(2|F|)}.
\end{equation}

Le résultat de Santos Correia est annoncé également pour les groupes finis pour $|F|\leq\frac{1}{2}|G|$. L'inégalité de Coulhon et Saloff-Coste (Théorème~\ref{cscthm}) implique en particulier que pour un groupe de croissance exponentielle, sa fonction de Følner est au moins exponentielle. Similairement, il est connu que les fonctions de F\o lner des groupes de croissances polynomiales sont au plus polynomiales (voir par exemple~\cite[Section~I.4.C]{woess2000random}). Une autre inégalité sur l'isopérimétrie des groupes est donné par Żuk~\cite{Zuk2000}. Vershik~\cite{vershik1973countable} demande si la fonction de Følner peut être super-exponentielle, ce qui marque le début de l'étude des fonctions de Følner. Il suggère le produit en couronne $\Z\wr\Z$ comme un exemple à considérer. Pittet~\cite{Pittet1995} montre que les fonctions de F\o lner des groupes polycycliques sont au plus exponentielles (elles sont donc exponentielles pour les groupes polycycliques de croissance exponentielle). Cela est plus généralement vrai pour les groupes résolubles avec rang de Prüfer fini, voir~\cite{Pittet2003} et~\cite{Kropholler2020}. Le premier exemple de groupe avec fonction de F\o lner super-exponentielle est obtenu par Pittet et Saloff-Coste~\cite{PittetSaloffCoste} pour $\Z^d\wr\Z/2\Z$. Plus tard les fonctions de F\o lner des produits en couronnes avec certains conditions de régularité sur les groupes de base sont décrites par Erschler~\cite{Erschler2003} à équivalence asymptotique prêt. Spécifiquement, on dénote qu'une fonction $f$ vérifie la propriété $(*)$ si pour tout $C>0$ il existe $k>0$ tel que $f(kn)>Cf(n)$. Son résultat dit alors que pour deux groupes dont les fonctions de F\o lner vérifient cette propriété, la fonction de F\o lner de leur produit en couronne $A\wr B$ est $\Fol_{A\wr B}(n)=\Fol_B(n)^{\Fol_A(n)}$.

Une direction d'études des fonctions de F\o lner cherche à décrire la classe de fonctions $f$ pour lesquelles il existe un groupe dont la fonction de F\o lner est asymptotiquement équivalente à $f$. Plusieurs auteurs ont trouvé des conditions de plus en plus faibles. Gromov~\cite[Section~8.2,~Remark~(b)]{Gromov2009} construit des groupes avec des fonctions de F\o lner prescrits pour toutes les fonctions dont des dérivées croissent assez vite. Saloff-Coste et Zheng~\cite{saloffcostezheng} décrivent les fonctions de F\o lner, entre autres, d'une classe des «bubble» groupes et d'une classe de groupes cycliques de Neumann-Segal. Plus récemment, Brieussel et Zheng~\cite{BrieusselZheng} démontrent que pour toute $f$ croissante avec $f(1)=1$ et $n/f(n)$ croissante, il existe un groupe dont la fonction de F\o lner est asymptotiquement équivalente à l'exponentielle de la fonction inverse de $n/f(n)$. Erschler et Zheng~\cite{Erschler2017} obtient des exemples pour une classe de fonctions super-exponentielles en dessous de $\exp(n^2)$ avec des conditions de régularité plus faibles. Spécifiquement, pour tout $d\in\N$ et $\tau(n)\leq n^d$ largement croissante elles obtiennent qu'il existe un groupe $G$ et une constante $C$ avec

\begin{equation}\label{annatyani}
	Cn\exp(n+\tau(n))\geq\Fol_G(n)\geq\exp(\frac{1}{C}(n+\tau(n/C))).
\end{equation}

La coté gauche est toujours asymptotiquement équivalente à $\exp(n+\tau(n))$, et il suffit donc que la coté droite le soit aussi pour décrire la fonction de F\o lner de $G$. En particulier, il suffirait que $\tau$ vérifie~$(*)$. Remarquons que les conditions décrites ici ne considèrent que les fonctions plus grandes que $\exp(n)$; c'est une question ouverte de savoir si une fonction de F\o lner peut avoir croissance intermédiaire (voir Grigorchuk~\cite[Conjecture~5(ii)]{grigsurvey}). Par Erschler~\cite[Lemme~3.1]{Erschler2006}, une réponse négative impliquerait le Growth Gap Conjecture. On peut définir une version faible de la conjecture pour les fonctions de F\o lner de façon similaire à la forme faible du Growth Gap Conjecture. Les versions faibles sont équivalentes (voir la discussion après Conjecture~6 dans~\cite{grigsurvey}).

On connait encore moins les descriptions exactes des fonctions de F\o lner. Dans un travail en cours~\citeme{lampl} (voir Chapitre~\ref{lampl}) on obtient des valeurs exactes pour les fonctions de F\o lner du produit en couronne (voir Section~\ref{lamplsect}) $\Z\wr\Z_2$ pour deux ensembles générateurs (on dénote $\Z_2=\Z/2\Z$), et des résultats isopérimétriques sur le groupe de Baumslag-Solitar $BS(1,2)$. Des connaissances de l'auteur, ce sont les premières exemples où les valeurs exactes d'une fonction de F\o lner non-polynomiale sont connues. On rappelle que les ensembles de F\o lner standards $F_n$ sur $\Z\wr\Z_2$ sont $F_n=\{(k,f)|k\in[\![1,n]\!],\supp(f)\subset[\![1,n]\!]\}$. On dénote $t=(1,\mymathbb{0})$ et $\delta=(0,\delta_0^1)$. Les deux ensembles générateurs qu'on considéra ici sont l'ensemble standard $S=\{t,\delta\}$ et l'ensemble «switch-walk-switch» $S'=\{t,\delta,t\delta,\delta t,\delta t\delta\}$.

\begin{defi}\label{optimal}
On dira qu'un sous-ensemble $F$ fini d'un groupe $G$ est \textbf{optimal} par rapport au bord intérieur (respectivement extérieur, par rapport aux arrêtes) si pour tout $F'$ avec $|F'|\leq|F|$, on a $$\frac{|\partial_{in}F'|}{|F'|}\geq\frac{|\partial_{in}F|}{|F|}$$
(respectivement $\frac{|\partial_{out}F'|}{|F'|}\geq\frac{|\partial_{out}F|}{|F|}$, $\frac{|\partial F'|}{|F'|}\geq\frac{|\partial F|}{|F|}$), et si $|F'|<|F|$, les inégalités sont strictes.
\end{defi}

On obtient alors :

\begin{thmme}\label{thmlamp}
Considérons le produit en couronne $\Z\wr\Z_2$.
\begin{enumerate}
	\item Pour tout $n\in\N$, l'ensemble de F\o lner standard $F_n$ est optimal par rapport au bord extérieur et le bord par rapport aux arrêtes pour l'ensemble générateur standard $S$. Autrement dit, pour tout $F\subset\Z\wr\Z_2$ tel que $|F|\leq|F_n|$, on a
	$$\frac{|\partial F|}{|F|}\geq\frac{|\partial_{out}F|}{|F|}\geq\frac{|\partial_{out}F_n|}{|F_n|}=\frac{|\partial F_n|}{|F_n|},$$
	et si $|F|<|F_n|$, les inégalités sont strictes,
	\item Pour tout $n\in\N$ on a
	\begin{enumerate}
		\item Pour $S$, $F_n\bigcup\partial_{out}F_n$ est optimal par rapport au bord intérieur,
		\item Pour $S'$, $F_n\bigcup\partial'_{out}F_n$ est optimal par rapport au bord intérieur,
	\end{enumerate}
	\item Les résultats de $(2)$ impliquent que, pour $n\geq2$, la fonction de F\o lner sur $\Z\wr\Z_2$ pour l'ensemble générateur standard est
	$$\Fol(n)=2n2^{2(n-1)}$$
	et pour l'ensemble «switch-walk-switch» elle est
	$$\Fol_{sws}(n)=2n2^{2n}.$$
\end{enumerate}
\end{thmme}

De plus les ensembles qui donnent l'égalité sont uniques à translation prêt. Remarquons que le point $(3)$ est le Théorème~\ref{thmfollamp}.

On substitue ces valeurs dans l'inégalité de Coulhon et Saloff-Coste pour étudier les constantes multiplicatives. L'inégalité~\ref{csceq} implique (pour toute groupe infini et toute ensemble générateur fini) :

$$2\Fol(n)>V(\frac{n}{2}-1).$$

Pour les groupes de croissance exponentielle, il n'est pas difficile de voir que la constante multiplicative devant $n$ est plus importante que les autres constantes. Effectivement, si on obtient $A\Fol(n)\geq V(n(\frac{1}{2}+\varepsilon)-B)$ pour certains $\varepsilon,A,B>0$, ce résultat est strictement plus fort pour $n$ assez grand. On peut donc demander :

\begin{question*}\label{constq}
	Pour un groupe $G$ et un ensemble générateur $S$, on dénote $C_{G,S}$ le supremum de l'ensemble des constances $C$ tels qu'ils existent $A$ et $B$ avec $A\Fol(n)\geq V(Cn-B)$. Quel est l'infimum $C_0$ de l'ensemble de tout $C_{G,S}$ sur tout groupe et tout ensemble générateur fini ?
\end{question*}

L'inégalité originale donne une réponse positive pour $C=\frac{1}{8|S|}$ (et donc $C_0\geq\frac{1}{8|S|}$), et les résultats de \cite[Theorem~5.11]{pete} et \cite{csc2020} qu'on a cité en tant qu'Équation~\ref{csceq} montrent que $C_0\geq\frac{1}{2}$.

Il n'est pas difficile de voir que si les limites $\lim\frac{\ln\Fol(n)}{n}$ et $\lim\frac{\ln V(n)}{n}$ existent pour un groupe et un ensemble générateur, le supremum $C_{G,S}$ sera leur quotient. La deuxième limite existe toujours. Chaque élément de longueur au plus $mn$ s'écrit comme le produit de deux éléments de longueur respectivement au plus $m$ et au plus $n$. On a donc
$$V(m+n)\leq V(m)V(n),$$
et $\ln V(n)$ est sous-additive. La limite existe alors par le lemme sous-additif de Fekete. Par contre, l'autre limite $\lim\frac{\ln\Fol(n)}{n}$ peut ne pas exister. Un exemple trivial vient des groupes avec fonctions de F\o lner super-exponentielles, où la suite diverge vers $+\infty$. Mais même si on décide de considérer cela comme une suite convergente (vers $+\infty$), la limite n'est encore pas toujours existant. On peut considérer des exemples de Erschler et Zheng où la fonction de F\o lner oscille entre $\exp n$ et $\exp n^c$. Alors $\frac{\ln\Fol(n)}{n}$ oscille entre une constante finie et $+\infty$. Spécifiquement, considérons \cite[Example~3.8(2)]{Erschler2017} avec $\alpha=1$ et $\beta=2$. Prenons une suite $(\eta_i)$ et une fonction $\tau(n)=n^\alpha$ pour $n\in[\eta_{2j-1},\eta_{2j}]$ et $\tau(n)=n^\beta$ pour $n\in[\eta_{2j},\eta_{2j+1}]$. L'exemple nous donne un groupe dont la fonction de F\o lner vérifie Inégalité~\ref{annatyani}. Pour $n\in[\eta_{2j-1},\eta_{2j}]$ on a $\frac{\ln\Fol(n)}{n}\leq\frac{ln(Cn)}{n}+1+\frac{\tau(n)}{n}$, qui est plus petit que $3$ pour $n$ grand. En autre, si $n\in[\eta_{2j},\eta_{2j+1}]$, $\frac{\ln\Fol(n)}{n}\geq\frac{1}{Cn}(n+\tau(n/C))=\frac{1}{C}+\frac{n}{C^3}$. En particulier, il est plus grand que $4$ pour $n$ grand. On a donc que $\frac{\ln\Fol(n)}{n}$ ne converge pas vers une constante finie, et ne diverge pas vers $+\infty$. On peut quand même considérer $\liminf$.

\begin{propme}\label{quotient}
	$C_{G,S}=\frac{\liminf\frac{\ln\Fol(n)}{n}}{\lim\frac{\ln V(n)}{n}}$.
\end{propme}

D'après le Théorème~\ref{thmfollamp}, sur $\Z\wr\Z_2$ on a (voir~\citeme[Section~5]{lampl}; Chapitre~\ref{lampl} pour les estimations sur le volume) :

\begin{propme}
Le produit en couronne $\Z\wr\Z_2$ vérifie
$$C_{\Z\wr\Z_2,S}=\frac{\lim\frac{\ln\Fol(n)}{n}}{\lim\frac{\ln V(n)}{n}}=\frac{\ln4}{\ln(\frac{1}{2}(1+\sqrt{5}))}\approx2,88$$
pour l'ensemble générateur standard, et

$$C_{\Z\wr\Z_2,S'}=\frac{\lim\frac{\ln\Fol_{sws}(n)}{n}}{\lim\frac{\ln V_{sws}(n)}{n}}=2.$$
\end{propme}

On obtient une borne supérieure $C_0\leq2$. Cette borne était déjà connu avant de montrer que les ensembles standards sont optimaux; Théorème~\ref{thmfollamp} démontre que ces exemples ne peuvent pas donner mieux. Par contre, on démontre dans~\citeme{lampl} (voir Chapitre~\ref{lampl}) que $C_0\leq1$.

\begin{propme}\label{Dihedral}
Le produit en couronne permutationnel $D_\infty\wr_a\Z_2$ (qu'on a décrit dans Section~\ref{dihedsect}) avec l'ensemble générateur $\{t_x,t_y,\delta,t_x\delta,\delta t_x,\delta t_x\delta,t_y\delta,\delta t_y,\delta t_y\delta\}$ vérifie $\frac{\liminf\frac{\ln\Fol(n)}{n}}{\lim\frac{\ln V(n)}{n}}=1$.
\end{propme}

Spécifiquement, on obtient $\Fol(2n+1)=2(2n+1)2^{2n+1}$ et $\lim\frac{\ln\Fol(n)}{n}=\ln2$. Cela vient du fait que dans les ensembles standards, le support des fonctions est contenu dans un intervalle d'un rayon (le rayon qu'on voit sur la Figure~\ref{dinf} sur page~\pageref{dinf}), et (s'il est bien choisi) le bord du support est donc de cardinal $1$.

Une voie de recherche connue est l'étude de la série de croissance $\sum_n V(n)x^n$, spécifiquement si elle est une fonction rationnelle. Une réponse positive est obtenu pour les groupes hyperboliques pour tout ensemble générateur par Gromov~\cite{gromov87} (voir aussi \cite{Cannon1984},\cite[Chapitre~9]{ghys1990groupes}), et par Benson~\cite{Benson1983} pour les groupes virtuellement abéliens. Une condition suffisante qu'on remarque est d'avoir un "nombre fini de types coniques". Passant des groupes virtuellement abéliens vers les groupes nilpotents, Benson~\cite{Benson87} et Shapiro~\cite{Shapiro1989} montrent que la série de croissance du groupe de Heisenberg sur les entiers $H_3$ est rationnelle pour l'ensemble générateur standard. Stoll~\cite{Stoll1996} étudie le groupe de Heisenberg $H_5$ de dimension plus grande et obtient que la série n'est pas rationnelle pour l'ensemble standard, mais elle l'est pour un autre ensemble générateur. Duchin et Shapiro~\cite{duchinshapiro} obtiennent plus tard la rationalité sur $H_3$ pour tout ensemble générateur. Voir Grigorchuk-de~la~Harpe~\cite[Section~4]{Grigorchuk1997} pour un survol. Avoir des valeurs exactes pour les fonctions de F\o lner nous permet d'étudier la série $\sum_n\Fol(n)x^n$. Comme une corolaire de Théorème~\ref{thmfollamp}, on obtient que les séries dans ces deux exemples sont des fonctions rationnelles : respectivement $\frac{2x}{(4x-1)^2}$ et $\frac{8x}{(4x-1)^2}$. Il serait intéressant de trouver une condition géométrique suffisante qui explique cela.

On obtient de plus un résultat isopérimétrique sur le groupe de Baumslag-Solitar $BS(1,2)$ en terme du bord par rapport aux arêtes. Les groupes de Baumslag-Solitar sont définis par la présentation $BS(m,n)=\langle a,b|ba^mb^{-1}=a^n\rangle$. Il est moyennable si et seulement s'il est résoluble, si et seulement si $|m|=1$ où $|n|=1$. Le groupe $BS(1,p)$ est isomorphe au groupe engendré par $x\mapsto x+1$ et $x\mapsto px$ (qui seront respectivement l'image de $a$ et de $b^{-1}$). On peut écrire ces éléments de la forme $x\mapsto p^nx+f$ avec $n\in\Z$ et $f\in\Z[\frac{1}{p}]$. Les générateurs agissent (à droite) respectivement en rajoutant $p^n$ dans $f$ ou en changeant $n$, ce qui présente une structure similaire aux produits en couronnes. Si on écrit cet élément de la forme $(n,f)$, les ensembles standards s'expriment de la même façon que pour les produits en couronnes. Autrement dit, 

\begin{equation}\label{bsstand}
	F_n=\{p^kx+f|k\in[\![1,n]\!],f\in\Z,0\leq f<p^{n+1}\}.
\end{equation}

\begin{thm*}[Théorème~\ref{bs}]
	Considérons le groupe de Baumslag-Solitar $BS(1,2)$ avec l'ensemble générateur $\{a,b\}$. Alors pour tout $n\in\N$ et tout $F\subset BS(1,2)$ fini tel que $|F|\leq|F_n|$, on a $\frac{|\partial F|}{|F|}\geq\frac{|\partial F_n|}{|F_n|}$, et si $|F|<|F_n|$, l'inégalité est stricte.
\end{thm*}

Dans le cas général de $BS(1,p)$, on montre que dans $BS(1,8)$, l'ensemble standard avec $8$ éléments n'est pas optimal. Par contre, ce résultat est relié au fait que $p$ n'est pas négligeable par rapport au longueur de l'intervalle qui définit l'ensemble standard, et il est possible que pour $BS(1,p)$ aussi, les ensembles standards sont optimaux pour grands $n$.

\section{Marches aléatoires gouvernées par des mesures sur les groupes}

\subsection{Définitions}\label{defwalk}

Soit une mesure $\mu$ sur un groupe $G$. La marche aléatoire associée sur $G$ est la chaîne de Markov gouvernée par la probabilité de transition $p(f_1,f_2)=\mu(f_1^{-1}f_2)$. Autrement dit, $p(f,fg)=\mu(g)$. Intuitivement, à chaque pas on choisit un élément $g$ par $\mu$ et on multiplie (à droite) la position où on se trouve par $g$. Si on part de l'élément neutre, cela donne une trajectoire $T_n=g_1g_2\dots g_n$ où $g_i$ sont indépendantes et identiquement distribuées par $\mu$. Remarquons que la trajectoire reste dans le semi-groupe engendré par le support de $\mu$. On dira qu'une mesure est \textbf{non-dégénérée} si son support engendre $G$. Il vaut de noter qu'on aurait pu également multiplier à gauche - c'est un choix de convention.

On définit la marche aléatoire induite par une action de façon similaire. Encore une fois, à chaque pas on choisit un élément $g\in G$ par $\mu$ et on multiplie par lui. On obtient $p(x,y)=\sum_{x.g=y}\mu(g)$, et la trajectoire est $T_n=\mathfrak{o}.g_1g_2\dots g_n$. Noter qu'on a pris l'action à droite.

On cherche à comprendre le comportement limite de ces marches, spécifiquement en terme de leurs bords de Poisson. Le bord de Poisson (aussi dit de Poisson-Furstenberg) est défini de façon générale pour une marche quelconque, et il y a plusieurs définitions équivalentes (voir~\cite{kaimpoisson}).

\begin{defi}\label{poissondef}
Considérons une marche aléatoire et la mesure $P$ induite sur l'espace des trajectoires $G^{\Z_+}$. Considérons la relation d'équivalence suivante : $(x_0,x_1,\dots)\sim(y_0,y_1,\dots)$ si et seulement s'il existe $i_0\in\N$ et $k\in\Z$ tels que pour tout $i>i_0$, $x_i=y_{i+k}$. Autrement dit, deux trajectoires sont équivalentes quand elles sont les mêmes quitte à supprimer un nombre fini (possiblement différent) de points au début. Le \textbf{Bord de Poisson} de la marche est le quotient de $(G^{\Z_+},P)$ par l'enveloppe mesurable de cette relation d'équivalence.
\end{defi}

De façon équivalente, le bord de Poisson $B$ peut être défini comme le $\mu$-bord maximal, un $\mu$-bord étant un quotient de $P$ par une partition mesurable et invariante par rapport aux translations et par rapport aux multiplication par les éléments de $G$.

Pour une marche sur une groupe, une formule dite \textbf{formule de Poisson} donne un isomorphisme entre $L^\infty(B)$ et l'espace des fonctions $\mu$-harmoniques bornées sur le groupe. Une fonction est $\mu$-harmonique si pour tout $x$, $f(x)=\sum_g\mu(g)f(xg)$. Cela permet de définir le bord de Poisson aussi comme le spectre de l'algèbre de Banach que cet espace forme avec le produit approprié. Une autre réalisation abstraite du bord est en tant que l'espace des composantes ergodiques pour la translation. Voir aussi les survols par Erschler~\cite{Erschler2010}, Furman~\cite{FURMAN2002931}.

Si le bord de Poisson n'admet que des ensembles de mesure $0$ ou $1$, on dit qu'il est trivial. Quand le bord de la marche aléatoire induite sur un groupe $G$ par une mesure $\mu$ sur $G$ est trivial, on dit que $(G,\mu)$ est \textbf{Liouville}. Remarquons que la formule de Poisson dit qu'une mesure est Liouville si et seulement si les seules fonctions $\mu$-harmoniques bornées sur $G$ sont les fonctions constantes.

On a une définition similaire sur les graphes où on dit qu'un graphe $\Gamma$ vérifie la propriété de Liouville si les seules fonctions harmoniques bornées sur $\Gamma$ sont les fonctions constantes (pour un graphe de Cayley cela est équivalente au fait que la mesure de comptage normalisé sur $S\cup S^{-1}$ est Liouville). Cette propriété n'est pas stable par quasi-isométrie d'après un résultat de Lyons~\cite{lyons1987} : il décrit deux graphes quasi-isomorphes où l'un admet la propriété de Liouville et l'autre non. Benjamini~\cite{Benjamini1991} obtient de plus un exemple qui vérifie ces conditions et pour lequel les graphes sont de croissance polynomiale.

Pour une classe de mesures, on peut savoir si elles sont Liouville en utilisant l'entropie de la marche. L'entropie d'une mesure est défini par

$$H(\mu)=\sum_{g\in G}-\mu(g)\log{\mu(g)},$$
et celle de la marche associée (dite \textbf{entropie asymptotique}, voir Avez~\cite{avez72}) par

$$h(\mu)=\lim_{n\rightarrow\infty}\frac{H(\mu^{*n})}{n}.$$

On a $H(\mu*\lambda)\leq H(\mu)+H(\lambda)$ et donc si $H(\mu)$ est fini, cette limite existe et $h(\mu)$ est fini. Avez~\cite{Avez1976} obtient que si $h(\mu)=0$, alors la mesure est Liouville. Pour les mesures avec entropie fini, l'inverse est aussi vrai :

\begin{thm}[Critère d'entropie (Kaimanovich-Vershik~\cite{kaiver,kaimpoisson}, Derriennic~\cite{derast})]\label{entropy}
	Soit $G$ un groupe dénombrable et $\mu$ une mesure sur $G$ avec entropie finie. Alors $(G,\mu)$ est Liouville si et seulement si $h(\mu)=0$.
\end{thm}

Pour les mesures de premier moment fini, on peut relier l'entropie à la vitesse de fuite. Le premier moment d'une mesure est l'espérance de la longueur de mot $\sum_{g\in G}|g|\mu(g)$. Il dépende du choix d'ensemble générateur, mais sa finitude n'en dépend pas. La vitesse de fuite est $l_S(\mu)=\lim_{n\rightarrow\infty}\frac{L(n)}{n}$ où $L(n)=\sum_{g\in G}|g|\mu^{*n}(g)$ (et $S$ est un ensemble générateur). Il n'est pas difficile de voir que $h\leq\omega l$ (voir~\cite[Section~C]{AST_1980__74__47_0}), et donc si $l=0$, on a $h=0$. Pour les mesures symétriques, l'inverse est aussi vrai. Ceci est obtenu par Varopoulos~\cite{Varopoulos1985LongRE} pour les mesures de support fini, et par Karlsson et Ledrappier~\cite{Karlsson2007a} pour les mesures de premier moment fini.

\subsection{Liens avec la moyennabilité}\label{poisson}

Le bord de Poisson donne une autre critère de moyennabilité :

\begin{thm}\label{critent}
	Un groupe $G$ est moyennable si et seulement s'il existe un mesure Liouville $\mu$ non-dégénérée sur $G$.
\end{thm}

Le sens inverse est donné par Azencott~\cite{Azencott1970}, voir aussi Furstenberg~\cite{Furstenberg73} qui conjecture de plus le sens direct. Celui-ci est montré par Rosenblatt~\cite{rosenblatt} et Kaimanovich-Vershik~\cite{kaiver,kaimpoisson}.

Il vaut de noter qu'un groupe peut avoir certaines mesures qui sont Liouvilles et d'autres qui ne le sont pas. Kaimanovich et Vershik~\cite{kaimpoisson} montrent que les mesures non-dégénérés de support fini sur $\Z^d\wr\Z_2$ pour $d\geq3$ ne sont pas Liouville (et une mesure Liouville existe car le groupe est moyennable). Pour les mêmes groupes, Kaimanovich~\cite{Kai83} montre qu'il existe une mesure non-Liouville dont l'inverse est Liouville. Erschler~\cite{erschliouv} obtient que l'entropie asymptotique des mesures non-dégénérés sur une classe de groupes qui contient les groupes $\Z^d\wr\Z_2$ pour $d\geq3$ n'est jamais nulle. En particulier, toute mesure avec entropie finie n'est pas Liouville, et l'entropie de la mesure Liouville qui existe d'après le Théorème~\ref{critent} est infinie.

La théorème décrit la classe de groupes où il existe une mesure Liouville - les groupes moyennables. Parmi eux ils existent de plus des groupes où \textit{toute} mesure est Liouville. Ceci est obtenu pour les groupes abéliens par Blackwell~\cite{blackwell1955} (voir aussi~\cite{DoobSnellWilliamson},\cite{ChoquetDeny}), puis pour les groupes nilpotents~\cite{endsimple},\cite{Margulis1966}, et ensuite les groupes hyper-FC-centraux~\cite{LinZaidenberg},\cite{Jaworski2004}. Il vaut de noter qu'un groupe de type fini est hyper-FC-central si et seulement s'il est virtuellement nilpotent. Dans un résultat récent, Frisch, Hartman, Tamuz et Vahidi Ferdowsi~\cite{choquet-deny} montrent que toutes les mesures sur un groupe sont Liouville si et seulement si le groupe est hyper-FC-central. En particulier, sur tout groupe de croissance sur-polynomiale il existe une mesure non-Liouville. Cela était conjecturé pour les groupes de croissance exponentielle par Kaimanovich et Vershik~\cite{kaimpoisson}. Une description complète du bord de Poisson est donné dans \cite{ErschlerKaimanovich} pour une classe de mesures contenant les mesures non-Liouvilles présentées dans \cite{choquet-deny} (sur les groupes qui ne sont pas hyper-FC-centraux).

Dans~\citeme{hz} (voir Chapitre~\ref{hz}) on s'intéresse aux sous-groupes de $H(\Z)$ (voir Section~\ref{monodsection}). Il n'est pas connu si ce groupe est moyennable ou non, donc on ne sait pas s'il existe une mesure Liouville. On démontre que certaines classes de mesures sur des sous-groupes de $H(\Z)$ ne sont pas Liouville. Ces résultats sont inspirés par les travaux de Vaidim Kaimanovich sur le groupe de Thompson $F$ (comme on a mentionné, $H(\Z)$ contient $F$ comme sous-groupe).

\begin{defi}\label{defthomp}
	Le \textbf{groupe de Thompson $F$} est le groupe des homéomorphismes affines par morceaux de $[0,1]$ qui préservent l'orientation, avec un nombre fini de morceaux, dont les extrémités des morceaux sont dyadiques, et les pentes sont	des puissances de $2$.
\end{defi}

Il est de type fini, avec deux générateurs :

\begin{equation*}
%\begin{columns}
	\begin{minipage}{0.5\linewidth}
		\[A(t)=\begin{cases}\frac{t}{2} & 0\leq t\leq\frac{1}{2}\\
		t-\frac{1}{4} & \frac{1}{2}\leq t\leq\frac{3}{4}\\
		2t-1 & \frac{3}{4}\leq t\leq1\\
		\end{cases}\]
	\end{minipage}
	\begin{minipage}{0.5\linewidth}
		\[B(t)=\begin{cases}t & 0\leq t\leq\frac{1}{2}\\
		\frac{t}{2}+\frac{1}{4} & \frac{1}{2}\leq t\leq\frac{3}{4}\\
		t-\frac{1}{8} & \frac{3}{4}\leq t\leq\frac{7}{8}\\
		2t-1 & \frac{7}{8}\leq t\leq1\\
		\end{cases}\]
	\end{minipage}
%\end{columns}
\end{equation*}

C'est une question ouverte célèbre de savoir s'il est moyennable ou non. Vadim Kaimanovich~\cite{kaimanovichthompson} démontre que les mesures de support fini sur $F$ dont le support engendre $F$ comme semi-groupe sont non-Liouvilles. Dans~\citeme{hz} (voir Chapitre~\ref{hz}), on montre :

\begin{thm*}
	Pour tout sous-groupe de type fini $H$ de $H(\Z)$ qui n'est pas résoluble et toute mesure $\mu$ sur $H$ avec premier moment fini et dont le support engendre $H$ comme semi-groupe, $(H,\mu)$ n'est pas Liouville.
\end{thm*}

En considérant une généralisation de la notion de premier moment fini sur des sous-groupes de $H(\Z)$ qui ne sont pas de type fini, on obtient :

\begin{thm*}[Théorème~\ref{thmhz}]
	Pour tout sous-groupe de $H$ de $H(\Z)$ qui n'est pas localement résoluble et toute mesure $\mu$ sur $H$ avec espérance finie du nombre de fins de morceaux et dont le support engendre $H$ comme semi-groupe, $(H,\mu)$ n'est pas Liouville.
\end{thm*}

Il s'en suit que les mesures avec premier moment fini sur $F$, dont le support engendre $F$ comme semi-groupe, sont non-Liouville. Cela était soulevé comme question dans l'article de Kaimanovich~\cite[7.A]{kaimanovichthompson}. Pour les mesures de support fini qu'il considère, les configurations associées stabilisent (point par point) des que la marche transiente induite sur les nombres dyadiques sort d'un ensemble fini fixé. Pour les mesures de première moment fini, le valeur peut changer tout au long de la trajectoire, et on a du montrer (voir~\citeme[Lemma~7.2]{hz}; Chapitre~\ref{hz}) que l'espérance du nombre de changements est fini.

La condition de moyennabilité avec le bord de Poisson est nécessaire et suffisante, mais à mes connaissances, elle n'a pas été utilisée pour démontrer la non-moyennabilité d'un groupe. Dans l'autre direction par contre, elle a été utilisée pour montrer la moyennabilité d'un groupe. Bartholdi et Virág~\cite{Bartholdi2005} démontrent que le groupe de la Basilique (voir Section~\ref{autosim}) est moyennable en montrant que l'espérance de la distance à l'origine augmente de façon sous-linéaire; et puis en appliquant le critère de Kesten. Dans un article inspiré par leur méthode, Kaimanovich~\cite{Kaimanovich2005} démontre plus généralement que pour une classe de groupes auto-similaires (qui contient le groupe de la Basilique), pour certains mesures l'entropie asymptotique est zéro. Ils sont donc Liouvilles (voir Théorème~\ref{entropy}), et les groupes de cette classe sont moyennables.

\subsection{Graphes de Schreier}\label{schreierwalk}

On a aussi des résultats plus généraux sur les marches sur le graphe de Schreier de $F$ (voir Définition~\ref{defschreier}). On rappelle que la marche aléatoire est définie par le noyau $p(x,y)=\sum_{x.g=y}\mu(g)$. Il n'est pas difficile de voir que le bord de Poisson de cette marche est un quotient du bord de Poisson de la marche sur le groupe. En particulier, si le bord sur le graphe de Schreier est non-trivial, la mesure n'est pas Liouville.

Mishchenko~\cite{mischenko2015} développe une autre approche pour étudier le non-trivialité des bords de Poisson sur $F$. Il démontre que la marche aléatoire simple sur le graphe de Schreier que $F$ induit sur les nombres dyadiques a un bord de Poisson non-trivial. Kaimanovich~\cite[Section~6]{kaimanovichthompson} obtient ce résultat pour les mesures de support fini. Dans~\citeme{convend} (voir Chapitre~\ref{conved}) on prouve que le bord de Poisson de la marche induite sur le graphe de Schreier est non-trivial pour les mesures avec premier moment fini dont le support engendre $F$ comme semi-groupe. C'est une conséquence (d'un corollaire) du résultat suivant :

\begin{thm*}[Théorème~\ref{themschreier}]
	Considérons une action transitive d'un groupe $G$. Soit $S$ un ensemble générateur et $\Gamma$ le graphe de Schreier associé. Soit $\mu$ une mesure sur $G$ avec premier moment fini tel que la marche aléatoire induite sur $\Gamma$ est transiente. Alors elle converge presque surement vers un bout (aléatoire) du graphe.
\end{thm*}

Ce résultat était déjà connu dans le cas où l'action de $G$ sur $X$ est non-moyennable (voir Woess~\cite[Théorème~21.16]{woess2000random} - c'est un cas particulière de ce théorème), encore avec la condition de premier moment fini. La théorème cité est plus généralement vrai pour une marche aléatoire qui n'est pas nécessairement induite par une mesure sur un groupe. Elle suppose plutôt une marche uniformément irréductible, de premier moment uniforme, et avec $\rho<1$ (on rappelle le Critère de Kesten dans la Proposition~\ref{kesten}). Dans~\citeme{convend} (voir Chapitre~\ref{conved}), on montre aussi que le résultat n'est plus vrai si on ne suppose ni que la marche est induite par une mesure sur une groupe, ni $\rho<1$.

Il faut aussi mentionner que la transience est dans certains cas impliquée par les propriétés du graphe de Schreier. On utilise un lemme de comparaison de Baldi-Lohoué-Peyrière~\cite{var}.

\begin{lemma}[Lemme de comparaison]\label{var}
	Soit $P_1(x,y)$ et $P_2(x,y)$ des noyaux doublement stochastiques sur un ensemble dénombrable $X$ et supposons que $P_2$ est symétrique. Supposons qu'il existe $\varepsilon\geq 0$ tel que
	
	$$P_1(x,y)\geq\varepsilon P_2(x,y)$$
	pour tout $x,y$. Alors si $P_2$ est transient, $P_1$ l'est aussi.
\end{lemma}

Ici, doublement stochastique veut dire que les opérateurs sont inversibles et les inverses sont aussi Markov. De façon équivalente, ils préservent la mesure de comptage; le résultat est encore vrai dans un cas général où les opérateurs ont une autre mesure stationnaire commune, voir Kaimanovich~\cite[Section~3.C]{kaimanovichthompson}; voir aussi Woess~\cite[Sections~2.C~et~3.A]{woess2000random}. Pour les marches qu'on considère, il est direct de vérifier qu'ils sont doublement stochastiques.

Si on applique le lemme au Théorème~\ref{themschreier} on obtient :

\begin{cor*}[Corollaire~\ref{corschreier}]
	Considérons une action transitive d'un groupe $G$. Soit $S$ un ensemble générateur et $\Gamma$ le graphe de Schreier associé. Supposer que $\Gamma$ est transient. Alors pour tout mesure $\mu$ sur $G$ dont le support engendre $G$ en tant que semi groupe et qui a un premier moment fini, la marche aléatoire induite converge presque surement vers un bout du graphe.
\end{cor*}

On peut l'appliquer en particulier à l'action de $F$ sur les nombres dyadiques. La marche induite converge donc vers les bouts du graphe, et en utilisant l'auto-similarité du graphe il n'est pas difficile de voir qu'il ne peut pas converger avec probabilité $1$ vers un bout spécifique. Ce comportement non-trivial implique que son bord de Poisson n'est pas trivial. Sans la condition de premier moment fini par contre, il existe des mesures sur $F$ telles que la marche induite sur les nombre dyadiques a un bord trivial comme montré par Juschenko et Zheng~\cite{juszheng}. Juschenko~\cite{juscof} a aussi étudié les marches induites sur les ensembles de cardinal $n$ de nombres dyadiques, donnant une condition combinatoire pour le trivialité du bord de Poisson, et montrant qu'il existe une mesure avec un bord trivial pour $n=2$. Schneider et Thom~\cite[Corollary~6.2(3)]{Schneider2020} démontrent que pour une action fortement transitive $G\curvearrowright X$ (comme celle de $F$), pour tout $n$ il y a une mesure avec un bord trivial si et seulement si $F$ est moyennable en tant que sous-groupe topologique de $Sym(X)$. Avec cette topologie, $F$ est un sous-groupe de $Aut(\Z[\frac{1}{2}],\leq)$, qui est connu comme (extrêmement) moyennable d'après Pestov~\cite{pestov98}. On peut trouver une présentation plus détaillée de la moyennabilité extrême dans Kechris-Pestov-Todorcevic~\cite{Kechris2003}, où ils développent la théorie qui permet d'obtenir des groupes extrêmement moyennables d'après la théorie de Ramsey structurelle. En particulier, la moyennabilité extrême de $Aut(\Z[\frac{1}{2}],\leq)$ est équivalente~\cite[6(A)(iv)]{Kechris2003} à (une version généralisé du) théorème classique de Ramsey.

\subsection{Caractérisation complète des bords de Poisson}

Dans~\citeme{hz} (voir Chapitre~\ref{hz}) on démontre la non-trivialité du bord en décrivant un $\mu$-bord de configurations associées (comme Kaimanovich a fait dans~\cite{kaimanovichthompson}). Une question plus difficile serait d'obtenir une description complète du bord de Poisson. Kaimanovich~\cite{kaimanovichannals} a développé des critères géométriques pour montrer qu'un $\mu$-bord est le bord de Poisson pour des groupes avec des propriétés hyperboliques. Il décrit le bord des groupes hyperboliques, et aussi des sous-groupes discrets des groupes de Lie semi-simples et les groupes avec un nombre infini de bouts. Le «strip» critère de cet article a depuis été utilisé pour nombreuses descriptions complètes de bords de Poisson, comme les groupes de difféotopie (Kaimanovich et Masur~\cite{Kaimanovich1996}), $Out(F_N)$ (Horbez~\cite{10.1215/00127094-3166308}), produits en couronnes de groupes libres avec des groupes finis (Karlsson et Woess~\cite{Karlsson2007}), produits en couronnes $\Z^d\wr B$ où $B$ est fini (Erschler~\cite{erschler2011} pour $d\geq5$, Lyons et Peres~\cite{lyonsperes} pour $d\geq3$), groupes agissant sur des $\R$-arbres (Gautero et Mathéus~\cite{Gautero2012}), groupes d'automorphismes de complexes cubiques $CAT(0)$ (Nevo et Sageev~\cite{Nevo2013}), groupes fondamentaux de $3$-variétés fermées (Malyutin et Svetlov~\cite{malsvpoisson}).

\chapter{Non-triviality of the Poisson boundary of random walks on the group $H(\mathbb{Z})$ of Monod}\label{hz}
\includepdf[pagecommand={\thispagestyle{plain}},pages={-},noautoscale=true,offset=-25.5pt 0,scale=.8]{hz.pdf}
\chapter{Convergence Towards the End Space for Random Walks on Schreier Graphs}\label{conved}
First published in \textit{Journal of Theoretical Probability} (2021) by Springer Nature. Reproduced with permission from Springer Nature.
\includepdf[pagecommand={\thispagestyle{plain}},pages={-},noautoscale=true,offset=-25.5pt 0,scale=.8]{convend.pdf}
\chapter{Følner functions and sets on wreath products and Baumslag-Solitar groups}\label{lampl}
\includepdf[pagecommand={\thispagestyle{plain}},pages={-},noautoscale=true,offset=-25.5pt 0,scale=.8]{lampl.pdf}

\bibliographystyle{alphaurl}
\bibliographystyleme{unsrturl}
\bibliographyme{../auto,../manual}
\addcontentsline{toc}{chapter}{Bibliographie}
\bibliography{../auto,../manual}

\end{document}


