 \documentclass[12pt,reqno]{amsart}
\usepackage[latin1]{inputenc}
\usepackage{subfigure}
\usepackage{color}
\usepackage{enumerate}
\usepackage[headings]{fullpage}
\usepackage{dsfont}
\usepackage{tikz}
\usepackage{mathtools}
\usetikzlibrary{intersections,patterns,arrows,decorations.pathreplacing}
\usetikzlibrary{graphs,positioning}

\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}_+}
\def \beq{\begin{equation}}
\def \eq{\end{equation}}
\def \rm{\mathrm{Rec}^m}
\def \out{\mathrm{out}}
\def \E{\mathrm{Exc}}
\def \des{\mathrm{desc}}
\def \OO{\mathcal{O}}
\def \SS{\mathrm{Sym}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{pro}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}

\theoremstyle{definition}

\newtheorem{defn}[thm]{Definition}

\theoremstyle{remark}

\newtheorem{rem}[thm]{Remark}
\newtheorem{example}[thm]{Example}

%\newcommand\mps[1]{\marginpar[\raggedleft\tiny\sf\textcolor{blue}{#1}]{\raggedright\tiny\sf\textcolor{blue}{#1}}} %margin comments

\newcommand{\level}[2]{\mathrm{level}_{#2}\left(#1\right)}
\newcommand{\Stab}[2]{\mathrm{Stable}_{#2}\left(#1\right)}
\newcommand{\subg}[2]{#1 [ #2]} 			% G[X] = \subg{G}{X}, the subgraph of G induced by X
\newcommand\Rec[2]{\mathrm{Rec}_{#2}\left(#1\right)} 	% Rec_{v_0}(G) = \Rec{G}{v_0}
\newcommand\Levelpoly[3]{\mathrm{Level}_{#1,#2}\left(#3\right)} 	% Level_{G,v_0}(x) = \Levelpoly{G}{v_0}{x}
\newcommand{\gas}[2]{(#1,#2)}  				% gas=Graph And Sink  (G,v_0)=\gas{G}{v_0}
\newcommand{\Config}[2]{\mathrm{Config}_{#2}(#1)}    	% Config_{v_0}(G) = \Config{G}{v_0}
\newcommand{\rest}[2]{#1_{[#2]}}    			% restriction of V to {v_i,...,v_j}
\newcommand{\nodes}[1]{\mathsf{nodes}\left(#1\right)}	% nodes(T) = \nodes{T}
\newcommand{\parent}[1]{\mathsf{parent}(#1)}
\newcommand{\Dyck}{\mathrm{Dyck}}
\newcommand{\KRec}[1]{\Rec{#1}{}}

\def\softgrey{0.7}
\definecolor{mygray}{rgb}{\softgrey,\softgrey,\softgrey}

\newcommand{\thomastikzone}{
\begin{tikzpicture}
\node (v0) at (0,0) {$v_0$};
\node (v1) at (2,0) {$v_1$};
\node (v4) at (2.5,1.5) {$v_4$};
\node (v2) at (1,2.5) {$v_2$};
\node (v3) at (-0.5,1.5) {$v_3$};
\draw (v0)--(v1)--(v4)--(v2)--(v3)--(v0)--(v4)--(v1)--(v3)--(v4)--(v0)--(v2)--(v1);

\node (v5) at (-2,2) {$v_5$};
\draw (v3)--(v5);

%triangle with extra edge
\node (v6) at (-3,3.5) {$v_6$};
\node (v7) at (-1,3.5) {$v_7$};
\draw (v5)--(v6)--(v7)--(v5);
\draw (v5) to [out=150,in=270] (v6);

%second pentagram
\node (v11) at (1,3.5) {$v_{11}$};
\node (v10) at (1.5,5) {$v_{10}$};
\node (v9) at (0,6) {$v_9$};
\node (v8) at (-1.5,5) {$v_8$};
\draw (v7)--(v11)--(v10)--(v9)--(v8)--(v7)--(v10)--(v11)--(v8)--(v10)--(v7)--(v9)--(v11);

%K_4^2
\node (v13) at (6.5,1.5) {$v_{13}$};
\node (v12) at (4.5,4.5) {$v_{12}$};
\node (v14) at (4.5,2.5) {$v_{14}$};
\draw (v4)--(v13)--(v12)--(v4);
\draw (v4) to [out=85,in=200] (v12);
\draw (v4) to [out=335,in=205] (v13);
\draw (v12) to [out=340,in=95] (v13);
\draw (v4) to [out=15,in=230] (v14);
\draw (v4) to [out=45,in=190] (v14);
\draw (v13) to [out=135,in=350] (v14);
\draw (v13) to [out=165,in=310] (v14);
\draw (v12) to [out=250,in=110] (v14);
\draw (v12) to [out=290,in=70] (v14);
\end{tikzpicture}
}


\newcommand{\thomastikztwo}{
\subfigure[The cv-tree structure of the graph in Figure~\ref{fig:smaller_ex}.]{
	\begin{tikzpicture}
	\node (0) at (0,0) {$0$};
	\node (1) at (-2,1.5) {$1$};
	\node (2) at (-2,3) {$2$};
	\node (3) at (1,1.5) {$3$};
	\draw (0)--(1)--(2);
	\draw (0)--(3);
	\end{tikzpicture}
}
\subfigure[The constituent graphs of the cv-tree for Figure~\ref{fig:smaller_ex}. 
In the pentagram on the left, graph $H_0$ consists of those labels to the left of the `$/$'
and graph $H_2$ consists of those labels to the right of `$/$'. Both are isomorphic to $K_5$.
]{
	\begin{tikzpicture}
	%component H_0=H_2
	\node (v0) at (0,0) {$v_0/v_7$};
	\node (v1) at (2,0) {$v_1/v_{11}$};
	\node (v4) at (2.5,1.5) {$v_4/v_{10}$};
	\node (v2) at (1,2.5) {$v_2/v_{9}$};
	\node (v3) at (-0.5,1.5) {$v_3/v_{8}$};
	\draw (v0)--(v1)--(v4)--(v2)--(v3)--(v0)--(v4)--(v1)--(v3)--(v4)--(v0)--(v2)--(v1);
	\node [below,yshift=-10pt] at (1,0) {\large $H_0\cong H_2 \cong K_5$};
	%component H_1
	\node (v5) at (6,0) {$v_5$};
	\node (v6) at (5,1.5) {$v_6$};
	\node (v7) at (7,1.5) {$v_7$};
	\draw (v5)--(v6)--(v7)--(v5);
	\node [below,yshift=-10pt] at (6,0) {\large $H_1$};
	%component H_3
	\node (v4) at (9.5,0) {$v_4$};
	\node (v13) at (13.5,0) {$v_{13}$};
	\node (v12) at (11.5,3) {$v_{12}$};
	\node (v14) at (11.5,1) {$v_{14}$};
	\draw (v4)--(v13)--(v12)--(v4);
	\draw (v4) to [out=85,in=200] (v12);
	\draw (v4) to [out=335,in=205] (v13);
	\draw (v12) to [out=340,in=95] (v13);
	\draw (v4) to [out=15,in=230] (v14);
	\draw (v4) to [out=45,in=190] (v14);
	\draw (v13) to [out=135,in=350] (v14);
	\draw (v13) to [out=165,in=310] (v14);
	\draw (v12) to [out=250,in=110] (v14);
	\draw (v12) to [out=290,in=70] (v14);
	\node [below,yshift=-10pt] at (11.5,-0.3) {\large $H_3\cong K_4^{(2)}$};
	\end{tikzpicture}
}
}



\newcommand{\marktikzone}{
\begin{tikzpicture}
\def\myl{2}
\node (v0) at (0,0) {$v_0$};
\foreach \aa/\ll/\mm in {45/v1/v_1, 135/v2/v_2, 225/v3/v_3, 315/v4/v_4}
	\node (\ll)  at (\aa:\myl) {$\mm$};
\foreach \ii/\jj in {v0/v1,v0/v2,v0/v3,v0/v4,v1/v2,v1/v4,v2/v3,v3/v4}
	\draw (\ii)--(\jj);
\draw (v2) to [out=292,in=157] (v4);
\draw (v3) to [out=67.5,in=202.5] (v1);
\def\mya{20}
\def\nya{45-\mya}
\def\nyb{45+\mya}
\def\myr{3.5}
\def\mys{5}
\def\myb{10}
\def\oya{45-\myb}
\def\oyb{45+\myb}
\def\nyya{90+\nya}
\def\nyyb{90+\nyb}
\def\oyya{90+\oya}
\def\oyyb{90+\oyb}
\def\nyyya{180+\nya}
\def\nyyyb{180+\nyb}
\def\oyyya{180+\oya}
\def\oyyyb{180+\oyb}
\def\nyyyya{270+\nya}
\def\nyyyyb{270+\nyb}
\def\oyyyya{270+\oya}
\def\oyyyyb{270+\oyb}
\foreach \aa/\ll/\vv/\xx in {\nya/v5/v_5/\myr, \oya/v6/v_6/\mys, \oyb/v7/v_7/\mys, \nyb/v8/v_8/\myr, 
	\nyya/v9/v_9/\myr, \nyyb/v12/v_{12}/\myr, \oyya/v10/v_{10}/\mys, \oyyb/v11/v_{11}/\mys,
	\nyyya/v13/v_{13}/\myr, \nyyyb/v16/v_{16}/\myr, \oyyya/v14/v_{14}/\mys, \oyyyb/v15/v_{15}/\mys,
	\nyyyya/v17/v_{17}/\myr, \nyyyyb/v20/v_{20}/\myr, \oyyyya/v18/v_{18}/\mys, \oyyyyb/v19/v_{19}/\mys}
	{
	\node (\ll)  at (\aa:\xx) {$\vv$};
	%\draw [fill] (\ll) circle [radius=0.05];
	}
\foreach \xx/\yy in { v1/v5,v1/v6,v1/v7,v1/v8,v5/v6,v5/v7,v5/v8,v6/v7,v6/v8,v7/v8,v2/v9,v2/v10,v2/v11,v2/v12,v9/v10,v9/v11,v9/v12,v10/v11,v10/v12,v11/v12,v3/v13,v3/v14,v3/v15,v3/v16,v13/v14,v13/v15,v13/v16,v14/v15,v14/v16,v15/v16,v4/v17,v4/v18,v4/v19,v4/v20,v17/v18,v17/v18,v17/v19,v17/v20,v18/v19,v18/v20,v19/v20}
	\draw (\xx)--(\yy);
\def\Aswana{\nya-20}
\def\Bswana{\nyb+20}
\def\Dswana{\myr+0.4}
\def\Aswanb{\nya-20}
\def\Bswanb{\nyb+20}
\def\Dswanb{\myr+1.6}
\def\Aswanc{\nya-6}
\def\Bswanc{\nyb+6}
\def\Dswanc{\myr+1.2}
\def\Asswana{\Aswana+90}
\def\Bsswana{\Bswana+90}
\def\Assswana{\Aswana+180}
\def\Bssswana{\Bswana+180}
\def\Asssswana{\Aswana+270}
\def\Bsssswana{\Bswana+270}
\def\Asswanb{\Aswanb+90}
\def\Bsswanb{\Bswanb+90}
\def\Assswanb{\Aswanb+180}
\def\Bssswanb{\Bswanb+180}
\def\Asssswanb{\Aswanb+270}
\def\Bsssswanb{\Bswanb+270}
\def\Asswanc{\Aswanc+90}
\def\Bsswanc{\Bswanc+90}
\def\Assswanc{\Aswanc+180}
\def\Bssswanc{\Bswanc+180}
\def\Asssswanc{\Aswanc+270}
\def\Bsssswanc{\Bswanc+270}
\foreach \aa/\ll/\vv/\xx in {
	\Aswana/v21/v_{21}/\Dswana, \Aswanb/v22/v_{22}/\Dswanb, \Aswanc/v23/v_{23}/\Dswanc,
	\Asswana/v33/v_{33}/\Dswana, \Asswanb/v34/v_{34}/\Dswanb, \Asswanc/v35/v_{35}/\Dswanc,
	\Assswana/v45/v_{45}/\Dswana, \Assswanb/v46/v_{46}/\Dswanb, \Assswanc/v47/v_{47}/\Dswanc,
	\Asssswana/v57/v_{57}/\Dswana, \Asssswanb/v58/v_{58}/\Dswanb, \Asssswanc/v59/v_{59}/\Dswanc,
	\Bswana/v30/v_{30}/\Dswana, \Bswanb/v31/v_{31}/\Dswanb, \Bswanc/v32/v_{32}/\Dswanc,
	\Bsswana/v42/v_{42}/\Dswana, \Bsswanb/v43/v_{43}/\Dswanb, \Bsswanc/v44/v_{44}/\Dswanc,
	\Bssswana/v54/v_{54}/\Dswana, \Bssswanb/v55/v_{55}/\Dswanb, \Bssswanc/v56/v_{56}/\Dswanc,
	\Bsssswana/v66/v_{66}/\Dswana, \Bsssswanb/v67/v_{67}/\Dswanb, \Bsssswanc/v68/v_{68}/\Dswanc
	}
	\node (\ll)  at (\aa:\xx) {$\vv$};
\foreach \xx/\yy in {v5/v21,v5/v22,v5/v23,v21/v22,v21/v23,v22/v23,v9/v33,v9/v34,v9/v35,v33/v34,v33/v35,v34/v35,v13/v45,v13/v46,v13/v47,v45/v46,v45/v47,v46/v47,v17/v57,v17/v58,v17/v59,v57/v58,v57/v59,v58/v59}
	\draw (\xx)--(\yy);

\foreach \xx in {v8,v30,v31,v32}
	\foreach \yy in {v8,v30,v31,v32}
		\draw (\xx)--(\yy);
\foreach \xx in {v12,v42,v43,v44}
	\foreach \yy in {v12,v42,v43,v44}
		\draw (\xx)--(\yy);
\foreach \xx in {v16,v54,v55,v56}
	\foreach \yy in {v16,v54,v55,v56}
		\draw (\xx)--(\yy);
\foreach \xx in {v20,v66,v67,v68}
	\foreach \yy in {v20,v66,v67,v68}
		\draw (\xx)--(\yy);

\def\bang{5}
\def\Adonka{\oya-\bang}  % angle for v6 -10
\def\Adonkb{\oya}  % angle for v6
\def\Adonkc{\oya+\bang}  % angle for v6
\def\Aadonka{\Adonka+90}
\def\Aadonkb{\Adonkb+90}
\def\Aadonkc{\Adonkc+90}
\def\Aaadonka{\Adonka+180}
\def\Aaadonkb{\Adonkb+180}
\def\Aaadonkc{\Adonkc+180}
\def\Aaaadonka{\Adonka+270}
\def\Aaaadonkb{\Adonkb+270}
\def\Aaaadonkc{\Adonkc+270}
\def\Ddonka{\mys+2.4} % distance for v6+1
\def\Ddonkb{\mys+1.5} % distance for v6+1
\def\Ddonkc{\mys+2.4} % distance for v6+1
\foreach \aa/\ll/\vv/\xx in {
	\Adonka/v24/v_{24}/\Ddonka, \Adonkb/v25/v_{25}/\Ddonkb, \Adonkc/v26/v_{26}/\Ddonkc,
	\Aadonka/v36/v_{36}/\Ddonka, \Aadonkb/v37/v_{37}/\Ddonkb, \Aadonkc/v38/v_{38}/\Ddonkc,
	\Aaadonka/v48/v_{48}/\Ddonka, \Aaadonkb/v49/v_{49}/\Ddonkb, \Aaadonkc/v50/v_{50}/\Ddonkc,
	\Aaaadonka/v60/v_{60}/\Ddonka, \Aaaadonkb/v61/v_{61}/\Ddonkb, \Aaaadonkc/v62/v_{62}/\Ddonkc
}
	\node (\ll)  at (\aa:\xx) {$\vv$};
\foreach \xx/\yy in {v6/v24,v6/v25,v6/v26,v24/v25,v24/v26,v25/v26}
	\draw (\xx)--(\yy);
\foreach \xx in {v10,v36,v37,v38}
	\foreach \yy in {v10,v36,v37,v38}
		\draw (\xx)--(\yy);
\foreach \xx in {v14,v48,v49,v50}
	\foreach \yy in {v14,v48,v49,v50}
		\draw (\xx)--(\yy);
\foreach \xx in {v18,v60,v61,v62}
	\foreach \yy in {v18,v60,v61,v62}
		\draw (\xx)--(\yy);
% v24,v25,v26
\def\ADonka{\oyb-\bang}  % angle for v7 -10
\def\ADonkb{\oyb}  % angle for v7
\def\ADonkc{\oyb+\bang}  % angle for v7
\def\AaDonka{\ADonka+90}
\def\AaDonkb{\ADonkb+90}
\def\AaDonkc{\ADonkc+90}
\def\AaaDonka{\ADonka+180}
\def\AaaDonkb{\ADonkb+180}
\def\AaaDonkc{\ADonkc+180}
\def\AaaaDonka{\ADonka+270}
\def\AaaaDonkb{\ADonkb+270}
\def\AaaaDonkc{\ADonkc+270}
\def\DDonka{\mys+2.4} % distance for v6+1
\def\DDonkb{\mys+1.5} % distance for v6+1
\def\DDonkc{\mys+2.4} % distance for v6+1
\foreach \aa/\ll/\vv/\xx in {
	\ADonka/v27/v_{27}/\DDonka, \ADonkb/v28/v_{28}/\DDonkb, \ADonkc/v29/v_{29}/\DDonkc,
	\AaDonka/v39/v_{39}/\DDonka, \AaDonkb/v40/v_{40}/\DDonkb, \AaDonkc/v41/v_{41}/\DDonkc,
	\AaaDonka/v51/v_{51}/\DDonka, \AaaDonkb/v52/v_{52}/\DDonkb, \AaaDonkc/v53/v_{53}/\DDonkc,
	\AaaaDonka/v63/v_{63}/\DDonka, \AaaaDonkb/v64/v_{64}/\DDonkb, \AaaaDonkc/v65/v_{65}/\DDonkc
}
	\node (\ll)  at (\aa:\xx) {$\vv$};
\foreach \xx in {v7,v27,v28,v29}
	\foreach \yy in {v7,v27,v28,v29}
		\draw (\xx)--(\yy);
\foreach \xx in {v11,v39,v40,v41}
	\foreach \yy in {v11,v39,v40,v41}
		\draw (\xx)--(\yy);
\foreach \xx in {v15,v51,v52,v53}
	\foreach \yy in {v15,v51,v52,v53}
		\draw (\xx)--(\yy);
\foreach \xx in {v19,v63,v64,v65}
	\foreach \yy in {v19,v63,v64,v65}
		\draw (\xx)--(\yy);
\end{tikzpicture}
}

\newcommand{\marktikztwo}{
\begin{tikzpicture}
\def\myl{2}
\node (H0) at (0,0) {$0$};
\foreach \aa/\ll/\mm in {45/H1/1, 135/H2/2, 225/H3/3, 315/H4/4}
	\node (\ll)  at (\aa:\myl) {$\mm$};
\foreach \xx in {H1,H2,H3,H4}
	\draw (H0)--(\xx);
\def\bga{20}
\def\bgb{36.6}
\def\bgc{53.3}
\def\bgd{70}
\def\bgl{\myl+1.5}
\foreach \aa\ll\mm in {0/H5/5,90/H9/9,180/H13/{13},270/H17/{17}}
	\node (\ll) at (\aa+\bga:\bgl) {$\mm$};
\foreach \aa\ll\mm in {0/H6/6,90/H10/{10},180/H14/{14},270/H18/{18}}
	\node (\ll) at (\aa+\bgb:\bgl) {$\mm$};
\foreach \aa\ll\mm in {0/H7/7,90/H11/{11},180/H15/{15},270/H19/{19}}
	\node (\ll) at (\aa+\bgc:\bgl) {$\mm$};
\foreach \aa\ll\mm in {0/H8/8,90/H12/{12},180/H16/{16},270/H20/{20}}
	\node (\ll) at (\aa+\bgd:\bgl) {$\mm$};
\foreach \xx/\yy in {H1/H5,H1/H6,H1/H7,H1/H8,H2/H9,H2/H10,H2/H11,H2/H12,H3/H13,H3/H14,H3/H15,H3/H16,H4/H17,H4/H18,H4/H19,H4/H20}
	\draw (\xx)--(\yy);
\end{tikzpicture}
}

\newcommand{\tikzcyc}{
\begin{tikzpicture}
	\draw [thick] (0,1.5)--(-1,3)--(1,3)--(0,1.5);
	\draw [fill] (-1,3) circle [radius=0.1];
	\draw [fill] (1,3) circle [radius=0.1];
	\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
	\node[above,yshift=2pt] at (-1,3) {$v_1$};
	\node[above,yshift=2pt] at (1,3) {$v_2$};
	\node[right,xshift=2pt,yshift=-2pt] at (0,1.5) {$v_0$};
	\node [below,yshift=-5pt] at (0,1.5) {$G$};
\end{tikzpicture}
}

\newcommand{\tikzcycor}{
\begin{tikzpicture}
\path [name path=a] (0,1.5)--(-1,3);
\path [name path=b] (0,1.5)--(1,3);
\path [name path=c] (-1,3)--(1,3);
\draw [name path=1,fill=white,thick] (-1,3) circle [radius=0.25];
\draw [name path=2,fill=white,thick] (1,3) circle [radius=0.25];
\path [name intersections={of=a and 1,by=i1}];
\path [name intersections={of=b and 2,by=i2}];
\path [name intersections={of=c and 1,by=i3}];
\path [name intersections={of=c and 2,by=i4}];
\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
\draw [thick,->] (0,1.5)--(i1);
\draw [thick,->] (0,1.5)--(i2);
\draw [thick,->] (i4)--(i3);
\node at (-1,3) {$0$};
\node at (1,3) {$1$};
\end{tikzpicture}
}

\newcommand{\tikztreestructure}{
\begin{tikzpicture}[scale=0.6]
%
%component H_0
\draw [very thick,pattern=north west lines,pattern color=mygray] (0,0) to [out=165,in=270] (-3,2.5)
to [out=90,in=180] (0,4) to [out=0,in=90] (2,3) to [out=270,in=15] (0,0);
\node at (-1,2.5) {$H_0$};
%
%component H_1
\draw [very thick,pattern=north west lines,pattern color=mygray] (-3,2.5) to [out=270,in=270] (-6,2.5) 
to [out=90, in=195] (-5,5) to [out=15,in=165] (-4,5)
to [out=345,in=90] (-3,2.5);
\node at (-5,2.5) {$H_1$};
%
% component H_4
\draw [very thick,pattern=north west lines,pattern color=mygray] (-5,5) to [out=180,in=240] (-6.5,8)
to [out=60,in=105] (-5.5,8) to [out=295,in=90] (-5,5);
\node at (-6,6.5) {$H_4$};
%
%component H_5
\draw [very thick,pattern=north west lines,pattern color=mygray] (-4,5) to [out=90,in=180] (-2,8)
to [out=0, in=90] (-1,6) to [out=270,in=0] (-4,5);
\node at (-2,6) {$H_5$};
%
%component H_2
\draw [very thick,pattern=north west lines,pattern color=mygray] (0,4) to [out=105,in=270] (-0.5,6)
to [out=90,in=180] (0,7) to [out=0,in=90] (1.5,6) 
to [out = 270, in=75] (0,4);
\node at (0.8,5.7) {$H_2$};
%
%component H_6
\draw [very thick,pattern=north west lines,pattern color=mygray] (2,3) to [out=90, in=180] (4,7.5)
to [out=0,in=90] (6,5) to [out=270,in=0] (2,3);
\node at (3.1,6) {$H_6$};
%
%
%component H_7
\draw [very thick,pattern=north west lines,pattern color=mygray] (4,9.2) circle [radius=1.7];
\node at (4.8,9) {$H_7$};
%
%tree branches
\draw [very thick] 
(0,1.15) -- (-4.65,3.3) -- (-5.47,7) -- (-4.65,3.3) -- (-3.2,7);
%
%nodes 1,4,5
\draw [very thick, fill=white] (-4.65,3.3) circle [radius=0.2]
(-5.47,7) circle [radius=0.2]
(-3.2,7) circle [radius=0.2];
\node [above right, xshift=2pt, yshift=-4pt] at (-4.65,3.3) {$1$};
\node [above left, yshift=2pt] at (-5.47,7) {$4$};
\node [right, xshift=3pt] at (-3.2,7) {$5$};
%
%tree branch
\draw [very thick] (0,1.15) -- (0,6);
%
%node 2
\draw [very thick, fill=white] (0,6) circle [radius=0.2];
\node [above, yshift=3pt] at (0,6) {$2$};
%
%tree branches
\draw [very thick] (0,1.15) -- (4,4.9) -- (4,9.8);
%
%nodes 3,6
\draw [very thick, fill=white] (4,4.9) circle [radius=0.2]
(4,9.8) circle [radius=0.2];
\node [below right, yshift=-2pt] at (4,4.9) {$3$};
\node [above, yshift=4pt] at (4,9.8) {$6$};
%
%indication G
%\draw [ very thick, decorate, decoration={brace,amplitude=20pt,mirror}] (-6.5,-0.7) -- (6,-0.7) node[black,midway,yshift=-1.15cm] {$G$};
%sink
\draw [fill] (-0.2,-0.2) rectangle (0.2,0.2);
\node [below right, xshift=3pt, yshift=-4pt] at (0,0) {$v_0$};
%vertex v_1
\draw [fill] (-3,2.5) circle [radius=0.2];
\node [above right, xshift=2pt, yshift=-2pt] at (-3,2.5) {$v_1$};
%
%vertex v_2
\draw [fill] (0,4) circle [radius=0.2];
\node [above left, xshift=-2pt] at (0,4) {$v_2$};
%
%vertex v_3
\draw [fill] (2,3) circle [radius=0.2];
\node [below right,yshift=-2pt] at (2,3) {$v_3$};
%
%vertex v_4
\draw [fill] (-5,5) circle [radius=0.2];
\node [above left, xshift=-2pt, yshift=2pt] at (-5,5) {$v_4$};
%
%vertex v_5
\draw [fill] (-4,5) circle [radius=0.2];
\node [below right, xshift=-2pt, yshift=-5pt] at (-4,5) {$v_5$};
%vertex v_6
\draw [fill] (4,7.5) circle [radius=0.2];
\node [below right, yshift=-2pt] at (4,7.5) {$v_6$};
%
%node 0
\node [fill, very thick, pattern=north east lines,draw=none,minimum width=0.5cm,minimum height=0.1] at (0,1) {};
\draw [thick] (-0.25,1.15) -- (0.25,1.15);
\node [left, xshift=-5pt, yshift=-3pt] at (0,1.15) {$0$};
%
\end{tikzpicture}
}

\newcommand{\tikzmultiisthmus}{
\begin{tikzpicture}[scale=0.5]
\draw [very thick,pattern=north west lines,pattern color=mygray] (-2,0) circle [radius=2];
\draw [very thick,pattern=north west lines,pattern color=mygray] (3,0) circle [radius=2];
\draw [fill] (0,0) circle [radius=0.2];
\draw [fill] (1,0) circle [radius=0.2];
\draw [very thick] (0,0)--(1,0);
\draw [very thick] (1,0) arc (30:150:0.57735);
\draw [very thick] (1,0) arc (330:210:0.57735);
\draw [fill] (-4.2,-0.2) rectangle (-3.8,0.2);
\node [below left] at (-4.2,0) {$v_0$};
\node [below left, xshift=-1pt] at (0,0) {$v_n$};
\node [above right, xshift=1pt] at (1,0) {$v_{n+1}$};
\node at (-2,0) {{$H_1$}};
\node at (3,0) {{$H_2$}};
%\draw [ very thick, decorate, decoration={brace,amplitude=20pt,mirror}] (-4,-2) -- (5,-2) node[black,midway,yshift=-1.15cm] {$G$};
\end{tikzpicture}
}

\newcommand{\tikzisthmus}{
\begin{tikzpicture}[scale=0.5]
\draw [very thick,pattern=north west lines,pattern color=mygray] (-2,0) circle [radius=2];
\draw [very thick,pattern=north west lines,pattern color=mygray] (3,0) circle [radius=2];
\draw [fill] (0,0) circle [radius=0.2];
\draw [fill] (1,0) circle [radius=0.2];
\draw [very thick] (0,0)--(1,0);
\draw [fill] (-4.2,-0.2) rectangle (-3.8,0.2);
\node [below left] at (-4.2,0) {$v_0$};
\node [below left, xshift=-1pt] at (0,0) {$v_n$};
\node [above right, xshift=1pt] at (1,0) {$v_{n+1}$};
\node at (-2,0) {{$H_1$}};
\node at (3,0) {{$H_2$}};
%\draw [ very thick, decorate, decoration={brace,amplitude=20pt,mirror}] (-4,-2) -- (5,-2) node[black,midway,yshift=-1.15cm] {$G$};
\end{tikzpicture}
}

\newcommand{\tikzcutvertex}{
\begin{tikzpicture}[scale=0.5]
\draw [very thick,pattern=north west lines,pattern color=mygray] (-2,0) circle [radius=2];
\draw [very thick,pattern=north west lines,pattern color=mygray] (2,0) circle [radius=2];
\draw [fill] (0,0) circle [radius=0.2];
\draw [fill] (-4.2,-0.2) rectangle (-3.8,0.2);
\node [below left] at (-4.2,0) {$v_0$};
\node [above right, xshift=1pt] at (0,0) {$v_n$};
\node at (-2,0) {{$H_1$}};
\node at (2,0) {{$H_2$}};
%\draw [ very thick, decorate, decoration={brace,amplitude=20pt,mirror}] (-4,-2) -- (4,-2) node[black,midway,yshift=-1.15cm] {$G$};
\end{tikzpicture}
}

\newcommand{\tikzgraphedge}{
\def\harry{1}
\begin{tikzpicture}[scale=0.5]
\draw [very thick,pattern=north west lines,pattern color=mygray] (-2,0) circle [radius=2];
\draw [very thick,pattern=north west lines,pattern color=mygray] (2,0) circle [radius=2];
\draw [fill] (0,0) circle [radius=0.2];
\draw [fill] (-4.2,-0.2) rectangle (-3.8,0.2);
\node [below left] at (-4.2,0) {$v_0$};
\node [above right, xshift=1pt] at (0,0) {$v_n$};
\node at (-2,0) {{$H_1$}};
\node at (2,0) {{$H_2$}};
\draw [ very thick, decorate, decoration={brace,amplitude=12pt,mirror}]
(4,-2) -- (4,2);
\draw [very thick,<->] (5.6,0)--(7,0);
\draw [fill] (11+\harry,0) circle [radius=0.2];
\draw [line width=2] (7+\harry,0) -- (11+\harry,0);
\draw [very thick] (7+\harry,-0.25)--(7+\harry,0.25);
\node [fill, very thick, pattern=north east lines,draw=none,minimum width=0.3,minimum height=0.5cm] at (6.85+\harry,0) {};
\node [below, yshift=-10] at (7+\harry,0) {$H_1$ };
\node [below, yshift=-10] at (11+\harry,0) {$H_2$ };
\node [below, yshift=-2] at (9+\harry,0) {$v_n$ };
\end{tikzpicture}
}


\author{Mark Dukes and Thomas Selig}
\title{Decomposing recurrent states of the Abelian Sandpile Model}
\address{School of Mathematics and Statistics, University College Dublin, Dublin 4, Ireland.} 
\address{Department of Computer and Information Sciences, University of Strathclyde, Glasgow, G1 1XH, UK}
\keywords{Abelian sandpile model, recurrent states, graph decomposition, level polynomial, Tutte polynomial}
\thanks{Supported by the EPSRC grant EP/M015874/1: New combinatorial perspectives on the Abelian sandpile model}
\date{}

\begin{document}


\begin{abstract}
The recurrent states of the Abelian sandpile model (ASM) are those states that appear infinitely often.
For this reason they occupy a central position in ASM research.
The set of stable configurations on a graph form a Markov chain whereby a transition from a configuration $c$ to another $c'$ occurs if the addition of a grain to $c$ and the resulting sequence of topplings (if any) yields the state $c'$.
Checking whether a stable configuration is recurrent is a far from trivial task and requires Dhar's criterion, an algorithmic process, to be used.
We present several new results for classifying recurrent states of the Abelian sandpile model on graphs that may be decomposed in a variety of ways.
These results represent an enormous computational saving with respect to Dhar's criterion.
Furthermore, they allow us to classify, for certain families of graphs, recurrent states in terms of the recurrent states of its components.
We use these decompositions to give recurrence relations for the generating functions of the level statistic on the recurrent configurations.
We also interpret our results with respect to the sandpile group.
\end{abstract}

\maketitle

\thispagestyle{myheadings}
\font\Rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 77 \Rms (2018), Article~B77g\hfill}
\def\thepage{}

\section{Introduction}\label{sec:intro}
The Abelian sandpile model (ASM) has attracted a considerable amount of attention down through the years, 
and remains a constant source of new and interesting research topics. 
Perhaps the most recent of these is its relation to the discrete Riemann--Roch formula for graphs~\cite{Baker}.
One fundamental aspect of ASM research concerns the classification of the recurrent states of the model;
those states that appear infinitely often in the long-time running of the model. 

In order to calculate this important set of recurrent states of the ASM on a given graph one appeals to Dhar's criterion~\cite{Dhar},
an algorithmic procedure for checking when a stable configuration on a graph is recurrent.
Dhar's criterion is a global one in the sense that it induces a wave of topplings to occur throughout a graph and
it is indifferent to some sort of regular structure that may be inherent within the graph.
Consequently, the computations required to go through all possible stable configurations on a graph and check whether the criterion holds for each can take a significant amount of time.

In this paper we present several new results classifying recurrent states of the ASM on graphs which may be decomposed in a variety of ways.
The computational benefit of our results to the classification problem can be immense. 
The level statistic of a sandpile configuration, a quantity that is equal (up to an additive constant) to the sum of its heights, is studied with respect to these decompositions.

Alongside our classification results we give the generating functions of the level statistic (to be defined) on these graph decompositions, which we believe to represent a significant contribution in terms of computational savings. 
We then show the effect of these graph decompositions on the sandpile group, which is the set of recurrent states equipped with an Abelian addition operation.
These results also have an added benefit in that they provide a combinatorial setting in which to interpret set products of configurations that are almost recurrent states (up to some additive vector).
The studied decompositions in components of the graph are also lifted to product decompositions of the sandpile group of the whole graph into the sandpile group of the components. 
We almost interpret these decompositions in terms of set products of configurations (see Section~\ref{sec:sandpile_group} for details).

The motivation behind the current paper is twofold. 
First, we are interested in generalizing results of the first author for recurrent configurations of the sandpile model on the complete bipartite graph, and understanding how altering the graph (e.g. a doubling of edges) changes the combinatorial interpretation of the recurrent states as parallelogram polyominoes \cite{DLB,AADBH,AADB}.
Second, we are interested in understanding the sandpile model on graphs that have some notion of a `decomposition point', a vertex or edge that might afford product-style theorems to sets of recurrent states. The purpose behind this second goal is to attribute a meaning to products of combinatorial objects that represent recurrent states. 
Being able to explain this has the advantage that constructions on these objects (e.g. restricted lattice paths in the case of \cite{DLB}) and statistics upon them can be interpreted in terms of a toppling analysis on an appropriate graph.
Several other authors have considered decompositions on graphs in relation to the sandpile group and these include Lorenzini~\cite{lorenzini}, Jacobson et al.~\cite{jacobson}, Berget et al.~\cite{berget}, and Levine~\cite{levine}. In particular, Lorenzini~\cite{lorenzini} observed our Theorem~5.2 in the remark following the proof of his Proposition~1.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL MARK DUKES AND THOMAS SELIG}{\SMALL DECOMPOSING RECURRENT
STATES OF THE ABELIAN SANDPILE MODEL}

We now introduce the Abelian sandpile model on a graph and review some notation that is necessary in order for us to present our results.
Let $G=(V,E)$ be a finite, connected, loop-free, undirected multigraph with vertex set $V=\{v_0,\ldots,v_n\}$.  
Let $d_i = d_i^G = \mathrm{deg}(v_i)$ be the degree of the vertex $v_i$ in $G$.
We will consider the sandpile model on the graph $G$ in which a distinguished vertex, $v_0$ say, acts as a \emph{sink}.
We will indicate which vertex of a graph is being treated as a sink by writing it as a pair, e.g. $\gas{G}{v_0}$.

Let $\Z$ be the set of non-negative integers.
A \emph{configuration} on $\gas{G}{v_0}$ is a vector $c=(c_1,\ldots ,c_n) \in \Z^n$ that assigns the number $c_i$ to vertex $v_i$.
We think of $c_i$ as representing the number of grains of sand at the vertex $v_i$. 
Denote by $\Config{G}{v_0}$ the set of all configurations on $\gas{G}{v_0}$.
Let $\alpha_i \in \Z^n$ be the vector with $1$ in the $i$-th position and $0$ elsewhere. 
Throughout this paper, we will find it useful to refer to sets of vertices in $V$ and will use the following notation: given $i,j \in \Z$ with $i\leq j$, let $\rest{V}{i,j}=\{v_i,v_{i+1},\ldots,v_j\}$. 
Also, for some subset $W \subseteq V$, we let $\subg{G}{W}$ be the subgraph of $G$ with vertex set $W$ and edge set the edges of $G$ with both endpoints in $W$.

We will say that a vertex $v_i$ in a configuration $c=(c_1,\ldots ,c_n)\in \Config{G}{v_0}$ is \emph{stable} if $c_i < d_i$. 
Otherwise it is called \emph{unstable}. 
A configuration is called stable if all its non-sink vertices are stable, and we denote $\Stab{G}{v_0}$ the set of all stable configurations on $\gas{G}{v_0}$.

Unstable vertices may topple. 
We define the toppling operator $T_i$ corresponding to the toppling of an unstable vertex $v_i\in V$ in a configuration $c \in \Config{G}{v_0}$ by:
\beq\label{eq:toppling}
T_i(c) := c - d_i \alpha_i + \sum_{j: \{v_i,v_j\} \in E} \alpha_j,
\eq
where the sum is over all vertices adjacent to $v_i$, counted with multiplicity.

Performing this toppling may cause other vertices to become unstable, and we may topple these also. 
One can show that starting from some unstable configuration $c$ and toppling successively unstable vertices, we eventually reach a stable configuration $c'$ (think of the sink as absorbing grains). 
Moreover, this configuration $c'$ does not depend on the sequence in which vertices are toppled. 
We write $c' = \sigma(c)$ and call it the \emph{stabilization} of $c$.

We now define a Markov chain on the set of stable configurations of a graph $\gas{G}{v_0}$. 
Let $\mu=(\mu_1,\dots,\mu_n)$ be a probability distribution on $\{1,\dots,n\}$ such that $\mu_i>0$ for all $i \in \{1,\dots,n\}$. 
At each step of the Markov chain we add a grain at the vertex $v_i$ with probability $\mu_i$ and stabilize the resulting configuration.
Formally the transition matrix $Q$ is given by:
\begin{displaymath}
\text{for all } c,c' \in \Stab{G}{v_0}, \  Q(c,c')=\sum\limits_{i=1}^n \mu_i \mathds{1}_{\sigma \left(c+\alpha_i \right) = c'}.
\end{displaymath}

The recurrent states for the Markov chain are the set of configurations which appear infinitely often in the long-time running of the model. 
Given a graph $\gas{G}{v_0}$, we let $\Rec{G}{v}$ be the set of recurrent states on the graph $G$ in which the vertex $v$ acts as the sink.
We omit the subscript when it is clear which vertex is acting as the sink.

\begin{pro}\label{pro:rec_states}
A configuration $c \in \Config{G}{v_0}$ is \emph{recurrent} if there exists some configuration $a \in \Config{G}{v_0}$, satisfying $a_i \geq d_i$ for all $i \in \{1,\ldots,n\}$, such that $c=\sigma(a)$.
\end{pro}

An \emph{orientation} $\OO$ of $G$ is an orientation of every edge of $E$. 
If $H$ is a subgraph of $G$, then $\OO \big\vert_H$ will denote the restriction of the orientation $\OO$ to the edges of $H$.
An orientation is \emph{acyclic} if it contains no directed cycles. 
A vertex $v \in V$ is a \emph{source} of the orientation $\OO$ if it has no incoming edges. 
It is easy to check that an acyclic orientation has at least one source. 
The following result was first stated in these terms by Biggs \cite{Biggs}, although the author credits a previous paper \cite{GZ} as having equivalent results.

\begin{thm}\label{thm:acyclic_orientation}
Let $c \in \Stab{G}{v_0}$. 
Then $c$ is recurrent if, and only if, there exists an acyclic orientation $\OO$ of $G$, such that
\begin{enumerate}
\item[{\em(a)}] The sink $v_0$ is the unique source of $\OO$. We say that $\OO$ is \emph{sink-rooted}.
\item[{\em(b)}] We have: 
\beq\label{cond:or}
c_i \geq \out_i(\OO)\; \mbox{ for all $1\leq i \leq n$},
\eq 
where $\out_i(\OO)$ is the number of outgoing edges from the vertex $v_i$ in the orientation $\OO$.
\end{enumerate}
\end{thm}


Proposition~\ref{pro:rec_states} and Theorem~\ref{thm:acyclic_orientation} provide two characterizations of recurrent states. 
A further characterization, in terms of the so-called burning algorithm (see \cite{Red}) will be given in the proof of Theorem~\ref{thm:cut_vertex}. 
However, it is in general difficult to describe all the recurrent states for a given graph $\gas{G}{v_0}$.  
Using the matrix-tree theorem, one can show that the number of recurrent states equals the number of spanning trees of the graph \cite{Red}.
There are various bijective proofs of this result: in \cite{Red} the author provides a non-canonical bijection between recurrent states and spanning trees, while the authors of \cite{Ber} and \cite{CorLB} both provided refined versions which enumerate recurrent configurations according the the level statistic.


This statistic is a popular statistic on sandpile configurations, and we will study it in conjunction with some of our decomposition theorems.
Given a recurrent configuration $c \in \Rec{G}{v_0}$, define the \emph{level} of $c$ to be 
\beq\label{eq:def_level}
\level{c}{v_0} := d_{v_0} - |E| + \sum\limits_{v \in \rest{V}{1,n}} c_v,
\eq 
where $|E|$ denotes the number of elements in the set $E$.
From \cite[Thm. 3.5]{Lop} we have that if $G=(V,E)$ is a graph and $c \in \Rec{G}{v_0}$, 
then $0\leq \level{c}{v_0} \leq |E|-|V|$.
Consequently the level of a recurrent configuration is always a non-negative integer.
We define the \emph{level polynomial} of a graph $G$ to be the generating function of the level statistic over the set of recurrent configurations on that graph;
\beq\label{eq:def_level_poly}
\Levelpoly{G}{v_0}{x} := \sum\limits_{c \in \Rec{G}{v_0}} x^{\level{c}{v_0}}.
\eq
Recall that the Tutte polynomial of a (connected) graph $G=(V,E)$ is defined by
\beq\label{eq:def_Tutte}
T_G(x,y) := \sum\limits_{S \subseteq E} (x-1)^{\mathrm{cc}(S) -1} (y-1)^{\mathrm{cc}(S) + \vert S \vert - \vert V \vert},
\eq
where for $S \subseteq E$, $\mathrm{cc}(S)$ denotes the number of connected components of the subgraph $(V,S)$.

The level and Tutte polynomials of a graph are related by the following well-known result 
that was initially proven by L\'opez \cite{Lop}, following a conjecture by Biggs. 
Subsequent combinatorial (bijective) proofs have been given, for instance by Cori and Le Borgne~\cite{CorLB}, and Bernardi~\cite{Ber}.

\begin{thm}\label{thm:Tutte_level}
Let $G$ be a graph. Then we have
$\Levelpoly{G}{v_0}{x} = T_G(1,x).$ In particular, the level polynomial is independent of the choice of sink.
\end{thm}

Theorem~\ref{thm:Tutte_level} makes some of the results of this paper such as Corollaries~\ref{cor:cut_vertex_level} or \ref{cor:isthmus_level} entirely natural in terms of spanning trees of the graph. However, the structure inherent to the sandpile model, both in the case of the Markov chain transitions previously mentioned in this section and of the additive structure of the sandpile group introduced in Section~\ref{sec:sandpile_group}, is much more explicit in terms of the recurrent states than it is in terms of the spanning trees. As such, the focus of this paper is very much on the explicit description of the recurrent states of the graph with respect to the decompositions studied, which is more difficult.

\begin{example}\label{ex:intro}

Let $G$ be the graph in Figure~\ref{fig:cyc}, where the vertex $v_0$ acts as the sink. 

\begin{figure}[ht]
\centering
\tikzcyc
\caption{The graph $G$: the sink $v_0$ is represented by a square, the non sink vertices $v_1,v_2$ by circles.
The squares and circles will become important later in the paper when non-sink vertices may become sink vertices.
\label{fig:cyc}}
\end{figure}

We have $\Stab{G}{v_0} = \{ (0,0), (0,1), (1,0),(1,1) \}$. By Theorem~\ref{thm:acyclic_orientation}, the configuration $(0,0)$ cannot be recurrent. Indeed, any direction given to the edge $(v_1,v_2)$ would result in one of those two vertices having an outgoing edge, which would contradict Condition~\eqref{cond:or} (the inequality in Theorem~\ref{thm:acyclic_orientation}). For the configuration $(0,1)$, we build a sink-rooted, acyclic orientation which satisfies Condition~\eqref{cond:or} by directing the edges from $v_0$ to $v_1$, from $v_0$ to $v_2$, and from $v_2$ to $v_0$, as illustrated in Figure~\ref{fig:cycor}. Thus, by Theorem~\ref{thm:acyclic_orientation}, the configuration $(0,1)$ is recurrent. 

\begin{figure}[ht]
\centering
\tikzcycor
\caption{The configuration $(0,1)$ with the corresponding orientation.\label{fig:cycor}}
\end{figure}

By symmetry, the configuration $(1,0)$ is also recurrent. 
Finally, note that the orientation of Figure~\ref{fig:cycor} also satisfies Condition~\eqref{cond:or} for the configuration $(1,1)$, which is therefore recurrent. 
Finally, we conclude that 
\[ \Rec{G}{v_0} = \{ (0,1), (1,0),(1,1) \}. \]

We may deduce from this the level polynomial for the graph $G$. We get $ \Levelpoly{G}{v_0}{x} = x + 2 $. This may also be deduced from Theorem~\ref{thm:Tutte_level} since the Tutte polynomial of $G$ is given by $T_G(x,y)=x^2+x+y$, so that $T_G(1,x) = x+2$.

\end{example}

The process by which we determined that the configuration $(1,1)$ is also recurrent in Example~\ref{ex:intro} above leads to an interesting generalization. Given a graph $(G,v_0)$, there is a natural partial order $\preceq$ on the set $\Config{G}{v_0}$ of all configurations by setting $c \preceq c'$ if, and only if, $c_i \leq c'_i$ for all $ i \in \{1,\ldots,n\}$.

Now notice that, if we have a recurrent configuration $ c=(c_1,\ldots,c_n) $ and an orientation $ \OO $ which satisfies Condition~\eqref{cond:or},
 then the same orientation $\OO$ also satisfies the condition for the configuration $c+\alpha_i$, for any $ i \in \{1,\ldots,n\}$. This is also immediate from the definition of the Markov chain, since there is a positive probability of adding a grain at the vertex $v_i$, thus $Q(c,c+\alpha_i)>0$. This leads to the following result.

\begin{pro}\label{pro:poset}
For any graph $G$, the configuration $c^{\mathrm{max}}:=(d_1-1,\ldots,d_n-1)$ is recurrent. It is the maximal recurrent configuration for the partial order $\preceq$. Moreover, for any $c=(c_1,\ldots,c_n)$, the interval $\left[c,c^{\mathrm{max}}\right]$ of the poset $(\Rec{G}{v_0},\preceq)$ is given by
\begin{displaymath}
\left[c,c^{\mathrm{max}}\right] = \{c_1,c_1+1,\ldots ,d_1-1\} \times \ldots \times \{c_n,c_n+1,\ldots ,d_n-1\}.
\end{displaymath} 
\end{pro}

There is a well established characterization of recurrent states of the sandpile model on the complete graph in terms of parking functions.
We will make use of this in later sections, but will state it here since it serves as a good reference for considering small examples throughout the paper.
\begin{defn}
A {\it{parking function of size $n$}} is a sequence of non-negative integers\break $(a_1,\ldots,a_n)$ such that, 
when they are rearranged in weakly increasing order as $(b_1,\ldots,b_n)$, we have $b_i<i$ for all $1\leq i \leq n$.
\end{defn}

\begin{thm}\label{crecs}
The set $\Rec{K_n}{v_0}$ is characterized by the following set
$$\Rec{K_n}{v_0} = \{ (n-2-a_1 , \ldots, n-2-a_{n-1}) ~:~ (a_1,\ldots,a_{n-1}) \mbox{ if a parking function of size $n$}\}.$$
\end{thm}

Parking functions can be easily written down from permuting the heights of horizontal steps of Dyck paths/sequences.
Let $\Dyck_n = \{ (a_1,\ldots,a_n) ~:~ a_i \in \{0,\ldots,i-1\}\mbox{ and } 
a_1\leq a_2 \leq \cdots \leq a_n\}$.
For example, 
\begin{align}\label{threelist}
\Dyck_3 = \{(0,0,0),(0,0,1),(0,0,2),(0,1,1),(0,1,2)\}.
\end{align}
Using Theorem~\ref{crecs} in conjunction with the notion of Dyck paths/sequences allows us to write down an explicit expression for 
$\Rec{K_n}{v_0}$:
\begin{align}\label{computerecs}
\Rec{K_n}{v_0} = \{ (n-2-a_{\pi(1)},\ldots , n-2-a_{\pi(n-1)}) \,:\, \pi \in \SS_{n-1},
(a_1,\ldots,a_{n-1}) \in \Dyck_{n-1}\}.
\end{align}

\begin{example}\label{k4example}
We have
\begin{align}
\Rec{K_4}{v_0} = \{ (2-a_{\pi(1)},2-a_{\pi(2)},2-a_{\pi(3)}) ~:~ \pi \in \SS_3 \mbox{ and } (a_1,a_2,a_3) \in {\Dyck_3}\}.
\end{align}
Using the list in Equation~\eqref{threelist}, we have
\begin{align}
\Rec{K_4}{v_0} =& \{ (2,2,2),(2,2,1), (2,1,2), (1,2,2), (2,2,0), (2,0,2), (0,2,2), (2,1,1), \nonumber\\
& \;\; (1,2,1), (1,1,2), (2,1,0), (2,0,1), (1,2,0), (1,0,2), (0,1,2), (0,2,1)\}. \label{k4recs}
\end{align}
\end{example}

\begin{example}\label{k5example}
To determine 
$\Rec{K_5}{v_0}$, 
we list all 14 elements of $\Dyck_4$:
\begin{align*}
\Dyck_4=& \{
(0,0,0,0),
(0,0,0,1),
(0,0,0,2),
(0,0,0,3),
(0,0,1,1),
(0,0,1,2),
(0,0,1,3),\\
& \;\;
(0,0,2,2),
(0,0,2,3),
(0,1,1,1),
(0,1,1,2),
(0,1,1,3),
(0,1,2,2),
(0,1,2,3)\}
\end{align*}
Using this we have
$$
\Rec{K_5}{v_0} = \{ (3-a_{\pi(1)},3-a_{\pi(2)},3-a_{\pi(3)},3-a_{\pi(4)}) ~:~ \pi \in \SS_4 \mbox{ and } (a_1,a_2,a_3) \in {\Dyck_4}\}.$$
There will be 125 of these sequences, and we do not list them here.
\end{example}

Note that in general there are $n^{n-2}$ parking configurations on $K_n$, so the set of recurrent configurations may be huge.

\section{Recurrent states under edge duplication}\label{sec:Gk}
In this section we will show how recurrent states of the sandpile model on a graph change when every edge of a graph is replaced with $k$ copies of itself.
Let $G=(V,E)$ be a graph. 
For a positive integer $k$ we define $G^{(k)}$ to be the multigraph $G$ where every edge of $E$ is replaced with $k$ copies of itself. 
That is $G^{(k)} = \left(V,E^{(k)}\right)$, where $E^{(k)}$ is the multiset $\bigcup\limits_{e \in E} \{e_1,\ldots,e_k\}$, with $e_j=e$ for all $j \in \{1,\ldots,k\}$.

\begin{thm}\label{thm:Gk}
Let $c = (c_1,\ldots,c_n) \in \Config{G}{v_0}$. Then the following are equivalent:
\begin{enumerate}
\item[{\em(a)}] $c \in \Rec{G^{(k)}}{v_0}$.
\item[{\em(b)}] \begin{math} \tilde{c}:=\left( \floor*{c_1/k},\ldots, \floor*{{c_n}/{k}} \right) \in \Rec{G}{v_0} \end{math}.
\end{enumerate}
\end{thm}

\begin{proof}
We first show that (a)${}\Rightarrow{}$(b). Assume that $c \in \Rec{G^{(k)}}{v_0}$. 
By Theorem~\ref{thm:acyclic_orientation}, there exists a sink-rooted acyclic orientation $\OO^{(k)}$ on $G^{(k)}$, such that:
\beq\label{pr:comp}
c_i \geq \out_i\left(\OO^{(k)}\right) \;\; \mbox{ for all $1\leq i \leq n$.}
\eq 
Now since $\OO^{(k)}$ is acyclic, for any edge $e \in E$, the corresponding edges $e_1,\ldots,e_k \in E^{(k)}$ must all be oriented in the same direction (if two are oriented in opposite directions, those two edges create a directed cycle). 
By giving the edge $e$ the same orientation as that of the corresponding edges $e_1,\ldots,e_k$, this allows us to define an orientation $\OO$ on $G$, such that
\beq\label{Ok_to_O}
\out_i\left(\OO^{(k)}\right) = k\cdot \out_i(\OO) \;\; \mbox{ for all $1\leq i \leq n$.}
\eq 
Moreover, it is easy to check that since the orientation $\OO^{(k)}$ is sink-rooted and acyclic, so is the orientation $\OO$. Finally, we have:
\begin{displaymath} 
\out_i(\OO) = \frac1k \, \out_i\left(\OO^{(k)}\right) \leq \frac1k c_i = \frac{c_i}{k} \;\; \mbox{ for all $1\leq i \leq n$,}
\end{displaymath}
by using \eqref{Ok_to_O} followed by \eqref{pr:comp}. 
Since $\out_i(\OO)$ is an integer, this implies that
\begin{displaymath} 
\out_i(\OO) \leq \floor*{\frac{c_i}{k}} = \tilde{c}_i \;\; \mbox{ for all $1\leq i \leq n$.}
\end{displaymath}
Since $\OO$ is a sink-rooted acyclic orientation of $G$ satisfying the above, it follows from Theorem~\ref{thm:acyclic_orientation} that $\tilde{c} \in \Rec{G}{v_0}$.

We now show that (b)${}\Rightarrow{}$(a). Assume that $c$ is such that $\tilde{c} \in \Rec{G}{v_0}$. 
By Theorem~\ref{thm:acyclic_orientation}, there exists a sink-rooted acyclic orientation $\OO$ on $G$, such that:
\beq\label{pr:comp1}
\tilde{c}_i \geq \out_i(\OO) \;\;\mbox{ for all $1\leq i \leq n$}.
\eq 
Similarly to above, by orienting all edges $e_1,\ldots,e_k$ of $E^{(k)}$ corresponding to an edge $e$ of $E$ in the same direction as $e$, we get a sink-rooted acyclic orientation $\OO^{(k)}$ on $G^{(k)}$ satisfying Equation~\eqref{Ok_to_O}. It follows that:
\begin{displaymath} 
c_i \geq k\cdot \floor*{\frac{c_i}{k}} = k\cdot \tilde{c}_i \geq k\cdot \out_i(\OO) = \out_i\left(\OO^{(k)}\right) \;\;\mbox{ for all $1\leq i \leq n$},
\end{displaymath}
and as before, Theorem~\ref{thm:acyclic_orientation} implies that $c \in \Rec{G^{(k)}}{v_0}$.
\end{proof}

From Theorem~\ref{thm:Gk} we can deduce the following formula for the level polynomial of the graph $G^{(k)}$.

\begin{cor}\label{cor:level_Gk}
Let $k$ be a positive integer. We have: 
\begin{displaymath}
\Levelpoly{G^{(k)}}{v_0}{x} = \left(1+x+\ldots+x^{k-1}\right)^{\vert V \vert -1} \cdot \Levelpoly{G}{v_0}{x^k}.
\end{displaymath}
In particular, $ \left\vert \Rec{G^{(k)}}{v_0} \right\vert = k^{\left( \vert V \vert - 1 \right) } \vert \Rec{G}{v_0} \vert $.
\end{cor}

\begin{proof}
Let $c  \in \Config{G^{(k)}}{v_0}$, and $ \tilde{c}:=\left( \floor*{c_1/k},\ldots, \floor*{{c_n}/{k}} \right) $. 
Define $a_i:= c_i - k\floor*{c_i/k}$ for $i \in \{1,\ldots,n\}$. 
Standard floor inequalities show that $a_i \in \{0,\ldots,k-1\}$ for all $1\leq i \leq n$.

Thus Theorem~\ref{thm:Gk} can be re-stated as follows:
$ c = (c_1,\ldots,c_n) \in \Rec{G^{(k)}}{v_0}$ if, and only if, there exists a unique pair $(\gamma,r)$ with
$\gamma = (\gamma_1,\ldots,\gamma_n) \in \Rec{G}{v_0}, \ r=(r_1,\ldots,r_n) \in \{0,\ldots,k-1\}^n$
such that $c_i = k\gamma_i + r_i$ for all $1\leq i\leq n$.

If $c = (c_1,\ldots,c_n) \in \Rec{G^{(k)}}{v_0}$ then we can write
\begin{displaymath}
\level{c}{v_0} = d^{G^{(k)}}_{v_0} - \vert E^{(k)} \vert + \sum\limits_{i=1}^n c_i
= k d^G_{v_0} - k \vert E \vert + \sum\limits_{i=1}^n (k \gamma_i + r_i) = k \cdot \level{\gamma}{v_0} + \sum\limits_{i=1}^n r_i.
\end{displaymath}
Therefore, we can compute:
\begin{displaymath}
\begin{array}{ll}
\Levelpoly{G^{(k)}}{v_0}{x} 
	& = \sum\limits_{c \in \Rec{G^{(k)}}{v_0}} x^{\level{c}{v_0}} 
	~ = \sum\limits_{\substack{
	\gamma \in \Rec{G}{v_0}\\
	0\leq r_1,\ldots,r_n <k}
		}
		x^{( k \cdot \level{\gamma}{v_0} + r_1+\ldots+r_n)}\\[0.5em]
	&= \left( \sum\limits_{ 0\leq r_1,\ldots,r_n < k} \left(x^{r_1} \right) \ldots \left(x^{r_n}\right) \right) 
		\cdot 
		\left( \sum\limits_{\gamma \in \Rec{G}{v_0}} \left( x^k \right) ^{\level{\gamma}{v_0}} \right)\\[1em]
	&= \left(1+x+\ldots+x^{k-1}\right)^{n} \cdot \Levelpoly{G}{v_0}{x^k}.
\end{array}
\end{displaymath}
\end{proof}


\begin{example}\label{ex:Gk}

We develop an example to show some of the computational gains which can be made through applying Theorem~\ref{thm:Gk} and its corollary. Consider the graph $G$ from Figure~\ref{fig:ex_Gkthm} below. We wish to determine the recurrent configurations of $G^{(2)}$.

\begin{figure}[ht]
\centering
\begin{tikzpicture}

\draw [thick] (0,1.5)--(-1,3)--(1,3)--(0,1.5);
\draw [thick] (0,1.5) to [out=150,in=270] (-1,3);

\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
\draw [fill] (-1,3) circle [radius=0.1];
\draw [fill] (1,3) circle [radius=0.1];

\node[above,yshift=2pt] at (-1,3) {$v_1$};
\node[above,yshift=2pt] at (1,3) {$v_2$};
\node[right,xshift=2pt,yshift=-2pt] at (0,1.5) {$v_0$};

\node [below,yshift=-10pt] at (0,1.5) {{\large $G$}};

\draw [thick] (4,1.5)--(3,3)--(5,3)--(4,1.5);
\draw [thick] (4,1.5) to [out=150,in=270] (3,3);
\draw [thick] (4,1.5) to [out=180,in=240] (3,3);
\draw [thick] (4,1.5) to [out=90,in=330] (3,3);
\draw [thick] (3,3) to [out=30,in=150] (5,3);
\draw [thick] (5,3) to [out=270,in=30] (4,1.5);

\draw [fill] (3.9,1.4) rectangle (4.1,1.6);
\draw [fill] (3,3) circle [radius=0.1];
\draw [fill] (5,3) circle [radius=0.1];

\node[above,yshift=2pt] at (3,3) {$v_1$};
\node[above,yshift=2pt] at (5,3) {$v_2$};
\node[right,xshift=2pt,yshift=-2pt] at (4,1.5) {$v_0$};

\node [below,yshift=-10pt] at (4,1.5) {{\large $G^{(2)}$}};

\end{tikzpicture}
\caption{The graphs $G$ and $G^{(2)}$. \label{fig:ex_Gkthm}}
\end{figure}

We can show that $\Rec{G}{v_0} = \{(0,1),(1,0),(1,1),(2,0),(2,1) \}$. Now Theorem~\ref{thm:Gk} tells us that $ c = (c_1,c_2) \in \Rec{G^{(2)}}{v_0}$ if, and only if, there exists a unique pair $(\gamma,\alpha)$ with
$\gamma = (\gamma_1,\gamma_2) \in \Rec{G}{v_0}, \ \alpha=(\alpha_1,\alpha_2) \in \{0,1\}^2$
such that $c_i = k\gamma_i + \alpha_i$ for all $i=1,2$.

In words, recurrent configurations on $G^{(2)}$ are obtained from recurrent configurations on $G$ by multiplying them by two and adding up to one grain at each vertex. This is made clear in Table~\ref{tab:GtoGk}.

\begin{table}
\begin{center}
\begin{tabular}{c|c}
Recurrent & Corresponding recurrent \\
configurations on $G$  & configurations on $G^{(2)}$ \\
\hline
$(0,1)$ & $(0,2)$ \\
 & $(0,3),(1,2),(1,3)$ \\
\hline
$(1,0)$ & $(2,0)$ \\
 & $(2,1),(3,0),(3,1)$ \\
\hline
$(1,1)$ & $(2,2)$ \\
 & $(2,3),(3,2),(3,3)$ \\
\hline
$(2,0)$ & $(4,0)$ \\
 & $(4,1),(5,0),(5,1)$ \\
\hline
$(2,1)$ & $(4,2)$ \\
 & $(4,3),(5,2),(5,3)$ \\
\end{tabular}
\caption{The correspondence between recurrent configurations on $G$ and on $G^{(2)}$. \label{tab:GtoGk}}
\end{center}
\end{table}

This table allows us to determine $\Rec{G^{(2)}}{v_0}$. We may also compute the level polynomials. We get
\begin{displaymath}
\Levelpoly{G}{v_0}{x} = x^2+2x+2,
\end{displaymath}
and thus, by Corollary~\ref{cor:level_Gk}
\begin{displaymath}
\Levelpoly{G^{(k)}}{v_0}{x} = (1+x)^2 \cdot \left(\left(x^2\right)^2+2\left(x^2\right)+2\right) = x^6 + 2x^5 + 3x^4 + 4x^3 + 4x^2 + 4x + 2,
\end{displaymath}
which can also be computed directly using the second column of Table~\ref{tab:GtoGk}.
\end{example}

\section{Recurrent states on graphs having cut vertices}\label{sec:cut_vertex}
In this section we show how the recurrent states on a graph which contains a cut vertex may be decomposed into recurrent states on
the two different parts of the graph which meet at this cut vertex.
We then build on this result by showing that a graph whose set of cut vertices have a tree like structure has a recurrent configuration set that can be decomposed in a similar manner.

\begin{defn}
Let $G=(V,E)$ be a finite, connected graph. 
We say that $v \in V$ is a \emph{cut vertex} of $G$ if removing the vertex $v$ and all edges incident to $v$ makes $G$ disconnected.
\end{defn}

\begin{thm}\label{thm:cut_vertex}
Let $G=(V, E)$ be a finite, connected graph, on the vertex set $$V = \{ v_0,v_1, \ldots , v_{n+m} \}$$ where $m,n\geq 1$.
Assume that $v_n$ is a cut vertex of $G$. 
Let $H_1 := \subg{G}{\rest{V}{0,n}}$ and $H_2 := \subg{G}{\rest{V}{n,n+m}}$. 
Given $c =(c_1, \ldots, c_{n+m}) \in \Config{G}{v_0}$,
let $c^{(1)} := (c_1, \ldots, c_{n-1}, c_n - d^{H_2}_n)$ and $c^{(2)} := (c_{n+1}, \ldots, c_{n+m})$,
where $d^{H_2}_n$ is the degree of the vertex $v_n$ in the graph $H_2$.
Then 
$$c \in \Rec{G}{v_0} ~ \text{ if and only if } ~ 
c^{(1)} \in \Rec{H_1}{v_0} \mbox{ and }
c^{(2)} \in \Rec{H_2}{v_n}.
$$
\end{thm}

\begin{figure}[ht]
\centering
\tikzcutvertex
\caption{The graph $G$ with its cut vertex $v_n$.\label{tikz:cutvertex}}
\end{figure}

\begin{rem}
Theorem~\ref{thm:cut_vertex} is obvious in terms of the spanning trees of the graph. Indeed, the spanning trees of such a graph $G$ are simply given by the ``independent'' products of spanning trees of $H_1$ and $H_2$. The difficulty here is to describe such decompositions in terms of the recurrent states.
\end{rem}

\begin{proof}
First let us assume that $c^{(1)} \in \Rec{H_1}{v_0}$ and $c^{(2)} \in \Rec{H_2}{v_n}$. 
Then there exists a sink-rooted acyclic orientation $\OO_1$ of $H_1$, 
and an acyclic orientation $\OO_2$ of $H_2$ whose unique source is the vertex $v_n$, such that:
\begin{displaymath} 
c^{(1)}_i \geq \out_i(\OO_1), \mbox{ for all $1\leq i \leq n$, and }
c^{(2)}_j \geq \out_j(\OO_2), \mbox{ for all $n+1 \leq j \leq n+m$.}
\end{displaymath}
Since the edges of the graphs $H_1$ and $H_2$ form a partition of the edges of $G$, 
we may define an orientation $\OO:= \OO_1 \cup \OO_2$ of $G$. 
By construction, $\OO$ is sink-rooted and acyclic.

For $i \in \{1, \ldots, n-1 \}$, we have:
\begin{displaymath} 
c_i = c^{(1)}_i \geq \out_i(\OO_1) = \out_i(\OO).
\end{displaymath}
Similarly, for $j \in \{n+1, \ldots, n+m \}$, we have:
\begin{displaymath} 
c_j = c^{(2)}_j \geq \out_j(\OO_2) = \out_j(\OO).
\end{displaymath}
Finally, at the vertex $v_n$, we have:
\begin{displaymath} 
c_n = c^{(1)}_n + d^{H_2}_n \geq \out_n(\OO_1) + d^{H_2}_n = \out_n(\OO_1) + \out_n(\OO_2) = \out_n(\OO), 
\end{displaymath}
since $v_n$ is a source of the orientation $\OO_2$. 
Thus the orientation $\OO$ satisfies Condition~\eqref{cond:or}, 
and by Theorem~\ref{thm:acyclic_orientation}, the configuration $c$ is recurrent.

To show the converse, we first recall some results concerning the so-called \emph{burning algorithm} (see \cite{Red}). 
This algorithm inputs a stable configuration $a$ on a graph $G=(V, E)$, and establishes if $a$ is recurrent. 
We now describe this algorithm.

\begin{itemize}
\item[B1.] 	Initialise by setting $V^B_0 = \{ v_0 \}$. 
	The set $V^B_i$ will be the set of vertices burnt up to and including time $i$. 
\item[B2.] \begin{itemize}
	\item[(i)] Assume for some $i \geq 0$, we have constructed the set $V^B_{i}$ of vertices burnt up to and including time $i$.
	\item[(ii)] Let $V^U_{i}$ be the set of vertices not yet burnt and set  $G_i := \subg{G}{V^U_i}$. 
	\item[(iii)] Now set $\tilde{V}_i := \{ v \in V^U_i; \, a_v \geq d^{G_i}_v \}$ to be the 
		set of unstable vertices in the configuration $a$ restricted to $G_i$. 
	\item[(iv)] By construction, since $a$ is stable in the graph $G$, the instability of 
		any such vertex must arise from the burning of previous vertices. 
	\item[(v)] We set $V^B_{i+1} := V^B_i \cup \tilde{V}_i$.
	\end{itemize}
\item[B3.] The algorithm terminates when we reach a time $i$ such that no vertices can subsequently be burnt, i.e. $\tilde{V}_i = \emptyset$. 
It outputs $V^B:=V^B_i$, which is the set of all vertices burnt beforehand.
\end{itemize}
Notice that since $V^B_0 \subseteq V^B_1 \subseteq V^B_2 \subseteq \cdots \subseteq V$, the burning algorithm does indeed terminate.
Our interest lies in the following facts.

\begin{enumerate}
\item The configuration $a$ is recurrent if, and only if, $V^B = V$, i.e. the burning algorithm applied to $a$ burns all vertices of the initial graph.
\item Let $a \in \Rec{G}{v_0}$. 
	Define a total order $\prec_b$ on the set of vertices $V$ by 
	setting $v_i \prec_b v_j$ if, when applying the burning algorithm to $a$, either $v_i$ is burned before $v_j$, 
	or they are burned at the same time and $i<j$.
	Now define an orientation $\OO_b$ of $G$ by orienting the edge $\{v,w\}$ from $v$ to $w$ if, and only if, $v \prec_b w$. 
	Then this orientation is sink-rooted, acyclic, and satisfies:
	\begin{displaymath} 
	a_v \geq \out^{\OO_b}_v, \mbox{ for all $v \in V$.}
	\end{displaymath}
\end{enumerate}

We now return to the proof of Theorem~\ref{thm:cut_vertex}. 
Let $c \in \Rec{G}{v_0}$. 
Apply the burning algorithm to $c$, and let $\OO_b$ be the corresponding sink-rooted acyclic orientation as in part $(2)$ of the above. 
Since the cut vertex $v_n$ lies on all paths from the sink to vertices $v_k$ when $k \geq n+1$, 
this implies that the vertex $v_n$ must be burnt before any vertices with higher indices.
Therefore, in the orientation $\OO_b$, all edges from $v_n$ to vertices of $H_2$ are oriented away from $v_n$.

We now 
define $\OO_1 := \left. \OO_b \right\vert_{H_1}$ and $\OO_2 := \left. \OO_b \right\vert_{H_2}$. 
Due to the above, it follows that $v_n$ is the unique source of the orientation $\OO_2$. 
Moreover, by construction $\OO_1$ is sink-rooted, and both orientations are acyclic. 
Now let $k \in \{1, \ldots, n+m \}$. We have:
\begin{align}
\text{if } k \leq n-1, \text{ then }
& c^{(1)}_k = c_k \geq \out_k(\OO) = \out_k(\OO_1); \label{eq:1}\\
\text{if } k = n, \text{ then }
& c^{(1)}_n = c_n - d^{H_2}_n \geq \out_n(\OO) - d^{H_2}_n = \out_n(\OO) -  \out_n(\OO_2) = \out_n(\OO_1); \label{eq:2}\\
\text{if } k \geq n+1, \text{ then }
& c^{(2)}_k = c_k \geq \out_k(\OO) = \out_k(\OO_2) \label{eq:3}.
\end{align}
By Theorem~\ref{thm:acyclic_orientation}, Equations \eqref{eq:1} and \eqref{eq:2}
imply that $c^{(1)} \in \Rec{H_1}{v_0}$, while Equation~\eqref{eq:3} implies that $c^{(2)} \in \Rec{H_2}{v_n}$. 
This completes the proof of Theorem~\ref{thm:cut_vertex}.
\end{proof}

Theorem~\ref{thm:cut_vertex} implies the following decomposition for the level polynomial of a graph with a cut vertex.

\begin{cor}\label{cor:cut_vertex_level}
Let $G=(V, E)$ be a finite, connected graph, on the vertex set $$V = \{v_0, v_1, \ldots , v_{n+m} \}$$ where $m,n\geq 1$.
Assume that $v_n$ is a cut vertex of $G$. 
Let $H_1 := \subg{G}{\rest{V}{0,n}}$ and $H_2 := \subg{G}{\rest{V}{n,n+m}}$. 
Then we have:
\begin{displaymath} 
\Levelpoly{G}{v_0}{x} = \Levelpoly{H_1}{v_0}{x} \cdot \Levelpoly{H_2}{v_n}{x}.
\end{displaymath}
\end{cor}

\begin{proof}
Let $c$ be a configuration on $G$.
Let $c^{(1)}$ (respectively $c^{(2)}$) be the configurations on $H_1$ (respectively $H_2$) as defined in Theorem~\ref{thm:cut_vertex}. 
Then we have:
\begin{align*}
\level{c}{v_0}
&=d_0 - \vert E \vert + (c_1+\ldots+c_{n-1}) + c_n + (c_{n+1}+\ldots+c_{n+m}) \\
&= d_0 - (|E_1|+|E_2|) + \left(\sum\limits_{i=1}^{n-1} c^{(1)}_i\right) + (c^{(1)}_n + d^{H_2}_n) + \left(\sum\limits_{i=n+1}^{n+m} c^{(2)}_i\right) \\
&=\left( d_0-|E_1|+\sum\limits_{i=1}^{n} c^{(1)}_i  \right) + \left( d^{H_2}_n -|E_2|+\sum\limits_{i=n+1}^{n+m} c^{(2)}_i \right) \\
&= \level{c^{(1)}}{v_0} + \level{c^{(2)}}{v_n}, 
\end{align*}
and the claim immediately follows.
\end{proof}

We note that Corollary~\ref{cor:cut_vertex_level} is in fact a consequence of the Specification Theorem~\ref{thm:Tutte_level}, and the following result, due to Tutte \cite{Tutte}.

\begin{thm}\label{thm:Tutte_decomp_prod}
Let $G$ be a graph. Assume $G$ has a cut vertex which splits $G$ into two components $H_1$ and $H_2$. Then we have:
\begin{displaymath} 
T_G(x,y) = T_{H_1}(x,y) \cdot T_{H_2}(x,y). 
\end{displaymath}
\end{thm}

The proof of Theorem~\ref{thm:Tutte_decomp_prod} relies on the expression of the Tutte polynomial in terms of internal and external activities of spanning trees. However, our Theorem~\ref{thm:cut_vertex} gives a combinatorial explanation of this decomposition (at least at the specification $x=1$). It is also worth noting that a similar decomposition result was given for the so-called \emph{flow polynomial}, which is another specification of the Tutte polynomial, in \cite{SZ}.

\begin{example}\label{ex:cut_vertex}

\begin{figure}[ht]
\centering
\begin{tikzpicture}

\draw [thick] (0,1.5)--(-1,3)--(1,3)--(0,1.5);
\draw [thick] (0,1.5) to [out=150,in=270] (-1,3);
\draw [thick] (1,3)--(2.5,3)--(2.5,2)--(1,3);

\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
\node [below,yshift=-2pt] at (0,1.5) {$v_0$};
\draw [fill] (-1,3) circle [radius=0.1];
\node [above,yshift=2pt] at (-1,3) {\small{$v_1$}};
\draw [fill] (1,3) circle [radius=0.1];
\node [above,yshift=2pt] at (1,3) {\small{$v_2$}};
\draw [fill] (2.5,2) circle [radius=0.1];
\node [above,yshift=2pt] at (2.5,3) {\small{$v_3$}};
\draw [fill] (2.5,3) circle [radius=0.1];
\node [below,yshift=-2pt] at (2.5,2) {\small{$v_4$}};

\node [below,yshift=-10pt] at (1,1.5) {{\large $G$}};

\end{tikzpicture}
\caption{A graph $G$ with its cut vertex $v_2$.\label{fig:ex_cut}}
\end{figure}

Consider the graph $G$ of Figure~\ref{fig:ex_cut}. The vertex $v_2$ is a cut vertex. We may thus determine the recurrent configurations by combining recurrent configurations on the subgraphs $H_1$ and $H_2$, adding two grains at the cut vertex $v_2$, since it has two incident edges in $H_2$. We show this in the Table~\ref{tab:cut}, in which we also compute the level polynomials.

\begin{table}[ht]
\centering
\begin{tabular}{c|c|c|c}

Graph

&

\begin{tikzpicture}[scale=0.8]

\draw [thick] (0,1.5)--(-1,3)--(1,3)--(0,1.5);
\draw [thick] (0,1.5) to [out=150,in=270] (-1,3);

\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
\node [right,xshift=1pt,yshift=-1pt] at (0,1.5) {$v_0$};
\draw [fill] (-1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (-1,3) {\small{$v_1$}};
\draw [fill] (1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (1,3) {\small{$v_2$}};

\node [below,yshift=-10pt] at (0,1.5) {{\large $H_1$}};

\end{tikzpicture}

&

\begin{tikzpicture}[scale=0.8]

\draw [thick] (1,3)--(2.5,3)--(2.5,2)--(1,3);

\draw [fill] (0.9,2.9) rectangle (1.1,3.1);
\node [above,yshift=1pt] at (1,3) {\small{$v_2$}};
\draw [fill] (2.5,2) circle [radius=0.1];
\node [above,yshift=1pt] at (2.5,3) {\small{$v_3$}};
\draw [fill] (2.5,3) circle [radius=0.1];
\node [below,yshift=-1pt] at (2.5,2) {\small{$v_4$}};

\node [below,yshift=-5pt] at (1.75,1.5) {{\large $H_2$}};

\end{tikzpicture}

&

\begin{tikzpicture}[scale=0.8]

\draw [thick] (0,1.5)--(-1,3)--(1,3)--(0,1.5);
\draw [thick] (0,1.5) to [out=150,in=270] (-1,3);
\draw [thick] (1,3)--(2.5,3)--(2.5,2)--(1,3);

\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
\node [below,yshift=-1pt] at (0,1.5) {$v_0$};
\draw [fill] (-1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (-1,3) {\small{$v_1$}};
\draw [fill] (1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (1,3) {\small{$v_2$}};
\draw [fill] (2.5,2) circle [radius=0.1];
\node [above,yshift=1pt] at (2.5,3) {\small{$v_3$}};
\draw [fill] (2.5,3) circle [radius=0.1];
\node [below,yshift=-1pt] at (2.5,2) {\small{$v_4$}};

\node [below,yshift=-10pt] at (1,1.5) {{\large $G$}};

\end{tikzpicture}
\\
\hline
Recurrent       & $(0,1)$ & $(0,1),(1,0),(1,1)$ & $(0,3,0,1),(0,3,1,0),(0,3,1,1)$ \\
configurations  & $(1,0)$ & $(0,1),(1,0),(1,1)$ & $(1,2,0,1),(1,2,1,0),(1,2,1,1)$ \\
                & $(1,1)$ & $(0,1),(1,0),(1,1)$ & $(1,3,0,1),(1,3,1,0),(1,3,1,1)$ \\
                & $(2,0)$ & $(0,1),(1,0),(1,1)$ & $(2,2,0,1),(2,2,1,0),(2,2,1,1)$ \\
                & $(2,1)$ & $(0,1),(1,0),(1,1)$ & $(2,3,0,1),(2,3,1,0),(2,3,1,1)$ \\
\hline
Level           & $x^2+2x+2$ & $x+2$ & $x^3 + 4x^2 + 6x + 4$ \\
polynomial      & & & $=(x^2+2x+2) \cdot (x+2)$ 
\end{tabular}
\ \\[0.5em]
\caption{Applying Theorem~\ref{thm:cut_vertex} to determine the recurrent configurations of $G$.\label{tab:cut}}
\end{table}
\end{example}

%%
%% Section 3.2
%%
\subsection{Cut vertices in graphs with an underlying tree-like structure }
Theorem~\ref{thm:cut_vertex} showed us how to determine the recurrent configurations of the sandpile model on 
a graph $G$ when it has one cut vertex that splits it into two subgraphs $H_1$ and $H_2$.
The subgraph $H_1$ contained the sink of $G$, and the intersection of $H_1$ and $H_2$ is the cut vertex $v_n$.
If one considers the graphs $H_1$ and $H_2$ now as vertices, 
then Theorem~\ref{thm:cut_vertex} is the result (see Figure~\ref{abcde}) for a graph constructed on a single, rooted edge, where:
the root vertex corresponds to the subgraph $H_1$ containing the sink $v_0$ of $G$;
the non-root vertex corresponds to the other subgraph $H_2$;
the edge corresponds to the cut vertex $v_n$.
\begin{figure}[ht]
\centering
\tikzgraphedge
\caption{A graph with a cut vertex can be seen as a graph constructed on a single edge.\label{abcde}}
\end{figure}
In this subsection we generalize this from the case of a single rooted edge to the case of a rooted tree.
First we will need some notation to be able to discuss the associate tree-structure. 

Consider a tree $(T,\rho)$, rooted at some vertex $\rho$. 
For clarity, we will refer to vertices of the tree as \emph{nodes}, to distinguish them from vertices of the graph $G$.
Let $\nodes{T}$ denote the node set of $T$. 
%
Since $T$ is rooted, every non-root node $t\in \nodes{T} \setminus \{\rho\}$ will have an 
adjacent node on the (unique) path from $t$ to the root $\rho$ called the \emph{parent} of $t$ and denoted by $\parent{t}$.
All other nodes adjacent to $t$ are called \emph{descendants} of $t$, and this set is denoted $\des(t)$. 
If a node has no descendants then it is called a \emph{leaf}.

We now explain what we mean for a graph $G$ to have an underlying tree-structure $(T,\rho)$. 

\begin{defn}\label{cvtree}
We will say that the graph-sink pair $\gas{G}{v_\rho}$  
has an underlying {\emph{cv-tree structure $(T,\rho)$}} if the following holds.
The graph $G$ can be written as $$G = \bigcup\limits_{t\in \nodes{T}} H_t , $$ 
where the pair $(T,\rho)$ is a rooted tree and associated 
to every node $t \in \nodes{T}$ is a connected, loop-free, graph $H_{t}=(V_t,E_t)$.
Each graph $H_{t}$ has a distinguished vertex $v_t  \in V_t $ such that:
\begin{enumerate}
\item[(a)] for all $t \in \nodes{T} \setminus \{\rho\}$, we have $V_t\cap V_{\parent{t}} = \{v_t\}$;
\item[(b)] if $(t ,t')$ is not an edge of $T$, then $V_t \cap V_{t'} = \emptyset$.
\end{enumerate}
\end{defn}
See Figure~\ref{fig:tree_structure} for an illustration of the construction in Definition~\ref{cvtree}.

\begin{figure}[ht]
\centering
\tikztreestructure
\caption{A graph with its underlying tree structure.\label{fig:tree_structure}}
\end{figure}

\begin{rem}
Every graph can be decomposed into \emph{blocks}, where a block
is a maximal 2-connected subgraph. It is well-known that this block decomposition
has a tree structure as in that of Definition~\ref{cvtree}, and is thus a special case of a cv-tree structure
(the blocks of the cv-tree structure may be graphs which are not 2-connected but 
on which the recurrent configurations are well known, e.g. trees).
In particular, Theorems~\ref{thm:tree-like_structure} and \ref{thm:group_cvtree} allow one to reduce the
analysis of recurrent configurations to the 2-connected case.
\end{rem}

\begin{thm}\label{thm:tree-like_structure}
Let $G = \bigcup\limits_{t\in \nodes{T}} H_t $ have an underlying cv-tree structure $(T,\rho)$. 
Let $c \in \Config{G}{v_{\rho}}$.
For any node $t \in \nodes{T}$, we let $t_1,\ldots,t_k$ be the descendants of $t$ in $T$. 
Define the configurations $c^{(t)}$ on $\Config{H_t}{v_t}$ by: 
\begin{align*}
 c^{(t)}(v) &:= 
 	\begin{cases} 
 	c(v) & \text{ if } v \notin \{v_{t_1},\ldots,v_{t_k} \} \\ 
 	c(v) - d^{H_{t_i}}(v) & \text{ if } v=v_{t_i} 
 	\end{cases}
\end{align*}
Then $c \in \Rec{G}{v_{\rho}}$ if, and only if, 
$c^{(t)} \in \Rec{H_t}{v_t}$ for all $t \in \nodes{T}$.
\end{thm}

\begin{proof}
Our proof is by induction on the number of nodes in the cv-tree $\nodes{T}$.

If $|\nodes{T}|= 1$, then the tree $t$ is reduced to a single (root) vertex $\rho$, 
and the configuration $c^{(\rho)}$ is just the configuration $c$, since $\rho$ has no descendants. 
In this case the statement is a tautology.

Next, let us suppose that we have proven our result for $|\nodes{T}|=k$ for some $k \geq 1$. 
Let $(T, \rho)$ be a rooted tree with $k+1$ nodes, and assume that $G = \bigcup\limits_{t \in \nodes{T}} H_t $ has an underlying cv-tree structure $(T,\rho)$. 
Fix some leaf $\ell$ of $T$. Since $\ell$ has no descendants, the configuration $c^{(\ell)}$ is just the restriction of $c$ to $H_{\ell}$. 
Define $G':= \bigcup\limits_{t \in \nodes{T} \setminus \{\ell\} } H_t$, and let $c'$ be the configuration on $G'$ defined by 
\begin{displaymath}
c'(v) := 
\begin{cases} 
c(v) \text{ if } v \neq v_{\ell} \\ 
c(v_{\ell}) - d^{H_{\ell}}(v_{\ell}) \text{ if } v=v_{\ell}.
\end{cases}
\end{displaymath}
Now by construction, the vertex $v_{\ell}$ is a cut vertex of the graph $G$, splitting it into $H_{\ell}$ and $G'$. 
We may therefore apply Theorem~\ref{thm:cut_vertex}, to get that $c \in \Rec{G}{v_{\rho}}$ if, and only if, 
$c^{(\ell)} \in \Rec{H_{\ell}}{v_{\ell}}$ and $c' \in \Rec{G'}{v_{\rho}}$. 
But the graph $G'$ is constructed on a rooted tree with $|\nodes{T}| - 1 = k$ nodes, so that we may apply the induction hypothesis to $c'$, 
which combined with the above yields the desired result.
\end{proof}

Similarly to Corollary~\ref{cor:cut_vertex_level} in the cut vertex case, this yields a decomposition of the level polynomial for graphs with a tree-like structure.

\begin{cor}\label{cor:tree_structure_level}
Let $G = \bigcup\limits_{t \in \nodes{T}} H_t $ be constructed on a rooted tree $(T,\rho)$. Then we have
\begin{displaymath} 
\Levelpoly{G}{v_{\rho}}{x} = \prod\limits_{t \in \nodes{T}} \Levelpoly{H_t}{v_{t}}{x}.
\end{displaymath}
\end{cor}

\section{Recurrent states on graphs with isthmuses}

Having dealt with the cut vertex case, it is natural to ask ourselves what happens when the graph has an \emph{isthmus}, an edge whose removal disconnects the graph.

\begin{thm}\label{thm:isthmus}
Let $G=(V, E)$ be a finite, connected graph on the vertex set $$V = \{ v_0,v_1, \ldots , v_{n+m} \}$$ where $m,n\geq 1$.
Assume that the edge $e= (v_n, v_{n+1})$ is an isthmus. 
Let $H_1 := \subg{G}{\rest{V}{0,n}}$ and $H_2 := \subg{G}{\rest{V}{n+1,n+m}}$. 
Let $c =(c_1, \ldots c_{n+m}) \in \Config{G}{v_0}$.
Define $c^{(1)}:= (c_1, \ldots, c_{n-1}, c_n - 1 )$ and $c^{(2)}:= (c_{n+2},\ldots,c_{n+m})$.
Then $c \in \Rec{G}{v_0}$
if and only if
$c_{n+1} = d_{n+1} - 1,$ 
$c^{(1)} \in \Rec{H_1}{v_0}$, and
$c^{(2)} \in \Rec{H_2}{v_{n+1}}$.
\end{thm}

\begin{figure}[ht]
\centering
\tikzisthmus
\caption{A graph $G$ with an isthmus $(v_n,v_{n+1})$.\label{tikz:isthmus}}
\end{figure}

It is worth noting that Theorem~\ref{thm:isthmus} was proved by Lopez~\cite{Lop} in the 
special case where the isthmus is adjacent to the sink, as part of his proof of the Specification Theorem~\ref{thm:Tutte_level}. 

As in the cut vertex case, this theorem allows us to infer the following decomposition for the level polynomial.

\begin{cor}\label{cor:isthmus_level}
Let $G=(V, E)$ be a finite connected graph on the vertex set 
$$V = \{ v_0,v_1, \ldots, v_{n+m} \}$$ where $m,n\geq 1$.
Assume that the edge $e= (v_n, v_{n+1})$ is an isthmus of $G$. 
Let $H_1 := \subg{G}{\rest{V}{0,n}}$ and $H_2 := \subg{G}{\rest{V}{n+1,n+m}}$. 
Then we have:
\begin{displaymath} 
\Levelpoly{G}{v_0}{x} = \Levelpoly{H_1}{v_0}{x} \cdot \Levelpoly{H_2}{v_{n+1}}{x}.
\end{displaymath}
\end{cor}

This can also be inferred from Theorem~\ref{thm:Tutte_level}. 
Indeed, if $e$ is an isthmus, then $T_G(x,y) = x \cdot T_{G.e}(x,y)$, where $G.e$ is the graph $G$ with the edge $e$ contracted (reduced to a single vertex). 
In the case of the level polynomial, this yields $\Levelpoly{G}{v_0}{x} = \Levelpoly{G.e}{v_0}{x}$. 
Since contracting an isthmus creates a cut vertex at the contracted vertex, 
we can then apply Corollary~\ref{cor:cut_vertex_level} to get the desired result.

Rather than proving Theorem~\ref{thm:isthmus}, we prove a generalization to the case where the edge $(v_n,v_{n+1})$ is a multi-edge. That is, the graph $G$ is formed of two components $H_1,H_2$ connected by $k$ copies of the same edge, as illustrated in Figure~\ref{fig:multi-isthmus} below. We call such an edge a \emph{$k$-multi-isthmus}.

\begin{figure}[ht]
\centering
\tikzmultiisthmus
\caption{A graph $G$ with a $3$-multi-isthmus.\label{fig:multi-isthmus}}
\end{figure}

\begin{thm}\label{thm:multi-isthmus}
Let $G=(V, E)$ be a finite, connected graph on the vertex set 
$$V = \{ v_0,v_1, \ldots , v_{n+m} \}$$ where $m,n\geq 1$.
Assume that the edge $e= (v_n, v_{n+1})$ is a $k$-multi-isthmus for some $k \geq 1$. 
Let $H_1 := \subg{G}{\rest{V}{0,n}}$ and $H_2 := \subg{G}{\rest{V}{n+1,n+m}}$. 
Let $c =(c_1, \ldots c_{n+m}) \in \Config{G}{v_0}$.
Define $c^{(1)}:= (c_1, \ldots, c_{n-1}, c_n - k )$ and $c^{(2)}:= (c_{n+2},\ldots,c_{n+m})$.
Then we have
$c \in \Rec{G}{v_0}$
if and only if
$c^{(1)}\in \Rec{H_1}{v_0}$,
$c^{(2)}\in \Rec{H_2}{v_{n+1}}$, and
$$d^{H_2}_{n+1} = d_{n+1} - k \leq c_{n+1} \leq d_{n+1} - 1 .$$
\end{thm}

\begin{cor}\label{cor:multi-isthmus_level}
Let $G=(V, E)$ be a finite, connected graph on the vertex set $$V = \{ v_0,v_1, \ldots , v_{n+m} \}$$ where $m,n \geq 1$.
Assume that the edge $e= (v_n, v_{n+1})$ is a $k$-multi-isthmus for some $k \geq 1$. 
Let $H_1 := \subg{G}{\rest{V}{0,n}}$ and $H_2 := \subg{G}{\rest{V}{n+1,n+m}}$. 
Then we have
\begin{displaymath} 
\Levelpoly{G}{v_0}{x} = (1 + x + \ldots + x^{k-1} ) \cdot \Levelpoly{H_1}{v_0}{x} \cdot \Levelpoly{H_2}{v_{n+1}}{x}.
\end{displaymath}
\end{cor}

Since Theorem~\ref{thm:isthmus} and Corollary~\ref{cor:isthmus_level} correspond to Theorem~\ref{thm:multi-isthmus} and Corollary~\ref{cor:multi-isthmus_level} in the special case $k=1$, it is sufficient to prove the latter two results.

\begin{proof}
Define $I:=\subg{G}{\rest{V}{n,n+1}}$ to be the subgraph of $G$ consisting of the multi-isthmus $(v_n, v_{n+1})$. Since $v_n$ and $v_{n+1}$ are both cut-vertices, the graph $G$ has a cv-tree structure where the blocks are $H_1,I,H_2$ and the underlying tree is a path graph.
The set $\Rec{I}{v_n}$ of recurrent states of the block $I$ is straightforward to compute: 
\begin{equation}\label{eq:multi-isthmus_rec}
c=\left(c_{n+1} \right) \in \Rec{I}{v_n} \mbox{ if, and only if, } c_{n+1} \in \{0,\ldots,k-1\},
\end{equation} 
and Theorem~\ref{thm:multi-isthmus} immediately follows from this and Theorem~\ref{thm:tree-like_structure}.

Moreover, from Equation~\eqref{eq:multi-isthmus_rec}, we get that $\Levelpoly{I}{v_n}{x} = 1 + x + \cdots + x^{k-1}$, and applying Corollary~\ref{cor:tree_structure_level} gives us Corollary~\ref{cor:multi-isthmus_level}, as desired.
\end{proof}

\begin{example}\label{ex:multi-isthmus}

\begin{figure}[ht]
\centering

\begin{tikzpicture}

\draw [thick] (0,1.5)--(-1,3)--(1,3)--(0,1.5);
\draw [thick] (1,3) to [out=15,in=165] (2,3);
\draw [thick] (1,3) to [out=345,in=195] (2,3);
\draw [thick] (2,3)--(3.5,3)--(3.5,2)--(2,3);

\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
\node [below,yshift=-1pt] at (0,1.5) {$v_0$};
\draw [fill] (-1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (-1,3) {\small{$v_1$}};
\draw [fill] (1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (1,3) {\small{$v_2$}};
\draw [fill] (2,3) circle [radius=0.1];
\node [above,yshift=1pt] at (2,3) {\small{$v_3$}};
\draw [fill] (3.5,2) circle [radius=0.1];
\node [above,yshift=1pt] at (3.5,3) {\small{$v_4$}};
\draw [fill] (3.5,3) circle [radius=0.1];
\node [below,yshift=-1pt] at (3.5,2) {\small{$v_5$}};

\node [below,yshift=-10pt] at (1.25,1.5) {\large $G$};

\end{tikzpicture}

\caption{A graph $G$ containing a $2$-multi-isthmus $(v_2,v_3)$. \label{fig:ex_isth}}
\end{figure}

Consider the graph $G$ of Figure~\ref{fig:ex_isth}. This graph can be decomposed into two components $H_1$ and $H_2$, connected by the $2$-multi-isthmus $(v_2,v_3)$. By Theorem~\ref{thm:multi-isthmus}, the recurrent configurations are given by the products of recurrent configurations on $H_1$ and $H_2$ as in the cut vertex case, which we complete by putting either two or three grains of sand at the vertex $v_3$. We show this in Table~\ref{tab:isth}, and also compute the corresponding level polynomials.

\begin{table}[ht]
\centering
\begin{tabular}{c|c|c|c}
Graph
&
\begin{tikzpicture}[scale=0.8]
\draw [thick] (0,1.5)--(-1,3)--(1,3)--(0,1.5);
\draw [thick] (1,3) to [out=15,in=165] (2,3);
\draw [thick] (1,3) to [out=345,in=195] (2,3);
\draw [thick] (2,3)--(3.5,3)--(3.5,2)--(2,3);
\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
\node [below,yshift=-1pt] at (0,1.5) {$v_0$};
\draw [fill] (-1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (-1,3) {\small{$v_1$}};
\draw [fill] (1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (1,3) {\small{$v_2$}};
\draw [fill] (2,3) circle [radius=0.1];
\node [above,yshift=1pt] at (2,3) {\small{$v_3$}};
\draw [fill] (3.5,2) circle [radius=0.1];
\node [above,yshift=1pt] at (3.5,3) {\small{$v_4$}};
\draw [fill] (3.5,3) circle [radius=0.1];
\node [below,yshift=-1pt] at (3.5,2) {\small{$v_5$}};
\node [below,yshift=-10pt] at (1.25,1.5) {\large $G$};
\end{tikzpicture}
&
\begin{tikzpicture}[scale=0.8]
\draw [thick] (0,1.5)--(-1,3)--(1,3)--(0,1.5);
\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
\node [right,xshift=1pt,yshift=-1pt] at (0,1.5) {$v_0$};
\draw [fill] (-1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (-1,3) {\small{$v_1$}};
\draw [fill] (1,3) circle [radius=0.1];
\node [above,yshift=1pt] at (1,3) {\small{$v_2$}};
\node [below,yshift=-10pt] at (0,1.5) {\large $H_1$};
\end{tikzpicture}
&
\begin{tikzpicture}[scale=0.8]
\draw [thick] (2,3)--(3.5,3)--(3.5,2)--(2,3);
\draw [fill] (2,3) circle [radius=0.1];
\node [above,yshift=1pt] at (2,3) {\small{$v_3$}};
\draw [fill] (3.5,2) circle [radius=0.1];
\node [above,yshift=1pt] at (3.5,3) {\small{$v_4$}};
\draw [fill] (3.5,3) circle [radius=0.1];
\node [below,yshift=-1pt] at (3.5,2) {\small{$v_5$}};
\node [below,yshift=-10pt] at (2.75,1.5) {\large $H_2$};
\end{tikzpicture}
\\
\hline
Recurrent       & $(0,3,2,0,1),(0,3,3,0,1)$ & $(0,1)$ & $(0,1)$ \\
configurations  & $(1,2,2,0,1),(1,2,3,0,1)$ & $(1,0)$ & $(0,1)$ \\
                & $(1,3,2,0,1),(1,3,3,0,1)$ & $(1,1)$ & $(0,1)$ \\
                & $(0,3,2,1,0),(0,3,3,1,0)$ & $(0,1)$ & $(1,0)$ \\
                & $(1,2,2,1,0),(1,2,3,1,0)$ & $(1,0)$ & $(1,0)$ \\
                & $(1,3,2,1,0),(1,3,3,1,0)$ & $(1,1)$ & $(1,0)$ \\
                & $(0,3,2,1,1),(0,3,3,1,1)$ & $(0,1)$ & $(1,1)$ \\
                & $(1,2,2,1,1),(1,2,3,1,1)$ & $(1,0)$ & $(1,1)$ \\
                & $(1,3,2,1,1),(1,3,3,1,1)$ & $(1,1)$ & $(1,1)$ \\

\hline
Level           & $x^3 + 5x^2 + 8x + 4$ & $x+2$ & $x+2$ \\
polynomial      & $=(1+x) \cdot (x+2) \cdot (x+2)$ & & 
\end{tabular}
\ \\[0.5em]
\caption{Applying Theorem~\ref{thm:multi-isthmus} to determine the recurrent configurations of $G$.\label{tab:isth}}
\end{table}

\end{example}

%%%%%%%%%%%%%%%%%%%
%%%% SECTION 5 %%%%
%%%%%%%%%%%%%%%%%%%

\section{Decomposition of the sandpile group}\label{sec:sandpile_group}

In this section we look at how the decomposition results from Section~\ref{sec:cut_vertex} affect the so-called sandpile group.

Let $(G,v_0)$ be a graph, with vertex set $V=\{v_0,\ldots,v_n\}$ and edge set $E$. Recall that $\sigma: \Config{G}{v_0} \rightarrow \Stab{G}{v_0}$ denotes the stabilization operator. We define a binary operation $\oplus$ on $\Stab{G}{v_0}$ by:
\beq\label{def:plus}
\text{for all } c,c' \in \Stab{G}{v_0}, \, c \oplus c' := \sigma\left(c+c'\right),
\eq 
where $+$ denotes pointwise addition in $\Stab{G}{v_0}$. Dhar showed in \cite{Dhar2} that $\left( \Rec{G}{v_0},\oplus \right)$ is an Abelian group, called the \emph{sandpile group}. We denote it $S(G,v_0)$.

For the proofs of this section, we will need the following characterization of recurrent states, due to Dhar \cite{Dhar2}. We first define a configuration $b \in \Config{G}{v_0}$ by $b := \sum\limits_{i: \{v_i,v_0\} \in E} \alpha_i$, where the sum is over all vertices adjacent to the sink, counted with multiplicity. Thus the configuration $b$ corresponds to the toppling of the sink in an initially empty configuration.

\begin{pro}\label{pro:Dhar_rec}
A configuration $c \in \Config{G}{v_0}$ is recurrent if, and only if, $\sigma(c+b) = c$. 
Moreover, in the stabilization of $c+b$ every vertex in $\rest{V}{1,n}$ topples exactly once.
\end{pro}

\begin{thm}\label{thm:group_cut_vertex}
Let $G=(V, E)$ be a finite, connected graph, on the vertex set $$V = \{ v_0,v_1, \ldots , v_{n+m} \}$$ where $m,n\geq 1$.
Assume that $v_n$ is a cut vertex of $G$. 
Let $H_1 := \subg{G}{\rest{V}{0,n}}$ and $H_2 := \subg{G}{\rest{V}{n,n+m}}$. We have:
\begin{displaymath}
S(G,v_0)  ~\cong ~S(H_1,v_0) \times S(H_2,v_n),
\end{displaymath}
where the symbol $\cong$ denotes group isomorphism, and $\times$ is the direct product of two groups.
\end{thm}


We require two lemmas in order to prove this theorem.
Given $c =(c_1, \ldots, c_{n+m}) \in \Config{G}{v_0}$,
let $c^{(1)} := (c_1, \ldots, c_{n-1}, c_n - d^{H_2}_n)$ and $c^{(2)} := (c_{n+1}, \ldots, c_{n+m})$,
where $d^{H_2}_n$ is the degree of the vertex $v_n$ in the graph $H_2$.

\begin{lem}\label{lem:group_leaves}
For any configurations $c,c' \in \Rec{G}{v_0}$, we have
\beq\label{eq:group_leaves}
(c \oplus c')^{(2)} = c^{(2)} \oplus c'^{(2)}.
\eq 
\end{lem}

\begin{proof}
Let $c,c' \in \Rec{G}{v_0}$. Then $c \oplus c'$ is the stabilization of the configuration $c+c'$. 
Let us examine how this stabilization might occur. 
We may choose to first stabilize the configuration in $H_2$ except perhaps at $v_n$, by making only topplings at vertices in $\rest{V}{v_{n+1},\ldots,v_{n+m}}$. 
We will reach a configuration $\gamma$ where all these vertices are stable. 
The configuration $\gamma$, restricted to $\rest{V}{v_{n+1},\ldots,v_{n+m}}$, 
is exactly the same configuration we would reach in the graph $(H_2,v_n)$ by stabilizing the configuration $c^{(2)} + c'^{(2)}$, 
that is, the configuration $c^{(2)} \oplus c'^{(2)}$. 

Now of all the subsequent topplings to stabilize $c+c'$, only the topplings of the cut vertex $v_n$ will effect the configuration on $\rest{V}{v_{n+1},\ldots,v_{n+m}}$.
But the effect of toppling $v_n$ on these vertices is exactly the effect of toppling the sink on the graph $(H_2,v_n)$. 
Since the configuration reached on $(H_2,v_n)$ before any such toppling is $c^{(2)} \oplus c'^{(2)}$, which is recurrent, 
toppling the sink and then stabilizing leaves this configuration unchanged by Proposition~\ref{pro:Dhar_rec}. 
This completes the proof of Lemma~\ref{lem:group_leaves}.
\end{proof}

\begin{lem}\label{lem:group_root}
For any configurations $c,c' \in \Rec{G}{v_0}$, we have
\beq\label{eq:group_root}
(c \oplus c')^{(1)} = c^{(1)} \oplus c'^{(1)} \oplus \kappa,
\eq 
where $\kappa = \kappa\left(c^{(2)},c'^{(2)} \right) 
	:= \left( d^{H_2}_n + \vert c^{(2)} \vert + \vert c'^{(2)} \vert - \vert c^{(2)} \oplus c'^{(2)} \vert \right) \alpha_n $, 
with $\vert c \vert$ designating the total number of grains of a configuration $c$, 
and $\alpha_n$ is the configuration with one grain at the vertex $v_n$ and none elsewhere.
\end{lem}

\begin{proof}
A crucial remark that stems from the proof of Lemma~\ref{lem:group_leaves} is the following. 
When stabilizing the configuration $c+c'$, if the configuration is initially stabilized in $H_2$, then the topplings of the cut vertex $v_n$ have no effect in $H_2$.

Now once we have initially stabilized $c+c'$ in $H_2$, we may stabilize it in $H_1$. 
The configuration to stabilize is thus the configuration $c+c'$ restricted to $H_1$, to which a certain number $\lambda$ of grains have been added at $v_n$. 
These grains are added as a result of the original stabilization in $H_2$, they are the \emph{surplus} of grains toppled into $v_n$ through stabilizing $(c + c')^{(2)}$.
Thus $\lambda = \vert c^{(2)} \vert + \vert c'^{(2)} \vert - \vert (c \oplus c')^{(2)} \vert$, and we have
\begin{displaymath}
\left.(c \oplus c')\right\vert_{H_1} = \left. c\right\vert_{H_1} \oplus \left. c'\right\vert_{H_1} \oplus \lambda \alpha_n.
\end{displaymath}

Equation~\eqref{eq:group_root} with $\kappa=\left( \lambda + d^{H_2}_n \right) \alpha_n$ follows from the above, 
with the definition $c^{(1)}_n = c_n + d^{H_2}_n$ resulting in the adjustment by an additive constant.
\end{proof}



\begin{proof}[Proof of Theorem~\ref{thm:group_cut_vertex}]
Lemmas~\ref{lem:group_leaves} and \ref{lem:group_root} allow us to understand the operator $\oplus$ on\break $\Rec{G}{v_0}$, and in particular its behaviour when restricted to the components $H_1,H_2$.

The result then follows from a group theory argument that we will now explain. 
Lemmas~\ref{lem:group_leaves} and \ref{lem:group_root}, combined with the Decomposition Theorem~\ref{thm:cut_vertex}, mean that we have the following situation. 
We have a set $\mathcal{G}=\mathcal{H}_1 \times \mathcal{H}_2$, where $\mathcal{G}$,${H}_1$ and $\mathcal{H}_2$ are all equipped with an Abelian group structure.
However, the binary addition operation in $\mathcal{G}$ does not decompose to product addition in $\mathcal{H}_1$ and $\mathcal{H}_2$. 
Rather, for $(c_1,c_2),(c'_1,c'_2) \in \mathcal{G}$, we have
\begin{displaymath}
(c_1,c_2)+(c'_1,c'_2) = (c_1+c'_1+\kappa(c_2,c'_2),c_2+c'_2),
\end{displaymath}
where the function $\kappa$ is described by Lemma~\ref{lem:group_root}.

Now from \cite[Chapter~IV]{Brown} we get that such a group $\mathcal{G}$ is isomorphic to the direct product $\mathcal{H}_1 \times \mathcal{H}_2$ if there exists a function $a: \mathcal{H}_2 \rightarrow \mathcal{H}_1$ such that for any $c_2,c'_2 \in \mathcal{H}_2$, we have $\kappa(c_2,c'_2) = a(c_2) + a(c'_2) - a(c_2+c'_2)$. In our case, simply setting $a(c_2) = \left(\vert c_2 \vert + d^{H_2}_n\right) \alpha_n$ immediately yields the desired result.
\end{proof}

\begin{rem}
In fact, we make a slight abuse when using the group theory arguments in this case, since the configurations $\kappa,a(c_2)$ are not in general recurrent configurations on $H_1$. However, this difficulty can be overcome by considering the unique recurrent configurations to which they are toppling equivalent (see \cite[Theorem~1]{CorRos}) instead.
\end{rem}

\begin{example}\label{ex:group_cut}

Consider the graph $G$ of Figure~\ref{fig:ex_cut_group}, where the vertex $v_2$ is a cut vertex splitting the graph into two isomorphic components $H_1,H_2$. In Example~\ref{ex:intro}, we showed that the components $H_i$ have three recurrent configurations, which implies that $S\left(H_1,v_0 \right) \cong S\left(H_2,v_2 \right) \cong \mathbb{Z}/3\mathbb{Z}$. It immediately follows from Theorem~\ref{thm:group_cut_vertex} that
\begin{displaymath}
S\left(G,v_0\right) \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/3\mathbb{Z}.
\end{displaymath}
Note that this is not a straightforward consequence of simply enumerating the recurrent configurations of $G$, since an Abelian group with nine elements could also be (isomorphic to) $\mathbb{Z}/9\mathbb{Z}$.

\begin{figure}[ht]
\centering
\begin{tikzpicture}

\draw [thick] (0,1.5)--(-1,3)--(1,3)--(0,1.5);
\draw [thick] (1,3)--(2.5,3)--(2.5,2)--(1,3);

\draw [fill] (-0.1,1.4) rectangle (0.1,1.6);
\node [below,yshift=-2pt] at (0,1.5) {$v_0$};
\draw [fill] (-1,3) circle [radius=0.1];
\node [above,yshift=2pt] at (-1,3) {\small{$v_1$}};
\draw [fill] (1,3) circle [radius=0.1];
\node [above,yshift=2pt] at (1,3) {\small{$v_2$}};
\draw [fill] (2.5,2) circle [radius=0.1];
\node [above,yshift=2pt] at (2.5,3) {\small{$v_3$}};
\draw [fill] (2.5,3) circle [radius=0.1];
\node [below,yshift=-2pt] at (2.5,2) {\small{$v_4$}};

\node [below,yshift=-10pt] at (1,1.5) {{\large $G$}};

\end{tikzpicture}
\caption{A graph $G$ with its cut vertex $v_2$.\label{fig:ex_cut_group}}
\end{figure}

\end{example}

As with the transition from Theorem~\ref{thm:cut_vertex} to Theorem~\ref{thm:tree-like_structure}, an induction argument allows us to extend Theorem~\ref{thm:group_cut_vertex} to the case of graphs with an underlying cv-tree structure.

\begin{thm}\label{thm:group_cvtree}
Let $G = \bigcup\limits_{t\in \nodes{T}} H_t $ have an underlying cv-tree structure $(T,\rho)$. We have:
\begin{displaymath}
S\left(G,v_{\rho}\right) ~\cong~ \prod_{t\in \nodes{T}} S\left(H_t,v_t\right),
\end{displaymath}
where $\cong$ denotes group isomorphism, and $\prod$ the direct product of the groups involved.
\end{thm}

\begin{rem}
It is not clear that the result of Theorem~\ref{thm:isthmus} can be cast in a useful manner in terms of the sandpile group.
The enumeration result in Corollary~\ref{cor:isthmus_level} suggests a decomposition of the form $S(G^{(k)}) = S(G) \times \mathbb{Z}_k^{n-1}$, 
but there are some simple examples for which this both holds and does not hold.
\end{rem}
%%%%%%%%%%%%%%%%%%%
%%%% SECTION 6 %%%%
%%%%%%%%%%%%%%%%%%%

\section{Examples}\label{sec:big_ex}

In this part, we exhibit two examples which showcase the results of this paper.
They illustrate the computational gains that are made with respect to determining the 
recurrent configurations on a graph that can be decomposed in the terms we have described.


\begin{example}\label{bigexample}
Let $G$ be the graph in Figure~\ref{whopper}. 
Let us consider the sandpile model on $G$ wherein vertex $v_0$ is the sink.
Apply Theorem~\ref{thm:tree-like_structure} to this graph.
The cv-tree $(T,0)$ structure of $G$ is illustrated in Figure~\ref{whoppercv}.
The constituent graphs of the cv-tree are
\begin{align*}
H_{i} = 
\begin{cases}
\rest{G}{\{v_i,v_{4i+1},v_{4i+2},v_{4i+3},v_{4i+4}\}} & \mbox{ if } 0 \leq i \leq 4 \\
\rest{G}{\{v_i,v_{3i+6},v_{3i+7},v_{3i+8}\}} & \mbox{ if } 5 \leq i \leq 20,
\end{cases}
\end{align*}
and $\nodes{T} = \{0,1,\ldots,20\}$.
Note that $H_i$ is isomorphic to $K_5$ (respectively $K_4$) for all $i\leq 4$ (respectively $5\leq i \leq 20$).
The recurrent states of the sandpile model on these graphs are therefore characterized by Theorem~\ref{crecs}.

Theorem~\ref{thm:tree-like_structure} tells us that
$c=(c_1,\ldots,c_{68}) \in \Rec{G}{v_0}$ if, and only if, $c^{(t)} \in \Rec{H_{t}}{v_{t}}$ for all $0 \leq t \leq 20$.
This latter condition is equivalent to:
\begin{align*}
\begin{cases}
(c^{(i)}_{4i+1},c^{(i)}_{4i+2},c^{(i)}_{4i+3},c^{(i)}_{4i+4}) \in 
\Rec{K_5}{v_0}
& \mbox{ for all } 0 \leq i \leq 4\\
(c^{(i)}_{3i+6},c^{(i)}_{3i+7},c^{(i)}_{3i+8}) \in 
\Rec{K_4}{v_0} & \mbox{ for all } 5 \leq i \leq 20.
\end{cases}
\end{align*}
The set 
$\Rec{K_4}{v_0}$ 
is explicitly listed in Equation~\eqref{k4recs}, 
and the set 
$\Rec{K_5}{v_0}$ is described in Example~\ref{k5example}.

Now since $d^{H_{i}}(v_i)=4$ for $1\leq i \leq 4$,
and $d^{H_i}(v_i)=3$ for all $5 \leq i \leq 20$, we may conclude with our classification of recurrent states of the sandpile model on $G$:
$c \in \Rec{G}{v_0}$ if and only if
\begin{enumerate}[(i)]
\item $(c_1-4,c_2-4,c_3-4,c_4-4) \in \Rec{K_5}{v_0}$,
\item $(c_{4i+1}-3,c_{4i+2}-3,c_{4i+3}-3,c_{4i+4}-3) \in 
\Rec{K_5}{v_0}$ for all $1 \leq i \leq 4$, and
\item $(c_{3i+6},c_{3i+7},c_{3i+8}) \in 
\Rec{K_4}{v_0}$ for all $5 \leq i \leq 20$.
\end{enumerate}


We may also compute the level polynomial for the graph $G$ of Figure~\ref{whopper}. By Corollary~\ref{cor:tree_structure_level}, we have:
\begin{displaymath}
\Levelpoly{G}{v_0}{x} = \Levelpoly{K_5}{v_0}{x}^5 \Levelpoly{K_4}{v_0}{x}^{16}.
\end{displaymath}

The level polynomials of the complete graphs can be computed for instance by computing their Tutte polynomials and applying Theorem~\ref{thm:Tutte_level}. We get
\begin{align*}
\Levelpoly{K_4}{v_0}{x} & = x^3+3x^2+6x+6 \\
\Levelpoly{K_5}{v_0}{x} & = x^6+4x^5+10x^4+20x^3+30x^2+36x+24,
\end{align*}
and thus
\begin{align*}
\Levelpoly{G}{v_0}{x} & = (x^6+4x^5+10x^4+20x^3+30x^2+36x+24)^{5} (x^3+3x^2+6x+6)^{16} \\
 & = x^{78} + 68x^{77} + 2346 x^{76} + \ldots + 22463437455746924544.
\end{align*}
In other words, there is one recurrent configuration with level $78$, $68$ recurrent configurations with level $77$, and so on.

\end{example}

\begin{figure}[ht]
\centering
\marktikzone
\caption{The graph used in Example~\ref{bigexample}.\label{whopper}}
\end{figure}

\begin{figure}[ht]
\centering
\marktikztwo
\caption{The cv-tree $(T,0)$ of the graph $G$ in Figure~\ref{whopper} and Example~\ref{bigexample}.\label{whoppercv}}
\end{figure}




\begin{example}\label{smallerexample}
Let $G$ be the graph in Figure~\ref{fig:smaller_ex}. Let us consider the sandpile model on $G$ wherein vertex $v_0$ is the sink. We apply Theorems~\ref{thm:tree-like_structure} and \ref{thm:isthmus} to this graph. The cv-tree $(T,0)$ structure of $G$ and its constituent graphs are illustrated in Figure~\ref{fig:smaller_ex_dec}, where $H_0$ and $H_1$ are connected by an isthmus.
Note that $H_0$ and $H_2$ are isomorphic to $K_5$, $H_3$ is isomorphic to $K_4^{(2)}$, that is $K_4$ with all edges doubled, and that $H_1$ is a graph whose recurrent configurations have already been determined in Example~\ref{ex:cut_vertex}.

Theorems~\ref{thm:tree-like_structure} and \ref{thm:isthmus} tell us that $c=(c_1,\ldots,c_{14}) \in \Rec{G}{v_0}$ if, and only if, $c^{(t)} \in \Rec{H_{t}}{v_{t}}$ for all $0 \leq t \leq 3$, and $c_5=3$, since $v_5$ is the vertex of the isthmus $(v_3,v_5)$ ``furthest'' from the sink, and has degree four.
This latter condition is equivalent to:
\begin{align}
\bullet\;\; &(c^{(0)}_{1},c^{(0)}_{2},c^{(0)}_{3},c^{(0)}_{4}),(c^{(2)}_{8},c^{(2)}_{9},c^{(2)}_{10},c^{(2)}_{11}) \in 
\Rec{K_5}{v_0} \label{eq:small_ex1} \\
\bullet \;\; & c_5=3 \label{eq:small_ex4} \\
\bullet \;\; &(c^{(1)}_{6},c^{(1)}_{7}) \in \Rec{H_1}{v_5} \label{eq:small_ex2} \\
\bullet \;\; &(c^{(3)}_{12},c^{(3)}_{14},c^{(3)}_{15}) \in 
\Rec{K_4^{(2)}}{v_0}. \label{eq:small_ex3}
\end{align}


The set 
$\Rec{K_5}{v_0}$ is described in Example~\ref{k5example}. 
Since $d^{H_{1}}(v_3) = 1$ and $d^{H_{3}}(v_4)=6$, Equation~\eqref{eq:small_ex1} is equivalent to:
\begin{align*}
(c_{1},c_{2},c_{3}-1,c_{4}-6),(c_{8},c_{9},c_{10},c_{11}) \in 
\Rec{K_5}{v_0}.
\end{align*}

We have already computed the recurrent configurations of the component $H_1$ in 
Example~\ref{ex:cut_vertex}, so $\Rec{H_1}{v_5} = \big\lbrace (0,1),(1,0),(1,1),(2,0),(2,1) \big\rbrace$. 
Since $d^{H_{2}}(v_7) = 4$, Equation~\eqref{eq:small_ex2} is equivalent to:
\begin{align*}
(c_{6},c_{7}-4) \in \Rec{H_1}{v_5}.
\end{align*}

Finally, the set 
$\Rec{K_4}{v_0}$ is explicitly listed in Equation~\ref{k4recs}. 
The recurrent states of $K_4^{(2)}$ are linked to those of $K_4$ by Theorem~\ref{thm:Gk}, so that Equation~\eqref{eq:small_ex3} is equivalent to:
\begin{align*}
\left( \floor*{c_{12}/2},\floor*{c_{13}/2}, \floor*{c_{14}/2} \right) \in 
\Rec{K_4}{v_0}.
\end{align*}

Combining all this, we may conclude with our classification of recurrent states of the sandpile model on $G$:
$c \in \Rec{G}{v_0}$ if and only if
\begin{itemize}
\item $(c_{1},c_{2},c_{3}-1,c_{4}-6),(c_{8},c_{9},c_{10},c_{11}) \in 
\Rec{K_5}{v_0}$,
\item $c_5=3$,
\item $(c_{6},c_{7}-4) \in \Rec{H_1}{v_5}$, and
\item $\left( \floor*{c_{12}/2},\floor*{c_{13}/2}, \floor*{c_{14}/2} \right) \in 
\Rec{K_4}{v_0}$.
\end{itemize}

\begin{figure}[ht]
	\centering
	\thomastikzone
	\caption{A graph $G$ that can be decomposed as previously described.\label{fig:smaller_ex}}
\end{figure}

\begin{figure}[ht]
	\centering
	\thomastikztwo
	\caption{Decomposition of the graph $G$ from Figure~\ref{fig:smaller_ex}. \label{fig:smaller_ex_dec}}
\end{figure}

\end{example}


\begin{thebibliography}{99}
\bibitem{AADBH} J.-C. Aval, M. D'Adderio, M. Dukes, A. Hicks, and Y. {Le Borgne}. Statistics on parallelogram polyominoes and a $q,t$-analogue of the Narayana numbers. {\it J. Comb. Theory Ser.~A} 123(1):271--286, 2014.
\bibitem{AADB} J.-C. Aval, M. D'Adderio, M. Dukes, and Y. {Le Borgne}. Two operators on sandpile configurations, the sandpile model on the complete bipartite graph, and a cyclic lemma. {\it Adv. Appl. Math.} 73:59--98, 2016.
\bibitem{Baker} M. Baker and S. Norine. Riemann--Roch and Abel--Jacobi theory on a finite graph. {\it{Adv. Math.}} 215(2):766--788, 2007.
\bibitem{berget} A. Berget, A. Manion, M. Maxwell, A. Potechin, and V. Reiner. The critical group of a line graph. {\it{Ann. Combin.}} 16:449--488, 2012.
\bibitem{Ber} O. {Bernardi}. Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings. {\it{Electron. J. Comb.}} 15(1):\#R109, 53~pp., 2008.
\bibitem{Biggs} N. Biggs. The Tutte Polynomial as a Growth Function. {\it{J. Algebraic Combin.}} 10(2):115--133, 1999.
\bibitem{Brown} K. Brown. Cohomology of groups, volume~87 of {\it Graduate Texts in  Mathematics}. Springer-Verlag, New York-Berlin, 1982.
\bibitem{CorLB} R. Cori and Y. {Le Borgne}. The sand-pile model and Tutte polynomials. {\it{Adv. Appl. Math.}} 30(1-2):44--52, 2003.
\bibitem{CoriPou} R. Cori and D. Poulalhon. Enumeration of $(p,q)$-parking functions. {\it Discrete Math.} 256(3):609--623, 2002. LaCIM 2000 Conference on Combinatorics, Computer Science and Applications.
\bibitem{CorRos} R. Cori and D. Rossin. On the sandpile group of a graph. {\it Eur. J. Combin.} 21:447--459, 2000.
\bibitem{Dhar2} D. Dhar. Self-organized critical state of sandpile automaton models. {\it Phys. Rev. Lett.} 64:1613--1616, 1990.
\bibitem{Dhar} D. Dhar. Theoretical studies of self-organized criticality. {\it{Phys.~A}} 369(1):29--70, 2006.
\bibitem{DLB} M. Dukes and Y. {Le Borgne}. Parallelogram polyominoes, the sandpile model on a complete bipartite graph, and a $q,t$-Narayana polynomial. {\it J. Comb. Theory Ser.~A} 120(4):816--842, 2013.
\bibitem{GZ} C. Greene and T. Zaslavsky. On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. {\it{Trans. Amer. Math. Soc.}} 280(1):97--126, 1983.
\bibitem{jacobson} B. Jacobson, A. Niedermaier, and V. Reiner. Critical groups for complete multipartite graphs and Cartesian products of complete graphs. {\it{J. Graph Theory}} 44:231--250, 2003.
\bibitem{levine} L. Levine. Sandpile groups and spanning trees of directed line graphs.  {\it{J. Combin. Theory Ser.~A}} 118(2):350--364, 2011.
\bibitem{lorenzini} D. Lorenzini. A finite group attached to the laplacian of a graph. {\it{Discrete Math.}} 91:277--282, 1991.
\bibitem{Lop} C. Merino. Chip firing and the Tutte polynomial. {\it{Ann. Comb.}} 1(1):253--259, 1997.
\bibitem{Red} F. Redig. Mathematical aspects of the Abelian sandpile model. {\it{Lecture Notes of Les Houches Summer School 2005}}, Mathematical Statistical Physics, Session LXXXIII.  Elsevier, 2006.
\bibitem{SZ} K. Sekine and C.Q. Zhang. Decomposition of the Flow Polynomial. {\it{Graphs Combin.}} 13(2):189--196, 1997.
\bibitem{Tutte} W.T. {Tutte}. A contribution to the theory of chromatic polynomials. {\it{Can. J. Math.}} 6:80--91, 1954.
\end{thebibliography}
\end{document}
