% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
% Please remove all other commands that change parameters such as
% margins or pagesizes.
% only use standard LaTeX packages
% only include packages that you actually need
% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}
\usepackage[utf8x]{inputenc}
% we recommend the graphicx package for importing figures
\usepackage{graphicx}
% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins
% YLB additions
%% \usepackage{amsmath,amssymb,epsfig,color,%here
%% float,url}
\usepackage{tikz}
%% \usetikzlibrary{arrows,snakes,backgrounds}
% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% if needed include a line break (\\) at an appropriate place in the title
\title{\bf On computation of Baker's and, Norine's rank\\ on complete graphs}
% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address
\author{Robert Cori \thanks{The first author acknowledges the support of ERC under the agreement ``ERC StG 208471 - ExploreMap''}\\
\small LaBRI \\[-0.8ex]
\small Université de Bordeaux\\[-0.8ex]
\small Talence, France\\
\small\tt cori@labri.fr\\
\and
Yvan Le Borgne \thanks{Part of this work was done in PIMS, Simon Fraser University, Burnaby, Canada}\\
\small CNRS, LaBRI\\[-0.8ex]
\small Université de Bordeaux\\[-0.8ex]
\small Talence, France\\
\small\tt borgne@labri.fr
}
% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}
\date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\
\small Mathematics Subject Classifications: 05C88, 05C89}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\degree}{\mathrm{degree}}
\newcommand{\test}[1]{\chi(#1)}
\newcommand{\area}{\mathrm{area}}
\newcommand{\bounce}{\mathrm{bounce}}
\newcommand{\dinv}{\mathrm{dinv}}
\newcommand{\cdinv}{\mathrm{cdinv}}
\newcommand{\prerankmap}{\theta}
\newcommand{\prerank}{\mathrm{prerank}}
\newcommand{\laplacianconf}[1]{\Delta^{(#1)}}
\newcommand{\topplingequiv}{\equiv_{\Delta}}
\newcommand{\proofs}[1]{\mathrm{Proofs}(#1)}
\newcommand{\park}{\mathrm{park}}
\newcommand{\stabilize}{\mathrm{stabilize}}
\newcommand{\distancedegreedistribution}{\mathrm{ddd}}
\newcommand{\lexorder}{<_{lex}}
\newcommand{\positivedegree}{\degree_{+}}
\newcommand{\diameter}[1]{\delta_{#1}}
\newcommand{\onechipconf}[1]{\epsilon^{(#1)}}
\newcommand{\permutations}[1]{S_{#1}}
\newcommand{\conf}[2]{(#1;#2)}
\newcommand{\compact}{\mathrm{compact}}
\newcommand{\sort}{\mathrm{sort}}
\newcommand{\topplingpermutingequivalent}{\equiv_{\Delta,S_{n-1}}}
\newcommand{\T}{T}
\newcommand{\compactsortedclass}[1]{CS(#1)}
\newcommand{\Titerate}[2]{{#1}^{[{#2}]}}
\newcommand{\shiftmod}{\ \mathrm{mad}\ }
\newcommand{\TK}{K_\T}
\newcommand{\prefixai}[3]{{#1}_{]{#2}_{#3}}}
\newcommand{\dyckToparking}{\mathrm{dyck2parking}}
\newcommand{\YLBnext}{\mathrm{next}}
\newcommand{\cutstrip}[1]{B[#1]}
\newcommand{\leftcutstrip}[1]{L[#1]}
\newcommand{\rightcutstrip}[1]{R[#1]}
\newcommand{\leftcutstriprow}[2]{L_{#1}[#2]}
\newcommand{\E}{E}
\newcommand{\traceuupdate}[1]{\mathrm{traceu}(#1)}
\newcommand{\extralength}{\mathrm{extralength}}
\newcommand{\lrtrace}{\mathrm{lrtrace}}
\newcommand{\substitutionLRToTE}{\pi_{L\rightarrow \E\T^{-1};R\rightarrow \T^{-1}}}
\newcommand{\almostbalancedword}{D}
\newcommand{\cutskewcylinder}[2]{\mathrm{cylinder}[{#1}\circlearrowleft {#2}]}
\newcommand{\leftcutskewcylinder}[2]{L[{#1} \circlearrowleft {#2}]}
\newcommand{\rightcutskewcylinder}[2]{R[{#1} \circlearrowleft {#2}]}
\newcommand{\oriented}[1]{{#1}\uparrow}
\newcommand{\scompact}[4]{\mathrm{scompact}[{#1}\Rightarrow {#2} \circlearrowleft {#3}; {#4}]}
\newcommand{\prefixtoconjugate}[2]{{#1}_{[{#2}}}
\newcommand{\rrinvolutionconf}{\xi}
\newcommand{\reverse}[1]{\tilde{#1}}
\newcommand{\sgrankdegree}{K}
\newcommand{\leftset}[1]{\mathrm{left}[#1]}
\newcommand{\rightset}[1]{\mathrm{right}[#1]}
\newcommand{\sgleftright}{M}
\newcommand{\lefttorightcell}[2]{LR[#1 \circlearrowleft #2]}
\newcommand{\righttoleftcell}[2]{RL[#1 \circlearrowleft #2]}
\newcommand{\nextleftcell}[3]{S_{[#1 \circlearrowleft #2]}(#3)}
\newcommand{\leftcellonrowi}[4]{L_{#3}[#1 \circlearrowleft #2;#4]}
\newcommand{\xpara}{\mathrm{xpara}}
\newcommand{\ypara}{\mathrm{ypara}}
\newcommand{\crossedleftcells}[3]{\mathrm{CL}[#1 \circlearrowleft #2;#3]}
\newcommand{\uncrossedrightcells}[3]{\mathrm{UR}[#1 \circlearrowleft #2;#3]}
\newcommand{\leftpara}[3]{\mathrm{left}[#1\circlearrowleft #2;#3]}
\newcommand{\rightpara}[3]{\mathrm{right}[#1\circlearrowleft #2;#3]}
\newcommand{\monomleftright}[3]{M_{[#1\circlearrowleft #2;#3]}}
\newcommand{\size}{\mathrm{size}}
\newcommand{\X}{\mathbb{X}}
\newcommand{\Y}{\mathbb{Y}}
\newcommand{\height}{h}
\newcommand{\R}{\mathrm{R}}
\begin{document}
\maketitle
% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..." or "we show that...". Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.
\begin{abstract}
The paper by M. Baker and S. Norine in 2007 introduced a new parameter on configurations of graphs and gave a new result in the theory of graphs which has an algebraic geometry flavor.
This result was called Riemann-Roch formula for graphs since it defines a combinatorial version of divisors and their ranks in terms of configurations on graphs.
The so called chip firing game on graphs and the sandpile model in physics play a central role in this theory.
In this paper we present an algorithm for the determination of the rank of configurations for the complete graph $K_n$.
This algorithm has linear arithmetic complexity.
The analysis of number of iterations in a less optimized version of this algorithm leads to an apparently new parameter which we call the prerank.
This parameter and the parameter dinv provide an alternative description to some well known $q,t$-Catalan numbers.
Restricted to a natural subset of configurations, the two natural statistics degree and rank lead to a distribution which is described by a generating function which, up to a change of variables and a rescaling, is a symmetric fraction involving two copies of Carlitz $q$-analogue of the Catalan numbers.
In annex, we give an alternative presentation of the theorem of Baker and Norine in purely combinatorial terms.%, which is more accessible and shorter than the original one.
% keywords are optional
%% \bigskip\noindent \textbf{Keywords:} graph reconstruction
%% conjecture; Broglington manifold; Pipletti's classification
\end{abstract}
\section{Introduction}
On a graph, a configuration is a map from its vertices to the integers of $\mathbb{Z}$.
Motivated by the generalization for graphs of a Riemann-Roch theorem, Baker and Norine~\cite{bakerNorine} defined for any configuration a parameter they called rank.
This parameter is an integer greater or equal to $-1$.
The abelian sandpile model~\cite{bakTang1,dhar1,dharIntro} provides a framework for the original definition of the rank which seems to involve non-trivial computations.
At submission date of this work, the complexity of the computation of the rank for general graphs was unknown.
Just after, Kiss and T\'othm\'er\'esz announced on arXiv~\cite{kisstothmeresz} their proof for general graphs that computation is NP-hard.
The complete graph $K_n$ is the non-oriented graph with $n$ vertices and exactly one edge between any pair of distinct vertices.
We present here an algorithm which computes the rank of a configuration in the particular case of complete graphs.
We prove that our most efficient version has a linear arithmetic complexity where the size of the problem is the number of vertices of the graph.
The design of this algorithm has enumerative byproducts in the context of the rank parameter and also some intensively studied $q,t$-Catalan numbers~\cite{haglund}.
The results in this second context strengthen the connection with the abelian sandpile model as in recent work involving one of the authors~\cite{DukesLeBorgne,ADDHL}.
Let $G=(V_G,E_G)$ be an non-oriented connected simple graph without loops and with vertex set $V_G$ and edge set $E_G$.
Baker's and, Norine's theorem~\cite{bakerNorine} states that for any configuration $u=(u_i)_{i\in V_G}\in \mathbb{Z}^{|V_G|}$ of $G$,
$$ \rank(u) - \rank(K_G-u) = \degree(u) + |E_G| - |V_G| $$
where the cardinality of a set $E$ is denoted by $|E|$; the definition of the parameter $\rank$ is still postponed to the preliminaries in Section~\ref{sec:naive-algo}; the configurations are seen as vectors allowing additions and subtractions; the degree of the configuration $u$ is $\degree(u):=\sum_{i\in V_G} u_i$; the configuration $K_G:=(k_i)_{i\in V_G}$ is defined by $k_i := d_i-2$ where $d_i$ is the degree of the vertex $i$ which is its number of incident edges. In this context, a configuration is called a divisor but we prefered to use the abelian sandpile model terminology.
This paper focus on the particular case where $G$ is a complete graph $K_n$: we use the integers $1,2,\ldots n$ to label the vertices $V_{K_n}$ of the complete graph $K_n$; the configuration $K_{K_n} = (k_i)_{i=1\ldots n}$ satisfies $k_i=n-3$ for all $i$.
The two next sections are dedicated to the design of our main algorithm which computes the rank of a configuration on $K_n$.
Section~\ref{sec:naive-algo} focus on correctness of a first version of the algorithm.
We use the numerous symmetries of the complete graphs to obtain a greedy algorithm computing the rank.
The complexity of this version is not clear but the aim of Section~\ref{sec:optimised-algo} is to optimize this algorithm.
We select a particular run of this non-deterministic first algorithm to reach the announced complexity while preserving the correctness.
The optimization requires to work at the level of orbits of a subgroup of symmetries.
The toppling equivalence, an additional equivalent relation on configurations based on the sandpile model framework, shows that one can efficiently reduce the computation to the case of a sorted parking configuration.
The configuration $u$ is a sorted parking configuration if $0 \leq u_i < i$ for $i < n$ and $u_1\leq u_2 \leq \ldots \leq u_{n-1}$.
Notice that there is no constrain on the value of $u_n$.
If we had used the divisor terminology, we may called this configuration a sorted $n$-reduced divisor.
The optimized algorithm computes the rank via the following rather explicit expression for the rank of a sorted parking configuration $u$ in $K_n$:
$$ \rank(u) = \left(\sum_{i=1}^{n-1}\max(0,q-i+u_i+\test{i\leq r}) \right)-1.$$
where $u_n+1 = q(n-1)+r$ is the euclidean division defining the quotient $q$ and the non-negative remainder $r$, and $\test{P}$ is $1$ if the proposition $P$ is true and $0$ otherwise.
The second optimized algorithm still manipulates the configurations as vectors.
Yet the proof that it corresponds to a run of the first algorithm deeply relies on another coding of some configurations.
These configurations on $K_n$ may be encoded by a Dyck word of size $n-1$ and one or two integers depending on its additional properties.
A word $v$ on the two-letter alphabet $\{a,b\}$ is a Dyck word of size $n$ if $|v|_a=|v|_b=n$ and for any prefix $p$ of $v$, $|p|_a \geq |p|_b$ where $|v|_c$ denotes the number of occurrences of letter $c$ in the word $v$.
This data is embedded in a cut skew cylinder to make use of a cyclic symmetry.
The skew cylinder of circumference $n$ is an already known slight variation of the usual $\mathbb{Z}\times \mathbb{Z}/(n-1)\mathbb{Z}$ cylinder, for example already presented by Kramers and Wannier~\cite{kramersWannier} in 1941.
The main interest of this skew is that it merges the usually ``parallel'' finite cycles interpreting $\mathbb{Z}/(n-1)\mathbb{Z}$ into a single infinite spiral traversal isomorphic to $\mathbb{Z}$.
A cut of this skew cylinder is a self-avoiding directed cycle made up of north and east steps disconnecting the cylinder into two components.
A classical cyclic lemma due to Dvoretsky and Motzkin~\cite{dvoMotzk} implies that any cut may be defined by the choice of a Dyck word of size $n-1$ and a starting vertex.
One interest of this change of encoding is that computation on configurations becomes simpler updates of the Dyck word or the integers.
After all, our optimized algorithm on the configuration $u=(u_i)_i$ may be interpreted as a spiral traversal of $u_n+1$ cells on a related cut skew cylinder counting the occurrences of cells in one of the two components defined by the cut.
In Section~\ref{sec:rank-byproducts}, we describe as follows the generating function
$$ K_n(r,d) := \sum_{u} r^{\rank(u)}d^{\degree(u)} = \frac{d^{{n-1 \choose 2}}}{rd}M_n(\frac{1}{d},rd)$$
where $u$ runs over \emph{sorted} parking configurations on $K_n$ and $M_n(x,y)$ is the coefficient of $z^{n-1}$ in
$$ \mathbb{M}(x,y;z) := \frac{1-xy}{(1-x)(1-y)}\frac{C(x;xz)+C(y;yz)-C(x;xz)C(y;yz)}{1-C(x;xz)zC(y;yz)}$$
where $C(q;z)$ is a classical Carlitz $q$-analogue of Catalan numbers counting the Dyck words according to size via the variable $z$ and the later defined area via the variable $q$.
The formula for $\mathbb{M}(x,y;z)$ comes from the decomposition, on each cut skew cylinder, of the spiral traversal at crossings of the cut, leading to geometric sums of reasons $x$ or $y$.
If the sum in $K_n(r,d)$ were not restricted to sorted parking configurations, we would have reached a two-variable zeta function for graphs introduced recently by Lorenzini~\cite{lorenzini}.
We provide a combinatorial interpretation of the generating function $M_n(x,y)$ in terms of cut skew cylinders.
Those cut skew cylinders admits an natural involution $\rrinvolutionconf$ which roughly speaking consists in reversing the spiral traversal.
This involution also explains via a superimposition principle why $M_n(x,y) = M_n(y,x)$.
In addition, this involution is related to the involution on configurations $u\rightarrow K_{K_n}-u$ appearing in Riemann-Roch theorem for graphs.
In Section~\ref{sec:qt-byproducts}, we study connections of this work with $q,t$-Catalan numbers presented for example by Haglund in~\cite{haglund}.
These $q,t$-Catalan numbers $(C_n(q,t))_{n\in\mathbb{N}}$ may be combinatorialy described by some pairs of statistics on a generic Dyck word $w$ chosen among the later defined $\area(w)$, $\bounce(w)$ and $\dinv(w)$:
$$C_n(q,t) := \sum_{w} q^{\area(w)}t^{\dinv(w)} = \sum_{w} q^{\area(w)}t^{\bounce(w)}$$
where $w$ runs over Dyck words of size $n$.
The symmetry $C_n(q,t)=C_n(t,q)$ is obvious once non-trivially proven equivalent to some alternative definitions.
There is still no combinatorial explanation of this symmetry \cite{Haglund2}.
In this context,Haglund designed an involution $\zeta$ on Dyck words which satisfies for any Dyck word $w$:
$$ (\dinv(w),\area(w)) = (\area(\zeta(w)),\bounce(\zeta(w)))$$
establishing combinatorially the equivalence of the two presented definitions of $C_n(q,t)$.
Our involution $\rrinvolutionconf$ on cut skew cylinders may be canonically restricted to Dyck words and this restriction also called $\rrinvolutionconf$.
It appears that $\dinv(\rrinvolutionconf(w))=\dinv(w)$.
An early optimization of our algorithm computing the rank leads us to the apparently new parameter $\prerank(w)=\area(\rrinvolutionconf(w))$.
Hence we have
$$ C_n(q,t) = \sum_w q^{\dinv(w)}t^{\prerank(w)} $$
where $w$ runs of Dyck words of size $n$.
There is also a relation between the maps $\zeta$ and $\rrinvolutionconf$:
$$ \zeta \circ \rrinvolutionconf = \R \circ \zeta $$
where $\R(w)$ classically maps the Dyck word $w$ to its reverse word where each occurrence of $a$ is replaced by $b$ and conversely.
\section{A first greedy algorithm \label{sec:naive-algo}}
In our preliminaries, we recall classical properties of the abelian sandpile model and
Baker's and, Norine's definition of the rank parameter.
We then prove the correctness of our first version of a greedy algorithm computing the rank for a configuration in a complete graph.
\subsection{Preliminaries}
%\subsubsection{Notations for the abelian sandpile model}
Let $G$ be a non-oriented connected graph without loops and where multiple edges are allowed.
We denote by $V=\{1,2,\ldots n\}$ where $n=|V|$ the vertex set of $G$ and $E$ its edge set.
The number of edges of $E$ between the vertices $i$ and $j$ is denoted by $e_{i,j}$.
Hence the \emph{degree $d_i$ of the vertex} $i\in V$ is $\sum_{j\in V} e_{i,j}.$
A \emph{configuration} $u=(u_i)_{i\in V}$ is a vector of $\mathbb{Z}^n$: the possibly negative number of grains $u_i$ is placed on vertex $i$ in configuration $u$.
Since a configuration $u$ is a vector we can add or subtract configurations: the configuration $w=u-v$ is defined by $w_i=u_i-v_i$ for any vertex $i$.
The \emph{degree of the configuration} $u$ is $\degree(u) := \sum_{i\in V} u_i$.
In the abelian sandpile model, the \emph{toppling of the vertex $i$} in configuration $u$ consists in sending from the vertex $i$ one unit along each incident edge to the opposite endpoint of the edge.
These amounts of one unit are also called \emph{grains}.
This leads to the configuration $u'=u-\laplacianconf{i}$ where $\laplacianconf{i}_i := d_i$ and $\laplacianconf{i}_j := -e_{i,j}$ otherwise.
This toppling is $\emph{legal}$ if $u_i \geq d_i$ ensuring that $u'_i\geq 0$ and $u'_j \geq u_j$ for any $j\neq i$.
In this paper non legal topplings are sometimes allowed.
The toppling of vertex $i$ preserves the degree of any configuration since $\degree(\laplacianconf{i})= 0$.
Two configurations $u$ and $v$ are \emph{toppling equivalent} if they differ by a finite combination of topplings:
$$ u \topplingequiv v := \exists (a_i)_{i\in V}\in \mathbb{N}^n,\ u = v-\sum_{i\in V} a_i\laplacianconf{i}$$
The symmetry of this equivalence relation comes from the relation $\sum_{i\in V}\laplacianconf{i} = 0$ which allows to use $-\laplacianconf{i} = \sum_{j\neq i} \laplacianconf{i}$ to change signs in the combination.
%\subsubsection{Definition of the rank}
We mainly summarize with our notation the definition of the rank presented by Baker and Norine in \cite{bakerNorine}.
A configuration $u$ is \emph{positive}, also denoted $u\geq 0$, if $u_i\geq 0$ for any vertex $i$.
A configuration $v$ is \emph{effective} if $v$ is toppling equivalent to a positive configuration: $\exists u, v\topplingequiv u,\mbox{ and } u\geq 0$.
The \emph{rank} of the configuration $u$ is defined by the following optimization:
$$ \rank(u) := -1 + \min_f \degree(f) $$
where $f$ runs over all positive configurations such that $u-f$ is non-effective.
An optimal choice $f$ for the computation of $\rank(u)$ is called a \emph{proof} for the rank of $u$.
The set of such proofs is denoted by $\proofs{u}$.
The test that a configuration $u$ is effective is a first difficulty in this description of the rank since naively it may require to run over the infinite set of all configurations toppling equivalent to $u$.
Hopefully, one can limit the test to a canonical configuration in the class of toppling equivalence: the $n$-parking configuration of $u$ denoted $\park(u)$ which will be defined below.\footnote{It corresponds to the notion of $n$-reduced divisor.}
\begin{lemma}[\cite{bakerNorine},see also Proposition~\ref{prop:eff_on_park} in annex]\label{lem:eff_on_park}
We have $u$ effective if and only if $\park(u)$ is positive.
\end{lemma}
The definition of these $n$-parking configurations requires additional notions.
By convention the vertex $n$ is distinguished and called the \emph{sink}.
A vertex $i$ in configuration $u$ is \emph{unstable} if $u_i \geq d_i$ where $d_i$ is the degree of the vertex $i$ in $G$.
A configuration $u$ is \emph{stable outside the sink} if any vertex $i\neq n$ is stable.
A configuration $u$ is \emph{positive outside the sink} if for any vertex $i\neq n$, $u_i\geq 0$.
This is also denoted by $u\geq_{\neq n} 0$.
A subset of vertices $A$ is \emph{set-unstable} in a configuration $u$ if $A$ is non-empty, $n\notin A$ and, in the configuration $u'=u-\sum_{a\in A} \laplacianconf{a}$, we have $u'_a \geq 0$ for any $a\in A$.
In other words, $A$ is set-unstable if the toppling of all the vertices of $A$ leads to a configuration whose restriction to $A$ is positive.
If $A$ is a singleton $\{ i \}$, $A$ is set-unstable if and only if $i$ is unstable and hence the toppling of $i$ is legal.
A configuration $u$ is \emph{set-stable} if there is no subset of vertices set-unstable in $u$.
A configuration $u$ is \emph{$n$-parking}, also shorten in \emph{parking}, if $u$ is stable and positive outside the sink and set-stable.
We refer to the literature \cite{dharIntro} for a proof that any configuration $u$ is toppling equivalent to exactly one $n$-parking configuration.
This property implies that the parking configuration $\park(u)$ toppling equivalent to the configuration $u$ is well-defined.
There exists many algorithms to compute the map $u\rightarrow \park(u)$ on any graph.
A recent one is due to Baker and Shokrieh~\cite{bakerShokrieh}.
We will use the existence of such an algorithm in this section but in Section~\ref{sec:optimised-algo} we will design a most efficient one in the case of the complete graphs.
The \emph{stabilization process} of the configuration $u$ consists in toppling one unstable vertex distinct from the sink $n$ while there exists at least one.
A key classical property of the abelian sandpile model~\cite{dharIntro} is that this stabilization process terminates on a configuration denoted $\stabilize(u)$ which is stable outside the sink and do not depend on the hence unspecified order in which the unstable vertices are toppled.
\subsection{A first greedy algorithm computing the rank on complete graphs}
From now on we assume that $G$ is a complete graph $K_n$ with $n\geq 2$.
Let $\onechipconf{i}$ be the configuration with $\onechipconf{i}_i=1$ and for $j\neq i$, $\onechipconf{i}_j=0$.
We consider the following greedy algorithm where the variable $g$ is a configuration on $K_n$:
\begin{center}
\begin{minipage}{15cm}
\framebox{\bf First greedy algorithm for the rank}:\newline
{\bf Input:} A configuration $u$ on $K_n$\newline
$u \leftarrow \park(u)$; $rank \leftarrow -1$; $g\leftarrow 0$;\newline
While $u_n\geq 0$ do let $i\neq n$ such that $u_i=0$ in $u\leftarrow \park(u-\onechipconf{i})$; $g\leftarrow g+\onechipconf{i}$;od;
{\bf Output:} rank ($=\rank(u)$) and $g$ ($\in \proofs{u}$).
\end{minipage}
\end{center}
\begin{proposition}[Correctness of the rank algorithm]\label{prop:correctness-rank} Given any configuration $u$ on $K_n$, the greedy naive algorithm for the rank terminates and returns $\rank(u)$ in the variable $rank$ and the configuration variable $g\in \proofs{u}$ is a proof of this rank.
\end{proposition}
The postponed proof of this proposition requires two main proofs: one for the existence of some vertex $i\neq n$ such that $u_i=0$ in any parking configuration and another one that $g$ is a proof for $\rank(u)$.
The second proof relies on the combination of the two following lemmas: the first is related on symmetries of the complete graph $K_n$ while the other, more general, is probably folklore.
\begin{lemma}[Greedy choice for rank's proof on $K_n$]\label{lem:greedy-choice} Let $u$ be a positive configuration on the complete graph $K_n$ such that there exists a vertex $i$ for which $u_i=0$.
Then there exists a proof $g\in\proofs{u}$ for the rank of $u$ such that $g_i>0$.
\end{lemma}
\begin{lemma}[Subproof for the rank]\label{lem:subproof-rank}
Let $u$ be a configuration on any graph $G$ and $i$ a vertex of $G$.
Assume there is a proof $g$ for the rank of $u$ such that $g_i >0$.
Then any proof $f'$ for the rank of $u'=u-\onechipconf{i}$ leads to a proof $f=f'+\onechipconf{i}$ of the rank of $u$.
\end{lemma}
The possibility in our algorithm of a greedy choice for finding a proof for the rank comes from the numerous symmetries of the complete graph.
Let $\sigma$ be a generic permutation of the set $\permutations{n}$ of permutations on elements of $\{1,2,\ldots n\}$.
The action of $\sigma$ on a configuration $u=(u_i)_{i=1\ldots n}$ is defined by $\sigma.u := (u_{\sigma(i)})_{i=1\ldots n}$.
We gather in the following lemma properties related to symmetries used in this section but also later:
\begin{lemma}[Symetries on $K_n$ and the rank]\label{lem:symetries}
Let $u$ and $v$ be any configuration on $K_n$ and $\sigma$ any permutation of $\permutations{n}$.
We have :
\begin{enumerate}
\item $u$ positive $\iff$ $\sigma.u$ positive,
\item $u\topplingequiv v$ $\iff$ $\sigma.u \topplingequiv \sigma.v$,
\item $u$ effective $\iff$ $\sigma.u$ effective,
\item $g \in \proofs{u}$ $\iff$ $\sigma.g \in \proofs{\sigma.u}$,
\item $\rank(\sigma.u) = \rank(u)$,
\item If $\sigma(n)=n$ (or with a slight abuse of notation $\sigma \in \permutations{n-1}\subset \permutations{n}$) then:
\begin{enumerate}
\item $u$ positive outside the sink $\iff$ $\sigma.u$ positive outside the sink,
\item $u$ set-stable $\iff$ $\sigma.u$ set-stable,
\item $u$ parking $\iff$ $\sigma.u$ parking.
\item $\park(\sigma.u) = \sigma.\park(u)$
\end{enumerate}
\end{enumerate}
\end{lemma}
Now we listed the required lemmas to prove the correctness of the algorithm, we use another schedule to prove them.
\begin{proof}(of Lemma~\ref{lem:symetries}: Symmetries on $K_n$ and the rank)
$(1)$ is straightforward.
We remark that $\sigma$ acts also nicely on the configurations $\laplacianconf{i}$, hence $u= v-\sum_{i} a_i \laplacianconf{i} \iff \sigma.u=\sigma.v-\sum_{i} a_i\laplacianconf{\sigma(i)}$.
This remark leads to $(2)$;
$(1)$ and $(2)$ imply $(3)$.
The following paragraph proves $(4)$.
If $g\in \proofs{u}$ then $u-g$ is non-effective and for any positive configuration $f$ such that $\degree(f) < \degree(g)$, $u-f$ is effective.
From $(3)$ we deduce that $\sigma.u-\sigma.g$ is non-effective and for any positive configuration $f$ such that $\degree(f) < \degree(g)$, $\sigma.u-\sigma.f$ is effective.
Since $\{f|f\geq 0,\degree(f) < \degree(g)\} = \{\sigma.f|\sigma.f\geq 0, \degree(\sigma.f)<\degree(\sigma.g)\}$ we deduce that $\sigma.g\in \proofs{\sigma.u}$. Conversely, for the opposite implication of $(4)$ we use similarly $\sigma^{-1}$, the inverse permutation of $\sigma$.
$(4)$ implies $(5)$.
The proof of $(6.(a))$ is similar to the proof $(1)$ and the proof of $(6.(b))$ to the proof of $(2)$: the single additional remark is that the sink vertex $n$ is simultaneously excluded from the set-unstable set of vertices and a fix-point of $\sigma\in \permutations{n-1} \subset \permutations{n}$.
$(6.(a))$ and $(6.(b))$ imply $(6.(c))$.
We have $\park(u)=u-\sum_{i} a_i\laplacianconf{i}$ hence like in the proof of $(2)$, $\sigma.\park(u) = \sigma.u - \sum_{i} a_i\laplacianconf{\sigma(i)}$ where $\sigma.\park(u)$ is parking according to $(6.(c))$ and toppling equivalent to $\sigma.u$ hence $\park(\sigma.u)=\sigma.\park(u)$.
\end{proof}
\begin{proof}(of Lemma~\ref{lem:greedy-choice} Greedy choice for rank's proof on $K_n$)
Let $f\in \proofs{u}$.
If $f_i > 0$ then $g=f$ concludes the proof.
In the remaining case, we have $f_i=0$.
Since $f$ is a proof, $u-f$ is non-effective hence there exists a vertex $j$ such that $u_j-f_j <0$.
We have $j\neq i$ since $u_i-f_i=0-0$.
We will show that $g=f+(f_j-u_j)(\onechipconf{i}-\onechipconf{j})$ is the expected proof for the rank of $u$.
By definition, $g_i=f_j-u_j > 0$ and more generally $g$ is positive and $\degree(g)=\degree(f)$.
Hence it simply remains to show that $u-g$ is non-effective.
We consider $u'=u-f+(f_j-u_j)\onechipconf{j}.$
Let $\sigma=(ij)$ the transposition of $\permutations{n}$ which exchanges $i$ and $j$: $\sigma(i)=j$, $\sigma(j)=i$ and otherwise $\sigma(k)=k$.
By definition $u'_j=u_j-f_j+(f_j-u_j)=0$ and $u'_i=0-0=0$, so $\sigma.u' = u'$.
Hence:
$$ \sigma.(u-g) = \sigma.(u-f-(f_j-u_j)(\onechipconf{i}-\onechipconf{j}))=\sigma.(u'-(f_j-u_j)\onechipconf{i}) = u'-(f_j-u_j)\onechipconf{j} = u-f.$$
Using $ \sigma.(u-g) = u-f$ and $(3)$ in lemma~\ref{lem:symetries} we deduce as expected that like $u-f$, $u-g$ is non-effective.
\end{proof}
\begin{proof}(of Lemma~\ref{lem:subproof-rank} Subproof for the rank)
Let $g$ a proof of $u$ such that $g_i >0$ and $f'$ a proof of $u'=u-\onechipconf{i}$.
On one hand, $u'-f'=u-(f'+\onechipconf{i})$ is non-effective so by definition of $g$, $\degree(f')+1 \geq \degree(g)$.
On the other hand, $u'-\onechipconf{i})=u-g$ is non-effective and $g-\epsilon^{(i)}$ is positive so by definition of $f'$ $\deg(g)-1 \geq \deg(f')$.
Joining these hands, $\degree(f')=\degree(g)-1$.
Since $f=f'+\onechipconf{i}$ is of degree $\degree(g)$ and $u-f=u'-f'$ is non effective, $f$ is a proof for the rank of $u$.
\end{proof}
\begin{proof}(of Proposition~\ref{prop:correctness-rank} Correctness of the rank algorithm)
First, if $u$ is a parking configuration on $K_n$ there exists a vertex $i$ distinct from the sink such that $u_i=0$.
Indeed we obtain a contradiction if for any $i\neq n$, $u_i \neq 0$.
Since $u$ is positive outside of the sink, it means that $u_i\geq 1$.
Hence $A=\{1,2,\ldots n-1\} = V-\{n\}$ is a set-unstable set.
This is in contradiction with the assumption that $u$ is parking.
We conclude the proof of correctness by an induction on the rank of the given configuration $u$.
If $\rank(u) = -1$, the configuration $u$ is non-effective so, according to Lemma~\ref{lem:eff_on_park}, $\park(u)$ has a negative value on the sink then the algorithm skips the while-loop and returns $rank=-1$ and $g=0$ as expected.
Let $m\geq 0$.
We assume that the algorithm is correct on any given configuration of rank at most $m-1$.
Let $u$ be a configuration of rank $m$, $v=\park(u)$ and $i$ the first chosen vertex by the algorithm such that $v_i=0$.
Lemma~\ref{lem:greedy-choice} on the greedy choice for the rank implies the existence of a proof $g$ for the rank of $u$ such that $g_i>0$ and so $g-\onechipconf{i}$ is positive.
Since $v-g = (v-\onechipconf{i}) - (g-\onechipconf{i})$ is non-effective, the rank of $v-\onechipconf{i}$ is at most $m-1$.
Our inductive assumption implies that the algorithm applied to $v-\onechipconf{i}$ leads to a proof $f$ of its rank.
Applying Lemma~\ref{lem:subproof-rank} about subproofs for the rank, the configuration $f+\onechipconf{i}$ is a proof for the rank of the given $u$.
This is also the value in the variable $g$ at the end of the run given the configuration $u$.
\end{proof}
% SKIPPED Discussion on complexities
\section{An algorithm of linear arithmetic complexity\label{sec:optimised-algo}}
In this section we optimize the correct greedy naive algorithm.
Subsection~\ref{subsec:compact-sorted} explains how to restrict quickly the algorithms to the manipulation of configurations soon defined and called compact and sorted.
Subsection~\ref{subsec:conf2skcyl} motivates this restriction by a bijection between these compact and sorted configurations and pointed cut skew cylinders.
This second class of combinatorial objects may be encoded by a Dyck word and one up to three integers.
In the algorithms computing the rank or the parking configurations, atomic updates or tests on configurations admits more regular interpretations in terms of pointed cut skew cylinders.
Subsection~\ref{subsec:formula-rank} translates a possible run of the algorithm for the rank into a simple partial spiral traversal in the cut skew cylinder.
The analysis of this traversal leads to an explicit formula for the rank of a sorted and parking configuration based on a single euclidean division.
Subsection~\ref{subsec:searchparking} describes an algorithm adapted to the complete graph to find the parking configuration toppling equivalent to any given configuration.
We conclude this section by discussing the details of a possible implementation in linear arithmetic complexity of an algorithm computing the rank of any configuration on $K_n$.
\subsection{Restriction to compact and sorted configurations} \label{subsec:compact-sorted}
The distinguished sink $n$ on $K_n$ implies that we frequently manipulate configurations where the sink is the only particular case.
We often abbreviate a configuration $u=(u_1,\ldots u_n)$ into $(u_i;u_n)$ which means implicitly that the variable $i$, part of the notation, runs from $1$ to $n-1$.
Our next definition illustrates this notation.
The \emph{compacted} configuration $u^c$ of $u$ is the configuration
$$\compact(u) := u^c := ( (u_i-u_n)\mod n;\degree(u)-\sum_{i=1}^{n-1} u^c_i).$$
In other words, for $i=1\ldots n-1$, $u^c_i := (u_i-u_n)\mod n$ and for $i=n$, $u^c_n:=\degree(u)-\sum_{i=1}^{n-1} u^c_i$.
\begin{lemma}\label{lem:compact}(Compact configuration on $K_n$)
For any configuration $u$ on $K_n$, we have $\compact(u) \topplingequiv u$.
\end{lemma}
\begin{proof}
On one hand, we topple $u_n$ times each vertex different from the sink in the configuration $u$ to obtain
$$ u \topplingequiv (u_i;u_n)-\sum_{j=1}^{n-1}u_n\laplacianconf{j} = (u_i-u_n;nu_n).$$
On the other hand, by definition of $u^c:=\compact(u)$ there exists $(k_1,\ldots,k_{n-1})\in \mathbb{Z}^n$ such that for $i\neq n$, $u_i-u_n=u^c_i+k_in$.
Joining the hands, $u\topplingequiv (u^c_i+k_in;nu_n)$.
Then we consider
$$ (u^c_i+k_in;nu_n)-\sum_{j\neq n} k_j(\laplacianconf{j}-\laplacianconf{n}) = (u_i^c;nu_n-n\sum_{j\neq n}k_j) = (u^c_i;\degree(u)-\sum_{j\neq n} u^c_j)$$
where $k_i(\laplacianconf{i}-\laplacianconf{n})$ cancels $k_in$ in $u_i^c+k_in$ and $\degree(u)$ is introduced using that topplings preserve the degree of configurations.
The rightmost term is the preceding sequence of equalities is $\compact(u)$ which is hence proved to be toppling equivalent to $u$.
\end{proof}
This definition of $\compact(u)$ particular to the complete graphs is inspired by a work on general graphs of Dhar, Ruelle and, Verma~\cite{dharRuelleVerma}.
One find similar ideas also in~\cite{bakerShokrieh}.
We observe that $\compact(u)$ can be quickly computed, it is positive and stable outside of the sink but not necessarily equal to $\stabilize(u)$.
A configuration $u$ on $K_n$ is \emph{compact} if $$\max_{i\neq n,j\neq n}|u_i-u_j|\leq n.$$
It is straightforward that the configuration $\compact(u)$ is compact.
Moreover, most of the configurations appearing in the optimized algorithms are compacts.
Another aspect of the optimization consists in working at the level of orbits under the action of $\permutations{n-1}\subset \permutations{n}$ permuting the vertices $1,2,\ldots n-1$ distinct from the sink.
The representative of the orbit of $u$ will be the defined below $\sort(u)$ sorted configuration.
A configuration $u$ is \emph{sorted} if $u_1,\ldots u_{n-1}$ is weakly increasing: for $i=2\ldots n-1$, $u_{i-1}\leq u_i$.
Notice that there is no constraint on $u_n$.
The configuration $\sort(u)$ is obtained by sorting in weakly increasing order of the first $n-1$ entries of the configuration $u$.
We also combine the action of $S_{n-1}$ and the toppling equivalence.
Two configurations $u$ and $v$ on $K_n$ are \emph{toppling and permuting equivalent}, denoted $u\topplingpermutingequivalent v$ if there exists a permutation $\sigma\in \permutations{n-1}\subset\permutations{n}$ such that $u$ and $\sigma.v$ are toppling equivalent.
\begin{lemma}(compatibilities for toppling and permuting equivalence)\newline\label{lem:sortedparking}$(1).$ The relation $\topplingpermutingequivalent$ is an equivalence relation.\newline
$(2).$ Moreover, for any configuration $u$, there exists a unique sorted and parking configuration $v := \sort(\park(u))$ toppling and permuting equivalent to $u$.
\end{lemma}
\begin{proof}
$(1).$ The relation is symmetric mainly according to the second of the following equivalences:
\begin{align}
u \topplingpermutingequivalent v & \iff \exists \sigma\in \permutations{n-1},\exists(a_i)_i\in \mathbb{Z}, \sigma.u = v-\sum_{i=1}^n a_i\laplacianconf{i} \nonumber\\
&\iff \exists \sigma\in \permutations{n-1},\exists(a_i)_i\in \mathbb{Z}, \sigma^{-1}.v = u-\sum_{i=1}^n (-a_{\sigma^{-1}(i)})\laplacianconf{\sigma^{-1}(i)} \nonumber\\
&\iff v \topplingpermutingequivalent u \nonumber
\end{align}
The transitivity of the relation comes from the composition of permutations. Let $\sigma.u=v-\sum_{i=1}^n a_i\laplacianconf{i}$ and $\tau.v = w - \sum_{i=1}^n b_i\laplacianconf{i}$ then
$$ (\tau \circ \sigma).u = w - \sum_{i=1}^n (b_i-a_{\tau^{-1}(i)})\laplacianconf{i}.$$
$(2).$ The existence of a sorted parking configuration toppling and permuting equivalent to $u$ is straightforward since by definition $\sort(\park(u))$ is such a configuration.
Our proof of the uniqueness considers two configurations $u$ and $v$ toppling and permuting equivalent.
By assumption, there is a permutation $\sigma\in \permutations{n-1}$ such that $\sigma.u$ is toppling equivalent to $v$.
The uniqueness of the parking configuration in a toppling equivalent class implies that $\park(\sigma.u)=\park(v)$.
Using the identity $6.(d)$ of Lemma~\ref{lem:symetries} on symmetries of $K_n$, we deduce that $\sigma.\park(u)=\park(v)$ hence $\sort(\park(u))=\sort(\park(v))$ as expected.
\end{proof}
\subsection{From sorted and compact configurations to pointed cut skew cylinders \label{subsec:conf2skcyl}}
The parking configurations on the complete graph $K_n$ admits a more explicit description which explains the adjective parking.
A \emph{parking function} of size $n$ is a map $f$ from $\{1,2,\ldots n\}$ to $\mathbb{Z}$ such that for $i=1\ldots n-1$, $f(i)\geq 0$ and for $j=1\ldots n$, $|\{i|f(i) \geq j\}| \leq n-j$.
%The existence of a superunstable set in a configuration positive outside of the sink on $K_n$ admits the following translation\cite{}.
It was already noticed in~\cite{coriRossin} that a configuration $u$ on $K_n$ is parking if and only if $f$ defined by $(f(i))_{i=1\ldots n-1} := (u_i)_{i=1\ldots n-1}$ is a parking function of size $n-1$.
We already observed that $u$ is parking if and only if $\sigma.u$ where $\sigma\in S_{n-1}\subset S_n$, in particular $\sort(u)$, is parking.
Sorting simplifies the checking: a sorted configuration $u$ is parking if and only if for $i=1\ldots n-1$, $0\leq u_i < i$.
Until now, we manipulated the configurations as vectors in $\mathbb{Z}^n$.
We introduce an alternative description of sorted and compact configurations on $K_n$ which will simplify our analysis.
This description requires some (painful but then rewarding) preliminaries.
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.9]
\draw (-8, 0) grid (9, 5.2);
\foreach \s/\x/\y/\color in {40/-7/0/black,46/-7/1/black,52/-7/2/black,58/-7/3/black,64/-7/4/black,70/-7/5/blue,35/-6/0/black,41/-6/1/black,47/-6/2/black,53/-6/3/black,59/-6/4/black,65/-6/5/blue,30/-5/0/black,36/-5/1/black,42/-5/2/black,48/-5/3/black,54/-5/4/black,60/-5/5/blue,25/-4/0/black,31/-4/1/black,37/-4/2/black,43/-4/3/black,49/-4/4/black,55/-4/5/blue,20/-3/0/black,26/-3/1/black,32/-3/2/black,38/-3/3/black,44/-3/4/black,50/-3/5/blue,15/-2/0/black,21/-2/1/black,27/-2/2/black,33/-2/3/black,39/-2/4/black,45/-2/5/blue,10/-1/0/black,16/-1/1/black,22/-1/2/black,28/-1/3/black,34/-1/4/black,40/-1/5/blue,5/0/0/black,11/0/1/black,17/0/2/black,23/0/3/black,29/0/4/black,35/0/5/blue,0/1/0/black,6/1/1/black,12/1/2/black,18/1/3/black,24/1/4/black,30/1/5/blue,1/2/1/black,7/2/2/black,13/2/3/black,19/2/4/black,25/2/5/blue,2/3/2/black,8/3/3/black,14/3/4/black,20/3/5/blue,3/4/3/black,9/4/4/black,15/4/5/blue,4/5/4/black,10/5/5/blue,5/6/5/blue,0/7/5/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {5/2/0/black,10/3/0/black,4/3/1/black,15/4/0/black,9/4/1/black,3/4/2/black,20/5/0/black,14/5/1/black,8/5/2/black,2/5/3/black,25/6/0/black,19/6/1/black,13/6/2/black,7/6/3/black,1/6/4/black,30/7/0/black,24/7/1/black,18/7/2/black,12/7/3/black,6/7/4/black,35/8/0/black,29/8/1/black,23/8/2/black,17/8/3/black,11/8/4/black,5/8/5/blue,40/9/0/black,34/9/1/black,28/9/2/black,22/9/3/black,16/9/4/black,10/9/5/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
% blue cut
\draw[line width=2,draw=blue] (-1,0) -- (-1,1) -- (0,1) -- (0,3) -- (1,3) -- (1,4) -- (3,4) -- (3,5) -- (5,5);
\draw[line width=1,draw=blue,dashed] (-1,0) -- (4,5);
% magenta cut: TODO
\draw[line width=2,draw=magenta] (1,0) -- (1,1) -- (2,1) -- (2,2) -- (5,2) -- (5,4) -- (7,4) -- (7,5);
\draw[line width=1,draw=magenta,dashed] (5,2) -- (8,5);
\draw[line width=1,draw=magenta,dashed] (2,0) -- (4,2);
% green segment
\foreach \y/\i in {3/1,4/2} {
\draw[line width=2,draw=green,->] (-1,\y) -- (-1,\y+1);
\draw node[green] at (-1.5,\y+.5) {\small{$a_{\oriented{28}\i}$}};
}
\foreach \y/\i in {0/3,1/4,2/5} {
\draw[line width=2,draw=green,->] (-7,\y) -- (-7,\y+1);
\draw node[green] at (-7.5,\y+.5) {\small{$a_{\oriented{28}\i}$}};
}
% red segment
\foreach \y/\i in {0/1,1/2,2/3,3/4,4/5} {
\draw[line width=2,draw=red,->] (-3,\y) -- (-3,\y+1);
\draw node[red] at (-3.5,\y+.5) {\small{$a_{\oriented{20}\i}$}};
}
% orange segment
\foreach \y/\i in {0/1,1/2,2/3,3/4,4/5} {
\draw[line width=2,draw=orange,->] (9,\y) -- (9,\y+1);
\draw node[orange] at (8.5,\y+.5) {\small{$a_{\oriented{\overline{40}}\i}$}};
}
\end{tikzpicture}
\caption{Skew cylinder of circumference $6$, two of its cuts and three oriented segments.\label{fig:defscompact}}
\end{center}
\end{figure}
The \emph{skew cylinder} of circumference $n$ is a kind of skewed two dimensional grid embedded in a cylinder.
A first precise definition considers the quotient of the usual grid of $\mathbb{Z}^2$ where each vertex of integer coordinates $(x,y)$ admits the four neighbours $\{(x+1,y),(x-1,y),(x,y+1),(x,y-1)\}$ by the equivalent relation $(x,y) \equiv (x',y')$ if there exists $k\in\mathbb{Z}$ such that $(x',y')=(x+kn,y+k(n-1))$.
A possible notation for this is $\mathbb{Z}^2/(n,n-1)\mathbb{Z}$.
We fix our notation on a second precise and more explicit definition of skew cylinder which has the drawback to partially hide the invariance by translation.
This definition is illustrated by the example in Figure~\ref{fig:defscompact}.
The \emph{strip} of $n-1$ rows is the subgraph of the usual two dimensional grid $\mathbb{Z}^2$ induced by the vertices $\{(x,y)| x\in \mathbb{Z}, 0 \leq y \leq n-1\}$.
The two-dimensional of \emph{cell} coordinates $(x,y)\in\mathbb{Z}^2$ is the unit square which corners are $\{(x,y),(x-1,y),(x-1,y+1),(x,y+1)\}$.
In other words the two-dimensional coordinates of a cell are the coordinates of its south-east corner.
For a cell $c$ we denote by $(x(c),y(c))$ its two-dimensional coordinates.
We will use the \emph{spiral coordinate} as an alternative coordinate for the cells of the strip.
The cell of two dimensional coordinate $(0,0)$ is labeled by the spiral coordinate $0\in\mathbb{Z}$, then we label the cells, incrementing the spiral coordinate, from south-west to north-east in the cells along the diagonal in north-east direction, then the next diagonal is the next on the west.
This \emph{spiral traversal} labels all the cells of spiral coordinate $k\in \mathbb{N}$.
In Figure~\ref{fig:defscompact}, the spiral coordinate of each cell is indicated by the small number written in the south-west corner.
Negative coordinate $-x$ is written $\overline{x}$ for graphical purpose.
This number is blue for partial cells in the top row and means that these are repetitions of the cells on the bottom row.
In the opposite direction and starting from the cell $(0,0)$, the reversed spiral traversal labels all the cells with a non-positive spiral coordinate.
Hence, this spiral traversal defines a bijection between the cells of the strip of $n-1$ rows and $\mathbb{Z}$.
We frequently use the cell (of spiral coordinate) $k\in \mathbb{Z}$ and the vertex (of spiral coordinate) $k$ which is the south-east corner of this cell $k$.
A more operational description is that the cell of two dimensional coordinates $(x,y)$ in the strip has spiral coordinate $ny-(n-1)x$ and the cell of spiral coordinate $k\in\mathbb{Z}$ has two dimensional coordinates $(r-q,r)$ where $k=q(n-1)+r$ is the euclidean division of $k$ by $n-1$.
We turn this strip into the skew cylinder of circumference $n$ by an identification of the vertices of coordinates $(x,0)$ and $(x+n,n-1)$ which implies that the south side of the cell $(x,0)$ is also the north side of the cell $(x+n-1,n-2)$.
In a word $w$, we denote by $|w|_x$ the number of occurrences of the letter $x$.
An \emph{almost balanced word} of size $n$ is a word on the alphabet $\{a,b\}$ such that $|w|_a=n-1$ and $|w|_b=n$.
Let $\almostbalancedword_n$ denotes the set of almost balanced words of size $n$.
Given a vertex $k\in \mathbb{Z}$ in the skew cylinder of circumference $n$ and a word $w$ on the two-letter alphabet $\{a,b\}$, the \emph{embedding of the word $w$ at vertex $k$} is the \emph{path} starting from vertex $k$ and such that an occurrence of letter $a$ in $w$ corresponds to a unit north step and an occurrence of letter $b$ to a unit east step.
The \emph{cell of a north step} in such a path is the cell whose east side is the north step.
We first observe that the embedding at vertex $m\in\mathbb{Z}$ of an almost balanced word $w\in\almostbalancedword_n$ in the skew cylinder of circumference $n$ also ends at vertex $m$.
This defines a (self-avoiding) loop that we call a \emph{cut}.
The resulting \emph{cut skew cylinder} is denoted by $\cutskewcylinder{m}{w}$.
In Figure~\ref{fig:defscompact}, the blue path is a cut defining $\cutskewcylinder{10}{abaababbabb}$ and the magenta path is a cut defining $\cutskewcylinder{2}{bbaabbaabab}=\cutskewcylinder{-3}{baabbaababb}$.
\begin{definition}
A cut skew cylinder $\cutskewcylinder{m}{w}$ and two additional integers $k\in\mathbb{Z}$ and $s\in\mathbb{Z}$ allow the definition of a configuration on $K_n$
$$ \scompact{k}{m}{w}{s} := (u_i;u_n) = (x(a_i)-x(a_{\oriented{k}i});s)$$
where the $a_{\oriented{k}i}$ for $i=1\ldots n-1$ are the $n-1$ north steps of the \emph{oriented segment} which is the embedding of the word $a^{n-1}$ at vertex $k$, and $a_i$ is the north step of the cut on $\cutskewcylinder{m}{w}$ which crosses the same row as the north step $a_{\oriented{k}i}$ and $x(.)$ is the first coordinate of the two-dimensional coordinates of the starting vertex of a step.
\end{definition}
In Figure~\ref{fig:defscompact}, there are three oriented segments: the red one starts from $20$, the orange one from $-40$ and the green one from $28$.
The last one is drawn into two green lines since it visits the two copies of the vertex $40$.
The red oriented segment, the blue cut and the integer $39$ define the configuration
$$ \scompact{20}{10}{abaababbabb}{39} = (2,3,3,4,6;39)$$
$$= (x(10)-x(20),x(11)-x(26),x(17)-x(32),x(18)-x(38),x(14)-x(44);39).$$
The properties of the description $\scompact{k}{m}{w}{s}$ require additional preliminary definitions.
Two cells are connected in a cut skew cylinder if they share a common side which is not a step of the cut.
In the cut skew cylinder $\cutskewcylinder{m}{w}$ there are two connected components of cells: the \emph{left component} $\leftcutskewcylinder{m}{w}$, which contains the cell $m$, and the other called the \emph{right component} $\rightcutskewcylinder{m}{w}$.
A cell is \emph{left} if it belongs to $\leftcutskewcylinder{m}{w}$ and \emph{right} otherwise.
A \emph{Dyck word} of size $n$ is a word $w$ on the two-letters alphabet $A=\{a,b\}$ where for any prefix $p$ of $w$, $|p|_a\geq |p|_b$ and in addition $|w|_a=|w|_b=n$.
Any factorization $w=w'w''$ defines a cyclic conjugate $v=w''w'$ of the word $w$.
The classical cyclic lemma due to Dvoreztky and Motzkin~\cite{dvoMotzk} states that among the $2n-1$ distinct cyclic conjugates of an almost balanced word $w\in \almostbalancedword_n$ exactly one may be written $vb$ where $v$ is a Dyck word of size $n-1$.
We recover this lemma in our setting.
In Figure~\ref{fig:defscompact}, a dashed line indicates the Dyck factor $abaababbab$ respectively $aabbaababb$ in the cyclic conjugate for the blue, respectively magenta, cut.
A first indication is that pairs $(w,s)$ where $w$ is a Dyck word of size $n-1$ and $s\in\mathbb{Z}$ are in classical bijection with sorted parking configurations on $K_n$ as follows.
$$ (u_i;u_n) = (\sum_{j=1}^i k_j;s) \leftrightarrow (w,s) = (ab^{u_2-u_1}ab^{u_3-u_2}\ldots ab^{u_{n-1}-u_{n-2}}ab^{n-1-u_{n-1}},u_n)$$
where\footnote{Remark that $k_1=0$ and $u_1=0$} $w=b^{k_1}ab^{k_2}ab^{k_3}\ldots ab^{k_n}$.
This bijection translates the fact that in a sorted parking configuration $u$ we have $0\leq u_i * k-1 \iff l_i \geq k$.
Moreover, $u_1=0$ so $k=l_1\in \leftcutskewcylinder{m}{w}$ and $k=\min \leftcutskewcylinder{m}{w}$.
Conversely, we suppose that $k=\min \leftcutskewcylinder{m}{w}$.
The cut is made of east or south steps so $k\in \leftcutskewcylinder{m}{w}$ implies recursively via the north sides of cells that $k+n(i-1) \in \leftcutskewcylinder{m}{w}$ for $i=1,\ldots, n-1$.
Combined with the backward equivalences of the previous argument we have $k \leq l_i \leq k+n(i-1)$ and so $0\leq u_i ** s\mbox{ and } s'\in \leftcutskewcylinder{vb}{s}\}$ which is the minimal spiral coordinate strictly greater than $s$ of a left cell in $\cutskewcylinder{m}{vb}$.
\begin{center}
\begin{minipage}{15cm}
\framebox{\bf Algorithms for the rank via a spiral traversal on a cut skew cylinder:}\newline
{\bf Input:} A sorted parking configuration $u=\scompact{m}{m}{vb}{s}$ on $K_n$.\newline
$rank = \leftarrow -1$;\newline
For $k$ from $m$ to $F(u)$ do\newline
\_\_\_\_ if $k$ is a left cell $(k\in \leftcutskewcylinder{m}{vb})$ then $rank\leftarrow rank+1$; od;\newline
{\bf Output:} $rank (=\rank(u))$.
\end{minipage}
\end{center}
\begin{center}
\begin{figure}[ht!]
\begin{tikzpicture}[scale=0.55]
\draw[black!30!white] (0,0) grid (10, 10);
\draw[->,line width = 1,dashed] (0,0) -> (10, 10);
\draw[->, line width = 1,dashed,blue] (0, -1) -> (0,12);
\draw[->,line width = 1,dashed,blue] (-4, 0)--(11, 0);
\foreach \x/\fx in {0/0,1/0,2/0,3/1,4/1,5/1,6/4,7/7,8/7,9/9}{
\draw node at (\x+0.5,12+1) {$\fx$};}
\draw node at (11, 13){\tikz{\draw[line width = 2] (0,0) circle (0.3);\draw node at (0,0) {$26$};}};
\foreach \x/\fx/\fnx in {0/0/0,0/1/0,0/2/1,1/3/1,1/4/1,1/5/4,4/6/7,7/7/7,7/8/9,9/9/10}{
\draw[blue,line width=2] (\x,\fx) -- (\x,\fx+1);
\draw[blue,line width=2] (\x,\fx+1) -- (\fnx,\fx+1);
}
%\draw[blue,line width=0,opacity=0.15,fill=blue] (\x,0) rectangle (\fx+1, \x);
\draw[black!30!white](-4,0) grid (0, 10);
\foreach \x/\y/\color/\currentsink in {0/0/green/0,1/1/white/1,2/2/white/2,3/3/white/3,4/4/white/4,5/5/white/5,6/6/white/6,7/7/green/7,8/8/white/8,9/9/green/9,0/-1/green/10,1/0/green/11,2/1/white/12,3/2/white/13,4/3/white/14,5/4/white/15,6/5/white/16,7/6/green/17,8/7/green/18,9/8/green/19,0/-2/green/20,1/-1/green/21,2/0/green/22,3/1/green/23,4/2/white/24,5/3/white/25,6/4/green/26}{
\draw node[black] at (\y-0.5,\x+0.5) {\small $\currentsink$};
}
\foreach \x/\y in {0/0,7/7,9/9,0/-1,1/0,7/6,8/7,9/8,0/-2,1/-1,2/0,3/1,6/4}{
\draw[opacity=0.6,fill=green,draw=green] (\y-0.5,\x+0.5) circle (0.4);
}
\foreach \x/\rx in {1/3,2/2,3/1,4/1,5/0,6/0,7/1,8/2,9/1,10/2}{
\draw[green!50!brown] node at (12,\x-0.1,) {$\rx$};
}
\draw[green!50!brown] node at (12,-0.5) {$=13$};
\draw[line width=0.7] (10,7) -- ( -4.8,7);
\draw[->,line width=2] (-5,0) -> (-5,7);
\draw node at (-6.2,3.5) {$R=7$};
\draw[->,line width=2] (10,10.6) -> (7,10.6);
\draw node at (8.5,11.5) {$Q=2$};
\end{tikzpicture}
\caption{Calculation of the rank on a Dyck path}
\label{fig:calcRank}
\end{figure}
\end{center}
We use two versions of this algorithm corresponding to the two distinct definitions of $F(u)$.
If $F(u):=\nextleftcell{m}{vb}{m+s}-1$, it defines the \emph{extended spiral traversal for the rank}.
If $F(u):=m+s$, it defines the \emph{shortest spiral traversal for the rank}.
In Figure~\ref{fig:calcRank}, we labeled the cells visited by the shortest spiral traversal for the rank of
$$u=(0,0,0,1,1,1,4,7,7,9;26)=\scompact{0}{0}{aaabaaabbbabbbaabbabb}{26}.$$
The $14$ visited cells in the left component contains a green disk so the returned value for the rank is $13$.
These two versions of the spiral traversal produce exactly the same values since all the additional cell visited in the extended version belongs to the right component by definition of $\nextleftcell{m}{vb}{m+s}$.
The extended spiral is closer to the algorithm selecting a run for the rank while the shortest spiral induces more symmetries in the forthcoming the enumerative studies.
This paragraph consider the connection between the extended spiral traversal for the rank and the selected run on sorted configurations for the rank.
We discuss the beginning of this spiral traversal, if any.
If $s<0$, then $\nextleftcell{m}{vb}{m+s} \leq m$ so there is no loop iteration and the output $rank=-1$ as expected.
Otherwise, let $j=\nextleftcell{m}{vb}{m}$.
We consider the iterations for $k$ from $m$ to $j-1$.
It visits $j-m$ cells $m$,$m+1$,\ldots $j-1$ where $m$ is a left cell and all other cells are right while $j$ is the next left cell.
This part may be interpreted as the computation of $\sort(\park(\E.u))=\scompact{j}{j}{gabfb}{s-(j-m)}$ as described by $8.$ in Proposition~\ref{prop:convert}: move via operator $\E$ the left cell $m=\min \leftcutskewcylinder{m}{vb}$ to the right component, increment the rank, then visit via operator $\T^{-1}$ all the $j-m$ cells starting at $m$ in spiral order until you find the next left cell $j=\min \leftcutskewcylinder{j}{gabfb}$.
In addition, the value of $s$ is decremented at each visit of a cell so we have $\nextleftcell{m}{vb}{m+s}=\nextleftcell{j}{gabfb}{j+s}$.
Hence, by induction, we observe that this traversal simulates the run of the sorted version of the correct algorithm.
\begin{proposition}(Reading a proof for the rank using spiral traversals)
Let $u=\scompact{m}{m}{vb}{s}$ be a sorted parking configuration.
The extended spiral traversal for the rank on $\cutskewcylinder{m}{vb}$ returns $\rank(u)$.
\end{proposition}
\begin{proof}
The discussion preceding this proposition shows that the correct algorithm on sorted configurations with input $u$ is simulated by the traversal algorithm on $\cutskewcylinder{m}{vb}$ so that both return $\rank(u)$.
\end{proof}
We recall that by definition all the cells of spiral indices from $m+s+1$ to $\nextleftcell{m}{vb}{s}-1$, if any, are right cells so the extended and shortest spiral traversals, which differs only by these cells, returns the same value.
We can also recover from the shortest traversal a proof $g$ for the rank of the sorted parking configuration $u=\scompact{m}{m}{vb}{s}$.
For a cut skew cylinder and $i=1\ldots n-1$ we define the set $\leftcellonrowi{m}{vb}{i}{s}$ of left cells of spiral coordinate at most $m+s$ and on the same row as the step related to $a_{\oriented{m}i}$ the $i$-th step of the oriented segment $a^{n-1}$ starting at $m$.
\begin{proposition}(Reading a proof for rank in spiral traversals) \label{prop:read-proof}
Let $u=\scompact{m}{m}{vb}{s}$ be a sorted parking configuration on $K_n$.
The configuration $g=(g_i;g_n) := (|\leftcellonrowi{m}{vb}{i}{s}|;0)$ is a proof for $\rank(u)$.
\end{proposition}
\begin{proof}
In the correspondence between the selected run on sorted configurations and the extended traversal, a grain $\epsilon^{(i)}$ is removed on the vertex $i$ each time a cell of the row related to $u_i$ is moved from the left to the right component.
All such left cells are the left cells in $\leftcutskewcylinder{m}{vb}$ of spiral coordinate between $m$ and $m+s$ since between $m+s+1$ and $m+\nextleftcell{m}{vb}{m+s}-1$ there are only right cells, if any.
When those cells are partitioned into rows, it corresponds exactly to the definition of $\leftcellonrowi{m}{vb}{i}{s}$.
Hence $g_i$ count the number of removed grains on vertex $i$ during the algorithm so $g$ is a proof for the rank of $u$ according to the sorted version of the correct greedy naive algorithm.
\end{proof}
It appears that the $(|\leftcellonrowi{m}{vb}{i}{s}|)_{i=1\ldots n-1}$ may be efficiently computed via a single euclidean division.
\begin{theorem}\label{theo:rank-formula}(Formula for the rank of a sorted parking configuration)
Let $u$ be a sorted parking configuration on $K_n$ and $u_n+1 = q(n-1)+r$ the euclidean division of $u_n+1$ by $n-1$.
$$ \rank(u) = \left(\sum_{i=1}^{n-1} \max(0,q-i+1+u_i+\test{i\leq r} \right)-1 $$
and the proof for the rank found from the algorithm selecting a run for the rank by collecting removed grains is
$$ g = (\max(0,q-i+1+u_i+\test{i\leq r};0).$$
\end{theorem}
\begin{proof}
Let $u=\scompact{m}{m}{vb}{s}$ with $s=u_{n}$.
In this proof, we consider that the visited cells during the traversal algorithm are exactly the cells with spiral coordinate from $m$ to $m+s$, if any.
It means that we deliberately ignore the cells of spiral coordinates from $m+s+1$ to $m+\nextleftcell{m}{vb}{m+s}-1$.
These cells are necessarily right cells by definition of $\nextleftcell{m}{vb}{m+s}$.
With this convention, the number of visited cells on the row crossed by $a_{\oriented{m}i}$ is $q+\test{i\leq r}$.
Moreover, on this row the traversal begins by visiting all the right cells of spiral coordinate at least $m$.
These cells are counted by $i-1-u_i\geq 0$ by definition of $\scompact{m}{m}{vb}{s}$.
We conclude that $$|\leftcellonrowi{m}{vb}{i}{s}| = \max(0,(q+\test{i\leq r})-(i-1-u_i))$$ since the visited left cell on the row crossed by $a_{\oriented{m}i}$ are the visited cells minus the possibly first visited right cells.
This shows that $g$ is the proof computed by the traversal algorithm and a summation leads to the formula for the rank.
\end{proof}
\subsection{Optimizing the search of the equivalent sorted parking configuration\label{subsec:searchparking}}
We describe here an efficient algorithm to compute for any configuration $u$ on $K_n$ the toppling and permuting equivalent configuration $ \sort(\park(u))$.
%Then we will apply to its result the efficient formula of the preceeding subsection to compute with a linear arithmetic complexity the rank of any configuration on $K_n$ .
\begin{center}
\begin{minipage}{15cm}
\framebox{\bf Search toppling and permuting equivalent sorted parking configuration}\newline
{\bf Input:} A configuration $u$ on $K_n$.\newline
$u'\leftarrow \compact(u)$;\newline
$u'\leftarrow \sort(u')$;\newline
For $i$ from $1$ to $n-1$ do $k_i \leftarrow (n-1)u'_i-n(i-1)$;od;\newline
$i_{\max }\leftarrow i$ such that $k_i = \max_{j=1\ldots n-1}(k_j)$;\newline
Let $k_{i_{\max}}=q(n-1)+r$ be the euclidean division by $n-1$ defining $q$ and $r$;\newline
For $i$ from $1$ to $n-1$ do $u''_{i} \leftarrow u'_{((i-1-r)\mod (n-1))+ 1}-q+r+\test{i\leq r} $;od;\newline
$u''_n \leftarrow u'_n+k_{i_{\max}}$;\newline
{\bf Output:} The configuration $u''$ ($=\sort(\park(u))$).
\end{minipage}
\end{center}
\begin{proposition}
The preceding algorithm correctly returns $u''=\sort(\park(u))$ and may be implemented with a linear arithmetic complexity.
\end{proposition}
\begin{proof}
First we show that this algorithm is correct.
We implicitly use a formula for $\T^j.u$ where $j\in\mathbb{Z}$ and $u$ is a sorted compact configuration:
$$ \T^j.u = (\T^{(1-n)})^{-q}\T^r.u = \T^r.u+q\laplacianconf{n} = (u_{(i-1-r\mod n-1)+1}-q+r-n\test{i\leq r};u_n+j)$$
where $j=q(n-1)+r$ is the euclidean division of $j$ by $n-1$.
This formula is obtain by iteration of the formula in the proof of $5.$ in Proposition~\ref{prop:convert}.
Roughly speaking, $u_{(i-1-r\mod n-1)+1}$ takes into account the cyclic permutations induced by $\T^r$, $-q$ corresponds to the $-q$ topplings of the sink, $+r$ to the $r$ topplings of vertices in $\T^r$ and $-n\test{i\leq r}$ compensate in the case where the vertex is toppled once during the computation of $\T^r$.
The configuration $u'=\sort(\compact(u))$ is a sorted and compact configuration.
We search the power $j\in \mathbb{Z}$ such that $\T^j.u'=u''=\sort(\park(u'))$.
If $u''=\T^j.u'$ is sorted and parking then in particular $u''_1=0$.
We use this equality as a criterion to filter the possible values of $j$.
We discuss the $n-1$ possible values of $r$ and indeed the two values of $\test{1\leq r}$.
It will appear that for each value there exists a single value $j_r$ such that $u^{(r)} := \T^{j_r}.u'$ satisfies $u^{(r)}_1=0$.
For any choice of $r$, let $j_r=q_r(n-1)+r$ the euclidean division by $n-1$ of this hypothetical $j_r$ and $i = (1-r) \mod (n-1) +1$.
We then use the preceding formula for $\T^{j_r}.u'$.
If $r=0$ then $i=r+1$ and $u^{(r)}_1 = 0 \iff u'_i-q_r+r = 0 \iff j_r = (n-1)u'_i+nr = (n-1)u'_i+n(i-1)$.
If $r > 0$ then $i=n-r$ and $u^{(r)}_1=0 \iff u'_i-q_r+r-n = 0 \iff j_r = (n-1)u'_i+nr-n(n-1)=(n-1)u'_i+n(i-1)$.
Hence, the expected value of $j$ appears in $\{(n-1)u'_i+n(i-1)\}_{i=1\ldots n-1}$ also called the $\{k_i\}_{i=1\ldots n-1}$ in the algorithm.
We may write $u'=\scompact{k}{0}{w}{s}$ for $k=(n-1)u'_1$, $s=u'_n$ and some almost balanced word $w$.
Since by definition $\T^{j_r}.u'=u^{(r)}=\scompact{k-j_r}{0}{w}{s+j_r}$ satisfies $u^{(r)}_1 = 0$, the cell of spiral coordinate $k-j_r$ is a left cell of $\cutskewcylinder{0}{w}$.
In the cut skew cylinder related to the sorted and parking $u''=\T^{j}.u'$ the cell $k-j$ should also be $\min \leftcutskewcylinder{0}{w}$ according to $6.$ in Proposition~\ref{prop:convert}.
This means that $j$ is the maximal value among the $\{j_r\}_{r=1\ldots n-1}=\{k_i\}_{i=1\ldots n-1}$.
This value is called $k_{i_{\max}}$ in the algorithm.
This algorithm is correct since it returns $u''=\T^{k_{i_{\max}}}.u'$ computed via the first formula of this proof.
Then we discuss how this algorithm may be implemented within a linear arithmetic complexity also called $O(n)$.
The explicit definition of $\compact(u)$ may be evaluated in $O(n)$.
The sort of the compact configuration $u'=\compact(u)$ may be performed in $O(n)$ using a classical sort by \emph{values} since those values are between $0$ and $n-1$.
More precisely we use a vector $v=(v_i)_{i=0\ldots n-1}$ initialized to $v=0\in \mathbb{Z}^{n-1}$, then we increment $v[u'_i]$ for $i=1\ldots n-1$ and finally we compute $\sort(u')$ has the concatenation of blocks of $v_i$ values $i$ for $i$ from $0$ to $n-1$.
Our model of complexity is called arithmetic since we assume that an euclidean division or a comparison may be performed in constant time, no matter of the size of the involved integers.
Within this framework, the evaluation of the $k_i$, the search of the maximal element $\max\{ k_i\}_{i=1\ldots n-1}$ by a classical loop and the evaluation of $\T^{k_{i_{\max}}}.u'$ are explicitly in $O(n)$.
\end{proof}
\begin{theorem}
There exists an explicit algorithm of linear arithmetic complexity computing the rank of any configuration on the complete graph $K_n$.
\end{theorem}
\begin{proof}
Let $u$ be a configuration on $K_n$.
We compute $u'=\sort(\park(\sort(\compact(u))))$ in $O(n)$ via the preceding algorithm.
Then we return $\rank(u')(=\rank(u))$ computed via an evaluation in $O(n)$ of the formula in Theorem~\ref{theo:rank-formula}.
\end{proof}
\section{Enumerative byproducts related to the context}
\label{sec:rank-byproducts}
%\subsection{On Laurent series for $(\degree,\rank)$ bistatistic on configurations}
The degree and rank parameters are the two parameters on configurations involved in the Riemann-Roch theorem for graphs.
These two parameters are invariant by toppling and permuting vertices.
We use as canonical element the unique sorted and parking configuration in each equivalence class by toppling and permuting.
Hence, a natural generating function in this context is
$$ \sgrankdegree_n(r,d) := \sum_{u} r^{\rank(u)}d^{\degree(u)} $$
where $u$ runs on sorted parking configurations on $K_n$.
This series is not a usual power series since $\degree(u)$ may be as small as wished however if is a formal Laurent series.
\begin{figure}[ht!]
\begin{center}
\begin{minipage}{9.5cm}
\begin{tikzpicture}[scale=0.52]
\draw (-1,0) grid (14,8);
\foreach \area/\level/\multiplicity in {-1/0/14,0/0/14,1/0/13,1/1/1,2/0/12,2/1/2,3/0/10,3/1/4,4/0/7,4/1/7,5/0/4,5/1/8,5/2/2,6/0/1,6/1/9,6/2/3,6/3/1,7/1/4,7/2/8,7/3/2,8/2/7,8/3/7,9/3/10,9/4/4,10/4/12,10/5/2,11/5/13,11/6/1,12/6/14,13/7/14} {
\draw node at (\area+0.5,\level+0.5) {\small $\multiplicity$};
}
\foreach \i in {-2,-1,...,12}{
\draw node at (\i+1.5,-0.5) {\small $d^{\i}$};
}
\foreach \i in {-1,0,...,6}{
\draw node at (-1.7,\i+1.5) {\small $r^{\i}$};
}
\end{tikzpicture}
\end{minipage}
\begin{minipage}{5.5cm}
\begin{tikzpicture}[scale=0.52]
\draw (0,0) grid (8,8);
\foreach \area/\level/\multiplicity in {0/0/1,0/1/4,0/2/7,0/3/10,0/4/12,0/5/13,0/6/14,1/0/4,1/1/9,1/2/8,1/3/7,1/4/4,1/5/2,1/6/1,2/0/7,2/1/8,2/2/3,2/3/2,3/0/10,3/1/7,3/2/2,3/3/1,4/0/12,4/1/4,5/0/13,5/1/2,6/0/14,6/1/1,7/0/14,0/7/14} {
\draw node at (\area+0.5,\level+0.5) {\small $\multiplicity$};
}
\foreach \i in {0,1,...,7}{
\draw node at (\i+0.5,-0.5) {\small$x^\i$};
\draw node at (-0.5,\i+0.5) {\small$y^\i$};
}
\draw[red,opacity=0.3,line width=2] (0,0) -- (8,8);
\end{tikzpicture}
\end{minipage}
\caption{Part of the support of $K_5(r,d)$ and the related support of $M_5(x,y)$\label{fig:support-K5}}
\end{center}
\end{figure}
Inspection of the data for the small values of $n$ leads to conjecture a symmetry.
In the left part of Figure~\ref{fig:support-K5} we present the values in a two dimensional array where the cell $(i,j)$ contains the coefficient $[d^ir^j]\sgrankdegree_5(r,d)$ for configurations on the complete graph $K_5$ of degree between $-2$ and $12$.
The complete support of $K_5(d,r)$ would require to add an half-infinite diagonal and an half-infinite horizontal line filled with the value $14$.
The coefficients $1,4,7,10,13,14,14,\ldots$ along the diagonal starting at $r^{-1}d^5$ also appears along the bottom horizontal row starting at the same $r^{-1}d^5$.
This property also appears for the next pairs of diagonals and horizontal rows.
In the right part of the same Figure~\ref{fig:support-K5}, the change of variable $(\degree,\rank)\rightarrow (\rank+1,{n-1\choose 2}-\degree + \rank)$ lay the values out so that the symmetry is the more explicit symmetry along the main diagonal.
This motivates the definition of the two parameters $\xpara(u):=\rank(u)+1$ and $\ypara(u) := {n-1\choose 2} - \degree(u)+\rank(u)$ on a configuration $u$ and the definition of the generating function
$$ \sgleftright_n(x,y) := \sum_{u} x^{\xpara(u)}y^{\ypara(u)}$$
where $u$ runs overs sorted parking configurations on $K_n$.
This generating function is a power series in $x$ and $y$ since by definition $\rank(u)\geq -1$ so $\xpara(u)\geq 0$ and $\ypara(u)\geq 0$ will be deduced from the proof of the conjectural symmetry $\sgleftright_n(x,y)=\sgleftright_n(x,y)$.
This symmetry will be proven by the involution of Riemann-Roch theorem detailed in Subsection~\ref{subsec:riemann-roch-symmetry}.
We will interpret this involution in terms of cut skew cylinders.
This interpretation will provide in Subsection~\ref{subsec:xypara-inter} an alternative definition of the parameters $\xpara$ and $\ypara$ in terms of the traversal computing the rank.
Moreover,in Subsection~\ref{subsec:degree-rank-enumeration} geometric sums will appear along these computations and their summations will lead to an expression for
$$ \mathbb{M}(x,y;z) = \sum_{n\geq 1} \sgleftright_n(x,y)z^n$$
as a rather simple rational function involving two copies of a classical generating function on Dyck words.
\subsection{On the involution in Riemann-Roch theorem}
\label{subsec:riemann-roch-symmetry}
For the graph $G$, the Riemann-Roch theorem relates the ranks of configurations $u$ and $K_G-u$ on $G$.
The map $u\rightarrow K_G-u$ is an involution.
For the complete graph $G=K_n$, we have $K_G = (n-3;n-3)$.
In this case, this involution combines nicely with the equivalence by toppling and permutation: if $u$ and $v$ are toppling and permuting equivalent then also are $K_G-u$ and $K_G-v$.
This leads to the involution on sorted parking configurations on $K_n$,
$$ \rrinvolutionconf.u := \sort\circ \park (K_G-u).$$
\begin{proposition}
Let $u$ be a sorted parking configuration on $K_n$, we have $$(\xpara(\rrinvolutionconf.u),\ypara(\rrinvolutionconf.u)) = (\ypara(u),\xpara(u)).$$
\end{proposition}
\begin{proof}
The proof is similar for any configuration $u$ on $K_n$.
The Riemann-Roch theorem applied to $u$ implies that
$$ \xpara(K_G-u) = \rank(K_G-u) + 1 = \rank(u) - \degree(u) + {n \choose 2} - n +1 = \ypara(u).$$
Applying the same proof to $K_G-u$, we obtain $\ypara(K_G-u) = \xpara(u)$.
\end{proof}
\begin{corollary}
For any $n\geq 1$, we have $\sgleftright_n(x,y)=\sgleftright_n(y,x)$.
\end{corollary}
This involution $\rrinvolutionconf$ corresponds to an natural involution on cut skew cylinders.
Roughly speaking, the involution on cut skew cylinders consists in reversing the order in which the cells are visited along the spiral traversal.
For a word $w=w_1w_2\dots w_k$ the \emph{reverse word} is $\reverse{w}=w_kw_{k-1}\ldots w_1$.
For any Dyck word $w$, let $w=fabg$ be the \emph{last maximum factorization} where $|fa|_a-|fa|_b$ is the longest prefix $p$ of $w$ where the maximal value $|p|_a-|p|_b$ is reached.
%In other words, the occurence of letter $a$ in the factorization leads to the last vertex of maximal (vertical height) of the Dyck path.
We define the map $$\rrinvolutionconf(w):=a\reverse{f}b\reverse{g}.$$
This map is an involution since in the last maximum factorization $f'abg'$ of $\rrinvolutionconf(w)$ we have $f'a=a\reverse{f}$ and $bg'= \reverse{g}b$.
A restriction of this involution $\rrinvolutionconf$ appears in previous work of one of the authors~\cite{leborgne}. % YLB upper interactions
In terms of cut skew cylinder, the involution $\rrinvolutionconf$ on sorted parking configurations will map the cell of spiral coordinate to a cell of spiral coordinate $C(w)-s$ where by definition
$$ C(w) := \max \rightcutskewcylinder{0}{w} - \min \leftcutskewcylinder{0}{w}.$$
\begin{proposition}\label{prop:xiinvol}
Let $u=\scompact{0}{0}{wb}{s}$ be a sorted parking configuration on $K_n$ and $w=fabg$ the last maximum factorization of $w$. We have
$$ \rrinvolutionconf.u = \scompact{0}{0}{\rrinvolutionconf(w)b}{C(w)-s-1}.$$
\end{proposition}
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=1]
\draw (-4, 0) grid (10, 7.2);
\foreach \s/\x/\y in {28/-3/0,36/-3/1,44/-3/2,52/-3/3,60/-3/4,68/-3/5,76/-3/6,21/-2/0,29/-2/1,37/-2/2,45/-2/3,53/-2/4,61/-2/5,69/-2/6,14/-1/0,22/-1/1,30/-1/2,38/-1/3,46/-1/4,54/-1/5,62/-1/6,7/0/0,15/0/1,23/0/2,31/0/3,39/0/4,47/0/5,55/0/6,0/1/0,8/1/1,16/1/2,24/1/3,32/1/4,40/1/5,48/1/6,1/2/1,9/2/2,17/2/3,25/2/4,33/2/5,41/2/6,2/3/2,10/3/3,18/3/4,26/3/5,34/3/6,3/4/3,11/4/4,19/4/5,27/4/6,4/5/4,12/5/5,20/5/6,5/6/5,13/6/6,6/7/6}{
\draw node[green] at (\x-0.2,\y+0.2) {\tiny{$\s$}};
\draw node[red] at (\x-0.8,\y+0.8) {\tiny{$\overline{\s}$}};
}
\foreach \s/\x/\y in {7/2/0,14/3/0,6/3/1,21/4/0,13/4/1,5/4/2,28/5/0,20/5/1,12/5/2,4/5/3,35/6/0,27/6/1,19/6/2,11/6/3,3/6/4,42/7/0,34/7/1,26/7/2,18/7/3,10/7/4,2/7/5,49/8/0,41/8/1,33/8/2,25/8/3,17/8/4,9/8/5,1/8/6,56/9/0,48/9/1,40/9/2,32/9/3,24/9/4,16/9/5,8/9/6,63/10/0,55/10/1,47/10/2,39/10/3,31/10/4,23/10/5,15/10/6}{
\draw node[green] at (\x-0.2,\y+0.2) {\tiny{$\overline{\s}$}};
\draw node[red] at (\x-0.8,\y+0.8) {\tiny{$\s$}};
}
\draw[line width=2,draw=blue] (1,0) -- (1,3) -- (2,3) -- (2,5) -- (4,5) -- (4,6) -- (6,6) -- (6,7) -- (9,7);
\foreach \y in {1,...,7}{
\draw[line width=2,draw=green,->] (-2.05,\y-1) -- (-2.05,\y);
\draw[line width=2,draw=red,<-] (-1.95,\y-1) -- (-1.95,\y);
\draw[line width=2,draw=green,->] (-2.05,\y-0.5) -- (-2.05,\y);
\draw node[green] at (-2.5,\y-0.5) {$a_{\oriented{21}\y}$};
\draw node[red] at (-1.5,8-\y-0.5) {$a_{\oriented{\overline{62}}\y}$};
}
\end{tikzpicture}
\caption{Example of the superimposition principle\label{fig:superimposition}}
\end{center}
\end{figure}
From the briefly postponed proof of this proposition, we extract in a lemma the following \emph{superimposition principle} for $u=\scompact{k}{m}{w}{s}$ based on the involution which maps the cell $k\in \mathbb{Z}$ to the cell $-k\in \mathbb{Z}$ reversing the spiral ordering of cells.
\begin{lemma}(Superimposition principle)\label{lem:superimposition}
Let $u=\scompact{k}{m}{w}{s}$ be a sorted and compact configuration on $K_n$.
$$ u':=(-u_{n-i};u_n) = \scompact{k'}{m'}{w'}{s'} $$
where $k'= n(1-n)+(2n-1)-k$, $m'=(2n-1)-m$, $w'=\reverse{w}$ and $s=s'$.
\end{lemma}
\begin{proof}
The configuration $\scompact{k}{m}{w}{s}$ is defined by a cut skew cylinder $\cutskewcylinder{m}{w}$ and an oriented segment $\oriented{k}$.
The claim is the consequence of the following symmetries: reverse the orientation of the segment $\oriented{k}$, reverse the order in which the cells are visited, the cell $k$ becoming the cell $-k$, and change the corner related to a cell from south-east to north-west.
This leads to a new cut skew cylinder $\cutskewcylinder{m'}{w'}$ and a new oriented segment $\oriented{k'}$ (toward south).
This data defines the new configuration $u'=\scompact{k'}{m'}{w'}{s}$ as the image via the central symmetry with respect to the origin exchanging left and right and also top and bottom.
An example is provided in Figure~\ref{fig:superimposition} where in red are the initial data and in green the new data.
In this case, the green oriented segment $\oriented{21}$ is reversed to become the red oriented segment $\oriented{\overline{62}}$.
Inspection shows that $k'=-n^2+3n-1-k$, $m'=2n-1-m$, and $w'=\reverse{w}$.
We also have
$$ u' := (u'_i;u'_n) = (-u_{n-i};u_n)$$
since the differences of abscissa are opposite and the order of steps in the oriented segment $\oriented{k'}$ reversed compared to $\oriented{k}$.
\end{proof}
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.8]
%grid
\draw (-5,0) grid (9,7);
% w and \Phi(w) cut
\draw[line width=2,draw=blue] (0,0) -- (0,2) -- (1,2) -- (1,5) -- (3,5) -- (3,6) -- (5,6) -- (5,7) -- (8,7);
% w Dyck path proof
\draw[line width=1,dashed,draw=green] (0,0) -- (7,7);
% w cut start
\draw[line width=0,fill=green] (0,0) circle (0.1);
% \Phi(w) Dyck path proof
\draw[line width=1,dashed,draw=red] (1,5) -- (-4,0);
\draw[line width=1,dashed,draw=red] (4,7) -- (2,5);
% \Phi(w) cut start
\draw[line width=0,fill=red] (1,5) circle (0.1);
% Label in w
\foreach \i/\j/\wlabel in {0/0/0,1/1/1,2/2/2,3/3/3,4/4/4,5/5/5,6/6/6,-1/0/7,0/1/8,1/2/9,2/3/10,3/4/11,4/5/12,5/6/13,-2/0/14,-1/1/15,0/2/16,1/3/17,2/4/18,3/5/19,4/6/20,-3/0/21,-2/1/22,-1/2/23,0/3/24,1/4/25,2/5/26,3/6/27,-4/0/28,-3/1/29,-2/2/30,-1/3/31,0/4/32,1/5/33,1/6/41}{
\draw node[green] at (\i-0.25,\j+0.25) {\tiny{$\wlabel$}};
}
% Label in Phi(w)
\foreach \i/\j/\phiwlabel in {1/5/0,0/4/1,-1/3/2,-2/2/3,-3/1/4,4/7/5,3/6/6,2/5/7,1/4/8,0/3/9,-1/2/10,-2/1/11,5/7/12,4/6/13,3/5/14,2/4/15,1/3/16,0/2/17,-1/1/18,6/7/19,5/6/20,4/5/21,3/4/22,2/3/23,1/2/24,0/1/25,7/7/26,6/6/27,5/5/28,4/4/29,3/3/30,2/2/31,1/1/32,8/7/33}{
\draw node[red] at (\i+0.25,\j-0.25) {\tiny{$\phiwlabel$}};
}
% % Cells of left/right component
% \foreach \j/\wj in {1/0,2/0,3/1,4/1,5/1,6/3,7/5}{
% \foreach \i in {-4,-3,...,\wj}{
% \draw[fill=red,opacity=0.3] (\i-1,\j-1) rectangle (\i,\j);
% }
% \foreach \i in {\wj+1,\wj+2,...,8}{
% \draw[fill=green,opacity=0.3] (\i-1,\j-1) rectangle (\i,\j);
% }
% }
% w spiral traversal
\foreach \diag/\length in {-2/3,-1/6}{
\foreach \j in {0,...,\length}{
\draw[green,line width=2,->,opacity=0.4] (\diag+\j+0.1,\j+0.1) -- (\diag+\j+1-0.1,\j+1-0.1);
}
}
% pointed vertex
\draw[fill=black,line width=0] (2,4) circle (0.12);
% \Phi(w) spiral traversal
\foreach \diag/\colength/\y in {-2/4/6,-3/0/4}{
\foreach \j in {\colength,...,\y}{
\draw[red,line width=2,->,opacity=0.4] (\diag+\j+0.9,\j+0.9) -- (\diag+\j+0.1,\j+0.1);
}
}
% rank w
\foreach \i/\j in {-1/0,-2/0,-1/1,0/2}{
\draw[line width=0,fill=green,opacity=0.4] (\i+0.5,\j+0.5) circle (0.15);
}
% rank Phi(w)
\foreach \i/\j in {1/4,2/4,3/5}{
\draw[line width=0,fill=red,opacity=0.4] (\i+0.5,\j+0.5) circle (0.15);
}
% w oriented segment
\draw[line width=4,opacity=0.6,draw=green,->] (0,0) -- (0,7);
% Phi(w) oriented segment
\draw[line width=4,opacity=0.6,draw=red] (1,5) -- (1,0);
\draw[line width=4,opacity=0.6,draw=red,->] (9,7) -- (9,5);
\draw node[red] at (0+0.25,7-0.25) {\tiny{$\overline{23}$}};
\end{tikzpicture}
\caption{Superimposition principle for the traversals related to the computation of the rank of $\scompact{0}{0}{aabaaabbabbabbb}{10}$ and $\scompact{0}{0}{aaabaabbbabbabb}{7}$.\label{fig:xypara-superimposition}}
\end{center}
\end{figure}
We then use this superimposition principle in the proof of Proposition~\ref{prop:xiinvol}.
\begin{proof}
By definition, we have $$ \sort(K_G - u) = (n-3-u_{n-i};n-3-u_n)= (-u_{n-i};-u_n)-(n-3)\laplacianconf{n}+n(n-3)\onechipconf{n}.$$
We factorize $w$ in $w=fabgb$ where $v=fabg$ is the factorization at last maximal height of the Dyck word $v$ defined by $w=vb$.
Using the superimposition principle of Lemma~\ref{lem:superimposition} and changing the value of $u_n$ to its opposite, we have
$$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1}{2n-1}{b\reverse{g}ba\reverse{f}}{-s}.$$
It appears that $a\reverse{f}b\reverse{g}b=\rrinvolutionconf(v)b$ is a cyclic conjugate of $b\reverse{g}ba\reverse{f}$.
According to $2.$ in Proposition~\ref{prop:convert}, we change the start of the cut to make appear this cyclic conjugate:
$$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1}{2n-1+n|b\reverse{g}b|_a-(n-1)|b\reverse{g}b|_b}{\rrinvolutionconf(v)b}{-s}.$$
On one hand $w$ is a cut, so we have $n|w|_a+(n-1)|w|_b = 0$, hence $n|b\reverse{g}b|_a-(n-1)|b\reverse{g}b|_b = -n|fa|_a+(n-1)|fa|_b$.
On another hand, since $m=0=\min \leftcutskewcylinder{0}{w}$, $C(w)=\max \rightcutskewcylinder{0}{fabg}$ is also the spiral label of the cell whose west vertical side is related to the explicit occurence of $a$ in $w=fabgb$, hence $C(w)=n|fa|_a-(n-1)|fa|_b-(2n-1).$
These two observations leads to
$$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1}{-C(w)}{\rrinvolutionconf(v)b}{-s}.$$
Using $3.$ of Proposition~\ref{prop:convert}, we increment the labeling of cells by $C(w)$ so that the cut starts in cell $0$:
$$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1+C(w)}{0}{\rrinvolutionconf(v)b}{-s}.$$
Adding $n(n-3)\onechipconf{n}$ modifies only the value on the sink $n$ and the $n-3$ topplings of this sink $n$ are equivalent to $\T^{(1-n)(n-3)}$ hence using $5.$ of Proposition~\ref{prop:convert} we obtain
$$\sort(K_{K_n}+(-u_{n-i};-u_n))=\scompact{3(1-n)+C(w)}{0}{\rrinvolutionconf(v)b}{-s+(n-3)}.$$
According to $6.$ (and then $5.$) in Proposition~\ref{prop:convert}, we apply $\T^{3(1-n)+C(w)}$ to obtain the toppling and permuting equivalent parking configuration $\sort(\park(K_{K_n}-u))=\rrinvolutionconf.u$ with the claimed expression in the proposition.
%% Inspection shows that $\rrinvolutionconf(w)b$ is the cyclic conjugate of $b\reverse{w}$ which may be written $vb$ where $v$ is a Dyck word.
%% We use $2.$ of Proposition~\ref{prop:convert} to move the start of the cut along the factor $b\reverse{g}b$ to replace the cut $b\reverse{w}=b\reverse{g}ba\reverse{f}$ by the cyclically equivalent cut $\rrinvolutionconf(w)b$: $$(-u_{n-i};-u_n)=\scompact{-n^2+3n-1}{2n-1+C(w)}{\rrinvolutionconf(w)b}{-s}.$$
%% Using $3.$ of Proposition~\ref{prop:convert}, we decrement the labeling of cells by $2n-1+C(w)$ so that the cut starts in cell $0$: $$(-u_{n-i};-u_n)=\scompact{-n^2+n-C(w)}{0}{\rrinvolutionconf(w)b}{-s}.$$
%% Adding $n(n-3)\onechipconf{n}$ modifies only the value on the sink $n$ and the $n-3$ topplings of this sink $n$ are equivalent to $\T^{(1-n)(n-3)}$ hence using $5.$ of Proposition~\ref{prop:convert} we obtain
%% $$ \sort(K_G - u) = \scompact{3(n-1)-C(w)}{0}{\rrinvolutionconf(w)b}{-s+n-3}.$$
%% The word $\rrinvolutionconf(w)$ is a Dyck word so $\min \leftcutskewcylinder{0}{\rrinvolutionconf(w)b} = 0$ and using $6.$ of Proposition~\ref{prop:convert} we have the expected expression for $ \sort(\park(\sort(K_G - u))) =: \rrinvolutionconf.u.$
\end{proof}
\subsection{Interpretation of $(\xpara,\ypara)$ on cut skew cylinders \label{subsec:xypara-inter}}
Let $u=\scompact{0}{0}{vb}{s}$ be a sorted parking configuration on $K_n$.
Let $w$ a cyclic conjugate of $vb$ and $m\in \mathbb{Z}$ be such that $\cutskewcylinder{m}{w} = \cutskewcylinder{0}{vb}$ proven by a change of the start for the cut.
The parameters $\xpara(u)$ and $\ypara(u)$ admits a description in terms of $\cutskewcylinder{m}{w}$ and $s$.
The \emph{crossed left cells} of $u=\scompact{k}{m}{w}{s}$ are
$$ \crossedleftcells{m}{w}{s} := \{k | k \leq s \mbox{ and } k\in \leftcutskewcylinder{m}{w} \}.$$
We also consider the \emph{uncrossed right cells} defined by
$$ \uncrossedrightcells{m}{w}{s} := \{k | k > s \mbox{ and } k\in \rightcutskewcylinder{m}{w}\}.$$
We denote the cardinalities of these sets by $$\leftpara{m}{w}{s} := |\crossedleftcells{m}{w}{s}|\mbox{ and }\rightpara{m}{w}{s} := |\uncrossedrightcells{m}{w}{s}|$$
We illustrate these definitions in Figure~\ref{fig:xypara-superimposition} in the particular case $w=vb$ where $v=aabaaabbabbabb$ is a Dyck word and so $m=0$, and $s=10$.
This factorization $w=vb$ is also proven by the dashed green diagonal.
The traversal of cells computing $\rank(\scompact{0}{0}{vb}{s})$ visits the cells of spiral coordinate from $0$ to $s$ and those cells are crossed by a green diagonal arrow in north-west direction.
%The origin of the name of these sets appears in this particular case.
There the cells of $\crossedleftcells{0}{vb}{s}=\{0,7,8,9\}$ are marked by a green disk and the cells of $\uncrossedrightcells{0}{vb}{s}=\{11,12,18\}$ by a red disk.
%% Let $u=\scompact{m}{m}{w}{s}$ be a sorted parking configuration on $K_n$.
%% The parameters $\xpara(u)$ and $\ypara(u)$ admits a description embedded in the related cut skew cylinder.
%% In the spirit of the definition of $(\leftcellonrowi{m}{w}{i}{s})_i$ is Subsection~\ref{}, we define the \emph{crossed left cells} of $\scompact{m}{m}{w}{s}$ by
%% $$ \crossedleftcells{m}{w}{s} := \{k | m \leq k \leq m+s \mbox{ and } k\in \leftcutskewcylinder{m}{w} \} (= \cup_{i=1}^{n-1}\leftcellonrowi{m}{w}{i}{s}).$$
%% We also consider the \emph{uncrossed right cells} defined by
%% $$ \uncrossedrightcells{m}{w}{s} := \{k | k > m+s \mbox{ and } k\in \rightcutskewcylinder{m}{w}\}.$$
%% We illustrate these definitions in Figure~\ref{fig:xypara-superimposition}.
%% The cells ``visited'' by the traversal for the computation of the rank of $\scompact{0}{0}{aabaaabbabbabbb}{10}$ are crossed by a green arrow.
%% The left cells crossed by this traversal are marked by a green circle: $\crossedleftcells{0}{aabaaabbabbabbb}{10} = \{0,7,8,9\}$.
%% The right cells not crossed by this traversal are marked by a red circle: $\uncrossedrightcells{0}{aabaaabbabbabbb}{10} = \{11,12,18\}$.
\begin{proposition}
Let $u=\scompact{0}{0}{vb}{s}$ be a sorted parking configuration on $K_n$, we have
$$ \xpara(u) = \leftpara{0}{vb}{s} \mbox{ and } \ypara(u) = \rightpara{0}{vb}{s}.$$
\end{proposition}
\begin{proof}
In this case $\min \leftcutskewcylinder{0}{vb}=0$, so $\crossedleftcells{0}{vb}{s}=\{k| 0 \leq k \leq s \mbox{ and } k \in \leftcutskewcylinder{0}{vb}\} = \cup_{i=1}^{n-1}\leftcellonrowi{0}{vb}{i}{s}.$
Hence the identity $$|\crossedleftcells{m}{vb}{s}| = \sum_{i=1}^{n-1}|\leftcellonrowi{m}{vb}{i}{s}| = \rank(u)+1 = \xpara(u)$$ directly follows from the Proposition~\ref{prop:read-proof} describing a proof for the rank of $u$ via the traversal.
The other identity is deduced from this first identity via an extension of the superimposition principle to the traversals computing the rank of $u$ and $\rrinvolutionconf.u$.
An example of this superimposition with traversals is given in Figure~\ref{fig:xypara-superimposition}.
%% In green, the dotted diagonal segment matches the cannoncial Dyck word $w=aabaaabbabbabb$ for $u=\scompact{0}{0}{wb}{s}$ where $s=10$.
The green oriented vertical segment toward north, which defines $u$, starts from the south-east corner of spiral green coordinate $0$.
%% The cells from green spiral coordinate $0$ to $s=10$ are the cells visited by the optimiszed algorithm computing the rank and crossed by green diagonal arrow toward north-east.
In red, we describe the same notions as in green but on $\rrinvolutionconf.u=\scompact{0}{0}{\rrinvolutionconf(w)b}{C(w)-s-1}$ where $C(w)=18$ so that $C(w)-s-1=7$.
The dashed red diagonal (drawn in two parts) matches $\rrinvolutionconf(w)$, the red oriented vertical segment toward south, which defines $\rrinvolutionconf.u$, starts from the north-west corner of red spiral coordinate $0$ and the visited cells during the computation of the rank of $\rrinvolutionconf.u$ are crossed by red diagonal arrows toward the south-west.
First we assume that $s\geq 0$ and $C(w)-s-1\geq 0$ as in Figure~\ref{fig:xypara-superimposition}.
It means that $(s+1)+(C(w)-s-1+1) = C(w)+1$ cells are crossed.
This number corresponds exactly to the number of cells of spiral between the cell of spiral green coordinate $0$ and the cell of spiral red coordinate $0$.
Hence the green and red sequences of diagonals both ends in the black disk which is the south-east corner of the cell of green spiral coordinate $s+n(=18$ on example).
Since the involution $\rrinvolutionconf$ on skew cylinders exchange left and right components, we deduce that the cells of spiral green coordinate $\uncrossedrightcells{0}{wb}{s}$ are also the cells of spiral red coordinate $\crossedleftcells{0}{\rrinvolutionconf(w)b}{C(w)-s-1}$.
Hence $|\uncrossedrightcells{0}{wb}{s}| = \xpara(\rrinvolutionconf.u) = \ypara(u)$.
If $s< 0$, then only red diagonal arrows may exist.
Inspection shows that $\uncrossedrightcells{0}{wb}{s} = \rightcutskewcylinder{0}{wb} \cap \{ s,\ldots \max \rightcutskewcylinder{0}{wb}\} = \crossedleftcells{0}{\rrinvolutionconf(w)b}{C(w)-s-1}$ hence $|\uncrossedrightcells{0}{wb}{s}|=\xpara(\rrinvolutionconf.u)=\rank(\rrinvolutionconf.u)+1=\ypara(u)$.
If $C(w)-s-1 < 0$, then only green diagonal arrows may exist.
We have $s\geq C(w)=\max(\rightcutskewcylinder{0}{wb}{s})$ so $\uncrossedrightcells{0}{wb}{s}$ is empty.
In addition, the value $C(w)-s$ on the sink of $\rrinvolutionconf.u$ implies that this configuration is non-effective so $\rank(\rrinvolutionconf.u)=-1$.
Hence, it this case one also has $|\uncrossedrightcells{0}{wb}{s}|=0=\xpara(\rrinvolutionconf.u) = \ypara(u)$.
\end{proof}
\subsection{Enumeration of sorted parking configurations according to $(\degree,\rank)$}
\label{subsec:degree-rank-enumeration}
According $7.$ in Proposition~\ref{prop:convert}, the bijective decomposition $u=\scompact{0}{0}{vb}{s}$ of sorted parking configuration on $K_n$ where $v$ is a Dyck word of size $n-1$ implies that
$$ \sgleftright_n(x,y) = \sum_{v}\sum_{s\in\mathbb{Z}} x^{\leftpara{0}{vb}{s}}y^{\rightpara{0}{vb}{s}}$$
where $v$ runs over Dyck words of size $n-1$.
We introduce a partial sum of $\sgleftright_n(x,y)$ indexed by a Dyck word $v$:
$$ \sgleftright_v(x,y) = \sum_{s\in\mathbb{Z}} x^{\leftpara{0}{vb}{s}}y^{\rightpara{0}{vb}{s}}.$$
We also introduce a slightly more general and redundant notation for monomials in these sums
$$ \monomleftright{m}{w}{s} = x^{\leftpara{m}{w}{s}}y^{\rightpara{m}{w}{s}}.$$
First, we study independently each $\sgleftright_v(x,y)$ for each Dyck word $v$ defining the sorted and parking configurations $(\scompact{0}{0}{vb}{s})_{s\in \mathbb{Z}}$.
The partition $(\leftcutskewcylinder{0}{vb},\rightcutskewcylinder{0}{vb})$ of cells indexed by their spiral coordinate induces a partition of $\mathbb{Z}$ into maximal intervals totally contained either in $\leftcutskewcylinder{0}{vb}$ or $\rightcutskewcylinder{0}{vb}$.
We describe this partition in intervals with the maximal elements of each interval, if any.
This leads to the sets
$$\lefttorightcell{0}{vb} := \{ s| s \in \leftcutskewcylinder{0}{vb}, s+1\in \rightcutskewcylinder{0}{vb}\}$$
and
$$\righttoleftcell{0}{vb} := \{ s| s\in \rightcutskewcylinder{0}{vb}, s+1\in \leftcutskewcylinder{0}{vb}\}.$$
\begin{lemma}\label{lem:geometric-sums}
Let $v$ be a Dyck word and $H(x,y) := \frac{1-xy}{(1-x)(1-y)}$. We have
$$ \sgleftright_v(x,y) = H(x,y)\left(\sum_{s\in \righttoleftcell{0}{vb}} \monomleftright{0}{vb}{s} - \sum_{s \in \lefttorightcell{0}{vb}} \monomleftright{0}{vb}{s} \right).$$
\end{lemma}
The notation of the proof are illustrated in Figure~\ref{fig:alternationofgeometrics}.
\begin{figure}[ht!]
\begin{center}
\begin{tikzpicture}[scale=0.8]
\draw (-4, 0) grid (9, 6.2);
\foreach \s/\x/\y/\color in {24/-3/0/black,31/-3/1/black,38/-3/2/black,45/-3/3/black,52/-3/4/black,59/-3/5/black,66/-3/6/blue,18/-2/0/black,25/-2/1/black,32/-2/2/black,39/-2/3/black,46/-2/4/black,53/-2/5/black,60/-2/6/blue,12/-1/0/black,19/-1/1/black,26/-1/2/black,33/-1/3/black,40/-1/4/black,47/-1/5/black,54/-1/6/blue,6/0/0/black,13/0/1/black,20/0/2/black,27/0/3/black,34/0/4/black,41/0/5/black,48/0/6/blue,0/1/0/black,7/1/1/black,14/1/2/black,21/1/3/black,28/1/4/black,35/1/5/black,42/1/6/blue,1/2/1/black,8/2/2/black,15/2/3/black,22/2/4/black,29/2/5/black,36/2/6/blue,2/3/2/black,9/3/3/black,16/3/4/black,23/3/5/black,30/3/6/blue,3/4/3/black,10/4/4/black,17/4/5/black,24/4/6/blue,4/5/4/black,11/5/5/black,18/5/6/blue,5/6/5/black,12/6/6/blue,6/7/6/blue,0/8/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {6/2/0/black,12/3/0/black,5/3/1/black,18/4/0/black,11/4/1/black,4/4/2/black,24/5/0/black,17/5/1/black,10/5/2/black,3/5/3/black,30/6/0/black,23/6/1/black,16/6/2/black,9/6/3/black,2/6/4/black,36/7/0/black,29/7/1/black,22/7/2/black,15/7/3/black,8/7/4/black,1/7/5/black,42/8/0/black,35/8/1/black,28/8/2/black,21/8/3/black,14/8/4/black,7/8/5/black,48/9/0/black,41/9/1/black,34/9/2/black,27/9/3/black,20/9/4/black,13/9/5/black,6/9/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
\draw[line width=2,draw=blue] (1,0) -- (1,1) -- (2,1) -- (2,4) -- (5,4) -- (5,6) -- (8,6);
% oplus
\foreach \x/\y in {7/6,6/6,4/4,3/4}{
\fill[white!60!red] (\x,\y) circle (0.2);
\draw node at (\x,\y) {$\oplus$};
}
% ominus
\foreach \x/\y in {5/5,2/3,2/2}{
\fill[white!60!green] (\x,\y) circle (0.2);
\draw node at (\x,\y) {$\ominus$};
}
% ri
\foreach \x/\y/\i in {6/5/1,3/3/2,5/5/3,2/3/4}{
\draw[red] node at (\x+0.5,\y+0.5) {$r_\i$};
}
% li
\foreach \x/\y/\i in {1/1/1,4/4/2,1/2/3}{
\draw[green] node at (\x+0.5,\y+0.5) {$l_\i$};
}
\end{tikzpicture}
\vspace{0.5cm}
\begin{tikzpicture}[scale=0.8]
\foreach \x in {1,...,4}{
\draw node[rotate=45] at (-\x,0) {\tikz[scale=0.57]{\draw (0,0) grid (1,1);}};
\draw node at (-\x,-0.25) {\tiny{$\overline{\x}$}};
}
\foreach \x in {0,...,12}{
\draw node[rotate=45] at (\x,0) {\tikz[scale=0.57]{\draw (0,0) grid (1,1);}};
\draw node at (\x,-0.25) {\tiny{$\x$}};
}
% ri
\foreach \x/\i in {-1/1,3/2,5/3,9/4}{
\draw node[red] at (\x,0.05) {$r_\i$};
\draw[line width=2,draw=blue] (\x+0.5-0.5,0+0.5) -- (\x+0.5+0.5,0-0.5);
\fill[white!80!red] (\x+0.5,0) circle (0.2);
\draw node at (\x+0.5,0) {$\oplus$};
}
% li
\foreach \x/\i in {1/1,4/2,8/3}{
\draw node[green] at (\x,0.05) {$l_\i$};
\draw[line width=2,draw=blue] (\x+0.5-0.5,0-0.5) -- (\x+0.5+0.5,0+0.5);
\fill[white!80!green] (\x+0.5,0) circle (0.2);
\draw node at (\x+0.5,0) {$\ominus$};
}
\draw node at (-5,0) {$\ldots$};
\draw node at (13,0) {$\ldots$};
\foreach \x in {-4,-3,-2,2,}{
}
\end{tikzpicture}
\caption{Example of decomposition of $\sgleftright_v(x,y)$ into an alternation of geometric sums.\label{fig:alternationofgeometrics}}
\end{center}
\end{figure}
\begin{proof}
If $s<0$, then by convention $s\in \rightcutskewcylinder{0}{vb}$.
If $s\geq (n+1)(n-1)$, then $s\in \leftcutskewcylinder{0}{vb}$ since the greatest possible integer in the right cut appears only in the case $\cutskewcylinder{0}{a^{n-1}b^n}$ and is $ n^2-3n+1$.
Hence $|\righttoleftcell{0}{vb}|=|\lefttorightcell{0}{vb}|+1$ and let $k := |\lefttorightcell{0}{vb}|$.
We sort in increasing order the elements of $\righttoleftcell{0}{vb} = \{r_1,\ldots,r_{k+1}\}$ and $\lefttorightcell{0}{vb} = \{l_1,\ldots ,l_k\}$.
So the partition of $\mathbb{Z}$ in maximal intervals induced by $(\leftcutskewcylinder{0}{vb},\rightcutskewcylinder{0}{vb})$ is
$$ ]-\infty,r_1],[r_1+1,l_1],[l_1+1,r_2],\ldots [r_k+1,l_k],[l_k+1,r_{k+1}],[r_k+1,+\infty[.$$
To observe that on a given interval $I$ of this partition, the sum $\sum_{s\in I} \monomleftright{0}{vb}{s}$ is a geometric sum of reason $x$ or $1/y$, the following key discussion comes directly from the definition of $\crossedleftcells{0}{vb}{s}$ and $\uncrossedrightcells{0}{vb}{s}$:
\begin{itemize}
\item either $s+1\in \leftcutskewcylinder{0}{vb}$, then $\crossedleftcells{0}{vb}{s+1} = \crossedleftcells{0}{vb}{s} \cup \{s+1\}$ and $\uncrossedrightcells{0}{vb}{s+1} = \uncrossedrightcells{0}{vb}{s}$.% leading to the reason $x$ for the sum on $I$.
\item or $s+1\in \rightcutskewcylinder{0}{vb}$, then $\crossedleftcells{0}{vb}{s+1} = \crossedleftcells{0}{vb}{s}$ and $\uncrossedrightcells{0}{vb}{s+1} = \uncrossedrightcells{0}{vb}{s}- \{s+1\}$. %leading to the reason $1/y$ for the sum on $I$.
\end{itemize}
Hence for $i=1,\ldots k$, for any $j$ in the interval $[r_i+1,l_i]$ we have $\monomleftright{0}{vb}{j}=x\monomleftright{0}{vb}{j-1}$ using previous discussion for $s=j-1$.
This leads to the geometric sum of reason $x$
$$ \sum_{j=r_i+1}^{l_i}\monomleftright{0}{vb}{j} = \frac{x\monomleftright{0}{vb}{r_i}-x\monomleftright{0}{vb}{l_i}}{1-x}.$$
Similarly, for $i=1,\ldots k$ and the intervals $[l_i+1,r_{i+1}]$, we obtain geometric sums of reason $1/y$ leading to
$$ \sum_{j=l_i+1}^{r_{i+1}} \monomleftright{0}{vb}{j} = \frac{(1/y)\monomleftright{0}{vb}{l_i}-(1/y)\monomleftright{0}{vb}{r_{i+1}}}{1-1/y} = \frac{-\monomleftright{0}{vb}{l_i}+\monomleftright{0}{vb}{r_{i+1}}}{1-y}.$$
For the two remaining infinite intervals $]-\infty,r_1]$ and $[r_{k+1}+1,+\infty[$ we obtain respectively, after an inversion of summation order over first interval,
$$ \sum_{j=-\infty}^{r_1} \monomleftright{0}{vb}{j} = \frac{\monomleftright{0}{vb}{r_1}}{1-y} \mbox{ and } \sum_{j=r_{k+1}+1}^{+\infty} \monomleftright{0}{vb}{j} = \frac{x\monomleftright{0}{vb}{r_{k+1}}}{1-x}.$$
In the sum $\sgleftright_v(x,y)=\sum_{j=-\infty}^{+\infty}\monomleftright{0}{vb}{j}$ decomposed into geometric sum on these intervals, each term $\monomleftright{0}{vb}{r_i}$ appears twice for a total factor of $H(x,y)=\frac{x}{1-x}+\frac{1}{1-y}$ and each term $\monomleftright{0}{vb}{l_i}$ also twice for a total factor $-H(x,y)$ as expected.
\end{proof}
\begin{figure}[ht!]
\begin{center}
% q-Carlitz
\begin{tikzpicture}[scale=0.8]
\draw (1, 0) grid (7, 6.2);
\foreach \s/\x/\y/\color in {1/2/1/black,8/2/2/black,15/2/3/black,22/2/4/black,29/2/5/black,36/2/6/blue,2/3/2/black,9/3/3/black,16/3/4/black,23/3/5/black,30/3/6/blue,3/4/3/black,10/4/4/black,17/4/5/black,24/4/6/blue,4/5/4/black,11/5/5/black,18/5/6/blue,5/6/5/black,12/6/6/blue,6/7/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {6/2/0/black,12/3/0/black,5/3/1/black,18/4/0/black,11/4/1/black,4/4/2/black,24/5/0/black,17/5/1/black,10/5/2/black,3/5/3/black,30/6/0/black,23/6/1/black,16/6/2/black,9/6/3/black,2/6/4/black,36/7/0/black,29/7/1/black,22/7/2/black,15/7/3/black,8/7/4/black,1/7/5/black}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
\draw[line width=1,draw=blue,dashed] (1,0) -- (7,6);
\draw[line width=2,draw=blue] (1,0) -- (1,2) -- (2,2) -- (2,3) -- (4,3) -- (4,6) -- (7,6);
\fill[fill=blue,opacity=0.3] (1,0) -- (1,2) -- (2,2) -- (2,3) -- (4,3) -- (4,6) -- (7,6) -- cycle;
\foreach \x in {2,...,6}{
\foreach \y in {\x,...,6}{
\draw node at (\x-0.5,\y-0.5) {$q$};
}
}
\foreach \x in {0,...,5}{
\draw node at (\x+1.3,\x+0.7) {$z$};
}
\draw[line width=3,draw=orange] (1,0) -- (2,0) -- (2,1) -- (3,1) -- (3,2) -- (4,2) -- (4,3) -- (5,3) -- (5,4) -- (6,4) -- (6,5) -- (7,5) -- (7,6);
\end{tikzpicture}
\caption{A Dyck path of size $6$, area $5$ and augmented area $11$\label{fig:area}}
\end{center}
\end{figure}
Our final expression for $\mathbb{M}(x,y;z)=\sum_{n\geq 1} \sgleftright_n(x,y)z^n$ uses the generating function of Dyck words/path according to the size and the area.
Figure~\ref{fig:area} contains in blue an embedding of the Dyck word $aababbaaabbb$ as a Dyck path.
Graphically, the area of the blue Dyck path is the number of cells completely included between the Dyck path and the dashed diagonal.
We use the equivalent following definition in terms of words.
The \emph{area} of a Dyck word $v$ is
$$\area(v) := \sum_{fa} (|f|_a-|f|_b)$$
where $fa$ runs over all prefixes of $v$ ending by an occurrence of letter $a$.
The \emph{size} of the Dyck word $v$ is denoted by $\size(v) := |v|_a$.
The \emph{Carlitz $q$-analogue} of Catalan numbers is
$$ C(q;z) := \sum_{v} q^{\area(v)}z^{\size(v)}$$
where $v$ runs over all possibly empty Dyck words.
The \emph{augmented area} of a Dyck path consists in adding to the area the cells crossed by the dashed diagonal in Figure~\ref{fig:area}.
These cells also contain the variable $z$ to suggest that its are counted by the size of the path.
Hence the augmented area of $v$ is $\area(v)+\size(v)$ and the generating function of Dyck words according to augmented area and size is $C(q;qz)$.
This generating function will appear in our proof via its interpretation as the cells between the blue and orange paths in Figure~\ref{fig:area} or the symmetric picture according to the main dashed diagonal.
Let $\Y$ be the language/set of possibly empty Dyck words and $\epsilon$ the empty word.
So $\Y-\epsilon$ denotes the language of non-empty Dyck words.
Let $\kappa$ the morphism on words defined on letters by $\kappa(a):=b$ and $\kappa(b):=a$.
Let $\X:=\kappa(\Y)$.
For example, $v=aababb\in \Y$ and $\kappa(v)=\kappa(a)\kappa(a)\kappa(b)\kappa(a)\kappa(b)\kappa(b)=bbabaa=\reverse{aababb}$.
An alternative definition of $\X$ is the set of reverses of Dyck words in $\Y$.
For a language $\mathbb{L}$, we recall a classical notion of formal languages: $\mathbb{L}^*:=\cup_{n\geq 0} \mathbb{L}^n$ where $\mathbb{L}^n$ is formed by the concatenations of $n$ words in $\mathbb{L}$.
\begin{theorem}
$$\mathbb{M}(x,y;z) = \frac{1-xy}{(1-x)(1-y)}\frac{C(x;xz)+C(y;yz)-C(x;xz)C(y;yz)}{1-C(x;xz)zC(y;yz)}.$$
\end{theorem}
\begin{proof}
The assumption $n\geq 3$ is comfortable in our generic proof that may degenerate for $n=1$ or $n=2$.
Hence, we first consider that $n=1$ and then $n=2$.
If $n=1$, the sorted parking configurations are the $((;s))_{s\in\mathbb{Z}}$ and $\degree((;s))=s$ and $\rank((;s))=\max(-1,s)$.
So $K_1(r,d) = \sum_{s\in \mathbb{Z}} d^sr^{\max(-1,s)}$ and after the change of variable, we have $L_1(x,y)=\frac{1-xy}{(1-x)(1-y)}=H(x,y)$.
If $n=2$, the sorted parking configurations are the $((0;s))_{s \in \mathbb{Z}}$ and $\degree((0;s))=s$ and $\rank((0;s))=\max(-1,s)$.
So $K_2(r,d) = K_1(r,d)$ and after the change of variable one obtain $L_2(x,y) = L_1(x,y)$.
\begin{figure}[ht!]
\begin{center}
% at ri
\begin{tikzpicture}[scale=0.8]
\draw (1, 0) grid (7, 6.2);
\foreach \s/\x/\y/\color in {1/2/1/black,8/2/2/black,15/2/3/black,22/2/4/black,29/2/5/black,36/2/6/blue,2/3/2/black,9/3/3/black,16/3/4/black,23/3/5/black,30/3/6/blue,3/4/3/black,10/4/4/black,17/4/5/black,24/4/6/blue,4/5/4/black,11/5/5/black,18/5/6/blue,5/6/5/black,12/6/6/blue,6/7/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {6/2/0/black,12/3/0/black,5/3/1/black,18/4/0/black,11/4/1/black,4/4/2/black,24/5/0/black,17/5/1/black,10/5/2/black,3/5/3/black,30/6/0/black,23/6/1/black,16/6/2/black,9/6/3/black,2/6/4/black,36/7/0/black,29/7/1/black,22/7/2/black,15/7/3/black,8/7/4/black,1/7/5/black}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
\draw (0,-1) grid (1,0);
\draw node[black] at (1-0.25,-1+0.25) {\tiny{$\overline{7}$}};
\draw node[red] at (1-0.5,-1+0.5) {$r_i$};
\fill[fill=blue,opacity=0.3] (1,0) -- (7,6) -- (8,6) -- (2,0) -- cycle;
\draw (7,5) grid (8,6);
\draw node[black] at (8-0.25,5+0.25) {\tiny{$\overline{7}$}};
\draw node[red] at (8-0.5,5+0.5) {$r_i$};
\foreach \x/\y in {3/3,4/3,3/2}{
\draw[line width=0,fill=white] (\x+0.5,\y+0.5) circle (0.25);
\draw[line width=0,fill=red,opacity=0.4] (\x+0.5,\y+0.5) circle (0.25);
}
\foreach \x/\y in {2/0,6/4}{
\draw[line width=0,fill=white] (\x+0.5,\y+0.5) circle (0.25);
\draw[line width=0,fill=green,opacity=0.4] (\x+0.5,\y+0.5) circle (0.25);
}
\foreach \x in {1,...,6}{
\foreach \y in {\x,...,6}{
\draw node at (\x+0.5,\y-0.5) {$y$};
}
}
\foreach \x in {2,...,6}{
\foreach \y in {2,...,\x}{
\draw node at (\x+0.5,\y-1.5) {$x$};
}
}
\draw[line width=5,draw=orange,opacity=0.8] (1,0) -- (2,0) -- (2,1) -- (3,1) -- (3,2) -- (4,2) -- (4,3) -- (5,3) -- (5,4) -- (6,4) -- (6,5) -- (7,5) -- (7,6) -- (8,6);
\draw[line width=2,draw=magenta] (0,0) -- (2,0);
\draw[line width=1,draw=blue,dashed,opacity=0.5] (1,0) -- (7,6);
\draw[line width=2,draw=magenta] (7,6) -- (8,6);
\draw[line width=2,draw=blue] (2,0) -- (3,0) -- (3,4) -- (7,4) -- (7,6);
\end{tikzpicture}
% at li
\begin{tikzpicture}[scale=0.8]
\draw (1, 0) grid (8, 6.2);
\foreach \s/\x/\y/\color in {1/2/1/black,8/2/2/black,15/2/3/black,22/2/4/black,29/2/5/black,36/2/6/blue,2/3/2/black,9/3/3/black,16/3/4/black,23/3/5/black,30/3/6/blue,3/4/3/black,10/4/4/black,17/4/5/black,24/4/6/blue,4/5/4/black,11/5/5/black,18/5/6/blue,5/6/5/black,12/6/6/blue,6/7/6/blue,0/8/6/blue}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\s$}};
}
\foreach \s/\x/\y/\color in {6/2/0/black,12/3/0/black,5/3/1/black,18/4/0/black,11/4/1/black,4/4/2/black,24/5/0/black,17/5/1/black,10/5/2/black,3/5/3/black,30/6/0/black,23/6/1/black,16/6/2/black,9/6/3/black,2/6/4/black,36/7/0/black,29/7/1/black,22/7/2/black,15/7/3/black,8/7/4/black,1/7/5/black,42/8/0/black,35/8/1/black,28/8/2/black,21/8/3/black,14/8/4/black,7/8/5/black}{
\draw node[\color] at (\x-0.25,\y+0.25) {\tiny{$\overline{\s}$}};
}
\draw (0,-1) grid (1,0);
\draw node[black] at (1-0.25,-1+0.25) {\tiny{$\overline{7}$}};
\draw node[green] at (1-0.5,-1+0.5) {$l_i$};
\fill[fill=blue,opacity=0.3] (1,0) -- (7,6) -- (8,6) -- (2,0) -- cycle;
\draw (7,5) grid (8,6);
\draw node[black] at (8-0.25,5+0.25) {\tiny{$\overline{7}$}};
\foreach \x/\y in {1/0,1/1,2/1,5/4}{
\draw[line width=0,fill=white] (\x+0.5,\y+0.5) circle (0.25);
\draw[line width=0,fill=red,opacity=0.4] (\x+0.5,\y+0.5) circle (0.25);
}
\foreach \x/\y in {4/2}{
\draw[line width=0,fill=white] (\x+0.5,\y+0.5) circle (0.25);
\draw[line width=0,fill=green,opacity=0.4] (\x+0.5,\y+0.5) circle (0.25);
}
\draw[line width=0,fill=white] (7.25,5.6) circle (0.25);
\draw[line width=0,fill=green,opacity=0.4] (7.25,5.6) circle (0.25);
\draw node at (7.25,5.6) {$x$};
\draw node[green] at (7.75,5.6) {$l_i$};
\foreach \x in {1,...,6}{
\foreach \y in {\x,...,6}{
\draw node at (\x+0.5,\y-0.5) {$y$};
}
}
\foreach \x in {2,...,6}{
\foreach \y in {2,...,\x}{
\draw node at (\x+0.5,\y-1.5) {$x$};
}
}
\foreach \y in {0,...,4}[{
\draw node at (7.5,\y+0.5) {$x$};
}
\draw[line width=5,draw=orange,opacity=0.8] (1,0) -- (2,0) -- (2,1) -- (3,1) -- (3,2) -- (4,2) -- (4,3) -- (5,3) -- (5,4) -- (6,4) -- (6,5) -- (7,5) -- (7,6) -- (8,6);
\draw[line width=2,draw=magenta] (1,-1) -- (1,1);
\draw[line width=1,draw=blue,dashed,opacity=0.5] (1,0) -- (7,6);
\draw[line width=2,draw=magenta] (8,5) -- (8,6);
\draw[line width=2,draw=blue] (1,1) -- (1,2) -- (5,2) -- (5,5) -- (8,5);
\end{tikzpicture}
\caption{$r_i$ leads to $bfb \in b\X a\Y (b\X a\Y)^* b$ and $l_i$ leads to $afa \in (\Y-\epsilon)b(\X a \Y b)^*(\X-\epsilon)$\label{fig:factors}}
\end{center}
\end{figure}
We assume that $n\geq 3$.
Starting from the expression of $\sgleftright_v(x,y)$ in Lemma~\ref{lem:geometric-sums}, we provide alternative descriptions of $\monomleftright{0}{vb}{r_i}$ where $r_i\in \righttoleftcell{0}{vb}$ and of $\monomleftright{0}{vb}{l_i}$ where $l_i\in \lefttorightcell{0}{vb}$.
The sequence of cells $(r_i+k)_{k=1\ldots n-1}$ contains the minimal cell in each row of spiral coordinate strictly greater than $r_i$.
In Figure~\ref{fig:factors} at left, it corresponds to the cells crossed by the dashed blue diagonal.
This observation proves that $\leftcutskewcylinder{r_i+n}{(ba)^{n-1}b} = \{ k| k > r_i\}$ and $\rightcutskewcylinder{r_i+n}{(ba)^{n-1}b} = \{k | k \leq r_i\}$.
In Figure~\ref{fig:factors}, the cut skew cylinder $\cutskewcylinder{r_i+n}{(ba)^{n-1}b}$ corresponds to the orange path.
By choice, $r_i \in \rightcutskewcylinder{0}{vb}$ and $r_i+1\in \leftcutskewcylinder{0}{vb}$ so the vertex in south-east corner of cell $r_i+n$ belongs to the cut of $\cutskewcylinder{0}{vb}$ and is preceded and followed by east steps.
Changing the start of the cut to $r_i+n$, we obtain a cyclic conjugate $bfb$ of $vb$ such that $\cutskewcylinder{0}{vb}=\cutskewcylinder{r_i+n}{bfb}$.
Intersecting the two preceding observations, we have
$$ \crossedleftcells{0}{vb}{r_i} = \rightcutskewcylinder{r_i+n}{(ba)^{n-1}b} \cap \leftcutskewcylinder{r_i+n}{bfb} $$
and
$$ \uncrossedrightcells{0}{vb}{r_i} = \leftcutskewcylinder{r_i+n}{(ba)^{n-1}b} \cap \rightcutskewcylinder{r_i+n}{bfb}.$$
The embedding of $(ba)^{n-1}b$ and $bfb$ both starts at the same vertex $r_i+n$.
We factorize $bfb$ at its steps which are common with those of $(ba)^{n-1}b$.
In Figure~\ref{fig:factors} at left, the steps of $bfb$ are magenta if forced and otherwise blue while the steps of $(ba)^{n-1}b$ are orange.
Hence we factorize $bfb$ at the blue (or magenta) and orange steps.
This example should help to convince the reader that $bfb=b(ba)a(aabb)b(ba)a()b$ is in general factorized as a word of $b\X a\Y(b\X a\Y)^*b$.
This factorization in non-ambiguous since the word $(ba)^{n-1}b$ is constant and the factors in $\X$ and $\Y$ are well defined.
Conversely, any word $w\in b\X a\Y(b\X a\Y)^*b$ such that $|w|_a\geq 2$ is almost balanced and may be written $bfb$ and is a cyclic conjugate of some word $vb$ where $v$ is a Dyck word.
Moreover, in the decomposition showing $bfb\in b\X a\Y(b\X a\Y)^*b$, the augmented area of factors in $\X$ counts the cells of $ \crossedleftcells{0}{vb}{r_i}$ and the augmented area of factors in $\Y$ counts the cells of $\uncrossedrightcells{0}{vb}{r_i}$.
On the example of $bfb=b(ba)a(aabb)b(ba)a()b$, the first factor $(ba)$ corresponds to $\{\overline{12}\} \subset \crossedleftcells{0}{vb}{r_i}$, the factor $(aabb)$ corresponds to $\{\overline{4},\overline{3},3\}=\crossedleftcells{0}{vb}{r_i}$ and the second factor $(ba)$ corresponds to $\{\overline{8}\}\subset \crossedleftcells{0}{vb}{r_i}$ and the empty factor $()$ in $\Y$ adds no cell to $\uncrossedrightcells{0}{vb}{r_i}$.
In terms of generating function, it leads to
$$ \sum_{v} \sum_{r_i \in \righttoleftcell{0}{vb}} \monomleftright{0}{vb}{r_i} = \frac{C(x;xz)zC(y;yz)}{1-C(x;xz)zC(y;yz)}-z $$
where $v$ runs over Dyck words of size at least $2$.
More precisely, $\frac{C(x;xz)zC(y;yz)}{1-C(x;xz)zC(y;yz)}$ is the generating function of all the almost balanced words written $bfb$ according to the augmented area of factors $\X$, counted by the variable $x$, and the augmented area of factors $\Y$, counted by the variable $y$, and the size $|bfb|_a\geq 1$ counted by $z$.
The subtracted term $z$ corresponds to the excluded almost balanced word of size $1$, $bab$.
The proof for a cell $l_i$ is very similar and illustrated by the right example in Figure~\ref{fig:factors}.
The choice $l_i\in \leftcutskewcylinder{0}{vb}$ and $l_i+1\in \rightcutskewcylinder{0}{vb}$ implies that the vertex $l_i+n$ belongs to the cut of $\cutskewcylinder{0}{vb}$ and is preceded and followed by north steps.
Hence when the vertex $l_i+n$ is chosen as the start of the cut, it makes appear a cyclic conjugate $afa$ of $vb$ such that $\cutskewcylinder{0}{vb} = \cutskewcylinder{l_i+n}{afa}$.
We have
$$ \crossedleftcells{0}{vb}{l_i} = \rightcutskewcylinder{l_i+n}{(ba)^{n-1}b} \cap \leftcutskewcylinder{l_i+n}{afa} $$
and
$$ \uncrossedrightcells{0}{vb}{l_i} = \leftcutskewcylinder{l_i+n}{(ba)^{n-1}b} \cap \rightcutskewcylinder{l_i+n}{afa}.$$
The factorization of $afa$ at the common steps of the embedding of $afa$ and $(ba)^{n-1}b$ leads to words in $(\Y-\epsilon)b(\X a\Y b)^*(\X -\epsilon)$ where the first $\Y$ factor and the last $\X$ factor are non empty due to the distinct extreme steps of these two embeded words.
Hence we have,
$$ \sum_{v} \sum_{l_i \in \lefttorightcell{0}{vb}} \monomleftright{0}{vb}{l_i} = \frac{(C(x;xz)-1)(C(y;yz)-1)}{1-C(x;xz)zC(y;yz)}$$
where $v$ runs over Dyck words of size at least $2$.
We conclude the proof by a summation following Lemma~\ref{lem:geometric-sums} to get the expected expression.
\end{proof}
\section{Enumerative byproducts related to $q,t$-Catalan numbers}
\label{sec:qt-byproducts}
In a Dyck word $v$ we denote by $a_i$ the $i$-th of the occurence of the letter $a$ in the word $v$.
The \emph{height} $\height(a_i)$ of $a_i$ is defined by $|p|_a-|p|_b$ where $v=pa_iq$ is a decomposition defining the prefix $p$.
The letter $a_i$ and $a_j$ in the Dyck word $v$ are in \emph{$\dinv$-interaction} if either $i] (-\x-0.5,-0.5) -- (-\x+9,9);
\draw[line width=2,draw=orange,opacity=1,fill=white] (-\x-0.5,-0.5) circle (0.35);
\draw node at (-\x+-0.5,-0.5) {\small{$\eta^{\x}$}};
}
\draw[line width=2,draw=blue] (1,0) -- (1,3) -- (2,3) -- (2,4) -- (3,4) -- (3,6) -- (6,6) -- (6,8) -- (9,8);
\draw[line width=2,draw=magenta] (9,8) -- (10,8);
\draw[line width=1,draw=blue,dashed] (1,0) -- (9,8);
\foreach \i/\j in {0/0,0/1,0/2,1/3,2/4,2/5,5/6,5/7}{
\draw[line width=2,draw=green] (\i+0.4,\j+0.45) -- (\i+1,\j+0.45);
\fill[line width=1,fill=white,draw=green] (\i+0.4,\j+0.45) circle (0.23);
\draw node[green] at (\i+0.4,\j+0.45) {\small{$a$}};
\draw[line width=2,draw=green,rounded corners] (\i-0.3,\j+0.8) -- (\i+0.7,\j+0.8) -- (\i+0.85,\j+0.5) -- (\i+1,\j+0.45);
\fill[line width=1,fill=white,draw=green] (\i-0.3,\j+0.7) circle (0.23);
\draw node[green] at (\i-0.3,\j+0.7) {\small{$b$}};
\draw[line width=2,draw=red] (\i+1.7,\j+0.7) -- (\i+1,\j+0.7);
\fill[line width=1,fill=white,draw=red] (\i+1.7,\j+0.7) circle (0.23);
\draw node[red] at (\i+1.7,\j+0.7) {\small{$a$}};
\draw[line width=2,draw=red,rounded corners] (\i+1,\j+0.7) -- (\i+1.2,\j+0.7) -- (\i+1.2,\j+0.45) -- (\i+2.45,\j+0.45);
\fill[line width=1,fill=white,draw=red] (\i+2.45,\j+0.45) circle (0.23);
\draw node[red] at (\i+2.45,\j+0.45) {\small{$b$}};
}
\end{tikzpicture}
\caption{Description of Haglund's $\zeta$ map via traversal of a cut skew cylinder\label{fig:zetamap}}
\end{center}
\end{figure}
In Figure~\ref{fig:zetamap}, we use the same example as Haglund (see page 50 in \cite{haglund}).
We embed our first algorithm describing the $\zeta$ map in a cut skew cylinder.
The spiral traversal visit the cells diagonals by diagonals drawn in orange.
Split diagonal by diagonal, this traversal corresponds to the nested loops on $h$ and $i$ in the algorithm defining $\zeta$ via the height vector.
We consider the cells visited during the traversal of the $h$-th diagonal supposed to define $\eta^{(h)}$.
If a cell is a contact $c_i$ in this diagonal, it means that the $a$ step in $vb$ in the same row is at height $h$ in $v$.
So it exactly corresponds to adding a letter $a$ to $\eta^{(h)}$.
We mark such a cell by a \emph{green} letter $a$ in the cell $c_i$.
If a cell is $c_j+(n-1)$ where $c_j$ is a contact, it means that the $a$ step in $vb$ in the same row is at height $h-1$ in $v$.
So it exactly corresponds to adding a letter $b$ in $\eta^{(h)}$.
We mark such a cell by a \emph{green} letter $b$ in the cell $c_j+(n-1)$.
Since the traversal of the diagonal respect the order of the inner loop on $i$ in the algorithm, we deduce that $\eta^{(h)}$ is also define by the order in which the preceding cells $c_i$ or $c_j+(n-1)$ are visited.
These observation should convince the reader that the second algorithm entitled ``Haglund's $\zeta$ map via traversal'' also defines the $\zeta$ map.
On the example, collecting the \emph{green} letters on each orange diagonal leads to $\eta^{(0)} = a$,$\eta^{(1)}=baa$, $\eta^{(2)}=baaaba$,$\eta^{(3)}=bbbab$ and $\eta^{(4)}=b$.
\begin{center}
\end{center}
We reformulated the definition of $\zeta$ into a spiral traversal since it is well suited for the superimposition principle.
The proof is similar to the proof of Proposition~\ref{prop:dinvpreserved} that $\rrinvolutionconf$ preserves the $\dinv$ parameter.
We keep only the (green) spiral coordinates here.
The vertical step defining the contact $c_i$ in $vb$ shows that $\zeta(v)$ add a letter $a$ in cell $c_i$ and a letter $b$ in cell $c_i+(n-1)$.
But this vertical step also appears in $\rrinvolutionconf(v)b$ and in the computation of $\zeta(\rrinvolutionconf(v))$, we add a (red) letter $a$ in cell $c_i-(n-1)$ and a letter (red) $b$ in cell $c_i-2(n-1)$.
Moving the red letters two west steps and exchanging the red letters $a$ and $b$ on each row leads exactly to the position of the green letters.
Then inspection shows that the reversed traversal in the computation of $\zeta(\rrinvolutionconf(v))$ leads also to $\R(\zeta(v))$.
\end{proof}
\subsection{A $\prerank$ statistic so that $(\prerank,\dinv)$ defines expected $q,t$-Catalan\label{subsec:prerank}}
The \emph{prerank} of a Dyck word $v$ is $$\prerank(v) := \area(\rrinvolutionconf(v)).$$
\begin{proposition}
For any $n\geq 0$, we have
$$ C_n(q,t) := \sum_{v} q^{\dinv(v)}t^{\area(v)} = \sum_{v} q^{\dinv(v)}t^{\prerank(v)}$$
where $v$ runs over Dyck words of size $n$.
\end{proposition}
\begin{proof}
The involution $\rrinvolutionconf$ satisfies $\prerank(v)=\area(\xi(v))$ and $\dinv(v)=\dinv(\rrinvolutionconf(v))$.
\end{proof}
We call this parameter prerank because of an early partial optimization of our algorithms computing the rank.
A \emph{staircase} (sorted parking) configuration $u$ on $K_n$ is such that for $i\neq n$, $u_i=i-1$ and there are no restriction on $u_n$.
Any staircase configuration may be written $u=\scompact{m}{m}{(ab)^{n-1}b}{s}$.
Applying $8.$ in Proposition~\ref{prop:convert}, we have $\sort(\park(u-\onechipconf{1}))=\scompact{m+1}{m+1}{(ab)^{n-1}b}{s-1}$ which is also a staircase configuration.
By induction, we have $$\rank(\scompact{m}{m}{(ab)^{n-1}b}{s}=\max(-1,s).$$
Hence one may accelerate the algorithm computing the rank as soon as we reach a staircase configuration.
It appears that, if $s$ is big enough, the number of loops before we reach such a staircase configuration is finite and is exactly the prerank of the initial Dyck word in the cut $vb$.
%\bibliography{references.bib}
%\bibliographystyle{plain}
\begin{thebibliography}{10}
\bibitem{aminiManjunath}
O.~Amini and M.~Manjunath.
\newblock Riemann-{R}och for sub-lattices of the root lattice $a_n$.
\newblock {\em Electronic J. of Combinatorics}, 17:R124, 2010.
\bibitem{ADDHL}
Jean-Christophe Aval, Michele D'Adderio, Mark Dukes, Angela Hicks, and Yvan
Le~Borgne.
\newblock Statistics on parallelogram polyominoes and a {$q,t$}-analogue of the
{N}arayana numbers.
\newblock {\em J. Combin. Theory Ser. A}, 123:271--286, 2014.
\bibitem{backman}
S.~Backman.
\newblock Riemann-{R}och theory for graph orientations.
\newblock preprint, arXiv:1401.3309, 2014.
\bibitem{bakTang1}
P.~Bak, C.~Tang, and K.~Wiesenfeld.
\newblock Self-organized criticality: An explanation of 1/f noise.
\newblock {\em Phys. Rev Letters}, 59:381---384, 1987.
\bibitem{bakTang2}
P.~Bak, C.~Tang, and K.~Wiesenfeld.
\newblock Self-organised criticality.
\newblock {\em Physical Review A.}, 38:364---374, 1988.
\bibitem{bakerNorine}
M.~Baker and S.~Norine.
\newblock Riemann-{R}och and {A}bel-{J}acobi theory on a finite graph.
\newblock {\em Advances in Mathematics}, 215:766---788, 2007.
\bibitem{bakerShokrieh}
M.~Baker and F.~Shokrieh.
\newblock Chip-firing games, potential theory on graphs, and spanning trees.
\newblock {\em J. Comb. Theory (A)}, 120:164---182, 2013.
\bibitem{bensonChakTetali}
B.~Benson, D.~Chakrabarty, and P.~Tetali.
\newblock G-parking functions, acyclic orientations and spanning trees.
\newblock {\em Discrete Mathematics}, 310:1340---1353, 2010.
\bibitem{biggs1}
N.~Biggs.
\newblock Chip-firing and the critical group of a graph.
\newblock {\em J. of Algebraic Comb.}, 9:25--45, 1999.
\bibitem{BjoLovShor}
A.~Bj{\"o}rner, L.~Lov\'asz, and P.Shor.
\newblock Chip-firing game on graphs.
\newblock {\em European J. Combin}, 12:283--291, 1991.
\bibitem{coriLeBorgne1}
R.~Cori and Y.~Le {B}orgne.
\newblock The sand-pile model and {T}utte polynomials.
\newblock {\em Advances in App. Math.}, 30:44---52, 2003.
\bibitem{coriLeBorgne2}
R.~Cori and Y.~Le {B}orgne.
\newblock On ranks of configurations on the complete graph.
\newblock {\em DMTCS Proceedings, 25th International Conference on Formal Power
Series and Algebraic Combinatorics (FPSAC 2013)}, 2013.
\bibitem{coriRossin}
R.~Cori and D.~Rossin.
\newblock On the sandpile group of dual graphs.
\newblock {\em Europ. J. Comb}, 21:447---459, 2000.
\bibitem{dhar2}
D.~Dhar.
\newblock Self-organized critical state of the sandpile automaton models.
\newblock {\em Phys. Rev. Lett.}, 64:1613---1616, 1990.
\bibitem{dharIntro}
D.~Dhar.
\newblock Theoretical studies of self-organized criticality.
\newblock {\em Physica A}, 369 (1), 2006.
\bibitem{dharMajumdar}
D.~Dhar and S.~Majumdar.
\newblock Equivalence between the {A}belian sandpile model and the $q
\rightarrow 0$ limit of the {P}otts model.
\newblock {\em Physica A}, 185:129---135, 1992.
\bibitem{dhar1}
D.~Dhar and R.~Ramaswamy.
\newblock Exactly solved model of self-organized critical phenomena.
\newblock {\em Phys. Rev. Lett.}, 63:1659---1662, 1989.
\bibitem{dharRuelleVerma}
D.~Dhar, P.~Ruelle, S.~Sen, and D.~Verma.
\newblock Algebraic aspects of abelian sandpile model.
\newblock {\em J. Phys. A}, A28:805---831, 1995.
\bibitem{DukesLeBorgne}
Mark Dukes and Yvan Le~Borgne.
\newblock Parallelogram polyominoes, the sandpile model on a complete bipartite
graph, and a {$q,t$}-{N}arayana polynomial.
\newblock {\em J. Combin. Theory Ser. A}, 120(4):816--842, 2013.
\bibitem{dvoMotzk}
A.~Dvoretsky and T.~Motzkin.
\newblock A problem of arrangements.
\newblock {\em Duke Math. J.}, 14:305---313, 1947.
\bibitem{farkasKra}
H.~M. Farkas and I.~Kra.
\newblock {\em Riemann Surfaces}.
\newblock Graduate {T}exts in {M}athematics, {Springer}, 1992.
\bibitem{kramersWannier}
Kramers H. and Wannier C.
\newblock Statistics of the two-dimensional ferromagnet. part {I}.
\newblock {\em Physical Review}, 60:252--262, 1941.
\bibitem{haglund}
J.~Haglund.
\newblock {\em The $q,t$-Catalan numbers and the space of diagonal harmonics}.
\newblock AMS University Lectures Series, 2008.
\bibitem{Haglund2}
Jim Haglund.
\newblock {\em Handbook of Enumerative Combinatorics}, chapter Catalan Paths
and $q,t$-Enumeration.
\newblock 2015.
\bibitem{kisstothmeresz}
V.~Kiss and L.~Th\'othm\'er\'esz.
\newblock Chip-firing games on eulerian digraphs and np-hardness of computing
the rank of a divisor on a graph.
\newblock preprint, arXiv:1407.6958, 2014.
\bibitem{knuthVol4}
D.~E. Knuth.
\newblock {\em The art of Computer Programming, Volume 4 Combinatorial
Algorithms, Fasc 4A}.
\newblock Addison Wesley, 2004.
\bibitem{leborgne}
Yvan Le~Borgne.
\newblock Counting upper interactions in {D}yck paths.
\newblock {\em S\'em. Lothar. Combin.}, 54:Art. B54f, 16 pp. (electronic),
2005/07.
\bibitem{lorenzini}
D.~Lorenzini.
\newblock Two-variable zeta-functions on graphs and riemann-roch theorems.
\newblock {\em Int. Math. Res. Notices.}, 2012,22:5100--5131, 2012.
\bibitem{merinoLopez}
C.~Merino-{L}opez.
\newblock Chip firing and {T}utte polynomials.
\newblock {\em Ann. Combin.}, 3:253---259, 1997.
\bibitem{mikhalkinZharkov}
Grigory Mikhalkin and Ilia Zharkov.
\newblock Tropical curves, their {J}acobians and theta functions.
\newblock In {\em Curves and abelian varieties}, volume 465 of {\em Contemp.
Math.}, pages 203--230. Amer. Math. Soc., Providence, RI, 2008.
\bibitem{perkPerlWilm}
D.~Perkinson, J.~Perlman, and J.~Wilmes.
\newblock Primer for the algebraic geometry of sandpiles.
\newblock preprint, arXiv:1112.6163, 2011.
\end{thebibliography}
\section{Annex: A proof of the Riemann Roch Theorem for graphs}
\newcommand{\fort}{\ \longrightarrow \ }
\newcommand{\faible}{\parbox[c]{28pt}{\begin{picture}(28,0)(0,0)
\multiput(4,0)(5,0){3}{\line(1,0){3}}
\put(19,0){\vector(1,0){4}}
\end{picture}}}
\newcommand{\rc}[3]{\textcolor{blue}{[#1]}\textcolor{red}{[#2]}\textcolor{green}{[#3]}}
\newcommand{\fortht}[1]{{\stackrel{#1}{\makebox[3pt]{}
\longrightarrow \makebox[1pt]{} }}}
\newcommand{\faibleht}[1]{{\stackrel{#1}{\makebox[3pt]{}
\faible \makebox[1pt]{} }}}
\newcommand{\vufaible}{{\stackrel{*}{\faible}}}
\newcommand{\vufort}{{\stackrel{*}{\ \longrightarrow \ }}}
\newcommand{\simil}{\sim_{L_G}}
\newcommand{\eps}{\varepsilon}
\newcommand{\deltaB}{\overline{\delta}}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Del}[1]{\Delta^{(#1)}}
%\newcommand{\f}{f(z,u,v)}
\newcommand{\Sn}[1] {{\mathcal S}_{#1}}
\newcommand{\Snp}[1]{{\mathbb S}_{#1}}
\newcommand{\etoile}{\stackrel{*}{\rightarrow}}
\newcommand{\mult}[1]{\left(
\begin{array}{c}
#1 \\
d_1 \ldots d_k
\end{array}
\right)
}
We consider the following solitary game on an undirected (non oriented) connected graph $G=(X,E)$ without loops:
at the beginning integer values $f_i$ are attributed to the $n$ vertices
$x_1, x_2, \ldots x_n$ of the graph, these values can be positive
or negative and define a configuration $f$. At each step a toppling can be performed by the player on a vertex $x_i$, it consists
in subtracting $d_i$ (the number of edges incident to $x_i$) to the amount $f_i$ and for each neighbor $x_j$ of $x_i$ increase $f_j$ by the number of edges between these two vertices.
In this operation the amount of vertex $x_i$ may become, or stay negative. The aim of the
player is to find a sequence of toppling operations which will
end with a configuration where all the $f_i$ are non negative. Since the sum of the $f_i$ is invariant by toppling, a necessary
condition to succeed is that in the initial configuration this sum should be non negative. We will see that
this condition is not sufficient.
This game has much to do with the chip firing game (see \cite{BjoLovShor}, \cite{biggs1})
and the sandpile model (see \cite{bakTang2}, \cite{dharIntro}, \cite{dharMajumdar}), for which recurrent configurations
where defined and proved to be canonical representatives of the classes
of configurations equivalent by a sequence of topplings (for a more algebraic treatment see also \cite{perkPerlWilm}).
The game was introduced and studied in detail by Baker and Norine in \cite{bakerNorine}
who also introduced a new parameter on graph configurations : the rank. One characteristic of the
rank $\rho(f)$ of a configuration $f$
is that it is non negative if and only if one can get from $f$ a configuration non-negative on every vertices by performing
a sequence of topplings.
For this parameter they obtain a simple formula expressing a symmetry
similar to the Riemann-Roch formula for surfaces and curves (a classical reference to this formula is
the book by H. Farkas and I. Kra \cite{farkasKra}).
Our aim here is to give a simple presentation of this Riemann-Roch like theorem for graphs.
It's wortwhile in this context to mention the independant work of Backman~\cite{backman} and the precedings works~\cite{mikhalkinZharkov,aminiManjunath}.
\subsection{Configurations on a graph}
Let $G= (X, E)$ be a multi-graph with $n$ vertices, where $X =\{x_1,x_2, \ldots, x_n\}$
is the vertex set and $E$ is a symmetric matrix such that $e_{i,j}$
is the number of edges with endpoints $x_i, x_j$, hence
$e_{i,j} = e_{j,i}$. In all this paper $n$ denotes
the number of vertices of the graph $G$ and $m$ the number of its edges.
We assume that $G$ is connected and
has no loops, so that $e_{i,i}=0$ for all $i$.
We will consider {\em configurations} on a graph, these are elements of
the discrete lattice $\Z^n$. Each configuration $f$ may be considered as
assigning (positive or negative) tokens to the vertices.
The symbol $\eps^{(i)}$
will denote the configuration in which the value 1
is assigned to vertex $x_i$ and the value 0 is assigned to all other vertices.
The {\em degree} of the configuration $f$ is the sum
of the $f_i$'s it is denoted by $deg(f)$.
\subsubsection{The Laplacian configurations}
These configurations correspond to the rows of the Laplacian
matrix of a graph, a classical tool in Algebraic Graph Theory.
The {\em Laplacian configuration} $\Del{i}$ is given by:
$ \Del{i} = d_i \eps^{(i)}- \sum_{i=1}^n e_{i,j}\eps^{(j)}$,
where $d_i = \sum_{i=1}^n e_{i,j}$ is the degree of the vertex $x_i$.
These configurations which degrees are equal to 0 play a central role.
We denote by
$L_G$ the subgroup of $\Z^n$
generated by the $\Del{i}$, and two configurations $f$ and $g$ will be said
{\em toppling equivalent} if $f -g\in L_G$, which will also be written as
$ f \simil g$.
In the sandpile model, the transition from
configuration $f$ to the configuration $f- \Del{i}$ is allowed only if $f_i \geq d_i$ and is called a toppling. The
same condition is assumed in the theory of chip firing games, and toppling is called firing; here we omit this condition and perform topplings even
if $f_i < d_i$.
Notice that $\sum_{i=1}^n \Del{i} = 0$ and that for a connected graph
this is the unique relation (up to multiplication by a constant) satisfied by the $\Del{i}$, moreover
the principal minors of the Laplacian matrix are all equal to the number of spanning trees
of the graph.
\subsubsection{Recurrent configurations}
We use in this section the notation usually considered in the sandpile model, so that we will call
{\em sandpile configuration} a configuration $f$ such that $f_i \geq 0$ for all
$i < n$. This corresponds to the fact that in the sandpile model the vertex $x_n$ is
considered as a sink collecting tokens, so that the number of tokens of the sink has not taken into account
in this context.
\begin{definition}
\label{def:toppling}
In the sandpile model, a toppling on vertex $x_i$, where $i \neq n$, may occur in
a sandpile configuration only if $f_i \geq d_i$. A sandpile configuration $f$ is stable if no toppling can occur, that is
$f_i < d_i$ for all $i ,line width=2] (\source) to (\dest);
}
\end{tikzpicture}
\caption{An orientation of $G$ and the corresponding configuration}
\label{fig:acycOrient}
\end{center}
\end{figure}
\begin{proposition}
\label{propo:acyclicNonEffective}
The configuration associated to an acyclic orientation of $G$ is
not $L_G$-effective.
\end{proposition}
\begin{proof}
Let $ \overrightarrow{G}$ be an acyclic orientation of $G$ and $f= C(\overrightarrow{G})$.
We will show that for any linear combination $g = \sum_{i=1}^n a_i \Del{i}$
the sum $h$ of $g$ and $f$ is not an effective configuration.
Let $\varepsilon_{i,j}$ denote the number of edges with head $x_j$ and tail
$x_i$ in $ \overrightarrow{G}$ . Then $e_{i,j} = \varepsilon_{i,j} + \varepsilon_{j,i}$ (but notice
that since the orientation is acyclic, at least one of the two values in the sum above is
equal to 0).
For any vertex $x_i$ of $G$ we have $d_i^{-} = \sum_{j=1}^n \varepsilon_{j,i}$
so that:
$$ h_i = -1 + \sum_{j=1}^n \varepsilon_{j,i} + a_id_i - \sum_{j=1}^na_je_{i,j}$$
Using $d_i = \sum_{j=1}^n e_{j,i}$ and decomposing each $e_{i,j}$ into
$\varepsilon_{i,j} + \varepsilon_{j,i}$ gives for any $i$:
\begin{equation}
h_i = -1 + \sum_{j=1}^n \varepsilon_{j,i} + a_i\sum_{j=1}^n (\varepsilon_{i,j} + \varepsilon_{j,i}) - \sum_{j=1}^na_j(\varepsilon_{i,j} + \varepsilon_{j,i})
\end{equation}
Separating the edges for which $x_i$ is a head in $ \overrightarrow{G}$ form those for which it is a tail, we get:
\begin{equation}
h_i = -1 + \sum_{j=1}^n (1+a_i-a_j)\varepsilon_{j,i}
+ \sum_{j=1}^n (a_i-a_j) \varepsilon_{i,j}
\end{equation}
Now take $i$ be such that $a_i \leq j$ for all $j \neq i$, we have $a_i - a_j\leq 0$ and $1+ a_i- a_j\leq 1$.
If there is a unique minimal value in the sequence $a_j$ we have $1 + a_j - a_i \leq 0$, hence $h_i <0$.
If there are many $a_i$'s attaining the minimal value take $k$ among them
such that $\varepsilon_{j,k} = 0$ for all the $j$ such that $ a_j = a_k$.
The existence of such a $k$ follows from the acyclicity of
$\overrightarrow{G}$. Then for this $k$ we have $h_k < 0$.
\end{proof}
\subsubsection{Characterization of $L_G$-effective configurations}
We can see that computing the parking configuration toppling equivalent
to a given configuration allows to determine if it is effective since we have
\begin{proposition}\label{prop:eff_on_park}
A configuration $f$ is $L_G$-effective if and only if the parking
configuration $g$ equivalent to $f$ is such that $g_n \geq 0$.
\end{proposition}
\begin{proof}
If $g_n \geq0$ $g$ is effective so that $f$ is $L_G$-effective.
If $f$ is $L_G$-effective then there exists an effective configuration $h$
such that $f \simil h$. Then $g$ is the unique parking configuration such that $h \simil g$,
it may be obtained form $h$ performing subset topplings. These do not decrease the value of
$h_n$, hence $g_n \geq h_n \geq 0$.
\end{proof}
The following Theorem is the central result in \cite{bakerNorine}.
\begin{theorem}
\label{th:caracEffective}
For any configuration $f$ one and only one of the following
assertions is satisfied:
(1) $f$ is $L_G$-effective
(2) There exists an acyclic orientation $\overrightarrow{G}$ such that
$C(\overrightarrow{G}) - f$ is $L_G$-effective.
\end{theorem}
\begin{proof}
Let $f$ be non $L_G$-effective, consider the parking configuration $g$ equivalent to $f$
and let $\overrightarrow{G}$ be the acyclic orientation given by Proposition \ref{prop:parkingToAcyclic}, let
$h= C(\overrightarrow{G}) -g$. Then for $i \neq n$ we have
$$ h_i = d_i^- - 1 - f_i \geq 0$$
and since $g_n <0$:
$$ h_n = -1 + g_n \geq 0.$$
Hence $h$ is effective, moreover since $f$ and $g$ are in the same class, so are
$C(\overrightarrow{G}) - f$ and $C(\overrightarrow{G})- g=h$ showing that
$C(\overrightarrow{G}) - f$ is $L_G$-effective.
%\medskip
Notice that
$f$ and $C(\overrightarrow{G}) - f$ cannot be both $L_G$-effective since
their sum $C(\overrightarrow{G})$ would be too, contradicting
Proposition \ref{propo:acyclicNonEffective}.
\end{proof}
\begin{corollary}
\label{cor:effectiveIfLargeDegree}
Any configuration $f$ with degree greater than $m-n$ is $L_G$-effective.
\end{corollary}
\begin{proof}
If $f$ such that $deg(f) > m-n $ is not $L_G$-effective, by the above
theorem there exists an acyclic orientation $\overrightarrow{G}$ of $G$
such that $C(\overrightarrow{G})- f$ is.
But the degree of this configuration is negative, giving a contradiction.
\end{proof}
\subsection{The rank of configurations}
From now on it will be convenient to denote effective configurations
using greek letters $\lambda, \mu$ and configurations with no particular
assumptions on them by letters $f, g, h$.
\subsubsection{Definition of the rank}
\begin{definition}
\label{def:rank}
The rank $\rho(f)$ of a configuration $f$ is the integer equal to:
\begin{itemize}
\item $-1$, if $f$ is non $L_G$-effective,
\item or, if $f$ is $L_G$-effective, the largest integer $r$
such that for any effective
configuration $\lambda$ of degree $r$ the configuration $f-\lambda$ is $L_G$-effective.
\end{itemize}
\end{definition}
Denoting {$ \mathbb{P}$} the set of effective configurations and
{$ \mathbb{E}$} the set of $L_G$-effective configurations this definition
can be given by the following compact formula which is valid in both
cases:
$$ \rho(f) +1 = \min_{\displaystyle \lambda \in \mathbb{P}, f- \lambda\notin \mathbb{E} }\ \ \ deg(\lambda)$$
In other words let $f$ be a configuration of rank $\rho(f)$ and
{$\lambda $} be an effective configuration such that
$deg(\lambda) \leq \rho(f)$ then {$f-\lambda$} is $L_G$-effective; moreover there exists
an effective configuration $\mu$ of degree $\rho(f) + 1$ such that $f-\mu$ is
not $L_G$-effective.
\bigskip
An immediate consequence of this definition is that if
$deg(f) < 0 $ or if $f =C(\overrightarrow{G})$
for an acyclic orientation $\overrightarrow{G}$ then the rank of $f$ is $-1$.
Moreover if two configurations $f$ and $g$ are such that
$f_i \leq g_i$ for all $i$ then $\rho(f) \leq \rho(g)$.
The following notion will be useful do prove properties of the rank:
\begin{definition}
\label{def:proofRank}
An effective configuration $\mu$ is a proof for the rank $\rho(f) $ of an $L_G$-effective
configuration $f$ if $f-\mu$ is not $L_G$-effective and $f-\lambda$ is $L_G$-effective for any
effective configuration $\lambda$ such that $deg(\lambda) < deg(\mu)$.
\end{definition}
Notice that if $\lambda$ is a proof for $\rho(f)$ then $\rho(f) =deg(\lambda) - 1$.
\begin{proposition}
\label{propo:largeDegreeRank}
A configuration $f$ of degree greater than $2m-2n$ has rank
$$ r= deg(f) - m +n -1$$
\end{proposition}
\begin{proof}
We first show that for any effective configuration $\lambda$ such that $deg(\lambda) =r$, the configuration
$f-\lambda$ is $L_G$-effective. This follows from $deg(f - \lambda) = deg(f) - r = m-n+1$
by Corollary \ref{cor:effectiveIfLargeDegree}.
%\medskip
We now build a effective configuration $\lambda$ of degree $r+1$ such
that $f-\lambda$ is not $L_G$-effective. Consider any acyclic orientation
$\overrightarrow{G}$ of $G$ and let $g = f- C(\overrightarrow{G})$
then $g$ is $L_G$-effective since its degree is equal to $deg(f) - m +n$
hence greater than $m-n$. Let $\lambda$ be the effective configuration
such that $ g \simil \lambda$, then $f-\lambda$ is such that
$$C(\overrightarrow{G}) \simil f-g \simil f - \lambda$$
so that $f-\lambda$ is not $L_G$-effective by Proposition \ref{propo:acyclicNonEffective}.
And the Proposition results from:
$$deg(\lambda) = deg(g) = deg(f) - deg(C(\overrightarrow{G})) = deg(f) -m +n = r+1$$
\end{proof}
\subsubsection{Riemann-Roch like theorem for graphs}
We give here a proof of the following theorem first proved in \cite{bakerNorine} which we estimate shorter and simpler
than the original one.
\begin{theorem}
\label{th:RR}
Let {$\kappa$} be the configuration such that {$\kappa_i = d_i -2$} for all $1 \leq i \leq n$,
so that {$deg(\kappa) = 2(m-n)$}. Any configuration {$f$} satisfies:
$$ \rho(f) - \rho(\kappa-f) \ \ = \ \ deg(f) + n - m$$
\end{theorem}
\begin{proof}
The main ingredient for the proof is to use Theorem \ref{th:caracEffective} and
remark that for any acyclic orientation $\overrightarrow{G}$ the orientation $\overleftarrow{G} $ of $G$ obtained from $\overrightarrow{G}$
by reversing the orientations of all the edges is such that: $C(\overrightarrow{G} )+ C(\overleftarrow{G})
=\kappa$.
%\medskip
Let $f$ be any configuration we first give an upper bound for $ \rho(\kappa-f)$, we define $\lambda$ to
be a proof for the rank of $f$ if $f$ is $L_G$-effective,
and to be equal to $0$ if $f$ is not $L_G$-effective. So that $\rho(f) = deg(\lambda) -1$ in both cases.
Since $f-\lambda$ is not $L_G$-effective, we have by Theorem \ref{th:caracEffective} that there exists
an acyclic orientation $\overrightarrow{G}$ of $G$ such that
$C(\overrightarrow{G}) - (f-\lambda)$ is $L_G$-effective, hence equivalent to an effective configuration
$\mu$. This may be written as:
\begin{equation}
\label{eq:proofRR1}
C(\overrightarrow{G}) - (f-\lambda) \simil \mu
\end{equation}
Now consider the orientation $\overleftarrow{G} $ of $G$ obtained from $\overrightarrow{G}$
by reversing the orientations of all the arrows, clearly $C(\overrightarrow{G}) + C(\overleftarrow{G})
=\kappa$. Hence adding $C(\overleftarrow{G})$ to both sides of (\ref{eq:proofRR1}) we have:
\begin{equation}
\label{eq:proofRR2}
\kappa- (f - \lambda) \simil \mu + C(\overleftarrow{G})
\end{equation}
which may be written as:
$$ (\kappa - f) - \mu \simil C(\overleftarrow{G}) -\lambda$$
Giving that $\kappa-f - \mu$ is not $L_G$-effective since the reverse of an acyclic orientation is also acyclic.
Hence by the definition of the rank we have
\begin{equation}
\label{eq:proofRR3}
\rho(\kappa-f) < deg(\mu)
\end{equation}
The degree of $\mu$ is obtained from (\ref{eq:proofRR1}) giving:
$$ deg(\mu) = deg(C(\overrightarrow{G})) - deg(f) + deg(\lambda) = m-n -deg(f) + \rho(f) +1$$
and:
\begin{equation}
\label{eq:proofRR4}
\rho(\kappa-f) < m-n -deg(f) + \rho(f) +1
\end{equation}
%\medskip
Now to obtain a lower bound for $\rho(\kappa-f)$ we exchange the roles of $f$ and $\kappa-f$ giving:
\begin{equation}
\label{eq:proofRR5}
\rho(f) < m-n -deg(\kappa-u) + \rho(\kappa-u) +1
\end{equation}
Since $deg(\kappa-u) = 2(m-n) - deg(f)$, inequality (\ref{eq:proofRR5}) may be written as:
\begin{equation}
\label{eq:proofRR6}
\rho(f) + m-n -deg(f) -1 < \rho(\kappa-f)
\end{equation}
Comparing inequalities (\ref{eq:proofRR4}) and (\ref{eq:proofRR6}), and noticing that the
rank is an integer gives
$$\rho(f) + m-n -deg(f) = \rho(\kappa-f) $$
hence proving the Theorem.
\end{proof}
\subsection{Enumerating the effective configurations}
\begin{proposition}
\label{polTutteNbEffective}
Let $T_G(x,y)$ be the Tutte polynomial of the graph $G$,
and let $t_i$ be the integer coefficients given by: $$T_G(1,y) =
\sum_{i=0}^{m-n+1} t_iy^i$$
Then the number of non equivalent $L_G$-effective configurations of degree $d$
is given by:
$$ \sum_{k = m-n+1-d}^{m-n+1} t_k$$
\end{proposition}
\begin{proof}
In \cite{merinoLopez} the level of a recurrent configuration $f$
was defined as
$$ level(f) \ \ = \ \ \sum_{i=0}^{n-1} f_i - m +d_n$$
where $d_n$ is the degree of the vertex $x_n$.
It was proved that this level varies from $0$ to $m-n+1$ and
that the number of recurrent
configurations of level $p$ and such that $x_n = q$
does not depend on $q$ and is equal to the coefficent $t_p$
of $y^p$ in the evaluation of the Tutte polynomial $T_G(x,y)$ of $G$ for $x=1$.
A bijective proof of this result was given in \cite{coriLeBorgne1}.
Using the bijection $\beta$ defined in Proposition \ref{prop:recToParking}
we have that the number of parking configurations $g$ such that
$\sum_{i=1}^{n-1} g_i = j$ and a given value for $g_n$
is equal to the number of recurrent
configurations $f$ such that:
$$\sum_{i=1}^{n-1} f_i = \sum_{i=1}^{n-1} (d_i - 1 - g_i) = \ \ 2m - d_n - (n-1) -j$$
and $f_n = d_n-1 - g_n$, which
is the number of recurrent configurations of level $k=m-n+1-j$ and a given value of $f_n$.
This number is equal to $t_k$.
In order that the configuration $g$ of degree $d$ to be $L_G$-effective we must have $g_n \geq 0$
so that $k$ must be greater or equal to 0 and not greater than $m-n+1$,
thus ending the proof.
\end{proof}
The generating function for non-equivalent $L_G$-effective configurations according to the degree counted by the variable $y$ is $\frac{y^{m-n+1}}{1-y}T_G(1,y^{-1})$.
\end{document}
*