\documentclass[final]{FPSAC2023}
\articlenumber{30}

\newtheorem{thm}{Theorem}%[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{corollary}[thm]{Corollary}

%our packages
%\usepackage{cite} % order the cites, not compatible with biber (but we don't use biber in this submission)
\usepackage{tablefootnote} %https://tex.stackexchange.com/questions/109467/footnote-in-tabular-environment
%\usepackage[normalem]{ulem}  
\definecolor{darkgreen}{rgb}{0,0.4,0}
\definecolor{green}{rgb}{0,0.4,0}
\definecolor{BrickRed}{rgb}{0.65,0.08,0}
\usepackage{tikz}
\usetikzlibrary {arrows.meta}
\usepackage{mathtools}
\usepackage{bm} %Access bold symbols in maths mode \mathsf

%our macros
\newcommand{\oeis}[1]{\text{\href{https://oeis.org/#1}{{\small \tt #1}}}} 
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\sN}{\uparrow}
\newcommand{\sNE}{\nearrow}
\newcommand{\sE}{\rightarrow}
\newcommand{\sSE}{\searrow}
\newcommand{\sS}{\downarrow}
\newcommand{\sSW}{\swarrow}
\newcommand{\sW}{\leftarrow}
\newcommand{\sNW}{\nwarrow}
\makeatletter
\newcommand\newref[1]{#1\def\@currentlabel{#1}}
\makeatother

%MACROS FOR PATTERNS
\newlength{\MCR}\setlength{\MCR}{3pt} % circle radius
\newlength{\MLW}\setlength{\MLW}{1pt} % line width
\newlength{\MSB}\setlength{\MSB}{-4pt} % skip before
\newlength{\MSA}\setlength{\MSA}{2pt} % skip after
\def\MAL{4.5pt} % arrow length
\newlength{\MR}\setlength{\MR}{-2.5pt} % raisebox

\newcommand{\pWW}{
		\raisebox{1pt}
		{\hspace{\MSB}
		\begin{tikzpicture}[scale = 0.35]
 \draw [fill] (2,0) circle (\MCR);
 \draw [fill] (1,0) circle (\MCR);
 \draw[line width=\MLW, line cap = round, -] (2, 0) to (1, 0);
 \draw[line width=\MLW, line cap = round, ->, arrows={-Latex[length=\MAL]}] (1, 0) to (-0.2, 0);
		\end{tikzpicture}\hspace{\MSA}}}

\newcommand{\pWNE}{
		\raisebox{\MR}
		{\hspace{\MSB}
		\begin{tikzpicture}[scale = 0.35]
 \draw [fill] (1,0) circle (\MCR);
 \draw [fill] (0,0) circle (\MCR);
 \draw[line width=\MLW, line cap = round, -] (1, 0) to (0, 0);
 \draw[line width=\MLW, line cap = round, ->, arrows={-Latex[length=\MAL]}] (0, 0) to (1.15, 1.15);
		\end{tikzpicture}\hspace{\MSA}}}

\newcommand{\pNEW}{
		\raisebox{\MR}
		{\hspace{\MSB}
		\begin{tikzpicture}[scale = 0.35]
 \draw [fill] (0,0) circle (\MCR);
 \draw [fill] (1,1) circle (\MCR);
 \draw[line width=\MLW, line cap = round, -] (0, 0) to (1, 1);
 \draw[line width=\MLW, line cap = round, ->, arrows={-Latex[length=\MAL]}] (1, 1) to (-0.2, 1);
		\end{tikzpicture}\hspace{\MSA}}}

\newcommand{\pNES}{
		\raisebox{\MR}
		{\hspace{\MSB}
		\begin{tikzpicture}[scale = 0.35]
 \draw [fill] (0,0) circle (\MCR);
 \draw [fill] (1,1) circle (\MCR);
 \draw[line width=\MLW, line cap = round, -] (0, 0) to (1, 1);
 \draw[line width=\MLW, line cap = round, ->, arrows={-Latex[length=\MAL]}] (1, 1) to (1, -0.2);
		\end{tikzpicture}\hspace{\MSA}}}

\newcommand{\pNENE}{
		\raisebox{\MR}
		{\hspace{\MSB}
		\begin{tikzpicture}[scale = 0.25]
 \draw [fill] (0,0) circle (5pt);
 \draw [fill] (1,1) circle (5pt);
 \draw[line width=\MLW, line cap = round, -] (0, 0) to (1, 1);
 \draw[line width=\MLW, line cap = round, ->, arrows={-Latex[length=\MAL]}] (1, 1) to (2.2, 2.2);
		\end{tikzpicture}\hspace{\MSA}}}

\newcommand{\pNENEx}{
		\raisebox{\MR}
		{\hspace{\MSB}
		\begin{tikzpicture}[scale = 0.238]
 \draw [fill] (0,0) circle (5pt);
 \draw [fill] (1,1) circle (5pt);
 \draw[line width=\MLW, line cap = round, -] (0, 0) to (1, 1);
 \draw[line width=\MLW, line cap = round, ->, arrows={-Latex[length=\MAL]}] (1, 1) to (2.2, 2.2);
		\end{tikzpicture}\hspace{\MSA}}}

\newcommand{\pSW}{
		\raisebox{\MR}
		{\hspace{\MSB}
		\begin{tikzpicture}[scale = 0.35]
 \draw [fill] (1,1) circle (\MCR);
 \draw [fill] (1,0) circle (\MCR);
 \draw[line width=\MLW, line cap = round, -] (1, 1) to (1, 0);
 \draw[line width=\MLW, line cap = round, ->, arrows={-Latex[length=\MAL]}] (1, 0) to (-0.2, 0);
		\end{tikzpicture}\hspace{\MSA}}}

\newcommand{\pWS}{
		\raisebox{\MR}
		{\hspace{\MSB}
		\begin{tikzpicture}[scale = 0.35]
 \draw [fill] (1,1) circle (\MCR);
 \draw [fill] (0,1) circle (\MCR);
 \draw[line width=\MLW, line cap = round, -] (1, 1) to (0, 1);
 \draw[line width=\MLW, line cap = round, ->, arrows={-Latex[length=\MAL]}] (0, 1) to (0, -0.2);
		\end{tikzpicture}\hspace{\MSA}}}

\newcommand{\pWWNE}{
		\raisebox{\MR}
		{\hspace{\MSB}
		\begin{tikzpicture}[scale = 0.35]
 \draw [fill] (2,0) circle (\MCR);
 \draw [fill] (1,0) circle (\MCR);
 \draw [fill] (0,0) circle (\MCR);
 \draw[line width=\MLW, line cap = round, -] (2, 0) to (1, 0);
 \draw[line width=\MLW, line cap = round, -] (1, 0) to (0, 0);
 \draw[line width=\MLW, line cap = round, ->, arrows={-Latex[length=\MAL]}] (0, 0) to (1.2, 1.2);
		\end{tikzpicture}\hspace{\MSA}}}

\pdfstringdefDisableCommands{
  \def\\{}
  \def\texttt#1{<#1>}
}

\title[From Kreweras to Gessel: A walk through patterns in the quarter plane]{From Kreweras to Gessel:\\ A walk through patterns in the quarter plane}

\author[A.~Asinowski, C.~Banderier, \texorpdfstring{\and}{} S.J.~Selkirk]{Andrei Asinowski\texorpdfstring{\thanks{\protect\href{https://me.aau.at/\string~anasinowski/}{https://me.aau.at/\textasciitilde anasinowski/}. Partially supported by the FWF project P32731.}\addressmark{1}}{}, 
Cyril Banderier\texorpdfstring{\thanks{\protect\href{https://lipn.fr/\string~banderier/}{https://lipn.fr/\textasciitilde banderier/}. Partially supported by the PHC Amadeus project 48736QG.}\addressmark{2}}{}, 
\and Sarah J.~Selkirk\texorpdfstring{\thanks{\protect\href{https://www.math.aau.at/selkirk/}{https://www.math.aau.at/selkirk/}. Supported by the FWF project DOC78.}\addressmark{1}}{}}

\address{\addressmark{1}Institut f\"ur Mathematik, Alpen-Adria-Uni\-ver\-si\-t\"at Klagenfurt, Klagenfurt, Austria \\ \addressmark{2}Laboratoire d'Informatique de Paris Nord, Universit\'{e} Sorbonne Paris Nord, France}

\received{\today}
%\revised{}

\abstract{We initiate a study of pattern avoidance in quarter-plane lattice walks.
First we demonstrate surprising links between Kreweras excursions (avoiding a pattern of length~$2$)
and some famous lattice walk models, such as Gessel, Gouyou-Beauchamps, and P\'olya excursions.
Next we explore the nature (algebraic, hypergeometric, D-finite) of the corresponding generating functions.
In particular, we show that pattern avoidance does not necessarily preserve algebraicity or D-finiteness.}

\keywords{lattice walks, pattern avoidance, bijections, generating functions} 

\usepackage[backend=bibtex]{biblatex} % cannot set alphabetic style...
\addbibresource{kreweras.bib}

\begin{document}
\maketitle

\section{Introduction}

In this paper we study pattern avoidance in quarter-plane lattice walks.
A \textit{lattice walk} is a word $w$ over a \textit{stepset} --- an alphabet $\mathcal{S}$,
whose elements (\textit{steps}) are interpreted as vectors in the plane, and then $w$ is visualized as these vectors 
concatenated to each other to form a polygonal line. A pattern in this context is a fixed word $p$,
and we deal with enumeration of walks that avoid $p$ (that is, $p$ is not a consecutive subsequence of $w$).

The case of \textit{directed walks} (the models where all the steps have a positive $x$-coordinate)
which avoid a given pattern was studied in~\cite{AsinowskiBacherBanderierGittenberger2020}. 
Therein, the vectorial kernel method was developed in order to obtain an explicit expression of the corresponding generating functions,
which are systematically algebraic.

In this work, we initiate the study of pattern avoidance for walks in the quarter plane~$\N^2$. 
We use the term \textit{excursion} to indicate a walk in $\N^2$ that starts and ends at~$(0, 0)$, 
and the term \textit{meander} to indicate a walk in~$\N^2$ that starts at~$(0, 0)$ and ends anywhere in the quarter plane. 
As a first step, in this article we focus on some combinatorial surprises which then occur.
Firstly, we show that some models of pattern-avoiding \textit{Kreweras excursions}
are in bijection with some famous walk models which do not involve any pattern avoidance.
Secondly, we comment on the nature of the corresponding generating functions 
and prove some cases of (non)-algebraicity or D-finiteness.
\newpage

\section{\texorpdfstring{Historical background: Kreweras, Gessel, P\'olya, and\\ Gouyou-Beauchamps models}
{Historical background: Kreweras, Gessel, P\'olya, and Gouyou-Beauchamps models}}\label{sec:history}
\vspace{-1mm}

We briefly survey the history of five noteworthy models
which will play a r{\^o}le in the next section for our study of patterns in lattice walks.
Each model is characterized by its allowed steps;
for example, the stepset of Kreweras' model is $\mathcal S=\{\sS, \sW, \sNE \}$ (see \cref{Fig1}).
\vspace{-1.5mm}

\begin{figure}[h!] 
 \centering
 \begin{tabular}{|c|c|c|c|c|}
 \hline
			\raisebox{-4pt}{ 
 \begin{tikzpicture}[scale = 0.4]
 \node(O) at (0, 0){};
 \node(E) at (1, 0){};
 \node(SE) at (1, -1){};
 \node(S) at (0, -1){};
 \node(SW) at (-1, -1){};
 \node(W) at (-1, 0){};
 \node(NW) at (-1, 1){};
 \node(N) at (0, 1){};
 \node(NE) at (1, 1){};
 \draw[help lines] (-1, -1) grid (1, 1);
				\draw [blue, fill] (0,0) circle (3pt);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (NE.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (S.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (W.center);
 \end{tikzpicture}}&
			\raisebox{-4pt}{
 \begin{tikzpicture}[scale = 0.4]
 \node(O) at (0, 0){};
 \node(E) at (1, 0){};
 \node(SE) at (1, -1){};
 \node(S) at (0, -1){};
 \node(SW) at (-1, -1){};
 \node(W) at (-1, 0){};
 \node(NW) at (-1, 1){};
 \node(N) at (0, 1){};
 \node(NE) at (1, 1){};
 \draw[help lines] (-1, -1) grid (1, 1);
				\draw [blue, fill] (0,0) circle (3pt);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (NE.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (N.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (S.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (SW.center);
 \end{tikzpicture}}&
			\raisebox{-4pt}{
			\begin{tikzpicture}[scale = 0.4]
 \node(O) at (0, 0){};
 \node(E) at (1, 0){};
 \node(SE) at (1, -1){};
 \node(S) at (0, -1){};
 \node(SW) at (-1, -1){};
 \node(W) at (-1, 0){};
 \node(NW) at (-1, 1){};
 \node(N) at (0, 1){};
 \node(NE) at (1, 1){};
				\draw[help lines] (-1, -1) grid (1, 1);
				\draw [blue, fill] (0,0) circle (3pt);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (N.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (S.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (E.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (W.center);
 \end{tikzpicture}}&
			\raisebox{-4pt}{
			\begin{tikzpicture}[scale = 0.4]
 \node(O) at (0, 0){};
 \node(E) at (1, 0){};
 \node(SE) at (1, -1){};
 \node(S) at (0, -1){};
 \node(SW) at (-1, -1){};
 \node(W) at (-1, 0){};
 \node(NW) at (-1, 1){};
 \node(N) at (0, 1){};
 \node(NE) at (1, 1){};
				\draw[help lines] (-1, -1) grid (1, 1);
				\draw [blue, fill] (0,0) circle (3pt);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (NW.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (SE.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (W.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (E.center);
 \end{tikzpicture}}&
			\raisebox{-4pt}{
 \begin{tikzpicture}[scale = 0.4]
 \node(O) at (0, 0){};
 \node(E) at (1, 0){};
 \node(SE) at (1, -1){};
 \node(S) at (0, -1){};
 \node(SW) at (-1, -1){};
 \node(W) at (-1, 0){};
 \node(NW) at (-1, 1){};
 \node(N) at (0, 1){};
 \node(NE) at (1, 1){};
				\draw[help lines] (-1, -1) grid (1, 1);
				\draw [blue, fill] (0,0) circle (3pt);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (NW.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (SE.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (SW.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (NE.center);
 \end{tikzpicture}}
 \\
 \hline
 \hspace{3mm} Kreweras \hspace{3mm} & \hspace{5mm} Gessel \hspace{5mm} & \hspace{5mm} P\'{o}lya \hspace{5mm} & Gouyou-Beauchamps & \hspace{3mm} Diagonal\hspace{2mm} \phantom{.}\\
 \hline
 \end{tabular}
\setlength\belowcaptionskip{-2mm}
\caption{The stepsets of five important models of lattice walks.}\label{Fig1}
\end{figure}
\vspace{-7mm}

\subsection{Kreweras walks}\label{sec:history:k}
\vspace{-1mm}

In his PhD thesis~\cite{Kreweras1965}, Kreweras
tackled the question of the enumeration of variants of solid partitions (initially studied by MacMahon in~\cite{MacMahon1915}),
and of other combinatorial structures (like Young tableaux) related to natural posets.
%He obtained the enumeration of maximal chains in these posets.
He applied this to the \textit{$m$-candidate ballot problem}: 
the number of ways that $n$ people can vote for candidates ${\mathcal C}_1, \dots, {\mathcal C}_m$\linebreak such 
that ${\mathcal C}_1$ remains in the lead (or tied) with respect to the other candidates during the ballot process. 
For 3 candidates, any such process corresponds to a Kreweras meander. 
If~${\mathcal C}_1$ remained in the lead but ties with all other candidates at the end, this corresponds to a Kreweras excursion
of length~$3n$.
They are counted (applying~\cite[Section~3.2]{Kreweras1965}) by 
\begin{equation}\label{eq:kreweras-gen-func}
 e_{3n} = \frac{4^n}{(2n+1)(n+1)}\binom{3n}{n}. 
\end{equation} % see also : https://oeis.org/A005118/a005118.pdf

This is the sequence \oeis{A006335} in the On-Line Encyclopedia of Integer Sequences (OEIS).
Kreweras proved~\eqref{eq:kreweras-gen-func} by a guess-and-prove approach, which was then simplified in collaboration with Niederhausen 
using hypergeometric identities~\cite{KrewerasNiederhausen1981, Niederhausen1983}. 
Gessel later proved~\eqref{eq:kreweras-gen-func} in~\cite{Gessel1986} with 
a probabilistic approach, rephrasing the problem in terms of walks in $\N^2$. 
For other stepsets deeper mathematical tools are required.
In fact, these more general walk models correspond to the evolution of two queues in parallel,
and probabilists were interested in the stationary distribution of the corresponding infinite Markov chain.
To this aim, they solved these models with the machinery of boundary-value problems and Riemann surfaces (see e.g.~\cite{FayolleIasnogorodskiMalyshev1999}).
 For Kreweras walks, Flatto and Hahn~\cite{FlattoHahn1984} %even 
proved that the 
generating function of this stationary distribution is algebraic. This method was revisited combinatorially by 
Bousquet-M\'{e}lou in~\cite{BousquetMelou2005}, and later with Mishna in~\cite{BousquetMelouMishna2010}, where 
they performed a classification of almost all models of walks with small steps as algebraic, D-finite, etc. 
(the classification was completed since).

%Furthermore, Kreweras walks attracted significant attention because they have the same enumeration as other combinatorial objects such as permutations relating 
%to stack-sorting~\cite{West} and planar maps~\cite{Guibert}. 
The algebraicity of Kreweras walks can also be established via a bijection with 
planar maps (see Bernardi~\cite{Bernardi2007:Kreweras}), but many combinatorialists 
still hope for an even simpler proof, e.g.~based on a link with the inherent algebraicity of tree-like structures 
(see~\cite{BanderierDrmota15,BousquetMelou06,HopkinsRubey2022}). %RubeyHopkins is here due to lack of space to comment more on it.
 
%The algebraicity of the Kreweras model is somehow frustrating for combinatorialists,
%one would like to have a more structural explanation of this miracle
%(see~\cite{mbm,BanderierDrmota2015}
%Owing to these developments, Kreweras walks played a central r{\^o}le in developing the theory of lattice paths in the quarter plane.

\subsection{Gessel walks}\label{sec:history:g}
\vspace{-1mm}
% In 2003, at the meeting \textit{Discrete Random Walks} at IHP in Paris, Ira Gessel puzzled the audience with an experimental discovery which he did in 2001: 
In 2001, Ira Gessel conjectured that, for the stepset $\{\sE, \sW, \sNE, \sSW \}$, the number $e_n$ of excursions of length $n$ is hypergeometric
(and given by the OEIS sequence~\oeis{A135404}):%
\bgroup
\setlength\abovedisplayskip{2mm}
\setlength\belowdisplayskip{2mm}
\begin{equation}e_{2n}=\frac{4^{2n} (1/2)_n (5/6)_n}{(2)_n (5/3)_n}, \text{ where $ (a)_m:=a (a+1) \cdots (a+m-1)$}.
\label{exc_gessel}\end{equation} 
\noindent This startling conjecture motivated the name ``Gessel walks'' since attached to this model.
%In Bousquet-M\'{e}lou and Mishna's thorough classification 
 % of the types of generating functions of all walks in the quarter plane with small steps~\cite{BousquetMelouMishna2010}, Gessel 
 %walks were the only holonomic type of walk (of 23) which could not be proven to be holonomic using the methods described in the paper.
 
 The hypergeometricity of Gessel excursions was first proven by Kauers, Koutschan, and Zeilberger in~\cite{KauersKoutschanZeilberger2009} using 
 computer algebra techniques. Later, Bostan and Kauers~\cite{BostanKauers2010} proved that the trivariate generating function (length, final location) is algebraic. 
These two proofs are nice examples of the ``guess and prove'' art via computer algebra.\linebreak
Puzzled by a discrepancy between the simplicity of the excursion formula~\eqref{exc_gessel} and the 
enormous size of algebraic equations required for its proof,
several authors looked for a more ``human'' approach.
Bostan, Kurkova, and Raschel~\cite{BostanKurkovaRaschel2017} found such a proof using\linebreak complex analysis, and Bousquet-M\'{e}lou~\cite{BousquetMelou2016} 
found another proof using generating function manipulations.~It~still~remains~a~challenge~to~find~an~elementary~combinatorial~proof.

\subsection{P\'olya walks and diagonal walks}\label{sec:history:p}
\vspace{-1mm}
\textit{P\'olya's drunkard problem} asks for the return probability of a random walk on the 
$\Z^2$ lattice (with equiprobable steps $\sS$, $\sN$, $\sE$, and $\sW$). This probability tends to 1 (as proven by P\'olya~\cite{Polya21}). %Polya19
A natural question is which conditions on walks in~$\N^2$ imply this property.
This is answered in~\cite{FayolleMalyshevMenshikov92}, where conditions for (null-)recurrence are given.

 P\'{o}lya walks in~$\N^2$ % (also sometimes called ``simple walks'') 
were also studied by Guy, Krattenthaler, and Sagan~\cite{GuyKrattenthalerSagan1992}, 
who gave bijective proofs for the number of walks between any 
two points. In particular, the number of P\'olya excursions in~$\N^2$ of length~$2n$ is given by the OEIS sequence~\oeis{A005568}: 
\begin{equation} 
 e_{2n}=C_n C_{n+1},\label{exc_polya}
\end{equation} %Shuffle + chu-vandermonde?
where $C_n$ is the $n$-th Catalan number.
These walks have connections to planar maps and shuffles of parenthesis systems,
 as studied by Cori, Dulucq, and Viennot in~\cite{CoriDulucqViennot1986}.
The diagonal walks (see \cref{Fig1}) are even simpler to enumerate:
 $e_{2n}=C_n^2$ ({\small OEIS} \oeis{A001246}). %~\cite{Polya19,Polya21}

\subsection{Gouyou-Beauchamps walks}\label{sec:history:gb}
\vspace{-1mm}
 In~\cite{GouyouBeauchamps86} Gouyou-Beauchamps studied P\'{o}lya walks in the quarter plane which stay weakly below the line $y = x$, leading to what is 
 now known as Gouyou-Beauchamps walks. %, to obtain formulas for the number of Young tableaux of height $\leq 5$~\cite{GouyouBeauchamps89}. 
Gouyou-Beauchamps excursions in~$\N^2$ are counted by the OEIS sequence~\oeis{A005700}:
\begin{equation} e_{2n}=C_n C_{n+2}-C_{n+1}^2.\label{exc_gouyou} \end{equation} 
\egroup
Gouyou-Beauchamps walks of length $2n$ ending on the $x$-axis 
are in bijection with P\'olya excursions of length $2n$,
and with Young tableaux of size $2n$ and height $\leq 4$~\cite{GouyouBeauchamps89}.

\section{Pattern avoidance in Kreweras excursions: bijections}\label{sec:bijections}
In this section, we consider avoidance of patterns of length~2 in Kreweras walks.
Recall that we deal with consecutive patterns, and note that several occurrences of a pattern can overlap
(e.g., the word $\mathsf{ABBBABABB}$ has precisely three occurrences of the pattern~$\mathsf{BB}$).

Due to the symmetry of the Kreweras stepset with respect to the diagonal $y=x$, 
there are just five patterns of length~2 that yield non-equivalent pattern-avoiding walk models.
We show that the corresponding
pattern-avoiding \textit{excursion} models exhibit 
surprising links to the well-known models mentioned in \cref{sec:history}: 
Gessel, Gouyou-Beauchamps, P\'{o}lya, and diagonal excursions.
These pattern-avoiding Kreweras excursion models are listed in \cref{table:patterns-length-2}, 
along with their respective enumerating sequences,
their OEIS entries, and equinumerous quarter-plane excursion models without any forbidden patterns.

\renewcommand{\arraystretch}{1.15}
\begin{table}[ht]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{|c|c|l|c|l|c|}
\hline
&
\textbf{Pattern~$p$}
& 
\begin{tabular}{c}
\textbf{\# \{Kreweras excursions} \\ \textbf{of length $3n$ avoiding $p$\}} 
\end{tabular}
&
\textbf{OEIS} 
&
\textbf{In bijection with}
&
\hspace{-4mm} \begin{tabular}{c} \textbf{Proven}\\ \textbf{in} \end{tabular}
\\ \hline
\newref{1}\label{entry:WW} & \pWW\
& 1, 2, 11, 85, 782, 8004, \ldots & \oeis{A135404} & Gessel excursions & Thm.~\ref{thm:WW-gessel}
\\ \hline
\newref{2}\label{entry:WNE} & \pWNE\
& 1, 2, 11, 85, 782, 8004, \ldots & \oeis{A135404} & Gessel excursions & Prop.~\ref{prop:WNE-Gessel}
\\ \hline
\newref{3}\label{entry:NES} & \pNEW\ 
& 1, 1, 5, 37, 332, 3343, \ldots & None & \hspace{-2mm}\begin{tabular}{l}Gessel excursions\\ ending with $\sS$\end{tabular}& Cor.~\ref{cor:NEW-gessel}
\\ \hline
\newref{4}\label{entry:NENE} & \pNENE\
& 1, 2, 10, 70, 588, 5544, \ldots & \oeis{A005568}~\tablefootnote{\label{fn:gb}It is \textit{footnoteworthy} that 
\oeis{A005568} (resp.~\oeis{A001246}) also enumerates Gouyou-Beauchamps walks of even (resp. odd) length ending on the $y$-axis, 
%yes, $Y$ axis here, not like in section 2.4.
and Young tableaux of height $\leq 4$ of even (resp.~odd) size; see~\cite{GouyouBeauchamps89}.} & P\'{o}lya excursions & Prop.~\ref{prop:NENE-Polya}
\\ \hline 
\newref{5}\label{entry:SW} & \pSW\
& 1, 1, 4, 25, 196, 1764, \ldots & \oeis{A001246}~\footref{fn:gb}& Diagonal excursions & Thm.~\ref{thm:gouyou-beauchamps}
\\ \hline
\end{tabular}
}
\setlength\belowcaptionskip{-5mm}%
\caption{Summary of results concerning quarter-plane models in bijection with pattern-avoiding Kreweras excursions.
Models 1, 2, and 3 are algebraic, while models 4 and 5 are D-finite, but not algebraic (see \cref{Sec4}).
}
\label{table:patterns-length-2}
\end{table}
\renewcommand{\arraystretch}{1}

Most notably, the first two entries of \cref{table:patterns-length-2} relate pattern-avoiding Kreweras excursions to Gessel excursions.
In particular, one deduces that the patterns $\pWW$ and $\pWNE$ are equidistributed among Kreweras excursions.
In the following theorem, we prove a stronger result about the \textit{joint} statistics of these two patterns.

%Note that we take care of possible overlaps: we count one occurrence of the pattern~$\pWW$to be $\sW$ followed by another $\sW$. 
%For example, a sequence of $k$ many $\sW$ steps has $k - 1$ occurrences of the pattern~$\sW\, \sW$.

\begin{thm}%[Equidistribution of the statistics $\pWW$and $\pWNE$] 
\label{thm:SS-SNE-involution}
The number of Kreweras excursions of length $3n$ with
$k$~occurrences of $\pWW$and $\ell$~occurrences of $\pWNE$ 
is equal to the number of Kreweras excursions of length $3n$ with
$\ell$~occurrences of~$\pWW$and $k$~occurrences of~$\pWNE$.
\end{thm}
\begin{proof}

We provide an autobijection on the set of Kreweras excursions of length $3n$ 
that switches the occurrences of the patterns $\pWW$and $\pWNE$.
In this bijection, the patterns can be independently considered despite the possible overlap of a $\sW$ step in both patterns. 

	Let $w$ be a Kreweras excursion with
	$k$~occurrences of the pattern~$\pWW$ and $\ell$~occurrences of the pattern~$\pWNE$.
 We mark each $\sW$ which is followed by a $\sW$, and separately each $\sNE$ which is preceded by a $\sW$. 
 Note that any $\sW$ step followed by a $\sNE$ step \textit{and} preceded by a $\sW$ step 
	(that is, any $\sW$ step being at the overlap of the two patterns) is never marked. 
 	
	We define the \textit{index} of a step 	to be its ordinal number, from $1$ to $n$, 
	\textit{among the steps of the same kind}, in the order as they occur in the excursion. 
 
 \begin{enumerate}[itemsep=.8mm,topsep=.8mm]
 \item \label{bij:SS-SNE} 
		Let $a_1, a_2, \ldots, a_k$ be the indices of the \textit{marked} $\sW$ steps, in the order as they occur in~$w$. 
%
		For each $i=1, 2, \ldots, k$, in this order, we remove the $\sW$ step with the index~$a_i$, 
 and insert it immediately before the $\sNE$ step with the index $a_i+1$. 
 This transformation yields a valid excursion, since the section 
 of the walk up until the $(a_i+1)$-th $\sNE$ step can have up to $a_i$ $\sW$ steps. The newly obtained excursion is denoted by $w'$.
 
 \item \label{bij:SNE-SS} 
 Next, let $b_1, b_2, \ldots, b_\ell$ be the indices of the \textit{marked} $\sNE$ steps, in the order as they occur in $w'$. 
 (Note that we only consider $\sNE$ steps marked before Step~\ref{bij:SS-SNE}.)
 %For each of the $\ell$ steps of type $\sW$ that occur immediately before a marked $\sNE$ step with 
 %index $b_j$, starting from $j = \ell$ and reducing $j$ by one at each iteration, remove the $\sW$ step and insert it into the path
 %at the position immediately before the $\sW$ step with index $b_j$. 
		For each $j=\ell, \ell-1, \ldots, 1$, in this order,
		we remove the $\sW$ step that occurs immediately before a \textit{marked} $\sNE$ step with index $b_j$,
		and insert it immediately before the $\sW$ step with index $b_j$. 
%		At each step of this transformation, 
%		the number of $\sNE$ steps that have occurred at any point in the path 
%		is greater than or equal to the number of $\sW$ steps, 
%		and thus each $\sW$ step either has the same position or is shifted to a later point in the path. 	
		As above, one can routinely show that the resulting walk is an excursion; we denote it by $w''$.
 \end{enumerate}

Refer to \cref{fig:SNE-SS-correspondence} for an example,
where the marked $\sW$ steps are coloured red, 
and the marked $\sNE$ steps are coloured blue. 
It is easily seen directly that $w \mapsto w''$ is an involution. Therefore, it is a bijection.
 
Finally, we show that $w''$ has $\ell$ occurrences of $\pWW$and $k$ occurrences of $\pWNE$.
At Step~\ref{bij:SS-SNE}, $k$ occurrences of $\pWW$yield $k$ distinct ``new'' occurrences of $\pWNE$ in $w'$.
The only way in which the patterns can overlap in $w'$, is a string \pWWNE\
where the first $\sW$ was adjacent to the (marked) $\sNE$ in $w$, and the second $\sW$ is an inserted one.
Then, at Step~\ref{bij:SNE-SS}, $\ell$~``old'' occurrences of $\pWNE$ yield distinct occurrences $\pWW$in $w''$.
In particular, in each string \pWWNE\ the step $\sNE$ is marked, therefore it yields both $\pWW$and $\pWNE$ in $w''$. 
All in all, it follows that $w \mapsto w''$ swaps the numbers of occurrences of $\pWW$and $\pWNE$.
\end{proof}

\vspace{-2mm}
\begin{figure}[ht]
 \centering
 \raisebox{3.5pt}{
 \begin{tikzpicture}[scale = 0.6]
 \draw[help lines] (0, 0) grid (3, 3);
 \draw [fill] (0,0) circle (3pt);
 \node at (-0.7, 2.5) {$w$};
 \draw[ultra thick, line cap = round, -] (0, 0) to (1, 1);
 \draw[ultra thick, line cap = round, -] (1, 1) to (2, 2);
 \draw[red, ultra thick, line cap = round, -] (2, 2) to (1, 2);
 \draw[ultra thick, line cap = round, -] (1, 2) to (0, 2);
 \draw[blue, ultra thick, line cap = round, -] (0, 2) to (1, 3);
 \draw[ultra thick, line cap = round, -] (1, 3) to (1, 2.15);
		\draw[ultra thick, line cap = round, -] (1, 2.15) to (1.15, 2.15);
 \draw[ultra thick, line cap = round, -] (1.15, 2.15) to (2, 3);
 \draw[ultra thick, line cap = round, -] (2, 3) to (2, 2.15);
		\draw[ultra thick, line cap = round, -] (2, 2.15) to (2.15, 2.15);
 \draw[ultra thick, line cap = round, -] (2.15, 2.15) to (3, 3);
 \draw[ultra thick, line cap = round, -] (3, 3) to (3, 2);
 \draw[ultra thick, line cap = round, -] (3, 2) to (3, 1);
 \draw[ultra thick, line cap = round, -] (3, 1) to (3, 0.2);
 \draw[ultra thick, line cap = round, -] (3, 0.2) to (2, 0.2);
 \draw[blue, ultra thick, line cap = round, -] (2, 0.2) to (2.8, 1);
 \draw[ultra thick, line cap = round, -] (2.8, 1) to (2.8, 0.325);
		\draw[ultra thick, line cap = round, -] (2.8, 0.075) to (2.8, 0);
 \draw[red, ultra thick, line cap = round, -] (2.8, 0) to (2, 0);
 \draw[red, ultra thick, line cap = round, -] (2, 0) to (1, 0);
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (1, 0) to (0.1, 0);
 \end{tikzpicture}}\quad
 \raisebox{27pt}{$\mapsto$}
 \begin{tikzpicture}[scale = 0.6]
 \draw[help lines] (0, 0) grid (3, 3);
 \draw [fill] (0,0) circle (3pt);
 \node at (-0.7, 2.5) {$w'$};
 \draw[ultra thick, line cap = round, -] (0, 0) to (1, 1);
 \draw[ultra thick, line cap = round, -] (1, 1) to (0, 1);
 \draw[ultra thick, line cap = round, -] (0, 1) to (1, 2);
 \draw[ultra thick, line cap = round, -] (1, 2) to (0, 2);
 \draw[blue, ultra thick, line cap = round, -] (0, 2) to (1, 3);
 \draw[ultra thick, line cap = round, -] (1, 3) to (1, 2.15);
 \draw[ultra thick, line cap = round, -] (1, 2.15) to (1.15, 2.15);
 \draw[ultra thick, line cap = round, -] (1.15, 2.15) to (2, 3);
 \draw[ultra thick, line cap = round, -] (2, 3) to (2, 2);
 \draw[ultra thick, line cap = round, -] (2, 2) to (1.2, 2);
 \draw[ultra thick, line cap = round, -] (1.2, 2) to (1.9, 2.7);
		\draw[ultra thick, line cap = round, -] (2.1, 2.9) to (2.2, 3);
 \draw[ultra thick, line cap = round, -] (2.2, 3) to (2.2, 2);
 \draw[ultra thick, line cap = round, -] (2.2, 2) to (2.2, 1);
 \draw[ultra thick, line cap = round, -] (2.2, 1) to (2.2, 0);
 \draw[ultra thick, line cap = round, -] (2.2, 0) to (1, 0);
 \draw[ultra thick, line cap = round, -] (1, 0) to (0.2, 0);
 \draw[blue, ultra thick, line cap = round, -] (0.2, 0) to (1, 0.8);
 \draw[ultra thick, line cap = round, -] (1, 0.8) to (1, 0.125);
		\draw[ultra thick, line cap = round, -] (1, -0.125) to (1, -0.2);
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (1, -0.2) to (0.15, -0.2);
 
 \end{tikzpicture}\quad
 \raisebox{27pt}{$\mapsto$}
	\raisebox{3.5pt}{ 
 \begin{tikzpicture}[scale = 0.6]
 \draw[help lines] (0, 0) grid (3, 3);
 \draw [fill] (0,0) circle (3pt);
 \node at (-0.7, 2.5) {$w''$};
 \draw[ultra thick, line cap = round, -] (0, 0) to (1, 1);
 \draw[ultra thick, line cap = round, -] (1, 1) to (0, 1);
 \draw[ultra thick, line cap = round, -] (0, 1) to (1, 2); %B
 \draw[ultra thick, line cap = round, -] (1, 2) to (2, 3);
 \draw[ultra thick, line cap = round, -] (2, 3) to (2, 2);
 \draw[ultra thick, line cap = round, -] (2, 2) to (3, 3);
 \draw[ultra thick, line cap = round, -] (3, 3) to (3, 1.85);
 \draw[ultra thick, line cap = round, -] (3, 1.85) to (2, 1.85); %R
 \draw[ultra thick, line cap = round, -] (2, 1.85) to (1.1, 1.85);
 \draw[ultra thick, line cap = round, -] (1.1, 1.85) to (1.85, 2.6); %B
 \draw[ultra thick, line cap = round, -] (1.85, 2.6) to (1.85, 2-0.025);
 \draw[ultra thick, line cap = round, -] (1.85, 1.725) to (1.85, 1);
 \draw[ultra thick, line cap = round, -] (1.85, 1) to (1.85, 0.15);
 \draw[ultra thick, line cap = round, -] (1.85, 0.15) to (1.15, 0.15);
 \draw[ultra thick, line cap = round, -] (1.15, 0.15) to (2-0.275, 1-0.275); %B
 \draw[ultra thick, line cap = round, -] (2-0.05, 1-0.05) to (2, 1); %B
 \draw[ultra thick, line cap = round, -] (2, 1) to (2, 0);
 \draw[ultra thick, line cap = round, -] (2, 0) to (1, 0); %R
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (1, 0) to (0.1, 0);
 \end{tikzpicture}}
 \caption{An example of the mapping $w \mapsto w''$ in the proof of \cref{thm:SS-SNE-involution}. } 
 \label{fig:SNE-SS-correspondence}
\end{figure}

For $k=0$ we immediately obtain the following result.
\begin{corollary}
 There is a bijection between $\pWW$-avoiding Kreweras excursions of length $3n$ 
 and $\pWNE$-avoiding Kreweras excursions of length $3n$.
\end{corollary}


The following table shows the number of Kreweras excursions of length $3n$ with precisely $k$ occurrences of
the pattern~$\pWW$ (or, due to \cref{thm:SS-SNE-involution}, of the pattern~$\pWNE$).
\begin{center}
 \begin{tabular}{r||c|c|c|c|}
 &$k=0$&$1$&$2$&$3$ \\ \hline
 $n=1$ & $2$ &&& \\
 $2$ &$11$&$5$&& \\
 $3$ &$85$&$93$&$14$& \\
 $4$ &$782$&$1432$&$560$&$42$ \\
 \end{tabular}
\end{center}
Of course, the row sums in this table are Kreweras numbers.
As noted in \cref{table:patterns-length-2} (the first two entries),
the first column, corresponding to avoidance, contains Gessel numbers: this will be proven in \cref{thm:WW-gessel}. 
On the other hand, the maximum possible number of occurrences 
of $\pWW$is~$n-1$,
and the Kreweras excursions that have that many occurrences of this pattern make a nice cameo of Catalan numbers, as we show now.

\begin{prop}
The number of Kreweras excursions of length $3n$ with $n-1$ occurrences of the pattern~$\pWW$ (or, equivalently, $\pWNE$) is the $(n+1)$-th Catalan number.
\end{prop}
\begin{proof}
The only way in which such an excursion can have $n-1$ occurrences of the pattern~$\pWW$
is when all $\sW$ steps occur consecutively, and this must happen after all of the $\sNE$ steps. Therefore the walk 
ends with a consecutive sequence of $n$ 
 $\sW$ steps followed 
by a (possibly empty) consecutive sequence of $\sS$ steps to return to $(0, 0)$. 
Since it is possible to reconstruct the end of the excursion by knowing where the first $\sW$ step is, we remove this end-section 
of the excursion and replace it with a $\sNE$ step followed by 
$\sS$ steps to reach the $x$-axis. 
The obtained walk then consists of $n+1$ steps of type $\sNE$ and $n+1$ steps of type $\sS$, 
which is a slanted Dyck path of length $2(n+1)$.
This correspondence is easily seen to be a bijection, and it is demonstrated in the following figure.

\begin{center}
 \begin{tabular}{|c|c|c|c|c|}
 \hline 
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (2, 2);
 \draw[red, ultra thick, line cap = round, -] [rounded corners=1pt] (0, 0) -- (2, 2);
 \draw[ultra thick, line cap = round][arrows={-Latex[length=6pt]}] (2, 2) -- (0,2) -- (0, 0.1);
 \node at (1.5, 3.2){};
 \end{tikzpicture}
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (3, 3);
 \draw[red, ultra thick, line cap = round, -][rounded corners=1pt] (0, 0) -- (2,2);
 \draw[ultra thick, line cap = round, -][rounded corners=1pt] (2, 2) -- (3, 3) -- (3,0);
 \end{tikzpicture}
 &
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (2, 2);
 \draw[red, ultra thick, line cap = round, -] [rounded corners=1pt] (0, 0) -- (2, 2) -- (2,1);
 \draw[ultra thick, line cap = round][arrows={-Latex[length=6pt]}] (2, 1) -- (0,1) -- (0, 0.1);
 \end{tikzpicture}
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (3, 3);
 \draw[red, ultra thick, line cap = round, -][rounded corners=1pt] (0, 0) -- (2,2) -- (2,1);
 \draw[ultra thick, line cap = round, -][rounded corners=1pt] (2, 1) -- (3, 2) -- (3,0);
 \end{tikzpicture}
 &
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (2, 2);
 \draw[red, ultra thick, line cap = round, -] [rounded corners=1pt] (0, 0) -- (1, 1) -- (1,0) -- (2,1);
 \draw[ultra thick, line cap = round][arrows={-Latex[length=6pt]}] (2, 1) -- (0,1) -- (0, 0.1);
 \end{tikzpicture}
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (3, 3);
 \draw[red, ultra thick, line cap = round, -][rounded corners=1pt] (0, 0) -- (1, 1) -- (1,0) -- (2,1);
 \draw[ultra thick, line cap = round, -][rounded corners=1pt] (2, 1) -- (3, 2) -- (3,0);
 \end{tikzpicture}
 & 
 \raisebox{-1.5pt}{
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (2, 2);
 \draw[red, ultra thick, line cap = round, -] [rounded corners=1pt] (0, 0) -- (2, 2) -- (2,0);
 \draw[ultra thick, line cap = round, ][arrows={-Latex[length=6pt]}] (2, 0) -- (0.1, 0);
 \end{tikzpicture}}
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (3, 3);
 \draw[red, ultra thick, line cap = round, -][rounded corners=1pt] (0, 0) -- (2, 2) -- (2,0);
 \draw[ultra thick, line cap = round, -][rounded corners=1pt] (2, 0) -- (3, 1) -- (3,0);
 \end{tikzpicture}
 & 
 \raisebox{-1.5pt}{
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (2, 2);
 \draw[red, ultra thick, line cap = round, -] [rounded corners=1pt] (0, 0) -- (1, 1) -- (1,0) -- (2,1) -- (2,0);
 \draw[ultra thick, line cap = round][arrows={-Latex[length=6pt]}] (2, 0) -- (0.1, 0);
 \end{tikzpicture}}
 \begin{tikzpicture}[scale = 0.45]
 \draw[help lines] (0, 0) grid (3, 3);
 \draw[red, ultra thick, line cap = round, -][rounded corners=1pt] (0, 0) -- (1, 1) -- (1,0) -- (2,1) -- (2,0);
 \draw[ultra thick, line cap = round, -][rounded corners=1pt] (2, 0) -- (3, 1) -- (3,0);
 \end{tikzpicture}
 \\ \hline
 \end{tabular}
\end{center}
\vspace{-6.3mm}
\end{proof}
\noindent
We now prove the links between constrained Kreweras excursions and Gessel excursions.
\begin{thm}[\cref{table:patterns-length-2}, Entry~\ref{entry:WW}]\label{thm:WW-gessel}
There is a bijection between $\pWW$-avoiding Kreweras excursions of length $3n$ 
and Gessel excursions of length $2n$. 
\end{thm}
\begin{proof} Consider the following correspondence between steps of $\pWW$-avoiding Kreweras excursions (left) and Gessel excursions (right):\vspace{-2mm}
\begin{center}
		\begin{tikzpicture}[scale = 0.5]
			\draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (1, 1);
 \draw[arrows={-Latex[length=6pt]}][ultra thick] (1, 1) to (-0.1, 1);
			\node at (0, 1.1) {};
		\end{tikzpicture}
 \hspace{2mm} \raisebox{1mm}{$\longleftrightarrow$} \hspace{2mm} 
 \begin{tikzpicture}[scale = 0.5]
 \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (0, 1);
 \end{tikzpicture} 
 \hspace{12mm}
 \begin{tikzpicture}[scale = 0.5]
 \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (0, -1);
 \end{tikzpicture} 
 \hspace{2mm} \raisebox{1mm}{$\longleftrightarrow$} \hspace{2mm}
 \begin{tikzpicture}[scale = 0.5]
 \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (0, -1);
 \end{tikzpicture}
 \hspace{12mm}
 \begin{tikzpicture}[scale = 0.5]
 \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (1, 1);
 \end{tikzpicture} 
 \hspace{2mm} \raisebox{1mm}{$\longleftrightarrow$} \hspace{2mm}
 \begin{tikzpicture}[scale = 0.5]
 \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (1, 1);
 \end{tikzpicture}
 \hspace{12mm} 
 \begin{tikzpicture}[scale = 0.5]
 \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (0, -1);
 \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, -1) to (-1, -1);
 \node at (0, 0.1) {};
 \end{tikzpicture}
 \hspace{2mm} \raisebox{1mm}{$\longleftrightarrow$} \hspace{2mm}
 \begin{tikzpicture}[scale = 0.5]
 \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (-1, -1);
 \end{tikzpicture} 
\end{center}
\vspace{-2mm}

Note that in $\pWW$-avoiding Kreweras excursions, a step immediately before a $\sW$ step 
can be either $\sNE$ or $\sS$. Therefore, ``short-cutting'' $\sNE$ and $\sS$ steps followed by $\sW$, 
and leaving all other steps unchanged, directly yields the desired bijection.
\end{proof}
\begin{prop}[\cref{table:patterns-length-2}, Entry~\ref{entry:WNE}]\label{prop:WNE-Gessel}
There is a bijection between $\pWNE$-avoiding Kreweras excursions of length $3n$ 
and Gessel excursions of length $2n$. 
\end{prop}

\begin{proof}
This follows directly from \cref{thm:SS-SNE-involution,thm:WW-gessel}. 
\end{proof}

Next we note that in the bijection from \cref{thm:WW-gessel}, $\sS$ steps (not followed by a $\sW$ step)
are preserved. Hence we have the following generalization.

\begin{prop}\label{prop:Gessel-Krew-S}
There is a bijection between Gessel excursions of length $2n$ with at least $m$ final $\sS$ steps
and $\pWW$-avoiding Kreweras excursions of length $3n$ which end with at least $m$ $\sS$ steps.
\end{prop}

The following theorem will be one key ingredient for proving some of the bijective links of \cref{table:patterns-length-2}.

\begin{thm}\label{thm:NES-SS-end-W}
There is a bijection between $\pNEW$-avoiding Kreweras excursions of length $3n$ 
and $\pWW$-avoiding Kreweras excursions of length $3n$ whose last step is $\sS$. 
\end{thm}

\begin{proof}
Let $w$ be a $\pNEW$-avoiding Kreweras excursion of length $3n$.
Consider the $n$-tuple $(\alpha_1, \ldots, \alpha_n)$, 
where $\alpha_i$ is the number of $\sW$ steps that immediately follow the $i$-th $\sS$ step.
Note that we have $\alpha_1 + \ldots + \alpha_n=n$.
Transform $(\alpha_1, \ldots, \alpha_n)$ into a $\{0,1\}$-sequence of length $2n-1$,
where the gap between entries contributes $0$,
and the entry $\alpha_i\geq 0$ contributes $\alpha_i$ $1$s. 
(This is a classical %\textit{``stars and bars''} %see \url{https://en.wikipedia.org/wiki/Stars\_and\_bars\_(combinatorics)\#Theorem\_two\_proof}.}.
bijection, popularized by Feller~\cite[Chapter II.5]{Feller50}, often called the ``balls and bars'' bijection.) %~\cite[Section I.3.1]{FlajoletSedgewick2009}.) 
Now erase from~$w$ all the $\sW$ steps,
thus obtaining a sequence~$\tilde{w}$ of $n$ $\sNE$ steps and $n$ $\sS$ steps in the same order as they were in~$w$,
and insert $\sW$ steps into~$\tilde{w}$ after precisely those positions where we have~$1$ in the $\{0,1\}$-sequence constructed above. 
Refer to \cref{fig:NES-SS-ends-W} for an illustration, where the $\sW$ steps are coloured blue.
The new Kreweras walk~$w'$ avoids $\pWW$ and has last step $\sS$, and it is routine to prove that it is an excursion, and that this mapping is a bijection. 
\end{proof}

\begin{figure}[ht]
 \centering
 \raisebox{25pt}{ 
 \begin{tikzpicture}[scale = 0.6]
 \draw[help lines] (0, 0) grid (4, 4);
 \draw [fill] (0,0) circle (3pt);
 \draw[ultra thick, line cap = round, -] (0, 0) to (1, 1);
 \draw[ultra thick, line cap = round, -] (1, 1) to (2, 2);
 \draw[ultra thick, line cap = round, -] (2, 2) to (2, 1);
 \draw[ultra thick, line cap = round, -] (2, 1) to (3, 2);
 \draw[ultra thick, line cap = round, -] (3, 2) to (4, 3);
 \draw[ultra thick, line cap = round, -] (4, 3) to (4, 2);
 \draw[blue, ultra thick, line cap = round, -] (4, 2) to (3.2, 2);
 \draw[blue, ultra thick, line cap = round, -] (2.8, 2) to (2.15, 2);
 \draw[blue, ultra thick, line cap = round, -] (1.8, 2) to (1, 2);
 \draw[blue, ultra thick, line cap = round, -] (1, 2) to (0, 2);
 \draw[ultra thick, line cap = round, -] (0, 2) to (1, 3);
 \draw[ultra thick, line cap = round, -] (1, 3) to (2, 4);
 \draw[ultra thick, line cap = round, -] (2, 4) to (2, 3);
 \draw[blue, ultra thick, line cap = round, -] (2, 3) to (1.2, 3);
 \draw[blue, ultra thick, line cap = round, -] (0.8, 3) to (0, 3);
 \draw[ultra thick, line cap = round, -] (0, 3) to (0, 2.2);
 \draw[ultra thick, line cap = round, -] (0, 1.85) to (0, 1);
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (0, 1) to (0, 0.15);
 \node at (-0.75, 0.25) {$w$}; 
 \end{tikzpicture}}\quad
 \hspace{3.5mm} \raisebox{58pt}{$\longleftrightarrow$} \hspace{-6.5mm} 
%img 2-3 comb
 \begin{tikzpicture}[scale = 0.6]
 \draw[help lines] (0, 0) grid (6, 4);
 \draw [fill] (0,0) circle (4pt);
 \draw[ultra thick, line cap = round, -] (0, 0) to (1, 1);
 \draw[ultra thick, line cap = round, -] (1, 1) to (2, 2);
 \draw[ultra thick, line cap = round, -] (2, 2) to (2, 1);
 \draw[ultra thick, line cap = round, -] (2, 1) to (3, 2);
 \draw[ultra thick, line cap = round, -] (3, 2) to (4, 3);
 \draw[ultra thick, line cap = round, -] (4, 3) to (4, 2);
 \draw[ultra thick, line cap = round, -] (4, 2) to (5, 3);
 \draw[ultra thick, line cap = round, -] (5, 3) to (6, 4);
 \draw[ultra thick, line cap = round, -] (6, 4) to (6, 3);
 \draw[ultra thick, line cap = round, -] (6, 3) to (6, 2);
 \draw[ultra thick, line cap = round, -] (6, 2) to (6, 1);
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (6, 1) to (6, 0);
 \node at (3, -1) {$\textcolor{blue}{(0, 4, 2, 0, 0, 0) \leftrightsquigarrow 011110110000}$};
 \node at (-0.75, 0.25) {$\tilde{w}$}; 
 \end{tikzpicture} \quad 
 \hspace{-7.5mm} \raisebox{58pt}{$\longleftrightarrow$} \hspace{-3mm} 
%img 4
	\raisebox{25pt}{ 
 \begin{tikzpicture}[scale = 0.6]
 \draw[help lines] (0, 0) grid (4, 4);
 \draw [fill] (0,0) circle (3pt);
 \draw[ultra thick, line cap = round, -] (0, 0) to (0.85, 0.85);
 \draw[ultra thick, line cap = round, -] (1.15, 1.15) to (2, 2);
 \draw[blue, ultra thick, line cap = round, -] (2, 2) to (1, 2);
 \draw[ultra thick, line cap = round, -] (1, 2) to (1, 1);
 \draw[blue, ultra thick, line cap = round, -] (1, 1) to (0, 1);
 \draw[ultra thick, line cap = round, -] (0, 1) to (0.85, 1.85);
 \draw[ultra thick, line cap = round, -] (0.85, 1.85) to (0.85, 2);
 \draw[blue, ultra thick, line cap = round, -] (0.85, 2) to (0, 2);
 \draw[ultra thick, line cap = round, -] (0, 2) to (1, 3);
 \draw[blue, ultra thick, line cap = round, -] (1, 3) to (0.05, 3);
 \draw[ultra thick, line cap = round, -] (0.05, 3) to (0.05, 2.25);
 \draw[ultra thick, line cap = round, -] (0.05, 2.25) to (0.95, 3.15);
 \draw[blue, ultra thick, line cap = round, -] (0.95, 3.15) to (0.15, 3.15);
 \draw[ultra thick, line cap = round, -] (0.15, 3.15) to (1, 4);
 \draw[blue, ultra thick, line cap = round, -] (1, 4) to (-0.125, 4);
 \draw[ultra thick, line cap = round, -] (-0.125, 4) to (-0.125, 3);
 \draw[ultra thick, line cap = round, -] (-0.125, 3) to (-0.125, 2);
 \draw[ultra thick, line cap = round, -] (-0.125, 2) to (-0.125, 1);
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (-0.125, 1) to (-0.125, 0.15);
 
 \node at (-1, 0.25) {$w'$};
 \end{tikzpicture}}
 \caption{An example of the bijection $w \leftrightarrow w'$ in the proof of \cref{thm:NES-SS-end-W}.}
 \label{fig:NES-SS-ends-W}
\end{figure}

Now, \cref{prop:Gessel-Krew-S} and \cref{thm:NES-SS-end-W}
yield directly the following correspondence.
\begin{corollary}[\cref{table:patterns-length-2}, Entry~\ref{entry:NES}]\label{cor:NEW-gessel}
There is a bijection between $\pNEW$-avoiding Kreweras excursions of length $3n$ 
and Gessel walks which end with at least one $\sS$ step.
\end{corollary}

\clearpage
\newpage
We now prove the link with P\'{o}lya excursions.
\begin{prop}[\cref{table:patterns-length-2}, Entry~\ref{entry:NENE}]\label{prop:NENE-Polya}
 There is a bijection between $\pNENE$-avoiding Kreweras excursions of length $3n$ 
 and P\'{o}lya excursions of length $2n$.
 \end{prop}
 \begin{proof}
 Similarly to the proof of \cref{thm:WW-gessel}, 
 the correspondence of steps of $\pNENE$-avoiding Kreweras (left)
	and P\'{o}lya (right) excursions is given by the following rules.
 \begin{center}
  \begin{tikzpicture}  
  [scale = 0.5]
  \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0)--(1, 1);
  \draw[arrows={-Latex[length=6pt]}][ultra thick] (1, 1)--(1, -0.1);
  \node at (0, 1.1){};
  \end{tikzpicture} 
  \hspace{2mm} \raisebox{1mm}{$\longleftrightarrow$} \hspace{2mm}
  \raisebox{0.3em}{\begin{tikzpicture}[scale = 0.5]
  \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (1, 0); 
  \end{tikzpicture}}
  \hspace{12mm}
  \begin{tikzpicture}[scale = 0.5]
  \draw[arrows={-Latex[length=6pt]}][ultra thick](0, 0) to (1, 1);
  \draw[arrows={-Latex[length=6pt]}][ultra thick] (1, 1) to (-.1, 1);
  \node at (0, 1.1){};
  \end{tikzpicture} 
  \hspace{2mm} \raisebox{1mm}{$\longleftrightarrow$} \hspace{2mm} 
  \begin{tikzpicture}[scale = 0.5]
  \draw[arrows={-Latex[length=6pt]}][ultra thick](0, 0) to (0, 1);
  \end{tikzpicture} 
  \hspace{12mm}
  \raisebox{0.3em}{\begin{tikzpicture}[scale = 0.5]
  \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (-1, 0);
  \end{tikzpicture}} 
  \hspace{2mm} \raisebox{1mm}{$\longleftrightarrow$} \hspace{2mm}
  \raisebox{0.3em}{\begin{tikzpicture}[scale = 0.5]
  \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (-1, 0);
  \end{tikzpicture}} 
  \hspace{12mm}
  \begin{tikzpicture}[scale = 0.5]
  \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (0, -1);
  \end{tikzpicture} 
  \hspace{2mm} \raisebox{1mm}{$\longleftrightarrow$} \hspace{2mm}
  \begin{tikzpicture}[scale = 0.5]
  \draw[arrows={-Latex[length=6pt]}][ultra thick] (0, 0) to (0, -1);
  \end{tikzpicture} \qedhere
 \end{center}
\end{proof}

Finally, we prove the link between $\pSW$-avoiding Kreweras excursions and diagonal excursions.

\begin{thm}[\cref{table:patterns-length-2}, Entry~\ref{entry:SW}]\label{thm:gouyou-beauchamps}
There is a bijection between $\pSW$-avoiding Kreweras excursions of length $3n$ and diagonal excursions of length $2n$.
\end{thm}
\begin{proof}
 Any Kreweras excursion which avoids the pattern~$\pSW$ is uniquely determined by the positions of the 
 $\sNE$ steps in the excursion: All steps in between $\sNE$ steps are a sequence of $\sW$ steps followed by a sequence of $\sS$ steps. 
 Therefore we can uniquely decompose the excursions into pairs of Dyck paths $(D_1, D_2)$, where $D_1$ consists of all $\sNE$ 
 and $\sS$ steps (in order) in the excursion, and $D_2$ all $\sNE$ and $\sW$ steps in the excursion. The original Kreweras excursion can be 
 obtained from pairs by placing all $\sW$ and $\sS$ steps between a given pair of $\sNE$ steps with $\sW$ steps first, 
 followed by $\sS$ steps. 

 From the pair $(D_1, D_2)$ of two Dyck paths of length $2n$, we consider the $i$-th step in $D_1 = d_{1,1}d_{1,2}\ldots d_{1,2n}$ and $D_2 = d_{2,1}d_{2,2}\ldots d_{2,2n}$ simultaneously, $1 \leq i \leq 2n$, 
 and form the $i$-th step $g_i$ of the diagonal excursion as follows: 
 \begin{itemize}[noitemsep,topsep=1mm]
 \item If $d_{1, i} = \sNE$ and $d_{2, i} = \sNE$, then $g_i = \sNE$.
 \item If $d_{1, i} = \sNE$ and $d_{2, i} = \sW$, then $g_i = \sNW$.
 \item If $d_{1, i} = \sS$ and $d_{2, i} = \sNE$, then $g_i = \sSE$.
 \item If $d_{1, i} = \sS$ and $d_{2, i} = \sW$, then $g_i = \sSW$.
 \end{itemize}
Now, diagonal excursions are decomposed into pairs of Dyck paths by considering 
 the projection of the excursion on the $x$- and $y$-axis. These Dyck paths correspond to $(D_1, D_2)$ as described above. 
See \cref{fig:gouyou-beauchamps} for an example.
\end{proof}

\begin{figure}[hb]
 \centering
 \begin{tikzpicture}[scale = 0.438]
 \draw[help lines] (0, 0) grid (6, 6);
 \draw [fill] (0,0) circle (3pt);
 \draw[ultra thick, line cap = round, -] (0, 0) to (1, 1);
 \draw[ultra thick, line cap = round, -] (1, 1) to (2, 2);
 \draw[ultra thick, line cap = round, -] (2, 2) to (2, 1);
 \draw[ultra thick, line cap = round, -] (2, 1) to (3, 2);
 \draw[ultra thick, line cap = round, -] (3, 2) to (4, 3);
 \draw[ultra thick, line cap = round, -] (4, 3) to (3, 3);
 \draw[ultra thick, line cap = round, -] (3, 3) to (3, 2.2);
 \draw[ultra thick, line cap = round, -] (3, 1.8) to (3, 1);
 \draw[ultra thick, line cap = round, -] (3, 1) to (4, 2);
 \draw[ultra thick, line cap = round, -] (4, 2) to (5, 3);
 \draw[ultra thick, line cap = round, -] (5, 3) to (6, 4);
 \draw[ultra thick, line cap = round, -] (6, 4) to (5, 4);
 \draw[ultra thick, line cap = round, -] (5, 4) to (4, 4);
 \draw[ultra thick, line cap = round, -] (4, 4) to (3, 4);
 \draw[ultra thick, line cap = round, -] (3, 4) to (2, 4);
 \draw[ultra thick, line cap = round, -] (2, 4) to (3, 5);
 \draw[ultra thick, line cap = round, -] (3, 5) to (2, 5);
 \draw[ultra thick, line cap = round, -] (2, 5) to (1, 5);
 \draw[ultra thick, line cap = round, -] (1, 5) to (1, 4);
 \draw[ultra thick, line cap = round, -] (1, 4) to (1, 3);
 \draw[ultra thick, line cap = round, -] (1, 3) to (1, 2);
 \draw[ultra thick, line cap = round, -] (1, 2) to (2, 3);
 \draw[ultra thick, line cap = round, -] (2, 3) to (1.15, 3);
 \draw[ultra thick, line cap = round, -] (0.85, 3) to (0, 3);
 \draw[ultra thick, line cap = round, -] (0, 3) to (0, 2);
 \draw[ultra thick, line cap = round, -] (0, 2) to (0, 1);
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (0, 1) to (0, 0.1);
 \end{tikzpicture}\quad
 \raisebox{12mm}{$\rightleftarrows$}\quad
 \begin{tikzpicture}[scale = 0.292]
 \draw[help lines] (0, 0) grid (9, 9);
 \draw [fill] (0,0) circle (4pt);
 \draw[ultra thick, line cap = round, -] (0, 0) to (1, 1);
 \draw[ultra thick, line cap = round, -] (1, 1) to (2, 2);
 \draw[ultra thick, line cap = round, -] (2, 2) to (2, 1);
 \draw[ultra thick, line cap = round, -] (2, 1) to (3, 2);
 \draw[ultra thick, line cap = round, -] (3, 2) to (4, 3);
 \draw[ultra thick, line cap = round, -] (4, 3) to (4, 2);
 \draw[ultra thick, line cap = round, -] (4, 2) to (4, 1);
 \draw[ultra thick, line cap = round, -] (4, 1) to (5, 2);
 \draw[ultra thick, line cap = round, -] (5, 2) to (6, 3);
 \draw[ultra thick, line cap = round, -] (6, 3) to (7, 4);
 \draw[ultra thick, line cap = round, -] (7, 4) to (8, 5);
 \draw[ultra thick, line cap = round, -] (8, 5) to (8, 4);
 \draw[ultra thick, line cap = round, -] (8, 4) to (8, 3);
 \draw[ultra thick, line cap = round, -] (8, 3) to (8, 2);
 \draw[ultra thick, line cap = round, -] (8, 2) to (9, 3);
 \draw[ultra thick, line cap = round, -] (9, 3) to (9, 2);
 \draw[ultra thick, line cap = round, -] (9, 2) to (9, 1);
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (9, 1) to (9, 0);
 \end{tikzpicture}\quad
 \begin{tikzpicture}[scale = 0.292]
 \draw[help lines] (0, 0) grid (9, 9);
 \draw [fill] (0,0) circle (4pt);	
 \draw[ultra thick, line cap = round, -] (0, 0) to (1, 1);
 \draw[ultra thick, line cap = round, -] (1, 1) to (2, 2);
 \draw[ultra thick, line cap = round, -] (2, 2) to (3, 3);
 \draw[ultra thick, line cap = round, -] (3, 3) to (4, 4);
 \draw[ultra thick, line cap = round, -] (4, 4) to (3, 4);
 \draw[ultra thick, line cap = round, -] (3, 4) to (4, 5);
 \draw[ultra thick, line cap = round, -] (4, 5) to (5, 6);
 \draw[ultra thick, line cap = round, -] (5, 6) to (6, 7);
 \draw[ultra thick, line cap = round, -] (6, 7) to (5, 7);
 \draw[ultra thick, line cap = round, -] (5, 7) to (4, 7);
 \draw[ultra thick, line cap = round, -] (4, 7) to (3, 7);
 \draw[ultra thick, line cap = round, -] (3, 7) to (2, 7);
 \draw[ultra thick, line cap = round, -] (2, 7) to (3, 8);
 \draw[ultra thick, line cap = round, -] (3, 8) to (2, 8);
 \draw[ultra thick, line cap = round, -] (2, 8) to (1, 8);
 \draw[ultra thick, line cap = round, -] (1, 8) to (2, 9);
 \draw[ultra thick, line cap = round, -] (2, 9) to (1, 9);
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (1, 9) to (0, 9);
 \end{tikzpicture}\quad
 \raisebox{12mm}{$\rightleftarrows$}\quad
 \begin{tikzpicture}[scale = 0.438]
 \draw[help lines] (0, 0) grid (6, 6);
 \draw [fill] (0.15,0) circle (3pt);
 \draw[ultra thick, line cap = round, -] (0.15, 0) to (2, 1.85); %(2, 2+0.15)--(1+0.15, 3)--(1, 3-0.15)--(2-0.15, 2)--(0, 0+0.15)
 \draw[ultra thick, line cap = round, -] (2, 1.85) to (2.85, 1);
 \draw[ultra thick, line cap = round, -] (2.85, 1) to (3.85, 2);
 \draw[ultra thick, rounded corners = 1pt] (3.85, 2)--(3, 2.85)--(3.15, 3)--(5.075, 1.075);
 \draw[ultra thick, line cap = round, -] (5.075, 1.075) to (6, 2);
 \draw[ultra thick, line cap = round, -] (6, 2) to (5, 3);
 \draw[ultra thick, line cap = round, -] (5, 3) to (4, 4);
 \draw[ultra thick, line cap = round, -] (4, 4) to (3, 5);
 \draw[ultra thick, line cap = round, -] (3, 5) to (2, 4);
 \draw[ultra thick, line cap = round, -] (2, 4) to (2.925, 3.075);
 \draw[ultra thick, line cap = round, -] (2.925, 3.075) to (2, 2.15);
 \draw[ultra thick, rounded corners = 1pt] (2, 2.15)--(1.15, 3)--(1, 2.85)--(1.85, 2);
 \draw[ultra thick, line cap = round, ->, arrows={-Latex[length=6pt]}] (1.85, 2) to (0, 0.15);
 \end{tikzpicture}
\setlength\abovecaptionskip{1mm}
\setlength\belowcaptionskip{0mm}
 \caption{An example for the bijection from \cref{thm:gouyou-beauchamps}.}
 \label{fig:gouyou-beauchamps}
\end{figure}


\section{Pattern avoidance and nature of generating functions}\label{Sec4}
In this section, we tackle the question of the (non)-algebraicity of pattern-avoiding walks.

To this aim, it is useful to first recall the notion of directed walks.
A walk is called \textit{directed} if all its steps $(x,y)$ have $x\geq0$.
Since such walks can be encoded by context-free grammars,
their generating functions are systematically algebraic; see e.g.~\cite{BanderierLacknerWallner20, Duchon00}.

%It is well known that directed lattice paths have an algebraic generating function; this can be proven by four different approaches:
%via closure properties on context-free grammars/pushdown automata (see e.g.~\cite{BanderierLacknerWallner20, Duchon00}),
%%,MerliniRogersSprugnoliVerri99,LabelleYeh90}),
%via a Wiener--Hopf decomposition of Laurent series (see~\cite{Gessel80}),
%via a result on Artin’s approximation (see~\cite{Popescu19}), %Popescu86
%via the kernel method (see~\cite{Banderier98,BousquetMelouPetkovsek00}). 

What happens for more general stepsets, when one additionally forbids a pattern, and constrains the domain?
This is summarized in the following theorem.

\begin{thm}[(Non)-algebraicity of generating functions]\label{th:nonalg}
For any fixed stepset, let \linebreak $F(t,x,y,v)$ be the generating function of walks constrained in a domain, 
where $t,x,y$, and $v$ encode respectively the length of the walk, its final $x$ and~$y$ coordinates, and the number of occurrences of a given pattern~$p$.
The nature of this generating function satisfies:
\begin{itemize}[noitemsep,topsep=1mm]
\item[a)] For walks in $\Z^2$ avoiding a pattern, $F$ is rational.
\item[b)] For walks in $\N\times \Z$ avoiding a pattern, $F$ is algebraic.
\item[c)] For directed walks in~$\N^2$ avoiding a pattern, $F$ is algebraic.
\item[d)] For non-directed walks in~$\N^2$ avoiding a pattern, $F$ is not necessarily algebraic.
\end{itemize}
\end{thm}
\begin{proof}
\begin{itemize}[noitemsep,topsep=1mm]
\item[a)] The walks in $\Z^2$ 
avoiding a pattern~$p$ 
with stepset ${\mathcal S}$
can be encoded by the complement of a regular expression, namely $ \{{\mathcal S}^* p { \mathcal S}^* \}^c $,
and thus have a rational generating function.
\item[b)] %Revisiting a result of Spitzer, 
%For this case, the functional equation involves only one boundary.
These pattern-avoiding walks in $\N\times \Z$ are encodable by a pushdown automaton with a single stack (encoding the distance to the $y$-axis), and thus by 
a context-free grammar~\cite{BanderierLacknerWallner20}; therefore, they have an algebraic generating function.
%More explicit algebraic expressions can even be obtained via the kernel method~\cite{BanderierFlajolet02}.
%of the generating function of walks in $\N\times \N$by context-free grammars or the kernel method (see~\cite{BanderierFlajolet02,BanderierLacknerWallner20}). %Spitzer intergrale pour la nature???

\item[c)] If the walk is directed, then, by the vectorial kernel method (as developed in~\cite{AsinowskiBacherBanderierGittenberger2020}),
%in~\cite{AsinowskiBacherBanderierGittenberger2020,AsinowskiBanderierRoitner2020,AsinowskiBanderier2020}),
 $F(t,x,y,v)$ is algebraic.
In particular, setting $v=0$, the generating function of directed walks avoiding a given pattern is algebraic.

\item[d)] For non-directed walks, one can have $F(t,x,y,1)$ algebraic, but $F(t,x,y,0)$ not algebraic.
It is e.g.~the case for % Kreweras excursions avoiding the pattern~$\pNENE$, 
Entry 4 of \cref{table:patterns-length-2}. 
Indeed, these walks are counted by $C_n C_{n+1} \sim 4 \frac{16^n}{\pi n^3}$.
Such asymptotics involving an $n^{-3}$ factor are not compatible~with the rather constrained asymptotics 
of algebraic function coefficients~\cite{BanderierDrmota15,Jungen31}.\qedhere
%Therefore, via our Theorem~\ref{}, the generating function of Kreweras excursions avoiding the pattern HHHH is not algebraic.\qedhere
\end{itemize}
\end{proof}

%meanders??? for Kreweras
%Proof : intersection of N-algebraic and a regular expression, or the vectorial kernel method.

It is natural to ask to what extent forbidding a pattern
impacts the nature of the generating function.
\cref{hypertranscendental}
illustrates the~drastic~impact~it~can~have.
\vspace{-3mm}

%\begin{remark}[From algebraic to hypertranscendental] \rm
%It is possible to exhibit an algebraic model
%such that by forbidding a finite set of patterns on it, 
%one then gets an hypertranscendental model
%(there is no nonzero polynomial~$P$ and an order $m$ such that $P(t,F(t), F'(t), \dots, \partial_t^m F(t)=0)$; see Figure~\ref{hypertranscendal},

\begin{figure}[hb]\centering
\begin{tabular}{ccccc}
\raisebox{20pt}{
%\hspace{-2.5mm}
\begin{tabular}{c}
Kauers--Yatchak's model~\cite{KauersYatchak2015}\\(NB: steps are with multiplicity)
\end{tabular}}
&
\begin{tikzpicture}[scale = 0.5]
 \node(O) at (0, 0){};
 \node(E) at (1, 0){};
 \node(SE) at (1, -1){};
 \node(S) at (0, -1){};
 \node(SW) at (-1, -1){};
 \node(W) at (-1, 0){};
 \node(NW) at (-1, 1){};
 \node(N) at (0, 1){};
 \node(NE) at (1, 1){};
 \draw[help lines] (-1, -1) grid (1, 1);
				\draw [blue, fill] (0,0) circle (3pt);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (W.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (NW.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (N.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (NE.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (E.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (SE.center);
				\draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (S.center);
				\node at (-1.3, -0) {\scalebox{0.8}{\textcolor{blue}{$1$}}};
				\node at (-1.3, 1.4) {\scalebox{0.8}{\textcolor{blue}{$1$}}};
				\node at (0, 1.4) {\scalebox{0.8}{\textcolor{blue}{$2$}}};
				\node at (1.4, 1.4) {\scalebox{0.8}{\textcolor{blue}{$1$}}};
				\node at (1.4, 0) {\scalebox{0.8}{\textcolor{blue}{$2$}}};
				\node at (1.4, -1.4) {\scalebox{0.8}{\textcolor{blue}{$1$}}};
				\node at (0, -1.4) {\scalebox{0.8}{\textcolor{blue}{$1$}}};
\end{tikzpicture}
&
\hspace{1mm}
&
\raisebox{20pt}{
\begin{tabular}{c}
Mishna--Rechnitzer's \\ model~\cite{MishnaRechnitzer2009}
\end{tabular}}
&
\raisebox{9pt}{
\begin{tikzpicture}[scale = 0.5] 
				\node(O) at (0, 0){};
 \node(E) at (1, 0){};
 \node(SE) at (1, -1){};
 \node(S) at (0, -1){};
 \node(SW) at (-1, -1){};
 \node(W) at (-1, 0){};
 \node(NW) at (-1, 1){};
 \node(N) at (0, 1){};
 \node(NE) at (1, 1){};
 \draw[help lines] (-1, -1) grid (1, 1);
				\draw [blue, fill] (0,0) circle (3pt);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (NW.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (NE.center);
 \draw[blue, thick, line cap = round, ->, arrows={-Latex[length=5pt]}] (O.center) to (SE.center);
				\end{tikzpicture}}  \hspace{-4mm}
\end{tabular}
\vspace{-3mm}
\setlength\abovecaptionskip{-4.5mm}
\setlength\belowcaptionskip{-6.5mm}
\caption{Forbidding some steps in the left (algebraic) model leads 
to the right (hypertranscendental) model (as follows by the work of Singer and Hardouin~\cite{HardouinSinger2021}).} %Dreyfus2022
\label{hypertranscendental}
\end{figure}

The models of Kreweras excursions of \cref{sec:bijections}
are thus much more structured than what could be expected,
as proven in the following proposition.

\bgroup
\setlength\abovedisplayskip{1.5mm}
\setlength\belowdisplayskip{1.5mm}
\begin{prop}For each pattern $p$ of length~2, the generating function for $p$-avoiding Kreweras excursions is D-finite
(and not algebraic for the patterns $\pNENEx$, $\pSW$, and $\pWS$).
\end{prop}
\begin{proof}
Due to the properties of the models 
discussed in \cref{sec:history}, the only case which is left open is Entry 3 in \cref{table:patterns-length-2}.
Yet, its generating function is just the extraction of the coefficient $[x^0y^1]$ in a trivariate algebraic generating function (the one of Gessel walks).\linebreak 
By classical closure~properties~\cite{Stanley1980} %{PetkovsekWilfZeilberger1996,Lipschitz}
this gives a D-finite function, and it can be checked that it satisfies the same differential equation as an algebraic function of degree 4.
\end{proof}

\vspace{-1.5mm}
The classification for \textit{meanders} is still open; let us explain what the obstacles are if one tries to extend the kernel method approaches.
Kreweras walks with each occurrence of $p=a_1a_2$ is marked by $v$ can be generated by an automaton with two states:
The walk is in state ${\mathcal Q}_1$ if its last step is $a_1$,
and in state ${\mathcal Q}_0$ otherwise. For example, for $p=\pWW$:
\vspace{-2.8mm}\begin{center}
\includegraphics[scale=0.39]{kreweras_LL_aut.pdf} 
\end{center} \vspace{-4.3mm}
In this example, the corresponding transition matrix is 
$A=\begin{pmatrix}
xy+y^{-1} & x^{-1} \\ xy+y^{-1} & vx^{-1}
\end{pmatrix}.$
Now, let $Q_i(t,x,y,v)$ be the generating function of walks starting in state ${\mathcal Q}_i$ 
(for short, we denote it hereafter by $Q_i(x,y)$). One thus has the following matrix equation
\begin{eqnarray}\label{eq:krew_WW}
(Q_0(x,y), Q_1(x,y)) & = & (1,0) + t \{x^{\geq 0} y^{\geq 0}\} (Q_0(x,y), Q_1(x,y)) A, \notag
\end{eqnarray} % \{x^{\geq 0} y^{\geq 0}\} not defined, but notations are intuitive
which, in turn, is equivalent to the following system of two equations:
\begin{eqnarray*}
\big(1-t(xy+\bar{y})\big) Q_0(x,y)- t (xy+\bar{y}) Q_1(x,y) & = & 1 - t \bar{y} \big(Q_0(x,0)+Q_1(x,0)\big), \label{eq:sys1} \\ 
-t \bar{x} Q_0(x,y) +(1 - tv \bar{x} ) Q_1(x,y) & = & - t\bar{x} \big(Q_0(0,y)+v Q_1(0,y)\big). \label{eq:sys2}
\end{eqnarray*}

More generally, a pattern of length $m$ leads similarly to a system of $m$ equations, 
with $3 m$ unknowns and $m^2$ ``kernels'' (the coefficients in front of the $Q_i(x,y)$'s).
In most cases, trying to obtain new equations via variants of the algebraic and vectorial kernel methods
(see~\cite{AsinowskiBacherBanderierGittenberger2020,BousquetMelou2005}) does not solve this system, 
except in a few noteworthy cases which possess more symmetries. 
This allows us to show, for example, that P\'olya walks avoiding the pattern $\pWW$ 
are counted by a pullback of a hypergeometric function (similarly to~\cite{BostanChyzakVanHoeijKauersPech2017}).
We plan to detail these aspects in our forthcoming article.

\smallskip

This concludes our investigation of patterns for lattice walks in $\N^2$: we focused here on patterns of length~2 leading to nice combinatorial features, so many natural extensions are possible. 
For example, it is possible to tackle longer or more complex patterns (e.g.~some regular expressions), to attach weights or multiplicities to the steps, to include border interactions,
to add parameters which mark how often a walk visits a given set of sites, to consider other domains than $\N^2$, to follow statistics such as the height or the (signed) area, 
to establish the corresponding asymptotics and limit laws\ldots The study of lattice path generating functions still has good days ahead! 
\egroup
\smallskip


\printbibliography
\end{document}