%% 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]{FPSAC2024}
\articlenumber{54}
%% 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}
\newtheorem{lem}{Lemma}

\newtheorem{theorem}{Theorem}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\vanish}[1]{}
\newcommand{\id}{\operatorname{id}}
\newcommand{\rank}{\operatorname{rk}}

%% define your title in the usual way
\title[A Whitney polynomial for hypermaps]{A Whitney polynomial for hypermaps}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Robert
  Cori\thanks{\href{mailto:cori@labri.fr}{cori@labri.fr}}\addressmark{1}
  \and G\'abor
  Hetyei\thanks{\href{mailto:ghetyei@charlotte.edu}{ghetyei@charlotte.edu}. G.\ Hetyei
    was partially supported by grant \#514648 from the Simons Foundation.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Labri, Universit\'e Bordeaux 1, 33405 Talence Cedex, France\\ \addressmark{2}Department of Mathematics and Statistics,
  UNC Charlotte, Charlotte NC 28223-0001}

%% 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{We introduce a Whitney polynomial for hypermaps and use
it to generalize the results connecting the circuit partition
polynomial to the Martin polynomial and the results on several graph
invariants.}

%% put your French abstract here, or comment this out if you don't have one
\resume{Nous introduisons un polyn\^ome de Whitney pour les hypercartes et
  nous l'utilisons pour g\'en\'eraliser les r\'esultats liant le
  polyn\^ome des partitions de circuit aux polyn\^omes de Martin et les
  r\'esultats de plusieurs invariants de graphes.}  

%% put your keywords here, or comment this out if you don't have them yet
\keywords{set partitions, noncrossing partitions, genus of a hypermap,
  Tutte polynomial, Whitney polynomial, medial map, circuit partition,
  characteristic polynomial, chromatic polynomial, flow polynomial}

%% 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; i.e., [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}
\addbibresource{ghetyei.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*{Introduction}

The Tutte polynomial is a key invariant of graph theory, which has been
generalized to matroids, polymatroids, signed graphs and hypergraphs in
many ways. A partial list of recent topological graph and hypergraph
generalizations includes~\cite{Bernardi-embeddings, Bernardi-sandpile,
  Bernardi-Kalman-Postnikov, Kalman, Kalman-Tothmeresz}. 

The work we present~\cite{Cori-Hetyei2} generalizes a variant of the Tutte
polynomial, the Whitney rank generating function to {\em hypermaps}
which encode hypergraphs topologically embedded in a surface. This
polynomial may be recursively computed using a generalized
deletion-contraction formula, and many of the famous special
substitutions (for instance, counting spanning subsets of edges, or
trees contained in the a graph) may be easily generalized to this
setting. Our approach seems to be most amenable to generalize results on
the Eulerian circuit partition polynomials, but we also have a promising
generalization of the characteristic polynomial. This last
generalization (involving the M\"obius function of the noncrossing
partition lattice) also indicates that, for hypermaps many invariants
cannot be obtained by a simple negative substitution into some
generalized Tutte polynomial. For similar reasons, a generalized Whitney
polynomial seems to work better than a generalized Tutte polynomial, and
the difference between the two should not be thought of as a mere linear
shift.   

Our work is organized as follows. After the Preliminaries, the key
definition of our Whitney polynomial is contained in
Section~\ref{sec:whitney}. We may generalize the
well-known deletion-contraction recurrence formulas from graphs to this
setting. This
section also contains several important specializations and 
the proof of the fact that taking the dual of a planar hypermap amounts
to swapping the two variables in its Whitney polynomial.

We introduce the directed medial map of a hypermap in
Section~\ref{sec:medial}. Every directed Eulerian graph arises as the
directed medial map of a collection of hypermaps. In this section and in
Section~\ref{sec:medialc}, we present analogues and generalizations of several
results of Arratia, Bollob\'as, Ellis-Monaghan, Martin and
Sorkin~\cite{Arratia-Bollobas,Bollobas-cp,Ellis-Monaghan-mp,Ellis-Monaghan-mpmisc,Ellis-Monaghan-cpp,Ellis-Monaghan-exploring,Martin-Thesis,Martin}
on the circuit partition polynomials of Eulerian digraphs and the medial
graph of a plane graph. 

The visually most appealing part of our work is in
Section~\ref{sec:visual}. Here we extend the circuit partition approach
to a refined count which keeps track of circuits bounding external
(``wet'') and internal (``dry'') faces and define a process that allows
the computation of the Whitney polynomial of a planar hypermap using
paper and a scissor. 

Finally, in Section~\ref{sec:charpoly} we introduce a characteristic
polynomial for hypermaps which generalizes the characteristic polynomial
of a map, as well as of a graded poset. We show that for hypermaps whose
hyperedges have length at most three, this variant of the characteristic
polynomial is still a chromatic polynomial, counting the admissible
colorings of the vertices. 

\section{Preliminaries}
\label{sec:prelim}

A {\em hypermap} is a pair of permutations $(\sigma,\alpha)$
acting on the same finite set of labels, generating a transitive permutation
group. It encodes a hypergraph, topologically embedded in
a surface. Fig.~\ref{fig:hypermap} represents the planar
hypermap $(\sigma,\alpha)$ for $\sigma=(1,4)(2,5)(3)$ and
$\alpha=(1,2,3)(4,5)$. The cycles of $\sigma$ are the {\em
  vertices}, the cycles of $\alpha$ are the {\em
  hyperedges} and the cycles of
$\alpha^{-1}\sigma=(1,5)(2,4,3)$ are the {\em
  faces}. A hypermap is a {\em map} if the 
length of each cycle in $\alpha$ is at most $2$.
\begin{figure}[h]
%90%  
\begin{center}
\input{hypermap2.pdf_t}
\end{center}
\caption{The hypermap $(\sigma,\alpha)$}
\label{fig:hypermap} 
\end{figure}
In terms of the function $z(\pi)$, counting the cycles of
the permutation $\pi$, the {\em genus} $g(\sigma,\alpha)$ of a hypermap
may be computed using the equation $n + 2 -2g(\sigma,\alpha) = z(\sigma)
+ z(\alpha) + z(\alpha^{-1} 
\sigma)$ due to Jacques~\cite{Jacques}. 
The present work was motivated by the study of the {\em spanning
  hypertrees of a hypermap}, initiated in~\cite{Cori-hrec, Cori-Machi,
  Cori-Penaud, Machi} and continued in~\cite{Cori-Hetyei}. A 
hypermap $(\sigma,\alpha)$ is {\em unicellular} if it
has only one face, and it is a {\em hypertree} if it also has 
genus zero. A permutation
$\beta$ is a {\em refinement} of a permutation $\alpha$ if $\beta$ is 
obtained by replacing each cycle $\alpha_i$ of $\alpha$ by a permutation
$\beta_i$ acting on the same set of points in such a way that
$g(\alpha_i,\beta_i)=0$. We will use the notation $\beta\leq \alpha$ to
denote that $\beta$ is a refinement of 
$\alpha$. A hypermap $(\sigma,\beta)$ {\em spans}
the hypermap $(\sigma,\alpha)$ if $\beta$ is a refinement of
$\alpha$. A {\em hyperdeletion} is the operation of replacing
a hypermap $(\sigma,\alpha)$ with the hypermap 
$(\sigma,\alpha\delta)$ where $\delta=(i,j)$ is a transposition
{\em disconnecting $\alpha$}, that is, $i$ and $j$ must belong to the
same cycle. This time we will work with {\em collections of
  hypermaps} (defined in Section~\ref{sec:whitney}) hence we may perform
hyperdeletions even if the  permutation group generated by the pair
$(\sigma,\alpha\delta)$ has more orbits than the one generated by the
pair $(\sigma,\alpha)$. For maps the deletion operation corresponds to
deleting an edge $(i,j)$. A {\em hypercontraction} is the operation of
replacing a hypermap $(\sigma,\alpha)$ with the hypermap
$(\gamma\sigma,\gamma\alpha)$ where $\gamma=(i,j)$ is a transposition
disconnecting $\alpha$. All hypercontractions considered in this work
will be {\em topological}: $i$ and $j$ have to belong to different cycles of
$\sigma$, for maps this operation corresponds to contracting an edge
that is not a loop.  
 





\section{A Whitney polynomial of a collection of hypermaps}
\label{sec:whitney}

\begin{definition}
A {\em collection of hypermaps $(\sigma,\alpha)$} is an ordered pair of
permutations acting on the same set of points. We call the
orbits of the permutation group generated by $\sigma$ and $\alpha$ the
{\em connected components of $(\sigma,\alpha)$} and denote their number 
by $\kappa(\sigma,\alpha)$. 
\end{definition}  
\begin{definition}
\label{def:wrg}  
The {\em Whitney polynomial  $R(\sigma,\alpha;u,v)$} of a
collection of hypermaps $(\sigma,\alpha)$ on a set of $n$ points is
defined by the formula 
$$
R(\sigma,\alpha;u,v)=\sum_{\beta\leq\alpha}
u^{\kappa(\sigma,\beta)-\kappa(\sigma,\alpha)}\cdot
v^{\kappa(\sigma,\beta)+n-z(\beta)-z(\sigma)}
$$
Here the summation is over all permutations $\beta$ refining $\alpha$.
\end{definition}
For maps we recover the usual definition of the Whitney polynomial of
the underlying graph. This invariant is multiplicative for a pair of
collections of hypermaps on disjoint sets of points. The function
$R(\sigma,\alpha;u,v)$ may be computed recursively using the following
generalization of the the well-known deletion-contraction recurrence
for the Whitney polynomial $R(G;u,v)$ of a graph $G$.
\begin{theorem}
\label{thm:wrgrec}  
Let $H=(\sigma,\alpha)$ be a collection of hypermaps on the set
$\{1,2,\ldots,n\}$ and assume that $(1,2,\ldots,m)$ is a cycle of
$\alpha$ of length at least $2$. Then the Whitney polynomial $R(H;u,v)$
is given by the sum
$$
R(H;u,v)=\sum_{k=1}^m R(\phi_k(H);u,v)\cdot w_k,
$$
where each $\phi_k(H)$ is a collection of hypermaps and each $w_k$ is a
monomial from the set $\{1,u,v,uv\}$, according to the following rules:
\begin{equation}
\label{eq:Hrule}  
\phi_k(H)=
\begin{cases}
((1,k)\sigma,(1,k)\alpha(1,k-1))& \mbox{if $z((1,k)\sigma\leq z(\sigma)$},\\
(\sigma,(1,k)\alpha(1,k-1))& \mbox{otherwise}.  
\end{cases}  
\end{equation}
\begin{equation}
\label{eq:wrule}
w_k=
\begin{cases}
u^{\kappa(\phi_k(H))-\kappa(H)}& \mbox{if $z((1,k)\sigma\leq z(\sigma)$},\\
u^{\kappa(\phi_k(H))-\kappa(H)}v & \mbox{otherwise}.  
\end{cases}  
\end{equation}
In rule~(\ref{eq:Hrule}) we count modulo $m$, that is, we replace $k-1$
  with $m$ if $k=1$, and we read $(1,1)$ as a shorthand for the identity
  permutation. 
\end{theorem}  
In analogy to the case of maps, Theorem~\ref{thm:wrgrec} may be modified
in such a way that for a hypermap $(\sigma,\alpha)$ the recurrence only
involves hypermaps. This recurrence uses hyperdeletions and
hypercontractions.   
\begin{example}
For the hypermap shown in Fig~\ref{fig:hypermap}, repeated use of
Theorem~\ref{thm:wrgrec} gives 
$$R((1,4)(2,5)(3),(1,2,3)(4,5);u,v)=u^2+uv+4u+v+3.$$ 
\end{example}  
Certain substitutions into the Tutte polynomial
yield famous graph theoretic invariants. Some of these results carry over
easily to the Whitney polynomial of a collection of hypermaps. 
We define a {\em hyperforest} as a collection of genus zero unicellular
hypermaps and we call a collection of hypermaps $(\sigma,\beta)$
associated to some refinement $\beta$ of $\alpha$
$(\sigma, \alpha)$ {\em a spanning collection of hypermaps} if the subgroup
generated by $\sigma$ and $\beta$ has the same orbits as the permutation
group generated by $\sigma$ and $\alpha$. Then 
\begin{enumerate}
\itemsep=-5pt
\item $R(\sigma,\alpha;0,0)$ is the number of spanning hyperforests of
  $(\sigma,\alpha)$. 
\item $R(\sigma,\alpha;0,1)$ is the number of spanning collections of
  hypermaps of $(\sigma,\alpha)$.  
\end{enumerate}
The Tutte polynomial $T(G;x,y)$ of a graph $G$ (or of a map) is given by
$T(G;x,y)=R(G;x-1,y-1)$. Extending this definition to collections of
hypermaps the obvious way does not seem to be a good idea  
because of the following example.
\begin{example}
\label{ex:Narayana}  
Consider the hypermap $(\sigma,\alpha)$ given by $\sigma=(1)(2)\cdots(n)$
and $\alpha=(1,2,\ldots,n)$. For this, $R(\sigma,\alpha;u,v)$ and
$R(\alpha^{-1}\sigma,\alpha^{-1};u,v)$ are the {\em Narayana
  polynomials} of $u$ and and $v$, respectively, associated to the
noncrossing partitions of $\{1,2,\ldots,n\}$.  For $n=2$ these are $1+u$
and $1+v$ respectively, but they become much more complicated for larger
values of $n$. For $n=3$ we get $R(\sigma,\alpha;u,v)=u^2+3u+1$,
substituting $u=x-1$ yields $x^2+x-1$, a polynomial with a negative coefficient.
\end{example}  
On the other hand, we have the following generalized duality result. 
\begin{theorem}
\label{thm:planardual}   
A collection of hypermaps $(\sigma,\alpha)$ of genus zero and its dual
collection $(\alpha^{-1}\sigma,\alpha^{-1})$ satisfy 
$R(\sigma,\alpha;u,v)=R(\alpha^{-1}\sigma,\alpha^{-1};v,u)$. 
\end{theorem}  


\section{Medial maps}
\label{sec:medial}

\begin{definition}
Let $(\sigma,\alpha)$ be a collection of hypermaps on the set of points
$\{1,2,\ldots,n\}$. We define its {\em medial map $M(\sigma,\alpha)$} as
the following map $(\sigma',\alpha')$ on $\{1^-,1^+,2^-,2^+,\ldots,n^-,n^+\}$:
\begin{enumerate}
\itemsep=-5pt
\item the cycles of $\sigma'$ are all cycles of the form
  $(i_1^-,i_1^+,i_2^-,i_2^+,\ldots,i_k^-,i_k^+)$ where
  $(i_1,i_2,\ldots,i_k)$ is a cycle of $\alpha$;
\item the cycles of $\alpha'$ are all cycles of the form
  $(i^+,\sigma(i)^-)$.  
\end{enumerate}
\end{definition}
We obtain a collection of maps $(\sigma',\alpha')$ satisfying
$\sigma'(i^-)=i^+$ for all $i$, such that the endpoints of each edge have
opposite signs. We call each such collection of maps {\em Eulerian}
and define its {\em underlying Eulerian digraph} 
by directing each edge $(i^+,j^-)$ from its positive endpoint
toward its negative endpoint.  
\begin{figure}[h]
\begin{center}
\input{medial.pdf_t}
\end{center}
\caption{A planar hypermap and its medial map}
\label{fig:medial} 
\end{figure}
The process of creating the medial map of
$((1,5)(2,6)(3)(4),(1,2,3,4)(5,6))$ is shown in
Figure~\ref{fig:medial}.  
\begin{proposition}
\label{prop:dmg}  
Every directed Eulerian graph arises as the
directed medial graph of a collection of hypermaps.
\end{proposition}  
A hypermap of any genus has a medial map of the same genus. 
A planar map $(\sigma,\alpha)$ encodes a plane graph $G$. In this case
$M(\sigma,\alpha)$ is essentially the {\em directed medial graph} 
$\overrightarrow{G_m}$ of $G$, as defined by
Martin~\cite{Martin-Thesis,Martin}. Next we generalize the circuit
partition polynomials appearing in the works of
Ellis-Monaghan~\cite{Ellis-Monaghan-mp,Ellis-Monaghan-mpmisc} and
Arratia, Bollob\'as and Sorkin~\cite{Arratia-Bollobas} (see 
also the Introduction of~\cite{Bollobas-cp}). 
\begin{definition}
Let $(\sigma,\alpha)$ be a collection of Eulerian maps. A {\em
  noncrossing Eulerian state} is a partitioning of the edges of the
underlying directed medial graph into closed paths in such a way that
these paths do not cross at any of the vertices.   
\end{definition}  

\begin{figure}[h]
\begin{center}
\input{ncccp.pdf_t}
\end{center}
\caption{A noncrossing Eulerian state}
\label{fig:ncccp} 
\end{figure}
Figure~\ref{fig:ncccp} represents a noncrossing Eulerian state of the
Eulerian map shown in the right hand side of Figure~\ref{fig:medial}. We
partition the set of edges into closed paths by matching each negative
point on a vertex to a positive point on the same vertex. The arrows
inside the vertices are the ones pointing from the negative points
towards the positive  points. A noncrossing Eulerian state
is uniquely defined by a {\em coherent matching} that refines the vertex
permutation of the Eulerian map, and matches positive points to negative
points. 
\begin{definition}
We define the {\em noncrossing circuit partition
polynomial} of an Eulerian map $(\sigma,\alpha)$ as 
$$
  j((\sigma,\alpha);x)=\sum_{k\geq 0} f_k(\sigma,\alpha) x^k.
  $$
Here $f_k(\sigma,\alpha)$ is the number of noncrossing Eulerian states
with $k$ cycles.   
\end{definition}
The following result generalizes Ellis-Monaghan's generalization of
Martin's formula~\cite[Eq.\ (15)]{Ellis-Monaghan-cpp} from planar
maps to hypermaps. 
\begin{theorem}
\label{thm:genmartin}
Let $(\sigma,\alpha)$ be a genus zero collection of hypermaps and
$M(\sigma,\alpha)$ the collection of its medial maps. Then
$j(M(\sigma,\alpha);x)=x^{\kappa(\sigma,\alpha)} R(\sigma,\alpha;x,x)$
holds. 
\end{theorem}  

\section{A visual computation of $R(\sigma,\alpha;u,v)$
  in the planar case}
\label{sec:visual}

\begin{figure}[h]
\begin{center}
\input{papercuts.pdf_t}
\caption{A planar hypermap with the edges of its medial map shrunk to
  its outline}
\label{fig:papercuts}
\end{center}
\end{figure}
Consider the hypermap $(\sigma,\alpha)$ given by
$\sigma=(1,5,12)(4,11,10)(3,9,8)(2,7,6)$  and
$\alpha=(1,2,3,4)(5,6)(7,8)(9,10)(11,12)$, 
shown in Figure~\ref{fig:papercuts}. For each point $i$ we
add the points $i^-$ and $i^+$ of the medial map. The vertices
of  $M(\sigma,\alpha)$ are identified with the hyperedges
of $(\sigma,\alpha)$, and we 
``shrink'' the edges $(i^+,\sigma(i)^-)$ of $M(\sigma,\alpha)$ to follow
the outline of the original vertices and the hyperedges. Thus we fatten
the outline of the diagram of $(\sigma, \alpha)$, except for the
counterclockwise arcs from $i^-$ to   $i^+$ along the vertices (unless
$\sigma(i)=i$) and for he arcs from $i^+$ to 
$\alpha(i)^{-}$ along the hyperedges (unless $\alpha(i)=i$).
Next we select a coherent matching on the signed points. The {\em
  nontrivial choices} are the ones when $i^+$ is not matched to
 $\alpha(i)^{-}$, the remaining choices are trivial. We can think of the
  diagram of $(\sigma,\alpha)$ as a paper cutout, with the vertices and the
hyperedges being solid and the faces missing. Each nontrivial pair of
matched points corresponds then to a cut into the object using a
scissor, subject to the following rules:
\begin{itemize} 
\itemsep=-5pt  
\item[(R1)] Each cut is a simple curve connecting a point $i^+$ with a
  point $j^-$, inside a hyperedge. 
\item[(R2)] Each point $i^+$ and $j^-$ may be used at most once. 
\item[(R3)] The remaining points not used in the cuts
  must come in pairs $(i^+,\alpha(i)^-)$. 
\item[(R4)] A new cut cannot cut into the cut-line of a previous cut.
\end{itemize}  
At the end of the process the curves of the outline
correspond to the faces $\beta^{-1}\sigma$ of $(\sigma,\beta)$ for
some $\beta\leq \alpha$, and they
are also the circuits of the 
corresponding circuit partition. Let us think of the unbounded face of
the hypermap $(\sigma,\alpha)$ as ``the ocean''  with a ``wet
coastline''. After a few nontrivial cuts, we may have several connected
components, each has one coastline. Figure~\ref{fig:papercuts2}
illustrates this situation after 
performing the nontrivial cuts indicated in
Figure~\ref{fig:papercuts}. The shaded regions indicate the faces of
$\sigma,\alpha$ whose border has been merged with a (thickened) wet coastline. 
\begin{figure}[h]
\begin{center}
 \input{papercuts2.pdf_t}
\end{center}
\caption{Wet coastlines after a few cuts}
\label{fig:papercuts2}
\end{figure}
\begin{theorem}
\label{thm:visual}
Given a planar hypermap $(\sigma,\alpha)$, we may visually compute its
Whitney polynomial by making its model in paper, and performing the
above cutting procedure in all possible ways and associating to each
outcome $u$ raised to the power of the wet coastlines and $v$ raised to
the power of the dry faces. The sum of all weights is $u\cdot
R(\sigma,\alpha;u,v)$.   
\end{theorem}  

\section{Counting noncrossing Eulerian colorings}
\label{sec:medialc}


In this section we extend the formula counting the Eulerian colorings of
the medial graph of a plane graph~\cite[Evaluation
  6.9]{Ellis-Monaghan-exploring} to medial maps of planar hypermaps. The
following definition may be found in~\cite[Definition
  4.3]{Ellis-Monaghan-exploring}. 

\begin{definition} 
An {\em Eulerian $m$-coloring} of an Eulerian directed graph
$\overrightarrow{G}$ is an edge coloring
of $\overrightarrow{G}$ with $m$ colors so that for each color the
(possibly empty) set of all edges of the given color forms an Eulerian
subdigraph.  
\end{definition}

Consider now a planar hypermap $(\sigma,\alpha)$ and its directed
Eulerian medial map $M(\sigma,\alpha)$. Given an Eulerian $m$-coloring
of the edges, let us color the endpoints of $(i^+,\sigma(i)^-)$ with the
color of the edge. We call this coloring of the points the {\em coloring
  of the points induced by the Eulerian $m$-coloring}. In order to
relate the count of the Eulerian $m$-colorings to our Whitney
polynomial, we must restrict our attention to {\em noncrossing Eulerian
  $m$-colorings}, defined as follows.
\begin{definition}
Let  $(\sigma,\alpha)$ be a planar hypermap and let $M(\sigma,\alpha)$
be its directed medial map. We call an Eulerian $m$-coloring {\em
  noncrossing} if there is a noncrossing Eulerian state 
such that all edges of the same connected circuit have the same color.  
\end{definition}  
\begin{remark}
If $(\sigma,\alpha)$ is a map then the above noncrossing condition is
automatically satisfied by each Eulerian $m$-coloring of
$M(\sigma,\alpha)$ as all Eulerian
states of $M(\sigma,\alpha)$ are noncrossing. The more general case
of partitioning the edge set of an Eulerian digraph into Eulerian
subdigraphs was addressed
in~\cite{Arratia-Bollobas,Bollobas-cp,Ellis-Monaghan-mp}.       
\end{remark}

Using the induced coloring of the points we can verify vertex by vertex
whether an Eulerian $m$-coloring is non-crossing: it is necessary and
sufficient to be able to find a coherent matching at each vertex such
that only points of the same color are matched. This observation
motivates the following definition.

\begin{definition}
\label{def:legalc}  
Let $(\sigma,\alpha)$ be a planar hypermap on the set of points
$\{1,2\ldots,n\}$ and $M(\sigma,\alpha)=(\sigma',\alpha')$ its directed
medial map on the set of points $\{1^-,1^+,2^-,2^+,\ldots,n^-,n^+\}$. We call an
$m$-coloring of the points $\{1^-,1^+,2^-,2^+,\ldots,n^-,n^+\}$ a {\em
  legal coloring} if it satisfies the following conditions:
\begin{enumerate}
\itemsep=-5pt
\item The endpoints of each edge $(i^+,\sigma(i)^-)\in \alpha'$ of
  $M(\sigma,\alpha)$ have the same color.
\item There is a coherent matching of the set
  $\{1^-,1^+,2^-,2^+,\ldots,n^-,n^+\}$ such that each point is matched
  to a point of the same color. 
\end{enumerate}
\end{definition}  

Definition~\ref{def:legalc} is motivated by the following observation. 
\begin{proposition}
Given a planar hypermap $(\sigma,\alpha)$ and its directed medial map
$M(\sigma,\alpha)$ a coloring of the set of points of $M(\sigma,\alpha)$
is legal if and only if it is induced by a noncrossing Eulerian
$m$-coloring of the edges of $M(\sigma,\alpha)$.   
\end{proposition}  
\vanish{\begin{proof}
Condition (1) requires that the coloring of the signed points must be induced
by a coloring of the edges. This coloring of the signed points is
induced by an Eulerian coloring if and only if each cycle of $\sigma'$
contains the same number of positive points and negative points of each
color. The resulting partitioning of the edges into color sets is
represented by a noncrossing Eulerian state if and only if there is a
coherent matching connecting only points of the same color.        
\end{proof} } 

Note that for a given $m$-coloring of the signed points, induced by a
coloring of the edges in $\alpha'$, condition~(2) may be independently
verified at each vertex of $\sigma'$. This observation motivates the
following definition.
\begin{definition}
Let $(i_1^-,i_1^+,i_2^-,i_2^+,\ldots,i_k^-,i_k^+)$ be a cyclic signed
permutation and let is fix an $m$-coloring of its points. We say that
the {\em valence} of this colored cycle is number of coherent matchings
of its points that match each point the a point of the same color.   
\end{definition}  

Now we are able to state the generalization of~\cite[Evaluation
  6.9]{Ellis-Monaghan-exploring}.

\begin{theorem}
Let $(\sigma,\alpha)$ be a planar hypermap. Then, for a fixed positive
integer $m$, we have
$$
m^{\kappa(\sigma,\alpha)} R(\sigma,\alpha;m,m)=\sum_{\lambda}
\prod_{v\in\sigma'} \nu(v,\lambda).
$$
Here the summation runs over all Eulerian $m$-colorings $\lambda$ of the
directed medial map $M(\sigma,\alpha)=(\sigma',\alpha')$, and for each vertex
$v\in\sigma'$ the symbol $\nu(v,\lambda)$ represents the valence of $v$
colored by the restriction of the point coloring induced by $\lambda$ to the
points of $v$.  
\end{theorem}  
\vanish{\begin{proof}
By Theorem~\ref{thm:genmartin} the left hand side is
$j(M(\sigma,\alpha);m)$ which is the number of ways to select a
noncrossing Eulerian state, and then color each of its cycles with one
of $m$ colors. By the above reasoning, this may be also performed by
first selecting an Eulerian $m$-coloring $\lambda$ of the
directed medial map $M(\sigma,\alpha)$ and then a coherent matching on
each vertex that matches only points of the same color.  
\end{proof}}  

\begin{example}
For maps $(\sigma,\alpha)$, there are essentially two types of vertices
in the directed medial map $M(\sigma,\alpha)$: monochromatic vertices
and vertices colored with two colors. We can recover the
formula~\cite[Evaluation 6.9]{Ellis-Monaghan-exploring}:
$$
m^{\kappa(\sigma,\alpha)}R(\sigma,\alpha;m,m)=\sum_{\lambda} 2^{m(\lambda)}$$
where $m(\lambda)$ is the number of monochromatic vertices. Evaluating
this formula at $m=2$ was used by Las Vergnas~\cite{LasVergnas-tp} to
describe the exact power of $2$ that divides $R(\sigma,\alpha;2,2)$ for
a map $(\sigma,\alpha)$, or equivalently the evaluation of its Tutte
polynomial at $(3,3)$.    
\end{example}  


\section{The characteristic polynomial of a hypermap}
\label{sec:charpoly}

\begin{proposition}
Let $\alpha$ be a permutation of $\{1,2,\ldots,n\}$ with $k$ cycles of
lengths $c_1,\ldots,c_k$. Then the partially ordered set of all
refinements of $\alpha$, ordered by the refinement operation, is a
direct product 
$[\id,\alpha]=\prod_{i=1}^k \operatorname{NC}(c_i)$. 
Here $\id$ is the identity permutation $(1)(2)\cdots(n)$ and 
$\operatorname{NC}(c_i)$ is the lattice of noncrossing partitions
on $c_i$ elements.
\end{proposition}  
Using the results in~\cite{Simion-noncrossing}, the M\"obius function
$\mu(\beta,\alpha)$  of any interval $[\beta,\alpha]$ may be expressed in terms
of Catalan numbers.
\begin{definition}
\label{def_char}
Given a collection of hypermaps $(\sigma,\alpha)$ on the set of
points $\{1,2,\ldots,n\}$, we define its {\em
  characteristic polynomial $\chi(\sigma,\alpha;t)$} by 
$$\chi(\sigma,\alpha;t)=
\sum_{\beta\leq
    \alpha}\mu(\id,\beta)\cdot
t^{\kappa(\sigma,\beta)-\kappa(\sigma,\alpha)}. 
$$ 
\end{definition}
When $(\sigma,\alpha)$ is a collection of maps on the set
$\{1,2,\ldots,n\}$, we get that $\chi(\sigma,\alpha;t)$ is the
characteristic polynomial of its underlying graph. For a fixed
collection of hypermaps $(\sigma,\alpha)$, let us define the function
$X([\alpha_1,\alpha_2];t)$ on the intervals of the partially ordered set
of the refinements of $\alpha$ by
\begin{equation}
\label{eq:bigchi}  
X([\alpha_1,\alpha_2];t)=\sum_{\beta\in[\alpha_1,\alpha_2]}
  \mu(\alpha_1,\beta)\cdot
  t^{\kappa(\sigma,\beta)}
\end{equation}
A M\"obius inversion formula computation yields
$\sum_{\beta\leq \alpha}
X([\beta,\alpha];t)=t^{z(\sigma)}$. 
For maps, this computation implies that the chromatic polynomial
$\kappa(\sigma,\alpha)\chi(\sigma,\alpha;t)=X([\id,\alpha];t)$ is the
number of ways to color the vertices using $t$ colors such that adjacent
vertices have the same color.  This reasoning cannot be
extended to arbitrary hypermaps, but it is possible to generalize it to
hypermaps with hyperedges containing at most $3$ points.
\begin{theorem}
Let $(\sigma,\alpha)$ be a collection of hypermaps such that each cycle
of $\alpha$ has length at most $3$. Then for any positive integer $n$,
the number $n^{\kappa(\sigma,\alpha)}\cdot \chi(\sigma,\alpha,n)$ is the
number of ways to $n$-color the vertices of $(\sigma,\alpha)$ in such a way that
no two vertices of the same color are incident to the same cycle of $\alpha$.
\end{theorem}
\vanish{\begin{proof}
We only need to show that the above reasoning for collections of maps
can be extended to allowing hyperedges with $3$ points. This is a direct
consequence of the fact that every set partition of the set $\{1,2,3\}$
is also a noncrossing partition (with respect of any cyclic order).

Consider a $3$ cycle $(i_1,i_2,i_3)$ of $\alpha$ and let $v_j$ be the
vertex containing $i_j$ for $j=1,2,3$. If all three vertices have the
same color then $(i_1,i_2,i_3)$ is also a cycle of $\beta$. If two of
them, say $v_1$ and $v_2$ have the same color, but $v_3$ has a different
color, then the only good choice is to make $(i_1,i_2)(i_3)$ part of the
decomposition of $\beta$ into disjoint cycles. Finally, if all three
vertices have different colors then $(i_1)(i_2)(i_3)$ must be the cycles
of $\beta$ on $\{i_1,i_2,i_3\}$. As noted in Remark~\ref{rem:loop}
above, some of the vertices may coincide in that case the points
belonging to the same vertex must belong to the same cycle of $\beta$.    
\end{proof}  }

A completely analogous dual reasoning may be developed for the 
{\em flow polynomial $C(\sigma,\alpha,;t)$} of a
collection of hypermaps
$(\sigma,\alpha)$ on the set of points $\{1,2,\ldots,n\}$, defined  by
$$
C(\sigma,\alpha;t)=\sum_{\beta\leq \alpha} \mu(\beta,\alpha)
t^{n+\kappa(\sigma,\beta)-z(\beta)-z(\sigma)}. 
$$

\acknowledgements{The second author wishes to express his heartfelt thanks to Labri, Universit\'e
Bordeaux I, for hosting him as a visiting researcher in Summer 2019 and
in Summer 2023, where a great part of this research was performed.}


\nocite{*}

%% 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}
