\documentclass[11pt]{article}
\input{/Users/nicolascurien/Dropbox/Macros-bibli/macros-english2}
\newcommand{\pp}{\ensuremath{\sqsubset}}
\newcommand{\ppld}{\ensuremath{\sqsubset_{LD}}}
\newcommand{\rev}{\ensuremath{\textrm{\textup{rev}}}}
\newtheorem{exo}{Exercise}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{prperty}[theorem]{Property}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{exe}[theorem]{Example}
\newtheorem{open}{Open Question}
\newcommand{\rf}{\ensuremath{\mathfrak{R}}}
\newcommand{\m}{\mathcal{M}}
\newcommand{\T}{\mathcal{T}}
\renewcommand{\P}[1]{\mathbb{P}\left[#1\right]}
\newtheorem{rek}[theorem]{Remark}
\renewcommand{\sh}{\ensuremath{\textrm{\textup{sh}}}}
\renewcommand{\rg}{\ensuremath{\cyclearrowright}}
\usepackage{enumerate}
\def\llbracket{[\hspace{-.10em} [ }
\newcommand{\e}{\mbox{e}\hspace{-.34em}\mbox{\i}}
\renewcommand{\e}{\mathfrak{e}}
\def\rrbracket{ ] \hspace{-.10em}]}
\usepackage{amsmath}
%\usepackage{palatino}
\title{Metric Geometry}
\date{}
\author{}
\begin{document}
%\maketitle
\setcounter{section}{4}
\section{Schaeffer's Bijection}
\begin{exo} The goal of this exercise is to introduce the reverse construction of the Schaeffer bijection. In the following $Q$ is a finite quadrangulation with $n$ faces with a distinguished oriented edge $\overrightarrow{e}$ with endpoints $e_{-}$ and $e_{+}$. We denote the graph distance in $Q$ by $\op{d}_{\op{gr}}$.
\begin{enumerate}
\item Show that $Q$ is bipartite: if $u$ and $v$ are two neighboring vertices then $$\big|\op{d}_{\op{gr}}(e_{-},u) - \op{d}_{\op{gr}}(e_{-},v)\big| =1.$$
\end{enumerate}
Hence the faces of the quadrangulation $Q$ can be decomposed into two subsets: The faces $\mathrm{f}$ such that the distance to $e_{-}$ of the vertices of $\mathrm{f}$ are $(i,i+1,i+2,i+1)$ or $(i,i+1,i,i+1)$. We add a ``red'' edge in each face following the rule given by the figure below.
\begin{figure}[h]
\begin{center} 
\includegraphics[height=3cm]{schaeffer} \end{center}
\end{figure}
\begin{enumerate}
\setcounter{enumi}{1}
\item Apply this construction to this quadrangulation.\footnote{For the connoisseurs this is Le Gall's map.}

\begin{figure}[h] 
\begin{center} 
\includegraphics[height=5cm]{legallmap}
 \end{center} \end{figure}
\end{enumerate} 
We denote $\mathfrak{T}$ the graph formed by the red edges and the vertices of $Q$ they span. We aim at proving that $\mathfrak{T}$ is a tree that spans $V \backslash\{e_-\}$.
\begin{enumerate} 
\setcounter{enumi}{2}
\item Show that $e_{-}$  is not a vertex of $\mathfrak{T}$.
\item Using Euler's formula, show that it suffices to prove that $\mathfrak{T}$ has no cycle.
\item Suppose that we can form a simple cycle $\mathcal{C}$ with the red edges. Pick a vertex $u$ of this cycle whose distance to $e_{-}$ is minimal among the vertices of the cycle. Show that we can find two vertices $v$ and $v'$ which are separated by $\mathcal{C}$ and such that 
$$ \op{d}_{\op{gr}}(e_{-},v)=\op{d}_{\op{gr}}(e_{-},v')= \op{d}_{\op{gr}}(e_{-},u)-1.$$
\item Find a contradiction.
\end{enumerate}
\end{exo}

\begin{exo}[Re-rooting] Let $\mathcal{Q}_{n}^{*}$ be the set of all rooted quadrangulations with $n$ faces and an extra oriented edge $\overrightarrow{e}$. If $(q,\overrightarrow{e}) \in\mathcal{Q}_{n}^{*}$ we put $\mathfrak{R}(q,\overrightarrow{e})$ for the map $q$ but re-rooted at $\overrightarrow{e}$. \begin{enumerate} 
\item Show that the image of the uniform distribution on $\mathcal{Q}_{n}^{*}$ by $\mathfrak{R}$ is the uniform distribution over the set of rooted quadrangulations with $n$ faces.
\end{enumerate}
Let $Q_{n}$ be a uniform rooted quadrangulation with $n$ faces. Conditionally on $Q_{n}$, let $(X_{n})_{n \geq 0}$ be a simple random walk on $Q_{n}$ starting from the end point of the root-edge of $Q_{n}$ and denote $(\overrightarrow{E}_{1}, \overrightarrow{E}_{2}, ... )$ the oriented edges traversed by the walk.
\begin{enumerate}
\setcounter{enumi}{1}
\item  Prove that for every $k \geq 1$, $\mathfrak{R}(Q_{n}, \overrightarrow{E}_{k})  = Q_{n}$,  in distribution.
\end{enumerate}
\end{exo}
\begin{exo}Who are these charming gentlemen ?
\begin{figure}[h] 
\begin{center} 
\includegraphics[height=5cm]{schaefferg}
\includegraphics[height=5cm]{cori}
 \end{center} 
 \end{figure}
\end{exo} 
\nocite{Sch98}
\nocite{CV81}
\nocite{BDFG04}
\bibliographystyle{alpha}
\bibliography{/Users/nicolascurien/Dropbox/Macros-Bibli/bibli}

\end{document}