\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{combinatorial map} \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak \noindent\hyperlink{oriented_maps_and_hypermaps}{Oriented maps and hypermaps}\dotfill \pageref*{oriented_maps_and_hypermaps} \linebreak \noindent\hyperlink{classical_combinatorial_maps}{Classical combinatorial maps}\dotfill \pageref*{classical_combinatorial_maps} \linebreak \noindent\hyperlink{representing_an_embedded_graph_as_a_combinatorial_map}{Representing an embedded graph as a combinatorial map}\dotfill \pageref*{representing_an_embedded_graph_as_a_combinatorial_map} \linebreak \noindent\hyperlink{hypermaps_and_constellations}{Hypermaps and constellations}\dotfill \pageref*{hypermaps_and_constellations} \linebreak \noindent\hyperlink{fixed_vertexedgeface_degrees}{Fixed vertex/edge/face degrees}\dotfill \pageref*{fixed_vertexedgeface_degrees} \linebreak \noindent\hyperlink{realizing_a_combinatorial_map_as_a_graph_embedded_in_a_riemann_surface}{Realizing a combinatorial map as a graph embedded in a Riemann surface}\dotfill \pageref*{realizing_a_combinatorial_map_as_a_graph_embedded_in_a_riemann_surface} \linebreak \noindent\hyperlink{genus_of_a_combinatorial_map}{Genus of a combinatorial map}\dotfill \pageref*{genus_of_a_combinatorial_map} \linebreak \noindent\hyperlink{dual_map}{Dual map}\dotfill \pageref*{dual_map} \linebreak \noindent\hyperlink{equivalence_with_other_families_of_objects}{Equivalence with other families of objects}\dotfill \pageref*{equivalence_with_other_families_of_objects} \linebreak \noindent\hyperlink{tetravalent_maps_with_bicolored_faces}{Tetravalent maps with bicolored faces}\dotfill \pageref*{tetravalent_maps_with_bicolored_faces} \linebreak \noindent\hyperlink{alternating_virtual_links}{Alternating virtual links}\dotfill \pageref*{alternating_virtual_links} \linebreak \noindent\hyperlink{the_category_of_oriented_maps}{The category of oriented maps}\dotfill \pageref*{the_category_of_oriented_maps} \linebreak \noindent\hyperlink{terminal_object}{Terminal object}\dotfill \pageref*{terminal_object} \linebreak \noindent\hyperlink{the_oriented_cartographic_group}{The oriented cartographic group}\dotfill \pageref*{the_oriented_cartographic_group} \linebreak \noindent\hyperlink{rooted_maps}{Rooted maps}\dotfill \pageref*{rooted_maps} \linebreak \noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{idea}{}\subsection*{{Idea}}\label{idea} A \textbf{combinatorial map} is a representation of a graph embedded in a surface (i.e., a [[topological map]]) as a set and a list of permutations acting on that set, with the property that two combinatorial maps are equivalent up to [[conjugation]] if and only if the corresponding graphs are isomorphic by a [[homeomorphism]] of the underlying surfaces. The precise formulation depends upon assumptions made about the underlying surface (e.g., whether it is [[connected space|connected]] and/or [[oriented]]) and about the underlying graph (e.g., whether all vertices have a fixed degree), but typically different classes of topological maps can be represented by lists of permutations satisfying different sets of constraints. \hypertarget{oriented_maps_and_hypermaps}{}\subsection*{{Oriented maps and hypermaps}}\label{oriented_maps_and_hypermaps} \hypertarget{classical_combinatorial_maps}{}\subsubsection*{{Classical combinatorial maps}}\label{classical_combinatorial_maps} The following definition corresponds to the case which is perhaps most well-studied: \begin{definition} \label{def_cmap}\hypertarget{def_cmap}{} A \textbf{combinatorial map} $M$ is a set $D$ (whose elements are called \emph{darts}) equipped with a triple of [[permutations]] $(\sigma,\alpha,\phi)$ on $D$ such that: \begin{enumerate}% \item the [[subgroup]] $\langle \sigma,\alpha,\phi\rangle$ of $Aut(D)$ generated by the permutations acts [[transitive action|transitively]] on $D$; \item the composition of the permutations is the identity: $\phi\alpha\sigma = id$; \item $\alpha$ is a [[fixed point]]-free [[involution]]. \end{enumerate} \end{definition} A [[homomorphism]] of combinatorial maps \begin{displaymath} M \to M' \end{displaymath} where $M = (D,(\sigma,\alpha,\phi)), M' = (D',(\sigma',\alpha',\phi'))$ is a function $h : D \to D'$ which commutes with each of the respective permutations, \begin{displaymath} h\sigma = \sigma'h \qquad h\alpha = \alpha'h \qquad h\phi = \phi' h. \end{displaymath} Hence, $M$ and $M'$ are [[isomorphic]] as maps if and only there is a bijection $h : D \cong D'$ between their underlying sets of darts, such that the triple of permutations $(\sigma,\alpha,\phi)$ is mapped by [[conjugation]] along $h$ to the triple of permutations $(\sigma',\alpha',\phi')$. In the literature, many authors equivalently define a combinatorial map by a pair $(\sigma,\alpha)$ of permutations, since by condition (2) above, the third permutation $\phi$ can always be recovered uniquely as $\phi = \sigma^{-1}\alpha^{-1}$. \hypertarget{representing_an_embedded_graph_as_a_combinatorial_map}{}\subsubsection*{{Representing an embedded graph as a combinatorial map}}\label{representing_an_embedded_graph_as_a_combinatorial_map} Let $\theta$ be an embedding of a [[graph]] $G$ with $n$ edges into a [[surface]] $X$ which is [[compact]], [[connected]], [[oriented]], and without [[boundary]] (below we will just call these ``oriented surfaces'' for short). We can associate a combinatorial map to this topological embedding, which is unique up to isomorphism: \begin{itemize}% \item $D$ is defined as a set containing $2n$ elements, with a pair of distinct darts $e^+,e^- \in D$ for each edge $e \in G$. These darts may be visualized as oriented edges, or alternatively as half-edges (splitting each of the original edges in the middle). \item the collection of edges induces a fixed point-free involution $\alpha$ on $D$, by swapping $e^+$ with $e^-$ for each edge $e \in G$. \item suppose darts are visualized as oriented edges: we will say that a dart $d$ is \emph{incident} to a vertex $x$ if $x$ is the unique vertex located at the source of $d$. Then every vertex $x\in G$ determines a cyclic ordering of the darts incident to $x$, by considering (say) a counterclockwise-oriented [[loop]] around $\theta(x)$. In this way (which relies on the assumption that $X$ is oriented), each vertex determines a cycle of the permutation $\sigma$. \item similarly, we say that a dart $d$ is incident to a face $f$ (i.e., a connected component of $X \setminus \theta(G)$) if $f$ is the unique face appearing to the left of $d$. Then each face $f$ determines a cyclic ordering of darts incident to $f$ (corresponding to a counterclockwise traversal along the perimeter of $f$), and we can combine these disjoint cycles into a single permutation $\phi$. \item if we start at any dart $d \in D$, then apply the permutation $\sigma$ followed by $\alpha$ followed followed by $\phi$, we always end up back at $d$. \end{itemize} \hypertarget{hypermaps_and_constellations}{}\subsubsection*{{Hypermaps and constellations}}\label{hypermaps_and_constellations} There are several directions for generalizing the classical definition. A small but useful generalization is to drop the requirement that $\alpha$ be [[fixed point]] free, while keeping the requirement that it be an [[involution]] (i.e., that $\alpha^2 = id$). This can be seen as allowing the possibility for the graph to include ``dangling edges''. In particular, every $\alpha$-[[orbit]] has length 2 or 1, with orbits of length 2 representing complete edges and orbits of length 1 representing dangling edges. As a bigger step, it is possible to drop condition (3) altogether: \begin{definition} \label{def_hmap}\hypertarget{def_hmap}{} A \textbf{combinatorial hypermap} is a set $D$ equipped with a triple of [[permutations]] $(\sigma,\alpha,\phi)$ on $D$ such that: \begin{enumerate}% \item the [[subgroup]] $\langle \sigma,\alpha,\phi\rangle$ of $Aut(D)$ generated by the permutations acts [[transitive action|transitively]] on $D$; \item the composition of the permutations is the identity: $\phi\alpha\sigma = id$. \end{enumerate} \end{definition} A combinatorial hypermap gives a representation of a topological embedding of a [[hypergraph]] in a oriented surface, but (as noted by Walsh) this is equivalent to an embedding of an ordinary graph equipped with a [[vertex coloring|2-coloring]] of its vertices. (Such a graph is necessarily a [[bipartite graph]].) Then, the permutations $\sigma$ and $\alpha$ represent the cycles around the black and white vertices, respectively, while $\phi$ as before represents the faces. Any ordinary map with all black vertices can be seen as a hypermap with a white vertex dividing each edge (thinking of darts as half-edges), and from that perspective, the definition of hypermap simply corresponds to lifting the restriction that white vertices have degree 2. Both of these generalizations of the standard notion of combinatorial map are studied in the literature on so-called [[dessins d'enfants]], sometimes using the following terminology to distinguish the different cases: \begin{itemize}% \item $\alpha$ is a fixed point free involution : ``clean dessin'' \item $\alpha$ is an involution : ``pre-clean dessin'' \item no conditions on $\alpha$ (besides (1) and (2) above): ``dessin'' \end{itemize} Another line of generalization is to consider an arbitrary number of permutations (rather than only three). This more general notion of hypermap is called a ``constellation'' in \hyperlink{LandoZvonkin04}{Lando \& Zvonkin}. \begin{definition} \label{def_constellation}\hypertarget{def_constellation}{} A \textbf{k-constellation} is a set $D$ equipped with a $k$-[[tuple]] of [[permutations]] $\alpha_1,\dots,\alpha_k$ on $D$ such that: \begin{enumerate}% \item the [[subgroup]] $\langle \alpha_1,\dots,\alpha_k\rangle$ of $Aut(D)$ generated by the permutations acts [[transitive action|transitively]] on $D$; \item the composition of the permutations is the identity: $\alpha_k\dots\alpha_1 = id$. \end{enumerate} \end{definition} \hypertarget{fixed_vertexedgeface_degrees}{}\subsubsection*{{Fixed vertex/edge/face degrees}}\label{fixed_vertexedgeface_degrees} If one adds, say, the condition that \begin{itemize}% \item $\sigma^3 = id$ and $\sigma$ has no fixed points \end{itemize} to the definition of combinatorial map, then the resulting class of permutations represent embeddings of \emph{trivalent} graphs, i.e., where every vertex has degree 3. Dually, placing the condition that \begin{itemize}% \item $\phi^3 = id$ and $\phi$ has no fixed points \end{itemize} gives a way of representing arbitrary [[triangulations]] of oriented surfaces. Analogous to what we saw above in the case of the edge involution $\alpha$, dropping the condition that $\sigma$ or $\phi$ be fixed point free also allows for the possibility of degenerate vertices/faces of degree 1. More generally, we can say that a map has type $(m,n)$ if the permutations $\sigma$ and $\phi$ have [[order\#in\_the\_sense\_of\_group\_theory|order]]s $m$ and $n$ respectively (allowing for the possibility that $m = \infty$ or $n = \infty$ in the case where the set of darts is infinite). This algebraic condition translates to the geometric condition that $m$ is the [[least common multiple]] of the degrees of the vertices of the map, and $n$ is the least common multiple of the degrees of the faces. \hypertarget{realizing_a_combinatorial_map_as_a_graph_embedded_in_a_riemann_surface}{}\subsubsection*{{Realizing a combinatorial map as a graph embedded in a Riemann surface}}\label{realizing_a_combinatorial_map_as_a_graph_embedded_in_a_riemann_surface} Conversely, any combinatorial map $M = (D,(\sigma,\alpha,\phi))$ can be realized as a graph embedded in a surface, in other words as a [[topological map]]. The first explicit algorithm for computing such an embedding was given by \hyperlink{Edmonds60}{Edmonds 1960}. The underlying graph $G(M)$ of $M$ is easy to describe using the ``Serre'' definition of a graph (as explained [[graph\#definition\_in\_terms\_of\_action\_on\_a\_set\_of\_halfedges|here]]) $G(M) = (H,V,i,s)$. The set of half-edges $H$ and the involution $i$ are just $D$ and $\alpha$, respectively, while the set of vertices $V$ is the set of $\sigma$-orbits, and the function $s : H \to V$ sends any dart to its orbit under $\sigma$. Some more work is required in order to define a surface $X$ and an embedding of $G(M)$ into $X$. \hyperlink{JonesSingerman78}{Jones and Singerman 1978} actually proved a stronger result than Edmonds' algorithm, showing that any combinatorial map (of finite type $(m,n)$) can be realized as a graph embedded in a [[Riemann surface]]. As a corollary, this implies that any topological map (on a compact oriented surface without boundary) is isomorphic to some canonical map on a Riemann surface. \hypertarget{genus_of_a_combinatorial_map}{}\subsubsection*{{Genus of a combinatorial map}}\label{genus_of_a_combinatorial_map} The \textbf{genus} $g$ of a combinatorial map $M = (\sigma,\alpha,\phi)$ can be defined directly using the [[Euler characteristic|Euler-Poincaré formula]], \begin{displaymath} \chi(M) = c(\sigma) - c(\alpha) + c(\phi) = 2-2g \end{displaymath} where $c(\pi)$ counts the number of cycles in the [[permutation\#via\_cycle\_decompositions|cyclic decomposition]] of $\pi$ (i.e., the number of $\pi$-[[orbits]]). This definition of genus agrees with the genus of the underlying surface of the embedded graph associated to $M$. \hypertarget{dual_map}{}\subsubsection*{{Dual map}}\label{dual_map} Any embedded graph has a dual graph embedded into the same surface, constructed by placing a vertex in the middle of each face, and connecting two vertices whenever the corresponding faces share an edge. This construction is particularly easy to express on combinatorial maps: for any $M = (D,(\sigma,\alpha,\phi))$, the corresponding \textbf{dual map} is defined by $M^* = (D,(\phi^{-1},\alpha^{-1},\sigma^{-1}))$. This operation is clearly an involution (with fixed points, since some maps are self-dual). Moreover, it extends to an operation on hypermaps. \hypertarget{equivalence_with_other_families_of_objects}{}\subsection*{{Equivalence with other families of objects}}\label{equivalence_with_other_families_of_objects} \hypertarget{tetravalent_maps_with_bicolored_faces}{}\subsubsection*{{Tetravalent maps with bicolored faces}}\label{tetravalent_maps_with_bicolored_faces} To any graph $G$ embedded in an oriented surface $X$, one can associate a tetravalent graph $G^m$ embedded in the same surface $X$ by the following construction: \begin{itemize}% \item one vertex $v_e \in G^m$ for every edge $e \in G$; \item one edge $v_{e_1} \sim v_{e_2} \in G^m$ for every ordered pair of edges $e_1,e_2 \in G$ which occur consecutively along the same face in $\theta(G)$. \end{itemize} In graph theory, this is known as the \textbf{medial graph} construction. As with the dual graph construction, though, note that this is only well-defined as an operation on embedded graphs (i.e., topological maps) rather than on abstract graphs: the same graph can have different medial graphs, depending on how it is embedded into a surface. To avoid confusion, we refer to this as the \textbf{medial map} construction. Two topological maps $M_1$ and $M_2$ have isomorphic medial maps $M_1^m \cong M_2^m$ if and only if they are either isomorphic $M_1 \cong M_2$ or dual $M_1 \cong M_2^*$. To distinguish between duals, one can define a 2-coloring of the \emph{faces} of the medial map as follows: a face of $M^m$ is colored in black just in case it contains a vertex of $M$, and white otherwise. The construction of the 2-colored medial map thus defines a one-to-one correspondence between general maps and face 2-colored tetravalent maps on oriented surfaces. \hypertarget{alternating_virtual_links}{}\subsubsection*{{Alternating virtual links}}\label{alternating_virtual_links} Any \emph{alternating} virtual link (in the sense of [[virtual knot theory]]) is naturally represented by a face 2-colored tetravalent map: each ordinary crossing becomes a vertex of degree 4, with faces colored according to the pattern of under/over crossings (virtual crossings appearing in the link diagram disappear when the knot is embedded into the appropriate surface of higher genus). Thus, any alternating virtual link can be encoded by a unique combinatorial map, and vice versa: see Section 4 of \hyperlink{ZJZ2004}{Zinn-Justin and Zuber 2004} where they discuss this representation. \hypertarget{the_category_of_oriented_maps}{}\subsection*{{The category of oriented maps}}\label{the_category_of_oriented_maps} In this section we will adopt the more liberal notion of combinatorial map described above, for which the involution $\alpha$ is allowed to have fixed points corresponding to ``dangling'' edges. We will also sometimes write \emph{map} as shorthand for combinatorial map in this more liberal sense. \begin{definition} \label{def_cm}\hypertarget{def_cm}{} The \textbf{category of combinatorial maps} $CM$ is defined as follows: \begin{itemize}% \item objects are pairs of a set $D$ together with a triple of permutations $(\sigma,\alpha,\phi)$ on $D$ such that $\langle\sigma,\alpha,\rho\rangle$ acts transitively on $D$ and $\alpha^2 = \phi\alpha\sigma = id$. \item morphisms $(D,(\sigma,\alpha,\phi)) \to (D',(\sigma',\alpha',\phi'))$ are functions $h : D \to D'$ such that $h\sigma = \sigma' h$, $h\alpha = \alpha' h$, and $h\phi = \phi' h$. \end{itemize} \end{definition} The category $CM$ was defined by \hyperlink{JonesSingerman78}{Jones and Singerman 1978} essentially as above (they call it $AM$ for ``algebraic maps''). Specifically, Jones and Singerman take this category to include combinatorial maps in which the involution $\alpha$ may contain fix points. \begin{prop} \label{}\hypertarget{}{} $CM$ is a [[concrete category]], with a faithful functor $U : CM \to Set$ which sends any combinatorial map $(D,(\sigma,\alpha,\phi))$ to its underlying set of darts $D$, and any homomorphism of maps $h : M \to M'$ to a function $h : D \to D'$ between the underlying sets of darts. \end{prop} \hypertarget{terminal_object}{}\subsubsection*{{Terminal object}}\label{terminal_object} We note that the following property of $CM$ relies on allowing maps with dangling edges. \begin{prop} \label{}\hypertarget{}{} The set $1 = \{ * \}$ equipped with the triple of identity permutations $\sigma = \alpha = \phi = id_1$ is a map, and is a [[terminal object]] in $CM$. \end{prop} \hypertarget{the_oriented_cartographic_group}{}\subsubsection*{{The oriented cartographic group}}\label{the_oriented_cartographic_group} (See also article: [[cartographic group]].) \begin{definition} \label{def_cartgp}\hypertarget{def_cartgp}{} The \textbf{oriented cartographic group} $\mathcal{C}_2^+$ is the group generated by three elements $\rho_0,\rho_1,\rho_2$ satisfying the relations $\rho_1^2 = \rho_0\rho_1\rho_2 = 1$. \end{definition} \begin{prop} \label{}\hypertarget{}{} The oriented cartographic group is isomorphic to a [[free product of groups|free product]] of the integers with the integers modulo 2, $\mathcal{C}_2^+ \cong \mathbb{Z} \star \mathbb{Z}_2$. \end{prop} Every combinatorial map is a $\mathcal{C}_2^+$-set, i.e., a set equipped with an action of the oriented cartographic group. In fact, $CM$ is just the [[full subcategory]] of $\mathcal{C}_2^+Set$ consisting of sets equipped with a [[transitive action]] of $\mathcal{C}_2^+$. \begin{remark} \label{}\hypertarget{}{} The [[moebius transformation\#abstract\_structure\_of\_modular\_group|modular group]] $PSL_2(\mathbb{Z}) \cong \mathbb{Z}_3 \star \mathbb{Z}_2$ is a quotient of the oriented cartographic group. Sets equipped with a transitive action of $PSL_2(\mathbb{Z})$ are the same thing as trivalent combinatorial maps, which represent trivalent graphs (possibly including degeneracies) embedded in oriented surfaces (or dually, triangulations of oriented surfaces). \end{remark} For any given map $M$ with underlying set of darts $D$ we will denote the action of the oriented cartographic group by \begin{displaymath} *_M : D \times \mathcal{C}_2^+ \to D, \end{displaymath} omitting subscripts when clear from context. The fact that $\mathcal{C}_2^+$ acts transitively on $D$ corresponds to the topological condition that the graph represented by $M$ is connected. As we will see, this places strong restrictions on possible morphisms between maps: \begin{prop} \label{}\hypertarget{}{} A morphism $h : M_1 \to M_2$ of combinatorial maps is entirely determined given the image of a single dart $h(d_1) \in D_2$. \end{prop} \begin{proof} Let $d_1' \in D_1$. By assumption of transitivity, there exists a word $w \in \mathcal{C}_2^+$ such that $d_1' = d_1 *_1 w$. Hence $h(d_1') = h(d_1 *_1 w) = h(d_1) *_2 w$. \end{proof} \begin{prop} \label{}\hypertarget{}{} If $h : M_1 \to M_2$ is a morphism of combinatorial maps and $D_1$ is [[inhabited]], then the underlying function $h : D_1 \to D_2$ is a [[surjection]]. \end{prop} \begin{proof} Let $d_2 \in D_2$. By assumption that $D_1$ is inhabited there exists a $d_1 \in D_1$, and by assumption of transitivity there exists $w \in \mathcal{C}_2^+$ such that $d_2 = h(d_1) *_2 w$. Since $h(d_1) *_2 w = h(d_1 *_1 w)$, the dart $d_1 *_1 w \in D_1$ is in the inverse image of $d_2 \in D_2$. \end{proof} \hypertarget{rooted_maps}{}\subsubsection*{{Rooted maps}}\label{rooted_maps} Enumeration of maps is an active branch of [[combinatorics]], going back to the work of [[W. T. Tutte]] in the 1960s. One of the difficulties with trying to count (combinatorial or topological) maps directly, though, is that they can have non-trivial symmetries, which would need to be accounted for to avoid double-counting. This is why combinatorists typically begin with the easier problem of counting \emph{rooted maps}, as suggested in this autobiographical account by Tutte: \begin{quote}% Having made no progress with the enumeration of these diagrams (strict triangulations of the plane) I bethought myself of Cayley's work on the enumeration of trees. His first successes had been with the rooted trees, in which one vertex is distinguished as the ``root''. Perhaps I should root the strict triangulations in some way and try to enumerate the rooted ones. Eventually I decided that the rooting should consist of the choice of a face, edge and vertex, mutually incident\ldots{}. I am not sure what I would have replied at this stage if I had been asked why I preferred these rooted triangulations to the unrooted ones\ldots{}. Later I realized that the distinguishing feature and the great advantage of rooted maps is that they have no symmetry. Automorphisms seem to complicate enumerative problems. (From Chapter 10 of W. T. Tutte, \emph{Graph Theory As I Have Known It}, Oxford, 1998.) \end{quote} For a combinatorial map $(D,(\sigma,\alpha,\phi))$, choosing ``a face, edge and vertex, mutually incident'' is equivalent to choosing a dart $r \in D$: the root vertex, edge, and face can then be computed as the orbits of $r$ under the three permutations. Rooted combinatorial maps may be organized into another category: \begin{definition} \label{def_rcm}\hypertarget{def_rcm}{} The \textbf{category of rooted combinatorial maps} $CM_\bullet$ is defined as follows: \begin{itemize}% \item objects are pairs of a map $M = (D,(\sigma,\alpha,\phi))$ together with a distinguished dart $r \in D$ called the \emph{root}. \item morphisms $(M,r) \to (M',r')$ are map morphisms $h : M \to M'$ in $CM$ which preserve the root $h(r) = r'$. \end{itemize} \end{definition} Note that $CM_\bullet$ is equivalent to the [[comma category]] $1 \downarrow U$ of the singleton set 1 with the forgetful functor $U : CM \to Set$. Now we have the following basic observations, in line with the above remarks by Tutte: \begin{prop} \label{}\hypertarget{}{} For $M = (D,(\sigma,\alpha,\phi))$ a combinatorial map, the automorphism group $Aut(M)$ is by definition the subgroup of permutations on $D$ which commute with $\sigma$ and $\alpha$ and $\phi$, i.e., the [[centralizer]] of $\langle\sigma,\alpha,\phi\rangle$. \end{prop} \begin{prop} \label{}\hypertarget{}{} For $(M,r)$ a rooted combinatorial map, the automorphism group $Aut(M,r)$ is always trivial. In particular, if $h : (M,r) \to (M,r)$ is an endomorphism of $(M,r)$ in the category of rooted maps $CM_\bullet$, then $h$ must be the identity morphism. \end{prop} \begin{proof} Let $d \in D$ be any dart of $M$. Since the action of $\mathcal{C}_2^+$ is transitive, there is some word $w \in \mathcal{C}_2^+$ such that $d = r * w$, and therefore $h(d) = h(r * w) = h(r) * w = r * w = d$. \end{proof} \hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts} \begin{itemize}% \item [[cartographic group]] \item [[topological map]] \item [[child's drawing]] \item [[ribbon graph]] \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} \begin{itemize}% \item J. Edmonds (1960), A combinatorial representation for polyhedral surfaces, \emph{Notices Amer. Math. Soc.} 7, 646. \item A. Jacques (1970), Constellations et graphes topologiques, \emph{Colloque Math. Soc. Janos Bolyai}, 657-672. \item W. T. Tutte. What is a map? In \emph{New Directions in Graph Theory} (ed. F. Harary), Academic Press, New York, 309-325, 1973. \item W. T. Tutte. Duality and Trinity. In \emph{Infinite and Finite Sets (III)}, Colloq. Math. Soc. Janos Bolyai, vol. 10, 1459-1472, North Holland, Amsterdam, 1975. \item [[Gareth A. Jones]] and [[David Singerman]], Theory of Maps on Orientable Surfaces. Proceedings of the London Mathematical Society, 37:273-307, 1978. \item [[Gareth Jones]] and [[David Singerman]]. Maps, hypermaps, and triangle groups. In \emph{The Grothendieck Theory of Dessins d'Enfants}, [[L. Schneps]] (ed.), London Mathematical Society Lecture Note Series 200, Cambridge University Press, 1994. \item [[Sergei K. Lando]] and [[Alexander K. Zvonkin]], \emph{Graphs on Surfaces and Their Applications}, Springer, 2004. \item Samuel Vidal, \emph{Groupe Modulaire et Cartes Combinatoires. G\'e{}n\'e{}ration et Comptage.} PhD Thesis, Universit\'e{} Lille I, France, July 2010. \href{http://www.cafemath.fr/articles/thesis.pdf}{pdf} \item [[Alexander K. Zvonkin]], Functional Composition is a Generalized Symmetry, \emph{Symmetry: Culture and Science} Vol. 21, Nos.1-4, 333-368, 2010. (\href{https://www.labri.fr/perso/zvonkin/Research/tesselations.pdf}{pdf}) \item P. Zinn-Justin and J.-B. Zuber, Matrix Integrals and the Generation and Counting of Virtual Tangles and Links, \emph{Journal of Knot Theory and Its Ramifications}, 13:03, May 2004. (\href{http://arxiv.org/abs/math-ph/0303049v2}{arXiv}) \item Wikipedia page: \href{https://en.wikipedia.org/wiki/Combinatorial_map}{Combinatorial map} \end{itemize} [[!redirects algebraic map]] [[!redirects algebraic maps]] [[!redirects combinatorial maps]] [[!redirects combinatorial hypermap]] [[!redirects combinatorial hypermaps]] [[!redirects hypermap]] [[!redirects hypermaps]] \end{document}