\section{Introduction}

\subsection{Normalized characters}

Characters are a basic tool of representation
theory. After normalization, they are also
useful in asymptotic problems.

If $k\leq n$ are natural numbers, then any
permutation $\pi \in S_k$ can also be treated 
as an element of the larger symmetric group 
$S_n$ by adding $n-k$ additional fixpoints. 
For any permutation $\pi \in S_k$ and any
irreducible representation $\rho^{\lambda}$ 
of the symmetric group $S_n$ which corresponds 
to the Young diagram $\lambda$, we define 
\emph{the normalized character}
$$
\Sigma_{\pi}(\lambda)
= \begin{cases} 
          n(n-1)\cdots(n-k+1)\frac{\operatorname{Tr}\rho^{\lambda}(\pi)}{\text{dimension of }\rho^{\lambda}} & \text{for } k \leq n,\\
          0 & \text{otherwise.}
\end{cases}
$$

Of particular interest are the character
values on the cycles, therefore we
will use the shorthand notation
$$\Sigma_{k}(\lambda)=\Sigma_{(1,2,\ldots,k)}(\lambda).$$


\subsection{Free cumulants}

\emph{Free cumulants} are an important tool
of free probability theory \cite{VDN92} and
random matrix theory \cite{Voi91}. In the
context of the representation theory of the
symmetric groups they can be defined as follows,
see \cite{Bia03}. For a Young diagram $\lambda$
we define its free cumulants 
$R_2(\lambda), R_3(\lambda), \ldots$ as
$$R_k(\lambda)=\lim_{s\to\infty} \frac{1}{s^k}\Sigma_{k-1}(s\lambda),$$
where the diagram $s\lambda$ is created from 
the diagram $\lambda$ by dividing each box 
of $\lambda$ into an $s\times s$ square. 

The free cumulants are very helpful for studying
asymptotic behaviour of the characters on a cycle 
of length $k$ when the size of the Young diagram 
tends to infinity \cite{Bia98}.

\subsection{Kerov character polynomials}

Kerov \cite{Ker00} formulated the following result: 
for each permutation $\pi$ and any Young
diagram $\lambda$, the normalized 
character $\Sigma_{\pi}(\lambda)$ is 
equal to the value of some polynomial 
$K_{\pi}(R_2(\lambda), R_3(\lambda), \ldots)$
(now called \emph{the Kerov character polynomial})
with integer coefficients. The first 
published proof of this fact was provided 
by Biane \cite{Bia03}. The Kerov character
polynomial is \emph{universal} because it 
does not depend on the choice of $\lambda$. 
We are interested in the values of the 
characters on cycles, therefore for 
$\pi=(1, 2, \ldots, k)$ we use 
the simplified notation
\begin{align}
\label{kerpol}
\Sigma_k=K_k(R_2, R_3, \ldots)
\end{align}
for such Kerov polynomials. The first few Kerov polynomials $K_k$ are as follows:
\begin{align*}
K_1&=R_2,\\
K_2&=R_3,\\
K_3&=R_4+R_2,\\
K_4&=R_5+5R_3,\\
K_5&=R_6+15R_4+5R_2^2+8R_2,\\
K_6&=R_7+35R_5+35R_3R_2+84R_3, \\
K_7&=R_8+180R_2+224R_2^2+14R_2^3+56R_3^2+469R_4+84R_2R_4+70R_6.
\end{align*}

Kerov conjectured that the coefficients of 
the polynomial $K_k$ are \emph{non-negative} integers.
Goulden and Rattan \cite{GR05} found an explicit 
formula for the coefficients of the Kerov
polynomial $K_k$; unfortunately, their formula 
was complicated and did not give any combinatorial
interpretation to the coefficients. Later, 
F\'{e}ray proved positivity \cite{Fer09} and together 
with Dołęga and Śniady found a combinatorial 
interpretation of the coefficients \cite{DFS10}.
In this paper, we will use the combinatorial
interpretation given by them in the special case 
of linear and square coefficients.


\subsection{Goulden--Rattan conjecture}

Goulden and Rattan \cite{GR05} introduced 
a family of functions $C_2,C_3,\dots$ on 
the set of Young diagrams given by
$C_0=1$, $C_1=0$ and
$$C_k^{\lambda}=\frac{24}{k(k+1)(k+2)}\lim_{s\to\infty}\frac{1}{s^k}\Big(\Sigma_{k+1}(s\lambda)-R_{k+2}(s\lambda)\Big)$$
for $k\geq2$.

Śniady \cite{Sni06} proved the explicit form of $C_k$
(conjectured by Biane \cite{Bia03}) as a polynomial in the 
free cumulants $R_2, R_3, \ldots$ given by
\begin{align}
\label{cformula}
C_k=\sum_{\substack{j_2,j_3,\ldots \geq 0 \\ 2j_2+3j_3+\cdots=k}}
(j_2+j_3+\cdots)!\prod_{i\geq 2} \frac{\big( (i-1)R_i\big)^{j_i}}{j_i!}
\end{align}
for $k\geq 2$.
The aforementioned formula of Goulden and Rattan for 
the Kerov polynomials was naturally expressed in 
terms of these quantities $C_2,C_3,\dots$ \cite{GR05}. 
More specifically, they constructed an explicit 
polynomial $L_k$ with rational coefficients such that 
\begin{align}
\label{grpol}
K_k-R_{k+1}=L_k(C_2, C_3, \ldots).
\end{align}
These polynomials are called 
\emph{the Goulden--Rattan polynomials}. 
They formulated the following conjecture:
\begin{conjecture}
\label{hipotezaGR}
The coefficients of the Goulden--Rattan polynomials 
are non-negative numbers with small denominators. 
\end{conjecture}
The first few Goulden--Rattan polynomials are 
as follows \cite{GR05}:
\begin{align*}
K_1&-R_2=0\\
K_2&-R_3=0\\
K_3&-R_4=C_2,\\
K_4&-R_5=\frac{5}{2}C_3,\\
K_5&-R_6=5C_4+8C_2,\\
K_6&-R_7=\frac{35}{4}C_5+42C_3,\\
K_7&-R_8=14C_6+\frac{469}{3}C_4+\frac{203}{3}C_2^2+180C_2.
\end{align*}

Linear coefficients of the Goulden--Rattan polynomials 
are non-negative, because they are equal to certain 
scaled coefficients of the Kerov polynomial:
\[ [ C_j ] L_k=\frac{1}{j-1} [ R_j ] K_k. \]

In this paper we will prove that the coefficient 
of $C_2^2$ is non-negative. We hope that edge sliding 
will also be a useful tool in proving non-negativity of 
the square coefficients $[ C_i C_j ] L_k$.
The next step towards the proof of 
Goulden--Rattan conjecture would be to understand 
the cubic coefficients $ [ C_i C_j C_u ] L_k$; we 
hope that our methods will still be applicable there,
nevertheless, there seem to be some difficulties 
related to the inclusion-exclusion principle.

\subsection{Graphs on surfaces, maps and expanders}

We will consider graphs drawn on an oriented
surface. Each face of such a graph has some 
number of edges ordered cyclically by going 
along the boundary of the face  and touching 
it with the right hand. We will call it 
\emph{clockwise boundary direction}. If we use the left hand 
and visit the edges in the opposite order, we 
will call it {counterclockwise boundary direction}. 

By \emph{a map} we mean a bipartite 
graph drawn without intersections on an oriented 
and connected surface with minimal genus. The maps 
which we consider have a fixed choice of colouring 
of the vertices, i.e., each 
vertex is coloured black or white, with the edges
connecting the vertices of the opposite colours. 
An example of a map is shown in \cref{fig:mapa}.

\begin{figure}[H]
\torus{0.65}{1.0}
\caption
{
	\protect\subref{fig:rystorus} 
		An example of a map with $4$ vertices 
		and $5$ edges drawn on a torus.\\
	\protect\subref{fig:rysnormal} 
		The same map drawn for simplicity 
		on the plane. 
}
\label{fig:mapa}
\end{figure}

\emph{An expander} \cite[Appendix A.1]{Sni19} 
 is a map with the following properties.
\begin{itemize}

\item It has a distinguished edge (known as
the root) and one face.

\item Each black vertex is assigned a natural 
number, known as a weight, such that each 
non-empty proper subset of the set of black 
vertices has more white neighbours than the sum 
of its weights.

\item The sum of all weights is equal to 
the number of white vertices.

\end{itemize}
The map from \cref{fig:mapa} is an expander 
if each black vertex has weight $1$ 
(any choice of the root is valid).

Using the Euler characteristic we get
\begin{align}
\label{euler}
2-2g=\chi=V-k+1
\end{align}
where $g$ denotes the genus of the surface, 
$V$ denotes the number of vertices and $k$ 
denotes the number of edges.

\subsection{Combinatorial interpretation of 
the Kerov polynomial coefficients}
The following two theorems 
\cref{thm1} and \cref{thm3}
give a combinatorial interpretation to 
the linear and square coefficients of 
the Kerov character polynomials 
\cite[Theorem 1.2, Theorem 1.3]{DFS10}.
The first is as follows.
\begin{theorem}
\label{thm1} 
For all integers $l\geq2$ and $k\geq 1$ 
the coefficient $[R_l] K_k$ 
is equal to the number of pairs 
$(\sigma_1,\sigma_2)$ of permutations 
$\sigma_1, \sigma_2 \in S(k)$ such that
$\sigma_1\circ\sigma_2=(1,2,\ldots,k)$ and 
such that $\sigma_2$ consists of one
cycle and $\sigma_1$ consists of $l-1$ cycles.
\end{theorem}
The expanders are a graphical interpretation 
of these pairs of permutations.
There is a natural bijection between such 
pairs of permutations $(\sigma_1,
\sigma_2)$ and the expanders with one face, 
one black vertex, $l-1$ white
vertices and $k$ edges. Additionally, one edge 
is selected as the root and the unique black 
vertex has a weight $l-1$. More precisely:

\begin{itemize}

\item The edges are numbered $1, 2, \dots, k$.
The edge with number $1$ is selected as the root.

\item \emph{The counterclockwise angular cyclic order of the 
edges on a given vertex} (i.e., the order of edges 
ending at this vertex around it) corresponds to 
a cycle of a permutation
depending on the colour of this vertex, i.e., 
$\sigma_1$ for white and $\sigma_2$ for black
(in this case we have a unique cycle of 
the permutation $\sigma_2$). 

\item The unique face corresponds to the unique 
counterclockwise boundary
cycle of the permutation $(1, 2, \ldots, k)$.

\end{itemize}
Since there is only one face, the root determines the 
numbering of all edges. We can reformulate \cref{thm1} as follows. 
(See \cref{fig:reformone} for an example.)
\begin{theorem}
\label{thm2}
For all integers $l\geq2$ and $k\geq 1$ the 
coefficient $[R_l] K_k$ is equal to the number 
of expanders with $k$ edges, $l-1$ white vertices 
and $1$ black vertex with the weight $l-1$.
\end{theorem}

\begin{figure}[H]
\reform{1.05}
\caption
{
		Examples of expanders with $5$ edges and 
		their corresponding pair of permutations 
		$\sigma_1, \sigma_2$ such that 
		$\sigma_1 \sigma_2 = (1 \; 2\; 3 \; 4 \; 5)$. 
		The root is assigned the number $1$. 
		\protect\subref{fig:reformone} 
		The expander with one black vertex 
		and three white vertices. 
		\protect\subref{fig:reformtwo}
		The expander with two black vertices 
		and two white vertices.
}
\end{figure}

Similarly we use the second theorem \cite[Theorem 1.3]{DFS10} 
for square coefficients.
\begin{theorem}
\label{thm3}
For all integers $l_1, l_2\geq 2$ and $k\geq 1$ 
the coefficient $[R_{l_1} R_{l_2}] K_k$ is equal 
to the number of triples $(\sigma_1, \sigma_2, q)$ 
with the following properties.
\begin{itemize}

\item The permutations $\sigma_1, \sigma_2 \in S_k$ 
fulfill the equality $\sigma_1\circ\sigma_2=(1,2,\cdots, k)$.

\item The permutation $\sigma_1$ consists of two cycles and 
the permutation $\sigma_2$ consists of $l_1+l_2-2$ cycles.

\item The function $q$ associates the numbers 
$l_1$ and $l_2$ to the two cycles of $\sigma_1$. 
Furthermore, for each cycle $c$ of $\sigma_1$ there 
exist at least $q(c)$ cycles of $\sigma_2$ which 
intersect nontrivially $c$.
\end{itemize}
\end{theorem}
Analogously, we can also reformulate \cref{thm3}. 
(See \cref{fig:reformtwo} for an example.)
\begin{theorem}
\label{thm4}
For all integers $l_1, l_2\geq 2$ and $k\geq 1$ 
the coefficient $[R_{l_1} R_{l_2}] K_k$ is equal 
to the number of expanders with $k$ edges, 
$l_1+l_2-2$ white vertices and $2$ black 
vertices with weights $l_1-1, l_2-1$.
\end{theorem}

\subsection{Relationship between coefficients 
of Goulden--Rattan polynomials 
and coefficients of Kerov polynomials}

The formula \eqref{cformula} allows us to 
express $(C_i)$ in terms of free cumulants;
we see that the coefficients of the terms 
$R_i R_j$, $R_{i+j}$ and $R_{2j}$ in the expressions
$C_{i} C_{j}$, $C_{i+j}$ and $C_{2j}$ are given for $i \neq j$ by
\begin{align*}
C_i C_j &= (i-1)(j-1) R_i R_j + 0  R_{i+j} + \text{(sum of other terms)},\\
C_{i+j} &=2(i-1)(j-1)R_iR_j+(i+j-1)R_{i+j}+\text{(sum of other terms)},\\
C_{2j} &=(j-1)^2R_j^2+(2j-1)R_{2j}+\text{(sum of other terms)}. 
\end{align*}
Moreover, any product $C_{i_1} C_{i_2}\cdots C_{i_t}$
of at least $t\geq 3$ factors does not contain any 
of the terms $C_i C_j$, $C_{i+j}$ and $C_{2j}$.
It follows that the square coefficients of 
the Goulden--Rattan polynomial are related 
to the coefficients of the Kerov polynomial via
\begin{align*}
\frac{\partial^2L_k}{\partial{C_i}\partial{C_j}}\Bigg|_{0=C_1=C_2=\cdots}
&=\frac{1}{(i-1)(j-1)}\frac{\partial^2K_k}{\partial{R_i}\partial{R_j}}\Bigg|_{0=R_1=R_2=\cdots}
-2\frac{\partial L_k}{\partial{C_{i+j}}}\Bigg|_{0=C_1=C_2=\cdots}\\
&=\frac{1}{(i-1)(j-1)}\frac{\partial^2K_k}{\partial{R_i}\partial{R_j}}\Bigg|_{0=R_1=R_2=\cdots}
-\frac{2}{(i+j-1)}\frac{\partial K_k}{\partial{R_{i+j}}}\Bigg|_{0=R_1=R_2=\cdots}
\end{align*}
for $i \neq j$. Whereas the quadratic coefficients are related via
\begin{align*}
\frac{\partial^2L_k}{\partial{C_j^2}}\Bigg|_{0=C_1=C_2=\cdots}
&=\frac{1}{(j-1)^2}\frac{\partial^2K_k}{\partial{R_j^2}}\Bigg|_{0=R_1=R_2=\cdots}
-\frac{\partial L_k}{\partial{C_{2j}}}\Bigg|_{0=C_1=C_2=\cdots}\\
&=\frac{1}{(j-1)^2}\frac{\partial^2K_k}{\partial^2{R_j}}\Bigg|_{0=R_1=R_2=\cdots}
-\frac{1}{(2j-1)}\frac{\partial K_k}{\partial{R_{2j}}}\Bigg|_{0=R_1=R_2=\cdots}
\end{align*}
for any natural number $j$.
Thus, we obtain the explicit formula for 
the square coefficients of the Goulden–Rattan polynomial:
\begin{align}
\label{formula}
[C_j^2]L_k &=\frac{1}{(j-1)^2}[R_j^2]K_k-\frac{1}{2j-1}[R_{2j}]K_k \\
\intertext{and}
[C_iC_j]L_k &=\frac{1}{(i-1)(j-1)}[R_iR_j]K_k-\frac{2}{i+j-1}[R_{i+j}]K_k
\qquad \text{for $i\neq j$.}
\end{align}

\section{The main result} 

Let $Y_k(u)$ denote the set of expanders 
with $k$ edges, $u-1$ white vertices and 
one black vertex. Let $X_k(i, j)$ denote 
the set of expanders with $k$ edges, 
$i+j-2$ white vertices and two black 
vertices with weights $i-1$ and $j-1$. 
Using  \cref{thm2} and \cref{thm4} we can 
also reformulate the Goulden--Rattan 
conjecture for the square coefficients 
in terms of expanders, as follows.
\begin{con} 
    \label{con:GJ2}
Let $i \neq j$ be natural numbers. Then 
\begin{align*}
(2j-1)\ \left\| X_k(j, j) \right\|    &   \geq (j-1)^2\ \left\| Y_k(2j) \right\| \\
\intertext{and}
(i+j-1)\ \left\| X_k(i, j) \right\|  & \geq 2(i-1)(j-1)\ \left\| Y_k(i+j) \right\|
\end{align*}
for any natural number $k$. 
\end{con}
These inequalities are equivalent to the 
positivity of the coefficients $[C_j^2] L_k$ 
and $[C_i C_j] L_k$ respectively. 
In this text we prove only the first 
inequality  in the special case 
$j=2$. We hope to present
a proof of \cref{con:GJ2} in its general 
form in a future paper.

Using \cref{formula} 
we can calculate several examples of 
the coefficient of $C_2^2$ of 
the Goulden--Rattan polynomials
\begin{align*}
[C_2^2] L_4 &=0-0=0,\\
[C_2^2] L_5 &=5-\frac{1}{3} \cdot 15=0,\\
[C_2^2] L_6 &=0-0=0, \\
[C_2^2] L_7 &=224-\frac{1}{3} \cdot 469=\frac{203}{3}, \\
[C_2^2] L_8 &=0-0=0. 
\end{align*}
Note that if $k$ is even then $[C_2^2] L_k=0$ because there does not exist an expander with $4$ vertices and an even number of edges, since
$2-2g=2j-k+1$ by \cref{euler}. Additionally, $[C_2^2]L_1=0$ and $[C_2^2]L_3=0$. Thus we can assume that the number of edges $k$ is odd and $k \geq 5$. 

Let 
\begin{align}
\label{xdef}
X_k &= X_k(2, 2), \\
\label{ydef}
Y_k &= Y_k(4).
\end{align}
The set $X_k$ consists of expanders with 
$2$ black vertices and $2$ white vertices
such that each black vertex is connected 
with both white vertices;
each black vertex necessarily has weight 
equal to $1$. The set $Y_k$ consists of 
expanders with one black vertex 
(which necessarily has weight $3$) 
connected with all $3$ white vertices. 
From now on we will omit the weights 
of the black vertices.

The main goal of this paper is to prove 
the following:
\begin{theorem}
\label{mainthm2}
The inquality
$$3\big\|X_k\big\| \geq \big\|Y_k\big\|$$
is true for any natural number $k$.
\end{theorem}

\section{Maps, expanders, and edge sliding}

In this section we provide some necessary 
background details for the proof of \cref{mainthm2}.

\subsection{Edge sliding}

We define \emph{the edge sliding} on a 
graph as follows. We start from a graph
$G$ drawn on an oriented and connected 
surface with a selected 
set of \emph{special edges}. 
Further, we assume that some ends 
(at the vertices) of the special edges 
(not necessarily all) are assigned either 
the clockwise or counterclockwise boundary direction.

By \emph{the rest of the graph $G^{\res}$} we 
will understand the graph $G$ with the 
special edges removed. The graph $G^{\res}$ 
is drawn on the same surface, even if 
its genus is not minimal. A 
\emph{corner} of $G^{\res}$ is an inner angle 
in a vertex between two neighboring 
edges of $G^{\res}$ (or full angle for the 
degenerate case of no edge in a vertex). 
All ends of the special edges are located 
inside certain corners of $G^{\res}$.

Let $\sigma_{\res}$ be the permutation 
on the set of the corners of $G^{\res}$ 
such that each cycle of $\sigma_{\res}$
corresponds to the corners which belong 
to some face of $G^{\res}$, arranged in 
the clockwise boundary cyclic order (i.e., by 
going along the boundary of the face of
$G^{\res}$, touching it with the 
right hand). For the example on
\cref{fig:rysnum} we have 
$\sigma_{\res} = ( 1' )( 1, 2, 3, 4, 5, 6).$

\begin{figure}[H]
\sliding{0.95}
\caption
{
	An example of edge sliding.
	\protect\subref{fig:rysprzed} 
		A graph with the special 
		edges dashed and coloured red.
		The directions of the edge 
		ends are indicated by arrows.
	\protect\subref{fig:rysw} 
		The graph during the edge 
		sliding in the clockwise 
		boundary direction. 
	\protect\subref{fig:ryspo} 
		The graph after the edge 
		sliding. Directions have 
		already been reversed.
	\protect\subref{fig:rysnum} 
		The graph without the
		special edges with the 
		numbered order of the corners.
}
\label{fig:sliding}
\end{figure}

We assume that each corner of the 
graph $G^{\res}$ contains the ends 
of the special edges in the 
following counterclockwise angular 
order.  
\begin{itemize}

\item First, some number of the 
		ends of the special edges 
		with the clockwise 
		boundary direction.

\item Second, some number of the 
		ends of the special edges with 
		no assigned direction. 
\item Finally, some number of the
		ends of the special edges with 
		the counterclockwise 
		boundary direction. 
\end{itemize}  
Furthermore, we assume that there is no 
corner $c$ of $G^{\res}$ such that the corner 
$c$ contains the end of a special 
edge with the clockwise boundary direction and 
the corner $\sigma_{\res}(c)$ contains the end 
of a special edge with the  
counterclockwise boundary direction 
(see \cref{fig:rysprzed} for an example).

The output of the edge sliding is defined 
as the graph $G$ in which the ends of the 
special edges in a corner $c$ which have 
an assigned clockwise boundary direction 
are slid to the next corner $\sigma_{\res}(c)$. 
However the ends of the special edges which have 
an assigned counterclockwise boundary direction 
are slid to the previous corner $\sigma_{\res}^{-1}(c)$. 
Moreover, the output of the edge sliding
has opposite assignments of directions to
both ends of each special edge. \cref{fig:sliding} 
shows an example of the edge sliding. Note that 
in the degenerate case of no edge of the 
graph $G^{\res}$ in a vertex 
(like at the corner $1'$ in the picture \cref{fig:rysnum}), 
sliding does not really occur.

More precisely, after the edge sliding each corner $c$ 
contains the ends of special edges in the following 
counterclockwise angular order.  
\begin{itemize}

\item First, some number of the ends 
		of special edges with the clockwise
		boundary direction which 
		previously appeared in the 
		same angular order in the corner 
		$\sigma_{\res}(c)$
		with the counterclockwise boundary
		direction.
\item Second, some number of the ends 
		of special edges which 
		previously appeared in the 
		same angular order in the corner $c$
		without the direction. 
\item Finally, some number of the ends 
		of special edges with counterclockwise 
		boundary direction which previously 
		appeared in the same angular order 
		in the corner $\sigma_{\res}^{-1}(c)$
		with the clockwise boundary direction.
\end{itemize}  

The edge sliding is an involution on the 
set of graphs drawn on an oriented and 
connected surface with a selected set of 
special edges which satisfy the above conditions 
for correct selection of directions. Edge sliding 
is an invertible transformation, with the inverse 
also given by edge sliding. 

In addition, it is easy to see that the 
edge sliding on a graph does not change 
the number of faces of this graph.  


\subsection{The set $X_k$ of maps} 

We consider any map from the set $X_k$. 
This map has one face 
and an odd number of edges $k \geq 5$. 
We denote the black vertices by 
$b_1, b_2$ and the white vertices by 
$w_1, w_2$. There is at least one edge
between each pair of the vertices of
different colours. Of course, 
$\degg(b_1)+\degg(b_2)=k$ is an odd 
number. Without loss of generality we 
may assume that $\degg(b_1)>0$ is an 
odd number and $\degg(b_2)>0$ is an 
even number. Let $k_1, k_2 > 0$
denote the numbers of edges which 
connect the vertex $b_1$ with the 
vertices $w_1, w_2$, respectively. 
As $\degg(b_1)=k_1+k_2$ is 
an odd number, without loss of  
generality we may assume that $k_1$ 
is even and $k_2$ is odd. For example, 
the unique (up to choice of the root) 
map from the set $X_5$ is shown in
\cref{fig:rysalla}.

\begin{figure}[H]
\rysall{0.95}
\caption
{
Examples of maps from the sets 
\protect\subref{fig:rysalla}  $X_5$,
\protect\subref{fig:rysallb}  $T_{5}^{\odd}$,
\protect\subref{fig:rysallc}  $T_{5}^{\even}$,
\protect\subref{fig:rysalld}  $T_{5}^{\rest}$.
Special edges are dashed and coloured. 
The directions are indicated by arrows, and 
the root is not marked.
}
\label{fig:rysrest}
\end{figure}

\subsection{The set $Y_k$ of maps}

Let $\sigma$ be the cycle that encodes 
the clockwise boundary cyclic order of the 
corners on the unique face of $G$ 
(this is just $\sigma_{\res}$ for $G^{\res}$ 
with no special edges). We will say 
that \emph{the vertex $w_j$ is a
descendant of the vertex $w_i$} 
(we denote it by $w_i \rightarrow w_j$) 
if using the clockwise boundary order of 
the corners on the unique face of the 
map we can move (by walking along the 
edges and holding them with the right 
hand) in two steps from a certain corner 
$c_i$ of the vertex $w_i$ to a certain
corner $c_j$ of the vertex $w_j$, i.e., 
$\nast^2(c_i)=c_j$. 

We consider any map from the set $Y_k$. 
Any such map has one face and an odd 
number of edges $k \geq 5$. We denote 
the black vertex by $b$ and  the white
vertices by $w_1, w_2, w_3$. We will 
write the set $Y_k$ as a union of three 
sets which will be defined below.

Let $Y_{k}^{\odd}\subseteq Y_k$ be the 
set of maps for which there exists an
\emph{odd degree} white vertex (let us say it 
is $w_3$) which has the other two white
vertices as descendants, i.e., 
$w_3\rightarrow w_1$ and 
$w_3\rightarrow w_2$. 
Let $T_k^{\odd}$ be the set of all 
maps from the set $Y_k^{\odd}$ with a 
distinguished vertex $w_3$ with this 
property. Moreover, the set of edges of 
the vertex $w_3$ is fixed as the set of special 
edges. In addition, the edge ends at the 
vertex $w_3$ have no assigned direction, 
and the edge ends at the vertex $b$ have 
assigned clockwise boundary direction.
The unique (up to choice of the root) 
map from the set $T_{5}^{\odd}$ is 
shown in \cref{fig:rysallb}. Clearly
\begin{equation}
\label{ineqodd}
|T_{k}^{\odd}| \geq |Y_{k}^{\odd}|.
\end{equation}

Let $Y_{k}^{\even}\subseteq Y_k$ be 
the set of maps such that there
exists an \emph{even degree} white vertex 
(let us say it is $w_3$) which has 
the other two white vertices as 
descendants, i.e., 
$w_3\rightarrow w_1$ and 
$w_3\rightarrow w_2$. 
Let $T_k^{\even}$ be the set of all  
the maps from the set $Y_k^{\even}$ 
with a distinguished vertex $w_3$ with 
this property. Moreover, the set of edges 
of the vertex $w_3$ is fixed as the set of special 
edges. In addition, the edge ends at the 
vertex $w_3$ have no assigned direction, 
and the edge ends at the vertex $b$ have 
assigned clockwise boundary direction. 
The unique (up to choice of 
the root) map from the set $T_{5}^{\even}$ 
is shown in \cref{fig:rysallc}. Clearly
\begin{align}
\label{ineqeven}
|T_{k}^{\even}| \geq |Y_{k}^{\even}|.
\end{align}

Let $Y_{k}^{\rest}\subseteq Y_k$ be 
the set of maps not included in the
sets $Y_{k}^{\odd}$ and 
$Y_{k}^{\even}$, i.e.,
\begin{align}
\label{yrestdef}
Y_{k}^{\rest}=Y_k 
\setminus (Y_{k}^{\odd} 
\cup Y_{k}^{\even}).
\end{align}

Consider some map $m\in Y_{k}^{\rest}$. 
Obviously $w_1 \rightarrow w_2 
\rightarrow w_3 \rightarrow w_1$ or the 
other way around. Without  loss  of  
generality  we  may  assume  that 
$w_1 \rightarrow w_2 \rightarrow w_3 
\rightarrow w_1$ and as a consequence 
$w_1 \nleftarrow w_2 \nleftarrow w_3 
\nleftarrow w_1$.

\begin{lemma}
The map $m$ has a white vertex of odd 
degree, greater than $1$. 
\end{lemma}
\begin{proof}
By contradiction,  suppose this is not 
the case. The map $m$ has at least one 
odd degree white vertex, because 
$\degg(w_1)+\degg(w_2)+\degg(w_3)=k$ is 
odd. Without loss of generality we may 
assume that $\degg(w_1)$ is odd. Since 
$$\degg(w_1)+\degg(w_2)+\degg(w_3)=k>3=
1+1+1,$$ it follows that $\degg(w_1)=1$ 
and $\degg(w_2),\degg(w_3)$ are even, 
because $m$ does not have a white vertex 
with odd degree greater than $1$. The 
vertex $w_1$ is a leaf and thus has a 
unique corner which we denote by $c_1$.

Naturally $\nast^2(c_1)$ is a corner of 
the vertex $w_2$. Note that $\nast^2$ 
is a permutation of the corners of the 
white vertices which has only one cycle, 
because the map $m$ has only one face. 
The corners of the white vertices 
can be labelled 1, 2, 3 according to 
the names of the vertices 
they are in. If a corner $c$ has the 
label $a$, its descendant $\nast^2(c)$ 
has either the label $a$ or 
$1+a \operatorname{mod} 3$. 
There is only one corner which has the 
label $1$, so the corner labels 
(arranged in the cyclic order according 
to the unique cycle of $\nast^2$) are 
$(1, 2, \ldots, 2, 3, \ldots, 3)$. Since 
there exists only one corner $c_2$ of the 
white vertex $ w_2 $ such that 
$\nast^2(c_2)$ is a corner of the vertex 
$w_3$, then there exists a unique corner 
$c_0=\nast(c_2)$ of the vertex $b$ such that 
$\nast(c_0)$ is the corner of the vertex $w_3$ 
and $\nast^{-1}(c_0)$ is the corner of the 
vertex $w_2$. Thus the clockwise angular cyclic 
order of the edges around the black vertex 
$b$ is as follows: one edge connected to 
the vertex $w_1$, a certain number of edges 
connected to the vertex $w_2$, a certain 
number of edges connected to the vertex $w_3$.
\cref{fig:ryschangea} visualizes this situation.

\begin{figure}[H]
\ryschange{0.95}
\caption
{ 
\protect\subref{fig:ryschangea} The map $m$ before replacement 
								including the marked corner $c_0$. 
\protect\subref{fig:ryschangeb} A non-existent hypothetical map 
								with four vertices and an even
								number of edges. 
}
\label{fig:ryschange}
\end{figure}
It is easy to see that we can replace all 
edges of the white vertex $w_2$ by a single 
edge (see \cref{fig:ryschange}) and get a map 
with $4$ vertices, one 
face and an even number of edges. We get a 
contradiction, because such a map does not 
exist (see \cref{euler}). Therefore, the
map $m$ has a white vertex with an odd 
degree greater than $1$.
\end{proof}

\pagebreak[1]

We now fix all edges between 
the vertices $b$ and $w_3$ as special.
Furthermore, the ends of the special edges in the
vertex $w_3$ have no assigned direction. 
To all ends of the special edges in the vertex 
$b$ we assign the direction in such way that among 
them there is an even number with the clockwise boundary direction 
and an odd number with the counterclockwise boundary direction.
This is always possible, e.g. for a single edge 
with the counterclockwise boundary direction.

Let $T_k^{\rest}$ be the set of all the 
maps from the set $Y_k^{\rest}$ with a 
distinguished white vertex denoted by $w_3$ 
with a fixed choice of the set of special 
edges together with the directions of their 
ends satisfying the conditions just mentioned above. 
The unique (up to choice of the root) example 
of the map from the set $T_{5}^{\rest}$ is 
shown in \cref{fig:rysalld}. Clearly
\begin{align}
\label{ineqrest}
|T_{k}^{\rest}| \geq |Y_{k}^{\rest}|.
\end{align}


\section{Proof of main result}

\subsection{Goal}
In this section we will construct three bijections 
which show the cardinalities of the corresponding sets 
are equal. Using these equalities and the definitions 
of these sets we will prove \cref{mainthm2}.

\subsection{Three bijections}

\paragraph{The first bijection between $X_k$ and $T_k^{\odd}$.}
We start from a map $m \in X_{k}$. As the set of 
special edges we select all edges of
the vertex $b_1$. Recall that we have assumed that
$\degg(b_1)$ is odd. The ends of the special edges 
at the vertex $b_1$ have no assigned direction 
and the other ends have assigned
the counterclockwise boundary direction. We apply the 
edge sliding to the map $m$. Then we change 
the colour of the black vertex $b_1$ to white 
and its name to $w_3$, and the name of the vertex
$b_2$ to $b$. Of course, the degree of the vertex
$w_3$ does not change and is odd. In addition, 
$w_3\rightarrow w_1$ and $w_3\rightarrow w_2$,
because any map from the set $X_{k}$ has at 
least one edge between each pair of the vertices 
of different colours. We obtain a map from the 
set $T_{k}^{\odd}$. (At all times one of the edges 
is selected as the root.) Moreover, each map from the 
set $T_{k}^{\odd}$ can be produced in this way. Such a
transformation is a bijection between the set 
$X_k$ and the set $T_k^{\odd}$, 
since the edge sliding is reversible.  
\cref{fig:rysodd} shows an example of this
bijection for $k=5$. Thus
\begin{align}
\label{eqodd}
|X_k|=|T_k^{\odd}|.
\end{align}
\begin{figure}[H]
\rysodd{0.95}
\caption
{
The example of the first bijection 
for the $5$-edged map.
	\protect\subref{fig:rysodda} 
		The map from the set $X_{5}$.
	\protect\subref{fig:rysoddb} 
		The map during the edge sliding.
	\protect\subref{fig:rysoddc} 
		The map after the edge sliding.
	\protect\subref{fig:rysoddd} 
		The map from the set $Y_{5}^{\odd}$.
}
\label{fig:rysodd}
\end{figure}

\paragraph{The second bijection between $X_k$ and $T_k^{\even}$.}
We start from a map $m \in X_{k}$. As the set 
of special edges we take all edges of
the vertex $b_2$. Recall that we have assumed that 
$\degg(b_2)$ is even. The ends of the special edges 
at the vertex $b_2$ have no assigned direction
and the other ends have assigned
the counterclockwise boundary direction. We apply the 
edge sliding to the map $m$. Then we change 
the colour of the black vertex $b_2$ to white 
and its name to $w_3$, and the name of the vertex
$b_1$ to $b$. Of course, the degree of the vertex
$w_3$ does not change and is even. In addition, 
$w_3\rightarrow w_1$ and $w_3\rightarrow w_2$,
because any map from the set $X_{k}$ has at 
least one edge between each pair of the vertices 
of different colours. We obtain a map from the 
set $T_{k}^{\even}$. (At all times one of the edges 
is selected as the root.) Moreover, each map from the 
set $T_{k}^{\even}$ can be produced. Such a 
transformation is a bijection between the set 
$X_k$ and the set $T_k^{\even}$,
since the edge sliding is reversible. 
\cref{fig:ryseven} shows an example of this
bijection for $k=5$. Thus
\begin{align}
\label{eqeven}
|X_k|=|T_k^{\even}|.
\end{align}
\begin{figure}[H]
\ryseven{0.95}
\caption
{
\protect\subref{fig:rysevena}---\protect\subref{fig:rysevend} 
The example of the second bijection for the $5$-edged map. 
}
\label{fig:ryseven}
\end{figure}

\paragraph{The third bijection.}
We start from a map $m \in X_{k}$. As the set of 
special edges we select all edges of
the vertex $b_1$. Recall that we have assumed that
$\degg(b_1)$ is odd. The ends of the special edges 
at the vertex $b_1$ have no assigned direction,
the ends at the vertex $w_1$ have assigned
the counterclockwise boundary direction and at the vertex 
$w_2$ have the clockwise boundary direction. We apply the 
edge sliding to the map $m$. Then we change 
the colour of the black vertex $b_1$ to white 
and its name to $w_3$, and the name of the vertex
$b_2$ to $b$. Of course, the degree of the vertex
$w_3$ does not change and is odd. In addition, 
$w_3\rightarrow w_1$ and $w_2\rightarrow w_3$ 
(and $w_1\rightarrow w_2$),
because any map from the set $X_{k}$ has at 
least one edge between each pair of the vertices 
of different colours. We do not necessarily obtain 
a map from the set $T_{k}^{\rest}$ (it may be that 
we obtain a map from set $T_{k}^{\odd}$), but it can 
be seen that each map from the set $T_{k}^{\rest}$ 
can be produced. (At all times one of the edges 
is selected as the root.)
Such a transformation is a bijection between the 
set $X_k$ and some superset of the set $T_k^{\odd}$,
since the edge sliding is reversible. 
\cref{fig:rysrest} shows an example of this
bijection for $k=5$. Thus
\begin{align}
\label{eqrest}
|X_k| \geq |T_k^{\rest}|.
\end{align}
\begin{figure}[H]
\rysrest{0.95}
\caption
{
\protect\subref{fig:rysresta} - \protect\subref{fig:rysrestd} 
The example of the third bijection for the $5$-edged map.
}
\label{fig:rysrest}
\end{figure}



\subsection{The conclusion of the proof}
\begin{proof}[\unskip\nopunct]
We can now proceed to the proof of \cref{mainthm2}, we
have: 
\begin{align*}
3[C_2^2]L_k & =3[R_2^2]K_k-[R_4]K_k \tag*{by \eqref{formula}}\\ 
& =3|X_k|-|Y_k| \tag*{by \eqref{xdef}, \eqref{ydef}}\\ 
& \geq |T_k^{\odd}|+|T_k^{\even}|+|T_k^{\rest}|-|Y_k| \tag*{by \eqref{eqodd},
\eqref{eqeven}, \eqref{eqrest}}\\ & \geq |Y_k^{\odd}|+|Y_k^{\even}|+|
Y_k^{\rest}|-|Y_k| \tag*{by \eqref{ineqodd}, \eqref{ineqeven}, \eqref{ineqrest}}\\
& =|Y_k^{\odd} \cap Y_k^{\even}| \tag*{by \eqref{yrestdef}}\\ 
& \geq 0.
\end{align*}
\end{proof}

\section*{Acknowledgements}

I thank my supervisor, Piotr
Śniady, for his support. I thank also 
Doctor Stephen Moore for the help with the 
text editing.

\printbibliography 

\end{document} 
