% !TeX spellcheck = en_US
%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{25}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{propos}[thm]{Proposition}

\theoremstyle{remark}
\newtheorem*{example}{Example}

\usepackage{lipsum}
\usepackage{todonotes}
\usepackage{cleveref}
\usepackage{tikz}
\usepackage[normalem]{ulem}

\newcommand{\Sym}[1]{\mathfrak{S}_{#1}}
\newcommand*{\circled}[2][]{\tikz[baseline=(C.base)]{
        \node[inner sep=0pt] (C) {\vphantom{1g}#2};
        \node[draw, circle, inner sep=3pt, yshift=1pt] 
        at (C.center) {\vphantom{1g}};}}
    
%\DeclareMathOperator{\Jump}{JUMP}
%\DeclareMathOperator{\Exchange}{EXCHANGE}
\newcommand{\Jump}{\mathbb{J}}
\newcommand{\Exchange}{\mathbb{E}}

%\DeclareMathOperator{\Root}{parent}
\newcommand{\Root}{p}

\DeclareMathOperator{\Division}{DIVISION}
\DeclareMathOperator{\Jumpback}{JUMP--BACK}
\DeclareMathOperator{\Stretch}{STRETCH}
\DeclareMathOperator{\Ch}{Ch}



%% define your title in the usual way
\title[Bijection between trees and factorizations]{Bijection between trees \\ in Stanley character formula \\ and factorizations of a cycle}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Karolina Wojtyniak\thanks{\href{mailto:karolina5284@mat.umk.pl}{karolina5284@mat.umk.pl}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Nicolaus Copernicus University in Toruń, Faculty of Mathematics and Computer Science, ul.~Chopina 12/18, 87-100 Toruń, Poland}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)

\abstract{Stanley and F\'eray gave a formula for the irreducible character of the
    symmetric group related to a \emph{multi-rectangular Young diagram}. This
    formula shows that the character is a polynomial in the multi-rectangular
    coordinates and gives an explicit combinatorial interpretation for its
    coefficients in terms of counting certain decorated maps (i.e.,~graphs drawn on
    surfaces). In the current paper we concentrate on the coefficients of the
    top-degree monomials in the Stanley character polynomial which corresponds to
    counting certain decorated plane trees. We give an explicit bijection between
    such trees and minimal factorizations of a cycle.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{plane trees, minimal factorizations of a cycle, bijection, irreducible characters of the symmetric groups}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
%\usepackage{enumerate}
\usepackage{subfig}
\addbibresource{25Wojtyniak.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Motivations}

\subsection{Normalized characters and Stanley polynomials}

For a Young diagram $\lambda$ with $N=|\lambda|$ boxes and a partition $\pi\vdash k$ we denote by 
\[ \Ch_\pi(\lambda) = \begin{cases}
    N(N-1)(N-2)\cdots(N-k+1)\  \frac{\chi^{\lambda}\left(\pi\cup
    1^{N-k}\right)}{\chi^{\lambda} \left(1^N\right)} & \text{for } k\leq N,
\\ 0 & \text{otherwise}
\end{cases}
\]
%\[ \Ch_\pi(\lambda) = \begin{cases}
%    N^{\downarrow k}\  \frac{\chi^{\lambda}_{\pi\cup
%            1^{N-k}}}{\chi^{\lambda}_{1^N}}, & \text{for } k\leq N,
%    \\ 0 & \text{otherwise}
%\end{cases}
%\]
%
the \emph{normalized irreducible character of the symmetric group}, where
$\chi^\lambda(\rho)$ denotes the value of the usual irreducible character of
the symmetric group which corresponds to the Young diagram $\lambda$,
evaluated on any permutation with the cycle decomposition given by the
partition $\rho$. One of the goals of \emph{asymptotic representation
    theory} is to understand the behavior of such
normalized characters in the scaling when the partition $\pi$ is fixed
and the number of the boxes of the Young diagram $\lambda$ tends to infinity.





\begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.9]
        \draw[thick] (0,0) grid (5,2);
        \draw[ultra thick] (0,0) rectangle (5,2);
        \draw[thick] (0,2) grid (4,5); 
        \draw[ultra thick] (0,2) rectangle (4,5);
        \draw[thick] (0,5) grid (2,6); 
        \draw[ultra thick] (0,5) rectangle (2,6);
        \draw [<->,blue] (5.4,0) -- (5.4,2) node [midway,fill=white,inner sep=2pt] {\textcolor{black}{$p_1$}};
        \draw [<->,blue] (0,0.3) -- (5,0.3) node [midway,fill=white,inner sep=2pt] {\textcolor{black}{$q_1$}};
        \draw [<->,blue] (4.4,2) -- (4.4,5) node [midway,fill=white,inner sep=2pt] {\textcolor{black}{$p_2$}};
\draw [<->,blue] (0,2.3) -- (4,2.3) node [midway,fill=white,inner sep=2pt] {\textcolor{black}{$q_2$}};
        \draw [<->,blue] (2.4,5) -- (2.4,6) node [midway,fill=white,inner sep=2pt] {\textcolor{black}{$p_3$}};
\draw [<->,blue] (0,5.3) -- (2,5.3) node [midway,fill=white,inner sep=2pt] {\textcolor{black}{$q_3$}};
        
    \end{tikzpicture}
\caption{Multi-rectangular Young diagram $\mathbf{p}\times \mathbf{q}=(2,3,1) \times (5,4,2)$.}
\label{fig:multi}
\end{figure}






For a pair of sequences of non-negative integers
$\mathbf{p}=(p_1,\dots,p_\ell)$ and $\mathbf{q}=(q_1,\dots,q_\ell)$ such that
$q_1\geq \cdots \geq q_\ell$ we consider the \emph{multi-rectangular Young
    diagram $\mathbf{p}\times \mathbf{q}$}, see \cref{fig:multi}. Stanley
\cite{Stanley2003/04,Stanley2006} initiated investigation of the normalized
characters evaluated on such multi-rectangular Young diagrams and proved that
\begin{equation}\label{eq:char-multi}
    (\mathbf{p},\mathbf{q}) \mapsto \Ch_\pi\big(\mathbf{p}\times \mathbf{q}  \big) 
\end{equation}
is a polynomial (called now \emph{the Stanley character polynomial}) in the variables
$p_1,\dots,p_\ell$ and $q_1,\dots,q_\ell$. He also gave a conjectural formula (proved
later by F\'eray \cite{Feray2010}) which gives a combinatorial interpretation to
the coefficients of this polynomial in terms of certain \emph{maps} (i.e., graphs drawn
on surfaces). Stanley also explained how investigation of its coefficients might
shed some light on the \emph{Kerov positivity conjecture}, see \cite{Sniady2016} for
more context.

Despite recent progress in this field (for the proof of the Kerov positivity
conjecture see \cite{Feray2009,Dolega2010}) there are several other positivity
conjectures related to the normalized characters $\Ch_\pi$ that remain open (see
\cite[Conjecture 2.4]{Goulden2007} and \cite{Lassalle2008}) and which suggest the
existence of some additional hidden combinatorial structures behind such
characters. We expect that such positivity problems are more amenable to
bijective methods 
%(such as the ones from \cite{Chapuy2009}) 
and the current
article is the first step in this direction.


We will concentrate on the special case when $\pi=(k)$ consists of a single
part. In this case the degree of the Stanley polynomial \eqref{eq:char-multi}
turns out to be equal to $k+1$. We will also concentrate on the
combinatorial interpretation of the coefficients of the Stanley polynomial
\eqref{eq:char-multi} standing at monomials of this maximal degree $k+1$ which
turns out to be related to maps of genus zero, i.e., plane trees. Nevertheless,
the methods which we present in the current paper for this special case are
applicable in much bigger generality and in a forthcoming full version of this
paper \cite{Wojtyniak2021} we discuss the applications to maps with higher
genera.






%In \cref{sec:factorizations,sec:trees} we will introduce some necessary
%definitions and we will come back to the discussion of Stanley character
%polynomials in \cref{sec:top} below.


\pagebreak


\subsection{Stanley trees}
\label{sec:trees}

\begin{figure}
    \centering {\includegraphics[clip, trim=1.7cm 1.3cm 5.5cm 2.2cm,angle=-90, width=0.55\textwidth]{plot1}}
    
\caption{An example of a Stanley tree of type $(3,5,3)$. The circled numbers
    indicate the labels of the black verices. The black numbers indicate the
    labels of the edges. The colors (blue for $1$, red for $2$, green for $3$) indicate the values of the function $f$ on white vertices.}
\label{fig:plot1}
\end{figure}


Let $T$ be a \emph{bicolored} plane tree, i.e., a plane tree with each vertex
painted black or white and with edges connecting the vertices of opposite
colors. We assume that the tree has $k$ edges labelled with the numbers
$1,\dots,k$. We also assume that it has $n$ black vertices labelled with the
numbers $1,\dots,n$. We define the function $f$ which to each white vertex
associates the maximum of the labels of its black neighbors. We will say that
$T$ is a \emph{Stanley tree of type}
    \[ \Big( \big| f^{-1}(1) \big|, \dots, \big|f^{-1}(n) \big| \Big), \]
i.e., the type gives the information about the number of the white vertices
for which the function $f$ takes a specified value.
\cref{fig:plot1} gives an example of a Stanley tree of type $(3,5,3)$.
By $\mathcal{T}_{b_1,\dots,b_n}$ we denote the set of Stanley trees of type $(b_1,\dots,b_n)$.



\subsection{Coefficients of top-degree $\mathbf{p}$-squarefree monomials}

It turns out that in the analysis of Stanley polynomials it is enough to
restrict attention to \emph{$\mathbf{p}$-squarefree monomials}, i.e., the monomials of
the form $p_1 \cdots p_n q_1^{b_1} \cdots q_n^{b_n}$, see \cite{Dolega2010}.


\begin{lem}
    For all integers $b_1,\dots,b_n\geq 0$ such that $b_1+\cdots+b_n+n=k+1$ the
$\mathbf{p}$-squarefree coefficient of the Stanley character polynomial is given
by
\[\left[p_1 \cdots p_n q_1^{b_1} \cdots q_n^{b_n} \right]   \Ch_k\big(\mathbf{p}\times \mathbf{q}  \big) = \pm \frac{1}{(k-1)!} \left| \mathcal{T}_{b_1,\dots,b_n} \right|. \]
%is equal to the number of Stanley trees of type $(b_1,\dots,b_n)$.
\end{lem}
In order to be concise we will not discuss the sign on the right-hand side. The
above lemma is a special case of a general formula conjectured by Stanley
\cite{Stanley2006} and proved by F\'eray \cite{Feray2010} and therefore we refer
to it as Stanley--F\'eray character formula.


%\todo{Rattan \cite{Rattan2007}}


%
%\subsection{Top-degree coefficients of Stanley polynomials}
%\label{sec:top}





\subsection{Minimal factorizations of long cycles}
\label{sec:factorizations}

We fix an integer $k\geq 1$ and denote by $\Sym{k}$ the corresponding
symmetric group. We say that a permutation $\pi\in\Sym{k}$ is a \emph{cycle of length
    $\ell$} if it is of the form $\pi=(a_1,\dots,a_\ell)$.

%Let $\delta\in\Sym{k}$ be an arbitrary cycle of length $k$ and
Let $a_1,\dots ,a_n\geq 2$ be integers. We say that a tuple
$(\sigma_1,\dots,\sigma_n)$ is a \emph{factorization of a long cycle of type
    $(a_1,\dots,a_n)$} if $\sigma_1,\dots,\sigma_n\in\Sym{k}$ are such that the
product $\sigma_1 \cdots \sigma_n$ is a cycle of length $k$ and $\sigma_i$ is a
cycle of length $a_i$ for each choice of $i\in\{1,\dots,n\}$. %This exists only
% if
%$\sum_{i=1}^{n}(a_i-1) \geq k-1$, and the factorization is called minimal in
%case of equality.
In the current paper we concentrate on \emph{minimal factorizations} which
correspond to the special case when
\[ \sum_{i=1}^{n}(a_i-1) = k-1. \]
%By $\mathcal{C}_{a_1,\dots
%    ,a_n}(\delta)$ we denote the set of minimal factorizations of type
%$(a_1,\dots ,a_n)$ of the cycle $\delta\in\Sym{k}$ of length $k$. 
By $\mathcal{C}_{a_1,\dots ,a_n}$ we
denote the set of such minimal factorizations of a long cycle of type $(a_1,\dots ,a_n)$.

%\todo{work in progress here}

%
%Let $n\geq 1$ and $b_1,\dots ,b_n, k \in \mathbb{N}_+$. By $t^k_{b_1,b_2,\dots
%    ,b_n}$ we denote a plane tree without root with labeled $k$ edges from $1$ to
%$k$. This plane tree has $n$ black vertices labeled and $b_1+\dots +b_n$ white
%vertices. Each edge connects black with a white vertex. Plane tree $t$ has the
%property that after coloring each black vertex a different color and after
%coloring each white vertex to the color of the black vertex being the maximum
%of the neighbors of the black vertices, we will get $b_i$ of white vertices
%painted the color of the $i-th$ black vertex. By $T^k_{[{b_1,b_2,\dots
%        ,b_n}]}$ we denote set of all plane trees $t^k_{b_1,b_2,\dots ,b_n}$. Easy to
%see that for $k\neq \sum_{i}^{n}{b_i} +(n-1)$ our set $T^k_{[{b_1,b_2,\dots
%        ,b_n}]}$ is empty.




%\subsection{The problem}
%
%Our task is to count plane trees about almost all properties of trees in the set $T^k_{[{b_1,b_2,\dots ,b_n}]}$. The only differences are that our plane trees now have no edge labels and have a root. Let us denote the number of such flat trees by $[{b_1,b_2,\dots ,b_n}]R_{k+1}$.

\section{The main result: bijection between Stanley trees and minimal factorizations of long cycles}
\label{sec:algorithm}



\begin{thm}
    \label{thm:thm1}
Let $n\geq 2$ and $b_1,\dots,b_n\geq 1$ be integers.
We define the integers $a_1,\dots,a_n$ by
\[ a_i = \begin{cases} 
              b_i+1 & \text{if } i \in \{1,n\}, \\
              b_i+2 & \text{otherwise}.
           \end{cases} \] 
Then the algorithm presented below gives a bijection between the set  $\mathcal{C}_{a_1,\dots ,a_n}$ and the set $\mathcal{T}_{b_1,\dots ,b_n}$.
\end{thm}


\subsection{The first step: from a factorization to a tree with repeated edge labels}
\label{sec:first}

In the first step of our algorithm to a given minimal
factorization $(\sigma_1,\dots,\sigma_n)\in \mathcal{C}_{a_1,\dots ,a_n}$ we will associate a bicolored plane tree $T_1$ with
labelled black vertices and labelled edges. The remaining part of the current
section is devoted to the details of this construction.

\subsubsection{The tree $T_0$}
We start by creating a tree $T_0$ with $n$ black vertices labelled $1,\dots,n$ and
with $k$ white vertices labelled $1,\dots,k$. Each black vertex $i$
corresponds to the cycle $\sigma_i=(\sigma_{i,1}, \dots, \sigma_{i,a_i})$ and
so we connect the black vertex $i$ with the white vertices $\sigma_{i,1},
\dots, \sigma_{i,a_i}$. 
%All edges surrounding the white vertex with the label
%$j\in\{1,\dots,k\}$ are also labelled by the label~$j$; note that the edges of
%labels may repeat.

In order to give this tree  the structure of a \emph{plane tree} we need to
specify the cyclic order of the edges around each vertex. We declare that
going clockwise around the black vertex~$i$ the cyclic order of the labels of the white neighbours
should correspond to the cyclic order $\sigma_{i,1}, \dots, \sigma_{i,a_i}$.
The cyclic order around the white vertices is more involved and we present it in
the following.

\medskip



The path between the two black vertices with the labels $1$ and $n$ will be
called \emph{the spine}; on \cref{subfig:ex1} it is drawn in red. There will be
two separate rules which determine the cyclic order of the edges around a given
white vertex, depending whether the vertex belongs to the spine or not.

%\begin{enumerate}
%\item For any $i=1,\dots n$ we draw black vertex with label $i$ and with $a_i$
%tentacles (single edges exiting a black vertex terminating in a white vertex),
%which we label with the numbers from the $ith$ cycle clockwise. This object we
%will call a bush.

%\item We look for and combine the minimum number of bushes such that if I
%equate white vertices (combining them) with the same edge labels, we get the
%path from $1$ to $n$. From now on, we will call the shortest path (obviously
%without tentacles) the spine.





For each white vertex which is \emph{not} on the spine we declare that going
counterclockwise around it, the labels of its black neighbors should be arranged in
the increasing way (for example, the neighbors of the white vertex $6$ on
\cref{subfig:ex1} listed in the counterclockwise order are $3,4,6$).



For each white vertex $v$ which belongs to the spine there are exactly two black neighbors
which belong to the spine; we denote their labels by $x_1$ and $x_2$ with
$x_1<x_2$. Going counterclockwise around $v$, all non-spine edges should be
inserted after $x_1$ and before $x_2$. Their order is determined by the
requirement that---after neglecting the vertex $x_2$---the cyclic counterclockwise
order of the remaining vertices should be increasing. For example, for the
white vertex $1$ on \cref{subfig:ex1} we have $x_1=7$, $x_2=11$ and the
counterclockwise cyclic order of the non-$x_2$ black neighbors is $4,7,13$.


%All non-spine edges of $v$ will be 
% and we can have more
%black vertices with the same edge label. So we put edges with the same labels
%in only one side of our spine going black vertices ascending counterclockwise
%from $\min(x_1,x_2)$ to $\max(x_1,x_2)$, but we imagine that our
%$\max(x_1,x_2)$ is equal to $\min(x_1,x_2)$.
%\end{enumerate}

%\begin{figure}
%\centering 
%  {\includegraphics[clip, trim=1.7cm 1.3cm 1.4cm 2.2cm,angle=-90,width=0.5\textwidth]{plot2}}
%\caption{The output of the first step of the algorithm applied to the minimal
%    factorization \eqref{eq:factorization}. The spine is drawn in red.} \label{fig:plot2}
%\end{figure}

\medskip

%For example, \cref{fig:plot2} gives the output of the first step of our algorithm 
%applied to the minimal factorization $(\sigma_1,\dots,\sigma_{10})$ with
%\begin{multline}
%    \label{eq:factorization}
%   \sigma_1=(1,14), \quad 
%   \sigma_2=(2,6,7), \quad
%   \sigma_3=(2,9,8),\quad
%   \sigma_4=(2,3,17), \quad
%   \sigma_5=(9,12,13), \\
%   \sigma_6=(9,10,11), \quad
%   \sigma_7=(2,4,5), \quad
%   \sigma_8=(1,15,2), \quad
%   \sigma_9=(3,19,18), \quad
%   \sigma_{10}=(3,16).
%\end{multline}
 





\begin{figure}
    \centering
    \subfloat[]{\label{subfig:ex1}
        \includegraphics[width=0.4\textwidth]{example1}}
    \quad
    \subfloat[]{\label{subfig:ex2}
        \includegraphics[width=0.4\textwidth]{example2}}
    \caption{\protect\subref{subfig:ex1} The output $T_0$ of the first step of the algorithm applied to the minimal
        factorization \eqref{eq:example}. The spine is drawn in red. \protect\subref{subfig:ex2} The tree $T_1$ which is the starting point of the second step of our algorithm.}    
    \label{fig:ex12}
\end{figure}


For example, \cref{subfig:ex1} gives the tree $T_0$ which corresponds to the minimal factorization $(\sigma_1,\dots,\sigma_{14})\in
\mathcal{C}_{2,3^{12},2}$ with
\begin{multline}
    \label{eq:example}
    \sigma_1=(2,3), \quad 
    \sigma_2=(13,14,15), \quad
    \sigma_3=(6,10,9),\quad
    \sigma_4=(1,26,6), \quad
    \sigma_5=(11,12,15), \\
    \sigma_6=(6,7,8), \quad
    \sigma_7=(1,15,16) \quad
    \sigma_8=(21,24,27), \quad
    \sigma_9=(22,25,23), \quad
    \sigma_{10}=(16,18,19), \\
    \sigma_{11}=(2,1,20),\quad
    \sigma_{12}=(20,21,22), \quad
    \sigma_{13}=(1,4,5), \quad
    \sigma_{14}=(16,17).
\end{multline}

The product $\sigma=\sigma_1\dots\sigma_{14}$ is a cycle of length $27$ and
\begin{multline}
\sigma=(11,12,13,14,15,16,17,18,19,26,10,9,6,7,8,1,4,5,20,24,27,21,25,23,22,3,2).
\end{multline}


\subsubsection{Information about the initial tree $T_0$}

In  the current section we will define certain sets and functions which
describe the shape of the initial tree $T_0$. In the language of programmers: we will create variables
$B_x$, $\Root_x$, $S_B$, $S_E$ which will not change their values during the
execution of the algorithm.

\medskip

%We recall that the path in $T_0$ between the two black vertices with the labels
%$1$ and $n$ is called \emph{the spine}.

For each white vertex label $x\in\{1,\dots,k\}$ we denote by
$B_x\subseteq\{1,\dots,n\}$ the set of labels of its black neighbors. We can
orient the non-spine edges of the tree so that the arrows point towards the
spine. For a white non-spine vertex label $x\in\{1,\dots,k\}$ we denote by
$\Root_x\in\{1,\dots,n\}$ the label of the black neighbor of the white vertex
$x$ which is in the direction of the spine. By $S_B\subseteq\{1,\dots,n\}$ we denote the set of the
labels of black spine vertices. By $S_E\subseteq\{1,\dots,k\}$ we denote the set of labels of white
spine vertices. 

%\todo[inline]{Tradycyjnie, czy można zastąpić \cref{fig:plot2} przez \cref{subfig:ex2}?}
%For example, on \cref{fig:plot2} we have $B_3=\{4,9,10\}$,
%$B_9=\{3,5,6\}$, $\Root_9=3$, and $S_B=\{1,8,4,10\}$, $S_E=\{1,2,3\}$.

%\todo{trailing text missing}

For the example from \cref{subfig:ex1} we have:
%read the necessary informations. For each the label of white vertex $i$ with degree $d$ (where $d\geq 2$) we designate set $B_i$. If the given white vertex belongs outside spine we also designate $\Root_i$. We also define sets $S_B$ and $S_E$.
\begin{multline}
    \label{eq:step}
    B_1=\{4,7,11,13\}, \quad
    B_2=\{1,11\}, \quad 
    B_6=\{3,4,6\},  \quad  
    B_{16}=\{7,14,10\},
    \\
    B_{15}=\{2,5,7\}, \quad 
    B_{20}=\{11,12\}, \quad
    B_{22}=\{9,12\},\quad
    B_{21}=\{8,12\}, \\
    \Root_6=4, \quad
    \Root_{15}=7, \quad
    \Root_{20}=11, \quad
    \Root_{22}=12, \quad
    \Root_{21}=12, \\
    S_B=\{1,7,11,14\}, \quad 
    S_E=\{1,2,16\}.
\end{multline}

%\todo{work in progress ahead}

Let $L$ be the sequence of labels of the vertices which are white, non-spine,
and non-leaf, arranged in the following order. We start from the unique edge
connecting the black vertex labelled $1$ with a white spine vertex from the
set $S_E$. Then we traverse the tree holding it with the right hand and
order the vertices in $L$ according to the time of the first visit
(``depth-first search'').
For example, for the tree $T_0$ shown on \cref{subfig:ex1} we have $L=(6,15,20,21,22)$. 

\medskip

We denote by $T_1$ the tree $T_0$ in which each edge is labelled by its white
endpoint and then all labels of the white vertices are removed, see
\cref{subfig:ex2}. The tree $T_1$ is the output of the first step of the
algorithm.


\subsection{The second step: from a tree with repeated edge labels to a tree with unique edge labels}
\label{sec:second}

The starting point of the second step of our algorithm is the
bicolored plane tree $T_1$ with black vertices labelled $1,\dots,n$ and with edges
labelled with the numbers $1,\dots,k$; note that the edge labels are repeated.
Our goal in this second step of the algorithm is to transform the tree so that
the edge labels are not repeated.
As an auxiliary tool we will use two operations, called \emph{jump} and
\emph{exchange}.




\medskip

%Now, we would like to plane tree without repeated edges and with the corresponding numbers $b_i$. To do this, we need two operations \textit{exchange} and \textit{jump}, which we see in Figure \ref{fig:plot34}.

\begin{figure}
    \centering
    \subfloat[]{\label{subfig:jumpA}
        {\includegraphics[angle=-90,width=0.4\textwidth]{jump1.pdf}}  }
    \quad
    \subfloat[]{\label{subfig:jumpB}
        {\includegraphics[angle=-90,width=0.4\textwidth]{jump2.pdf}}}
    \caption{\protect\subref{subfig:jumpA} The initial configuration of the tree.
    \protect\subref{subfig:jumpB} The output of $\Jump_{x,y}$.}
    \label{fig:jump}
\end{figure}


\subsubsection{The building blocks of the second step: jump $\Jump_{x,y}$}
\textbf{The input of $\Jump_{x,y}$.}
The operation $\Jump_{x,y}$ takes as an input a bicolored tree $T$ together with a choice of two
of black vertices $x$, $y$ which are assumed to be at the distance $2$, see
\cref{subfig:jumpA}. We denote their common white neightbor by $v_1$. 

We denote by $j$ the black neighbor of $v_1$ which---going clockwise around
the vertex $v_1$---is immediately after $y$ (note that it might happen that
$j=x$). We also assume that the two edges which form the path between $y$ and
$j$ are labelled by the same symbol denoted by $E_1$,  see
\cref{subfig:jumpA}.


%We also assume that the two edges which form the path between $x$ and $y$ are labelled
%by the same symbol denoted by $E_1$ and that going clockwise around the
%vertex $v_1$ there are no black neighbors after $y$ and before $x$. 

We also assume that the black vertex $y$ has degree at least $3$; we denote the edges
around the vertex $y$ by $E_1,\dots, E_d$ (going clockwise, starting from the
edge $E_1$) with $d\geq 3$. We denote the white endpoint of the edge $E_i$ by
$v_i$.

\medskip

\textbf{The output of $\Jump_{x,y}$ is defined as follows.} We remove the three
edges connecting $y$ with $v_1,v_2,v_3$. We create a new white vertex denoted
$w$ and we connect it to the vertex $j$ by a new edge which we label $E_2$.
More specifically, going clockwise around $j$ the newly created edge
$E_2$ is immediately after the edge $E_1$.

We also connect the vertex $w$ to the vertex $y$ by a new edge which we label $E_3$.
The position of the edge $E_3$ in the vertex $y$ replaces the three edges which were removed from $y$.

We merge the vertices $v_2$ and $v_3$ to the vertex $w$. More specifically,
the clockwise cyclic order of the edges around the vertex $w$ is as follows:
the edge $E_2$, then the edges from the vertex $V_3$ (listed in the clockwise
order starting from the removed edge $E_3$; on \cref{fig:jump} these edges are
marked red), the edge $E_3$, then the edges from the vertex $v_2$ (listed in
the clockwise order starting from the removed edge $E_2$; on \cref{fig:jump}
these edges are marked blue), see \cref{subfig:jumpB}.


\medskip


\begin{figure}
    \centering
    \subfloat[]{\label{subfig:exA}
                {\includegraphics[clip,trim=1.5cm 0cm 1.9cm 3.5cm,angle=-90,width=0.4\textwidth]{exchange1.pdf}}  
    }
    \quad
    \subfloat[]{\label{subfig:exB}
                {\includegraphics[clip,trim=0.9cm 0cm 2.5cm 3.5cm,angle=-90, width=0.4\textwidth]{exchange2.pdf}}
    }
    \caption{\protect\subref{subfig:exA} The initial configuration of the tree.
        \protect\subref{subfig:exB} The output of $\Exchange_{x,y}$.}
    \label{fig:ex}
\end{figure}


%\begin{figure}
%    \centering
%    %\subfloat[Jump.]{\label{plot3}
%    %\fbox{\includegraphics[clip, trim=0cm 1.3cm 0cm 1cm,angle=-90, width=0.4\textwidth]{plot3}}  }
%    %\quad
%    \subfloat[Exchange.]{\label{plot4}
%        \includegraphics[angle=-90, width=0.4\textwidth]{plot4}}
%    \caption{Operations thanks to which we obtain trees from the set $T^k_{[{b_1,b_2,\dots ,b_n}]}$.}
%    \label{fig:plot34}
%\end{figure}

\subsubsection{The building blocks of the second step: exchange $\Exchange_{x,y}$}

\textbf{The input of $\Exchange_{x,y}$.}
The operation $\Exchange_{x,y}$ takes as an input a bicolored tree $T$ together with a choice of two
of black vertices $x$, $y$ which are assumed to be at the distance $2$, see
\cref{subfig:exA}. We denote their common white neighbor by $v_1$. 
%We also assume that the two edges which form the path between $x$ and $y$ are labelled
%by the same symbol denoted by $E_1$. 
We also assume that the black vertex $y$ has degree at least $2$; we denote the edges
around the vertex $y$ by $E_1,\dots, E_d$ (going clockwise, starting from the
edge $E_1$) with $d\geq 2$. We denote the white endpoint of the edge $E_i$ by
$v_i$.

\medskip

\textbf{The output of $\Exchange_{x,y}$ is defined as follows.} We remove the
edge between $y$ and $v_2$. The label of the edge between $v_1$ and $y$ is
changed to $E_2$. Then we merge the vertex $v_2$ with the vertex $v_1$ in such
a way that going clockwise around $v_1$ the newly attached edges are
immediately before the edge $E_2$ (these edges are marked blue on
\cref{fig:ex}). 



\medskip





%Using these operations, we reduce repeating edges and we can easily obtain plane tree from the set $T^k_{[{b_1,b_2,\dots ,b_n}]}$.\\






%\todo[inline]{??? If edge labels around the while vertex are repeated, we assume that white vertex belong to every black vertex having this edge. 
%}



\subsubsection{Spine treatment}




For each $i\in S_E$ we apply the following procedure (the final output will not
depend on the order in which we choose the elements of $S_E$). Since the spine
in $T_0$ is a path, the intersection $B_i\cap S_B$ corresponds to the labels of
the two black spine neighbors of the white vertex $i$ in the tree $T_0$. We denote $B_i\cap
S_B=\{x,y_1\}$ with  $x<y_1$. 
We run the following loop over $y\in B_i\setminus\{x\}$ (with the ascending order). If  $y=y_1$ or
$y<x$ then we apply $\Exchange_{x,y}$;  otherwise we apply $\Jump_{x,y}$.


\medskip







\begin{example}
We continue the example from \cref{subfig:ex2}. We recall that $S_E=\{1,2,16\}$.


%\begin{figure}
%    \centering
%    \subfloat[]{\label{subfig:ex1a}
%        \includegraphics[width=0.4\textwidth]{example1}}
%    \quad
%    \subfloat[]{\label{subfig:ex2a}
%        \includegraphics[width=0.4\textwidth]{example2}}
%    \caption{\protect\subref{subfig:ex1} The output $T_0$ of the first step of the algorithm applied to the minimal
%        factorization \eqref{eq:example}. The spine is drawn in red. \protect\subref{subfig:ex2a} The tree $T_1$ which is the starting point of the second step of our algorithm.}    
%    \label{fig:ex12a}
%\end{figure}

\begin{figure}
    \centering
    \subfloat[]{\label{subfig:ex3}
        \includegraphics[width=0.4\textwidth]{example3}}
    \quad
    \subfloat[]{\label{subfig:ex4}
        \includegraphics[width=0.4\textwidth]{example4}}
    \caption{
    \protect\subref{subfig:ex3} The output of $\Exchange_{1,11}$. \protect\subref{subfig:ex4} The output of $\Exchange_{7,4}$.}
    \label{fig:ex34}
\end{figure}

%The initial configuration of the tree. 
    
    
For $i=2$ we have $x=1$ and $y_1=11$. Since $B_2\setminus \{1\}=\{11\}$, the
internal loop is applied once with $y=11$. As a result we apply $\Exchange_{1,11}$, see
\cref{subfig:ex3}.


\begin{figure}
    \centering
    \subfloat[]{\label{subfig:ex5}
        \includegraphics[width=0.4\textwidth]{example5}}
    \quad
    \subfloat[]{\label{subfig:ex6}
        \includegraphics[width=0.4\textwidth]{example6}}
    \caption{
    \protect\subref{subfig:ex5} The output of $\Exchange_{7,11}$. \protect\subref{subfig:ex6} The output of $\Jump_{7,13}$.}
    \label{fig:ex56}
\end{figure}


For $i=1$ we have $x=7$ and $y_1=11$.
Since $B_1\setminus \{7\}=\{4,11,13\}$ the loop runs over:
$\bullet$ $y=4$
and  we apply $\Exchange_{7,4}$,
see \cref{subfig:ex4};
$\bullet$ $y=11$ and we apply $\Exchange_{7,11}$, see \cref{subfig:ex5};
$\bullet$~$y=13$ and we apply $\Jump_{7,13}$, see \cref{subfig:ex6}.


\begin{figure}
    \centering
    \subfloat[]{\label{subfig:ex7}
        \includegraphics[width=0.4\textwidth]{example7}}
    \quad
    \subfloat[]{\label{subfig:ex8}
        \includegraphics[width=0.4\textwidth]{example8}}
    \caption{
    \protect\subref{subfig:ex7} The output of $\Jump_{7,10}$. \protect\subref{subfig:ex8} The output of $\Exchange_{7,14}$.}
    \label{fig:ex78}  
\end{figure}

For $i=16$ we have $x=7$ and $y_1=14$. Since $B_{16}\setminus \{7\}=\{10,14\}$ the loop runs over:
$\bullet$ $y=10$ and we apply $\Jump_{7,10}$, see \cref{subfig:ex7};
$\bullet$ $y=14$ and we apply $\Exchange_{7,14}$, see \cref{subfig:ex8}.

\end{example}

%For this
%edge $i$ in black vertex with label $y_1$ we use \textit{exchange} and
%for every black vertex with label $y_2\in V$ we use: \textit{exchange} if
%$y_2<x$ or \textit{jump} if $y_2>x$. We fix the edges by going ascending along the labels of the black %vertices.
%We notice that after every operation on spine black vertices on spine lost one white vertex, while
%black vertices outside spine lost two vertices. After completing the treatment
%of the spine almost all black vertices which appeared lost two white vertices
%(except black vertex with label 1 or n which lost only one white vertices). So
%we see that from now on none of the black vertex can lose any white vertex.

\subsubsection{Rib treatment}

For each successive edge label $i$ from the set $L$ we apply the following
procedure (the final output depends on the order in which we choose the label of edges).

We run the following loop over $y\in B_i\setminus \{ \Root_i \}$ 
(with the ascending order).
If $y<\Root_i$ we apply $\Exchange_{\Root_i,y}$;
otherwise we apply  $\Jump_{\Root_i,y}$.

\medskip


\begin{example}

We continue the example from \cref{subfig:ex8}. We recall that $L=(6,15,20,21,22)$.



%FIGURE 9
\begin{figure}
    \centering
    \subfloat{\label{subfig:ex9}
        \includegraphics[width=0.4\textwidth]{example9}}
    \quad
    \subfloat{\label{subfig:ex10}
        \includegraphics[width=0.4\textwidth]{example10}}
    \caption{
    \protect\subref{subfig:ex9} The output of $\Exchange_{4,3}$ and $\Jump_{4,6}$. \protect\subref{subfig:ex10} The output of $\Exchange_{7,2}$ and $\Exchange_{7,5}$.}
    \label{fig:ex910}
%\end{figure}
%
%\begin{figure}
    \centering
    \subfloat{\label{subfig:ex11}
        \includegraphics[width=0.4\textwidth]{example11}}
    \quad
    \subfloat{\label{subfig:ex12}
        \includegraphics[width=0.4\textwidth]{example12}}
    \caption{
        \protect\subref{subfig:ex11} The output of $\Jump_{11,12}$. \protect\subref{subfig:ex12} The output of $\Exchange_{12,8}$.}
    \label{fig:ex1112}
%\end{figure}
%
%\begin{figure}
    \centering
    \subfloat{\label{subfig:ex13}
        \includegraphics[width=0.4\textwidth]{example13}}
    \quad
    \subfloat{\label{subfig:ex14}
        \includegraphics[width=0.4\textwidth]{example14}}
    \caption{
        \protect\subref{subfig:ex13} The output of $\Exchange_{12,9}$. \protect\subref{subfig:ex14} The output of our algorithm applied to the minimal factorization \eqref{eq:example}.}
    \label{fig:ex1314}
\end{figure}

For $i=6$ we have $\Root_6=4$.
Since $B_6\setminus \{4\}=\{3,6\}$ the loop runs over:
$\bullet$ $y=3$
and  we apply $\Exchange_{4,3}$, see \cref{subfig:ex9};
$\bullet$ $y=6$ and we apply $\Jump_{4,6}$, see \cref{subfig:ex9}.

For $i=15$ we have $\Root_{15}=7$.
Since $B_{15}\setminus \{7\}=\{2,5\}$ the loop runs over:
$\bullet$ $y=2$
and  we apply $\Exchange_{7,2}$, see \cref{subfig:ex10};
$\bullet$ $y=5$ and we apply $\Exchange_{7,5}$, see \cref{subfig:ex10}.





For $i=20$ we have $\Root_{20}=11$. Since $B_{20}\setminus \{11\}=\{12\}$, the
internal loop is applied once with $y=12$. As a result we apply $\Jump_{11,12}$, see
\cref{subfig:ex11}.

For $i=21$ we have $\Root_{21}=12$. Since $B_{21}\setminus \{12\}=\{8\}$, the
internal loop is applied once with $y=8$. As a result we apply $\Exchange_{12,8}$, see
\cref{subfig:ex12}.




For $i=22$ we have $\Root_{22}=12$. Since $B_{22}\setminus \{12\}=\{9\}$, the
internal loop is applied once with $y=9$. As a result we apply $\Exchange_{12,9}$, see
\cref{subfig:ex13}.

\cref{subfig:ex14} gives the output of our algorithm applied to
the minimal factorization \eqref{eq:example}. The result is a Stanley tree of type $(1^{14})$.

\end{example}

%We look which black
%vertex $x$ comes out of spine and we look for other black vertices have the
%same edge label (let is denote this set as $Z$). 
%We go ascending over the labels of the black vertices from the set $V$ and we apply the appropriate %operation for them. If the given black vertex $y$ belongs to the set $\{v\in V:v<x\}$ we use 
%$\Exchange_{x,y}$ otherwise we use  $\Jump_{x,y}$.


%For this edge $i$ in every black
%vertex with label $y\in V$ we use: \textit{exchange} if $y<x$ or
%\textit{jump} if $y>x$. We fix the edges by going ascending along the labels of the black vertices. 
%We notice that number of white vertices in black
%vertex labeled $x$ has not change and in the vertices from the set $V$
%decreased by $2$.\\ 

%\subsection{Proof of \cref{thm:thm1}}

\medskip

Due to space restrictions, the explicit construction of the inverse of the
bijection from \crefrange{sec:first}{sec:second}, as well as the proof of its
correctness, is postponed to the forthcoming paper \cite{Wojtyniak2021}.


\acknowledgements{I thank Piotr Śniady for suggestions during the
    planning and development of this research work. 
    Research supported by Grant 2017/26/A/ST1/00189 of Narodowe Centrum Nauki.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography


\end{document}

