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

\usepackage[utf8]{inputenc}
\usepackage{amsmath,amsthm, amssymb}
\usepackage{tikz,color}
\usepackage{hyperref}
\usepackage{todonotes}
\usepackage{cleveref}
\usepackage{caption}
\usepackage{subcaption}
\usetikzlibrary{calc,math}
\usepackage{diagbox}
\usetikzlibrary{intersections}


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

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{question}[theorem]{Question}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{openproblem}[theorem]{Open Problem}


\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\permutahedralTiling}[1]{\mathcal{PT}_{#1}}
\newcommand{\heawoodGraph}[1]{H_{#1}}
\newcommand{\heawoodComplex}[1]{\mathcal{HC}_{#1}}
\newcommand{\affineGraph}[1]{\widetilde{G}_{#1}}
\newcommand{\HHaffine}{\widetilde{\mathcal{H}}}
\newcommand{\complexAffine}[1]{\widetilde{\mathcal{C}}_{#1}}
\newcommand{\latticeAffine}[1]{\widetilde{\mathcal{L}}_{#1}} % weight lattice 
\newcommand{\sublatticeAffine}[1]{\widetilde{\mathcal{S}}_{#1}} % sublattice
\newcommand{\fundamentalvectorsAffine}[1]{\widetilde F_{#1}} 
\newcommand{\fundamentalvectors}[1]{F_{#1}} 
\newcommand{\lattice}[1]{\mathcal{L}_{#1}} % weight lattice 
\newcommand{\torus}[1]{\mathcal{T}_{#1}} % torus 
\newcommand{\sublattice}[1]{\mathcal{S}_{#1}} % sublattice
\newcommand{\x}{\mathbf{x}}
\newcommand{\y}{\mathbf{y}}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\B}{\mathbf{B}} %ordered partition
\newcommand{\perm}[1]{\operatorname{Perm}_{#1}}
\newcommand{\fundamentaltile}[1]{P_{#1}}
\newcommand{\conv}{\operatorname{conv}}
\newcommand{\vertices}{\operatorname{Vert}}
\newcommand{\equivalent}[1]{\sim_{#1}}
\newcommand{\Zrowspan}[1]{\mathbb{Z}\text{-rowspan}(#1)}
\newcommand{\Zspan}[1]{\mathbb{Z}\text{-span}(#1)}
\newcommand{\parallelepipedDomainAffine}[1]{\widetilde {\mathcal{D}}^{\operatorname{par}}_{#1}}
\newcommand{\permutahedronDomainAffine}[1]{\widetilde {\mathcal{D}}^{\operatorname{perm}}_{#1}}
\newcommand{\parallelepipedDomain}[1]{{\mathcal{D}}^{\operatorname{par}}_{#1}}
\newcommand{\permutahedronDomain}[1]{{\mathcal{D}}^{\operatorname{perm}}_{#1}}

\newcommand{\heawoodFigure}[4]{
        % #1 = k_1  
        % #2 = k_2  
        % #3 = k_3  
        % #4 = scale?  0.3 is good for a small graph
        \begin{tikzpicture}%
            	[x={(240:2cm)},
            	y={(0:2cm)},
            	z={(120:2cm)},
                scale=#4,
                every node/.append style={circle,draw=black,fill=white,inner sep=1.8pt,align=center},
                boundary style one/.style={->, orange, ultra thick},
                boundary style two/.style={->, bluishgreen, ultra thick},
                boundary style three/.style={->, skyblue, ultra thick},
                ]
        
            % Modify these parameters to determine the size of the graph:
            \def\kone{#1}
            \def\ktwo{#2}
            \def\kthree{#3}


            % Side lengths (optional - remove if not needed)
            \node[draw=white] at ($(3,0,0)+{\kthree+0.8}*(0,0,3)$) {\kone};
            \node[draw=white] at ($(0,3,0)+{\kone+0.8}*(3,0,0)$) {\ktwo};
            \node[draw=white] at ($(0,0,3)+{\ktwo+0.8}*(0,3,0)$) {\kthree};

            % Shaded hexagon
            \coordinate (h1) at ($(3,2,1)+\kone*(3,0,0)$);
            \coordinate (h3) at ($(1,3,2)+\ktwo*(0,3,0)$);
            \coordinate (h5) at ($(2,1,3)+\kthree*(0,0,3)$);
            \coordinate (h2) at ($(h1)+(h3)$);
            \coordinate (h4) at ($(h3)+(h5)$);
            \coordinate (h6) at ($(h5)+(h1)$);
            
            \draw[draw=white, fill=black!10] (h1) -- (h2) -- (h3) -- (h4) -- (h5) -- (h6) -- cycle;

            % Central hexagon
            \draw[draw=white, fill=blue!20] (1,2,3) -- (2,1,3) -- (3,1,2) -- (3,2,1) -- (2,3,1) -- (1,3,2) -- cycle;

            % FUNDAMENTAL TILE:
            \foreach \a in {0,...,\kone}{
                \foreach \b in {0,...,\ktwo}{
                    \foreach \c in {0,...,\kthree}{
                        \begin{scope}[shift={($\a*(3,0,0)+\b*(0,3,0)+\c*(0,0,3)$)}]
                            \node (\a\b\c 123) at (1,2,3) {};
                            \node (\a\b\c 213) at (2,1,3) {};
                            \node (\a\b\c 132) at (1,3,2) {};
                            \node (\a\b\c 231) at (2,3,1) {};
                            \node (\a\b\c 312) at (3,1,2) {};
                            \node (\a\b\c 321) at (3,2,1) {};
                        
                            % \draw[blue] (123) -- (213) -- (312) -- (321) -- (231) -- (132) -- (123);      
                            \draw[blue] (\a\b\c 213) -- (\a\b\c 123) -- (\a\b\c 132) -- (\a\b\c 231);      
                        \end{scope}
                    }
                }    
            }    
        
        
            %BOUNDARY: 
            %Boundary edges one
            \begin{scope}[shift={($\kthree*(0,0,3)$)}]
            \draw[boundary style one] (2,1,3) -- (3,1,2);
            \foreach \i in {1,...,\kone}{
                \begin{scope}[shift={($\i*(3,0,0)$)}]
                        \draw[boundary style one] (1,2,3) -- (2,1,3) -- (3,1,2);
                \end{scope}
                }        
            \end{scope}
            %
            \begin{scope}[shift={(${\ktwo+1}*(0,3,0)$)}]
            \draw[boundary style one] (2,1,3) -- (3,1,2);
            \foreach \i in {1,...,\kone}{
                \begin{scope}[shift={($\i*(3,0,0)$)}]
                        \draw[boundary style one] (1,2,3) -- (2,1,3) -- (3,1,2);
                \end{scope}
                }        
            \end{scope}
            %%%
        
            %Boundary edges two
            \begin{scope}[shift={($\kone*(3,0,0)$)}]
            \draw[boundary style two] (3,2,1) -- (2,3,1);
            \foreach \i in {1,...,\ktwo}{
                \begin{scope}[shift={($\i*(0,3,0)$)}]
                        \draw[boundary style two] (3,1,2) -- (3,2,1) -- (2,3,1);
                \end{scope}
                }        
            \end{scope}
            %
            \begin{scope}[shift={(${\kthree+1}*(0,0,3)$)}]
            \draw[boundary style two] (3,2,1) -- (2,3,1);
            \foreach \i in {1,...,\ktwo}{
                \begin{scope}[shift={($\i*(0,3,0)$)}]
                        \draw[boundary style two] (3,1,2) -- (3,2,1) -- (2,3,1);
                \end{scope}
                }        
            \end{scope}
            %%%
        
            %Boundary edges three
            \begin{scope}[shift={($\ktwo*(0,3,0)$)}]
            \draw[boundary style three] (1,3,2) -- (1,2,3);
            \foreach \i in {1,...,\kthree}{
                \begin{scope}[shift={($\i*(0,0,3)$)}]
                        \draw[boundary style three] (2,3,1) -- (1,3,2) -- (1,2,3);
                \end{scope}
                }        
            \end{scope}
            %
            \begin{scope}[shift={(${\kone+1}*(3,0,0)$)}]
            \draw[boundary style three] (1,3,2) -- (1,2,3);
            \foreach \i in {1,...,\kthree}{
                \begin{scope}[shift={($\i*(0,0,3)$)}]
                        \draw[boundary style three] (2,3,1) -- (1,3,2) -- (1,2,3);
                \end{scope}
                }        
            \end{scope}
            %%%

        \end{tikzpicture}
}

\DeclareRobustCommand{\stirling}{\genfrac{\{}{\}}{0pt}{}} %Stirling numbers of the second kind


%Colors for colorblind equity 
%redone for grayscale 
%there's lots of ways to convert to gray, this is evenly distributing along 0.299R+0.587G+0.114B
\definecolor{blue}{rgb}{0, 0.445, 0.695}
\definecolor{bluishgreen}{rgb}{0, 0.626, 0.456}
\definecolor{red}{rgb}{0.896, 0.395, 0}
\definecolor{purple}{rgb}{0.783, 0.464, 0.640}
\definecolor{skyblue}{rgb}{0.359, 0.752, 0.973}
\definecolor{orange}{rgb}{0.999, 0.706, 0.0}
\definecolor{yellow}{rgb}{0.937, 0.890, 0.258}



%even more colors, generated by 'colorgorical' using the previous colors as inputs
%http://vrl.cs.brown.edu/color
\definecolor{olive}{RGB}{116,141,19}
\definecolor{green}{RGB}{108,208,48}
\definecolor{teal}{RGB}{47,77,62}
\definecolor{turquoise}{RGB}{86,235,211}
\definecolor{lightblue}{RGB}{150,178,153}
\definecolor{blue2}{RGB}{25,50,191}
\definecolor{indigo}{RGB}{142,128,251}
\definecolor{indigo2}{RGB}{114,32,246}
\definecolor{lightpurple}{RGB}{243,197,250}
\definecolor{purple2}{RGB}{105,66,131}
\definecolor{magenta}{RGB}{206,43,188}
\definecolor{brown}{RGB}{110,57,13} 


\newcommand{\JSD}[1]{\todo[size=\footnotesize,color=skyblue,inline]{#1  \hfill --- J.}} %Joseph
\newcommand{\cesar}[1]{\todo[size=\footnotesize,color=orange!30,inline]{#1  \hfill --- C.}}
\newcommand{\cesarm}[1]{\todo[size=\footnotesize,color=orange!30]{#1  \hfill --- C.}}
\newcommand{\cesarforjoseph}[1]{\todo[size=\footnotesize,color=red!30,inline]{For Joseph: #1  \hfill --- C.}}

\newcommand{\defn}[1]{{\color{green!50!black}\emph{#1}}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%  Macros to make hyperbolic tikz drawings         %%%%
%%%%  taken from Andrew Stacey on Tex Stack exchange  %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\makeatletter
\def\hyper@x#1,#2\relax{#1}
\def\hyper@y#1,#2\relax{#2}
\def\hyper@coords#1{#1}

\newif\ifhyper@vertical

\def\hyper@disc@computer#1#2{%
  \edef\hyper@toscan{(#1)}
  \tikz@scan@one@point\hyper@coords\hyper@toscan
  \edef\hyper@sx{\the\pgf@x}
  \edef\hyper@sy{\the\pgf@y}
  \edef\hyper@toscan{(#2)}
  \tikz@scan@one@point\hyper@coords\hyper@toscan
  \edef\hyper@ex{\the\pgf@x}
  \edef\hyper@ey{\the\pgf@y}
  \pgfmathsetmacro{\hyper@det}{\hyper@sx * \hyper@ey - \hyper@sy * \hyper@ex}
  \pgfmathparse{\hyper@det == 0 ? "\noexpand\hyper@verticaltrue" : "\noexpand\hyper@verticalfalse"}
  \pgfmathresult
  \ifhyper@vertical
  \edef\hyper@cmd{-- (\tikztotarget)}
  \else
  \pgfmathsetmacro{\hyper@mx}{(\hyper@ex + \hyper@sx)/2}
  \pgfmathsetmacro{\hyper@my}{(\hyper@ey + \hyper@sy)/2}
  \pgfmathsetmacro{\hyper@dx}{\hyper@ex - \hyper@sx}
  \pgfmathsetmacro{\hyper@dy}{\hyper@ey - \hyper@sy}
  \pgfmathsetmacro{\hyper@dradius}{\pgfkeysvalueof{/tikz/hyperbolic disc radius}}
  \pgfmathsetmacro{\hyper@t}{((\hyper@dradius)^2 - \hyper@sx * \hyper@ex - \hyper@sy * \hyper@ey)/(2 * (\hyper@sx * \hyper@ey - \hyper@sy * \hyper@ex))}
  \pgfmathsetmacro{\hyper@radius}{sqrt((\hyper@t)^2 + .25) * veclen(\hyper@dx,\hyper@dy)}
  \pgfmathsetmacro{\hyper@cx}{\hyper@mx + \hyper@t * \hyper@dy}
  \pgfmathsetmacro{\hyper@cy}{\hyper@my - \hyper@t * \hyper@dx}
  \pgfmathsetmacro{\hyper@sangle}{atan2(\hyper@sy-\hyper@cy,\hyper@sx - \hyper@cx)}
  \pgfmathsetmacro{\hyper@eangle}{atan2(\hyper@ey-\hyper@cy,\hyper@ex - \hyper@cx)}
  \pgfmathsetmacro{\hyper@eangle}{\hyper@eangle > \hyper@sangle + 180 ? \hyper@eangle - 360 : \hyper@eangle}
  \edef\hyper@cmd{arc[radius=\hyper@radius pt, start angle=\hyper@sangle, end angle=\hyper@eangle]}
  \fi
}

\tikzset{%
  hyperbolic disc radius/.initial={1cm},
  hyperbolic disc/.style={
    to path={
      \pgfextra{\hyper@disc@computer\tikztostart\tikztotarget}
      \hyper@cmd
    }
  },
}

\makeatother



%% define your title in the usual way
\title[Generalized Heawood graphs]{Generalized Heawood graphs and triangulations of tori}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Cesar Ceballos\thanks{\href{mailto:cesar.ceballos@tugraz.at}{cesar.ceballos@tugraz.at}. Both authors were supported by the Austrian Science Fund FWF, Project~P~33278. 
Our work was also supported by the ANR-FWF International Cooperation Project \mbox{PAGCAP}, funded by the FWF Project I 5788.}\addressmark{1} \and Joseph Doolittle\addressmark{1}
}

%% then use \addressmark to match authors to institutions here
\address{
\addressmark{1}TU Graz, Institut f\"ur Geometrie, Kopernikusgasse 24, 8010 Graz, Austria
}

%% 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{The Heawood graph is a remarkable graph that played a fundamental role in the development of the theory of graph colorings on surfaces in the 19th and 20th centuries. 
    Based on permutahedral tilings, we introduce a generalization of the classical Heawood graph indexed by a sequence of positive integers.
    We show that the resulting generalized Heawood graphs are toroidal graphs, which are dual to higher dimensional triangulated tori. We also present explicit combinatorial formulas for their $f$-vectors and study their automorphism groups.  
}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Heawood graph, triangulations of tori, permutahedron, map coloring.}

%% 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{biblio.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 Heawood graph is a remarkable graph which played a fundamental role in the historical development of the theory of map colorings on surfaces. 
The four color theorem is an important result in this area, and perhaps one of the most well known results in mathematics in general. 
It states that for any map on a sphere, for example Europe, there is a coloring of that map with four colors, such that each region (or country) has one color and any two adjacent regions\footnote{Two regions are adjacent if they share a common boundary curve segment, not just a point.} have different colors.  
This problem has an interesting history dating back to 1852, but the theorem was only proved  more than a hundred years later in 1976 by 
%Kenneth Appel and Wolfgang Haken~\cite{AppelHaken_fourColorTheorem_1976,AppelHaken_fourColor_discharging_1977,AppelHaken_fourColor_reducibility_1977,AppelHaken_fourColor_ScientificAmerican_1977} 
Kenneth Appel and Wolfgang Haken~\cite{AppelHaken_fourColor_ScientificAmerican_1977} 
after many false proofs and false counterexamples, and it is the first major result in mathematics that was proved using a computer.

One famous false proof of the four color theorem was given by Alfred Kempe in 1879~\cite{kempe_fourColor_1879}. 
His proof was announced in \emph{Nature}~\cite{kempe_fourColor_Nature_1880} and was regarded as an established fact for more than a decade. 
In 1890, Percy John Heawood found a gap in Kempe's proof, and modified his argument to show that five colors are sufficient to color a map on a sphere~\cite{heawood_torus_1984}. 
This became known as the five color theorem. 

In the same paper~\cite{heawood_torus_1984}, Heawood investigated coloring of maps on other surfaces. 
He showed that $N_p = \left\lfloor \frac{7+\sqrt{1+48p}}{2} \right\rfloor$ colors are sufficient to color a map on the oriented surface of genus $p\geq 1$, where 
$\lfloor x \rfloor$ is the largest integer not greater than $x$. 
For instance, it is possible to color any map on a torus (genus $p=1$ surface) using seven colors. 
Heawood also showed that for $p=1$ the number seven is tight, by showing a map of the torus where seven colors are necessary: a map consisting of seven regions for which any two regions are adjacent to each other. 

\begin{figure}[htb]
    \centering
    \include{figures/heawood2}
    \vspace{-1.1cm}
    \caption{Reproduction of Heawood's map on a torus from~1890. 
    The inner and outer circle are identified to produce a torus.}
    \label{fig_Heawood_newFigure}
\end{figure}


 

The fact that the number $N_p$ is tight for a genus $p$ orientable surface became known as Heawood's Conjecture, and was finally proved in 1968~\cite{ringel_youngs_torusmap_1968}. 
The case~$p=1$ (the torus) is known as the seven color theorem, and has inspired beautiful math-art works. 

 
\begin{figure}[htb]%change to p when figures are back
%    \begin{subfigure}[b]{0.48\textwidth}
    \begin{subfigure}[b]{0.32\textwidth}
    \centering
%     HeawoodFigure111
    \heawoodFigure{1}{1}{1}{0.20}
    \caption{$\kk=(1,1,1)$}
    \label{fig_heawoods_dimension2_a}
    \end{subfigure}
%    \begin{subfigure}[b]{0.48\textwidth}
%    \centering
%%     HeawoodFigure121
%    \heawoodFigure{1}{2}{1}{0.20}
%    \caption{$\kk=(1,2,1)$}
%    \end{subfigure}
%    %
%    \par\medskip \medskip
%    \begin{subfigure}[b]{0.49\textwidth}
    \begin{subfigure}[b]{0.32\textwidth}
    \centering
%     HeawoodFigure222
    \heawoodFigure{2}{2}{2}{0.15}
    \caption{$\kk=(2,2,2)$}
    \end{subfigure}
%    \begin{subfigure}[b]{0.49\textwidth}
%    \centering
%%     HeawoodFigure223
%    \heawoodFigure{2}{2}{3}{0.15}
%    \caption{$\kk=(2,2,3)$}
%    \end{subfigure}
%    %
%    \par\medskip \medskip 
%    \begin{subfigure}[b]{0.49\textwidth}
    \begin{subfigure}[b]{0.32\textwidth}
    \centering
%     HeawoodFigure312
     \heawoodFigure{3}{1}{2}{0.15}
    \caption{$\kk=(3,1,2)$}
    \label{fig_heawoods_dimension2_e}
    \end{subfigure}
%    \begin{subfigure}[b]{0.49\textwidth}
%    \centering
%%     HeawoodFigure321
%    \heawoodFigure{3}{2}{1}{0.15}
%    \caption{$\kk=(3,2,1)$}
%    \end{subfigure}
    \caption{Examples of the Heawood graph $\heawoodGraph{\kk}$ in dimension 2. The opposite sides (with the same color) are identified, making this graph a toroidal graph. The torus is the gray hexagon with opposite edges identified.}
    \label{fig_heawoods_dimension2}
\end{figure}

The Heawood graph is defined as the graph of Heawood's map: its vertices are the common points of three pairwise adjacent regions, and the edges are the lines connecting these points. 
It is a toroidal and distance-transitive graph on 14 vertices and 21 edges.
Our favorite representation of Heawood's graph is illustrated in~\Cref{fig_heawoods_dimension2_a}, which is based on a highly symmetric representation due to Leech in~\cite[Figure~2]{leech_seven_1955}.
Note that here, the graph is the graph induced by the edge graph of the seven hexagons, where the boundary is identified by gluing the opposite colored lines as illustrated.

The main purpose of this paper is to introduce a generalization $\heawoodGraph{\kk}$ of Heawood's graph that extends Leech's representation. 
Our generalization is indexed by a sequence $\kk=(k_1,\dots,k_{d+1})\in \N^{d+1}$ of positive integers for some~$d\geq 2$, and recovers the classical Heawood graph when $\kk=(1,1,1)$. 
As in the classical case, we show that $\heawoodGraph{\kk}$ is a toroidal graph which is naturally embedded in a~$d$-dimensional torus.  





When there are three parameters, the generalized Heawood graph $\heawoodGraph{(k_1,k_2,k_3)}$ is a 2-dimensional generalization of the classical Heawood graph. 
It is obtained by gluing together $\prod (k_i+1) - \prod k_i$ regular hexagons: From a ``central" hexagon one adds $k_i$ hexagons pointing in the direction at angle $(i-2) \frac{2\pi}{3}$ for $i=1,2,3$; then fill the ``big hexagon'' that they generate with other small hexagons.
Several examples are illustrated in~\Cref{fig_heawoods_dimension2}.
We also provide three different choices of fundamental domain in~\Cref{fig_fundamentaldomains}, where the torus can be visualized in its more common rectangular presentation.


\begin{figure}[htb]
    \centering
    \include{figures/fig_fundamentaldomains}
    \caption{Different presentations of the fundamental domain for the Heawood graphs $\heawoodGraph{(1,1,1)}$, $\heawoodGraph{(2,2,2)}$ and %$\heawoodGraph{(1,2,3)}$
    $\heawoodGraph{(3,1,2)}$.}
    \label{fig_fundamentaldomains}
\end{figure}



The case $d=3$ gives 3-dimensional generalizations of the Heawood graph. The smallest choice of parameters is $\heawoodGraph{(1,1,1,1)}$, which is obtained by gluing $15=2^4-1^4$ polytopes that are 3-dimensional permutahedra, see~\Cref{fig_permutahedraltiling3D}.
The boundary of the result is identified to itself to form the complex into a 3-dimensional torus (see~\Cref{sec_heawoodComplex}).  


\begin{figure}[htb]
    \centering
    % This is the figure which shows a 1111 permutahedra stacked together. Temporarily removed so that compile times are quicker.
%    \include{figures/figure1111collapsed}
    \include{figures/figure1111_heawood_and_collapsed}
    \caption{The Heawood graph $\heawoodGraph{(1,1,1,1)}$ is the edge graph of this portion of the 3-dimensional permutahedral tiling after properly identifying its boundary by translations (see~\Cref{sec_heawoodComplex}), making it into a toroidal graph.}
    \label{fig_permutahedraltiling3D}
\end{figure}

%Our motivation for this work arose in our study of Gil Kalai's conjecture  on reconstruction of simplicial spheres~\cite{blind_puzzles_1987,kalai_blog_2009}.
%The classical Heawood graph is the dual graph of a minimal triangulation of the 2-dimensional torus, which we used in~\cite{ceballosdoolittle_subword_2022} to provide examples of non-reconstructable triangulated 2-tori.  
%Except for the triangulation dual to the classical Heawood graph $\heawoodGraph{(1,1,1)}$, the techniques from~\cite{ceballosdoolittle_subword_2022} can not be applied to any other $\heawoodGraph{\kk}$, because their automorphism group coincides with the automorphism group of their dual graph (the generalized Heawood graph). 

One special object of interest is the dual triangulation of $\heawoodGraph{(1,1,\dots,1)}$.
This triangulation consists of $2^{d+1}-1$ vertices and appeared in the work of Wolfgang K\"uhnel and Gunter Lassmann from the 1980's in~\cite{kuhnel_lassmann_threedtorus_1984,kuhnel_lassmann_symmetrictorii_1988}.
Interestingly, it is conjectured to be a minimal triangulation of the $d$-dimensional torus~\cite[Conjecture 21]{lutz_triangulated_2005}. 
%(see \Cref{conj_minimaltriangulation}). 
%This conjecture holds in dimensions $d=1,2$ ($d=1$ is trivial and $d=2$ corresponds to the known classical Heawood graph case), and is supported by strong computational evidence in dimension $d=3$~\cite{lutz_triangulated_2005}. 


A longer version of this extended abstract with more details and proofs is available at~\cite{ceballosdoolittle_heawood_2023}.






\section{The generalized Heawood graph}\label{sec_heawood_graph}
The generalized Heawood graph $\heawoodGraph{\kk}$ is indexed by a sequence $\kk=(k_1,\dots,k_{d+1})\in \N^{d+1}$ of positive integers for some~$d\geq 2$. 
It is obtained by making some identifications on an infinite {graph $\affineGraph{d}$}, which is the graph of the $d$-dimensional permutahedral tiling. 
Before explaining this connection, we provide a direct definition in this section. 


%The \defn{graph $\affineGraph{d}$} is the graph whose 
The vertices $\vertices(\affineGraph{d})$ of the  \defn{graph $\affineGraph{d}$} are the elements of the affine~subspace 
\[
\{
\x=(x_1,\dots,x_{d+1}):\ x_1+\dots +x_{d+1}= 1+\dots +(d+1)
\}\subset \R^{d+1}
\]
whose entries are integers containing all the numbers $1,2,\dots, d+1$ mod~$(d+1)$. 
For instance, all permutations of $[d+1]$ satisfy this property. 
Two vertices $\x,\y$ of $\affineGraph{d}$ are connected by an edge if $\y-\x=e_j-e_i$ for some~$i\neq j$, where $e_1,\dots,e_{d+1}$ denote the standard basis vectors in $\R^{d+1}$.
\Cref{fig_permutahedral_tiling_graph_2} shows a portion of the graph $\affineGraph{2}$, where the blue hexagon is the convex hull of all permutations of $[3]$. 

\begin{figure}[htb]
    \centering
%    This figure is of the 2d grid, labeled by extended permutations.
    \include{figures/permutahedral_tiling_graph_2}
    \vspace{-1.3cm}
    \caption{The graph $\affineGraph{2}$ of the permutahedral tiling for $d=2$. 
    Commas and parenthesis are omited for simplicity. 
    An overlined number $\overline k$ represent the negative number $-k$. For instance, $\overline{1}43$ represents the vertex $(-1,4,3)$.}
    \label{fig_permutahedral_tiling_graph_2}
\end{figure}

For $\kk=(k_1,\dots,k_{d+1})\in \N^{d+1}$ we denote by $M_\kk$ the matrix 

\begin{align}\label{eq_matrix}
M_\kk=
\begin{pmatrix}
    k_1+1  & -k_2 &  &  &&&\\ 
       & k_2+1 & -k_3 &  &&& \\
      &   & \ddots  & \ddots  &&&  \\
    &  &   & \ddots  & \ddots  &&  \\
   & &  &   & k_d+1  & -k_{d+1}    \\
   -k_1 &  &   &   && k_{d+1}+1    \\
\end{pmatrix}
\end{align}
and let $w_1,\dots,w_{d+1}\in \Z^{d+1}$ be the vectors
\begin{align}\label{eq_vector_wi}
w_i = (d+1)e_i - \sum_{j=1}^{d+1} e_j.
\end{align}
Equivalently, $w_i$ has $i$th coordinate equal to $d$ and all other coordinates equal to $-1$.

Note that if $\x\in \vertices(\affineGraph{d})$ then $\x+w_i\in \vertices(\affineGraph{d})$. 
Moreover, if $\x,\y\in\vertices(\affineGraph{d})$ are connected by an edge then $\x+w_i$ and $\y+w_i$ are connected by an edge as well. 
In other words, the graph $\affineGraph{d}$ is invariant under translations by the vectors~$w_1,\dots,w_{d+1}$.   

We denote by $\lattice{d}$ the lattice of integer linear combinations of the \(w_i\)
\begin{align}\label{eq_lattice_one}
\lattice{d} := 
\{
a_1w_1+\dots + a_{d+1}w_{d+1} :\ a_1,\dots,a_{d+1}\in 
\Z^{d+1}\},
\end{align}
and by $\sublattice{\kk}\subset \lattice{d}$ the sublattice 
\begin{align}\label{eq_sublattice}
\sublattice{\kk} := 
\left\{ 
a_1w_1+\dots + a_{d+1}w_{d+1} :\   
\begin{array}{l}
    (a_1,\dots,a_{d+1})=(b_1,\dots,b_{d+1}) M_{\kk} \\ 
    \text{for some } b_1,\dots,b_{d+1}\in \Z
\end{array}
\right\}.
\end{align}
That is, $\sublattice{\kk}$ is the set of linear combinations of $w_1,\dots ,w_{d+1}$ whose coefficient vector $(a_1,\dots,a_{d+1})$ is an integer linear combination of the rows of $M_\kk$. 

We say that $\x,\y\in \vertices(\affineGraph{d})$ are \defn{$\kk$-equivalent}, in which case we write $\x\equivalent{\kk} \y$, if 
\begin{align}
\y=\x+v \text{ for some } v\in \sublattice{\kk}.
\end{align}
%Similarly, 
Two edges of $\affineGraph{d}$ are \defn{$\kk$-equivalent} if one is a translation of the other by a vector in $\sublattice{\kk}$. 

\begin{definition}[Generalized Heawood graph]
\label{def_heawoodGraph}
Let $\kk=(k_1,\dots,k_{d+1})\in \N^{d+1}$ be a sequence of positive integers for some $d\geq 2$. 
The \defn{Heawood graph} $\heawoodGraph{\kk}$ is the graph whose vertices and edges are the $\kk$-equivalent classes of vertices and edges of $\affineGraph{d}$, respectively. 
In other words,~$\heawoodGraph{\kk}$ is the graph obtained by identifying vertices and edges of $\affineGraph{d}$ up to translation by vectors in $\sublattice{\kk}$.     
\end{definition}


\begin{example}[Classical Heawood graph]
The classical Heawood graph is obtained when \(d=2\) and $\kk=(1,1,1)$, and is illustrated in~\Cref{fig_figure111}. 
The lattice $\lattice{2}$ consists of integer linear combinations of the vectors 
$w_1=(2,-1,-1)$ ,
$w_2=(-1,2,-1)$,
$w_3=(-1,-1,2)$.

%\begin{align*}
%w_1&=(2,-1,-1) \\
%w_2&=(-1,2,-1) \\
%w_3&=(-1,-1,2)
%\end{align*}
%
The associated matrix is
\begin{align*}
M_{(1,1,1)}=
\begin{pmatrix}
    2  & -1 & \\ 
       & 2 & -1 \\
     -1 &   & 2   \\
\end{pmatrix}
\end{align*}
%
The sublattice $\sublattice{(1,1,1)}$ consists of integer linear combinations of the rows of this matrix, when considered as vectors of coefficients of the $w_i$'s, %:
%\begin{align*}
%2w_1-w_2\\
%2w_2-w_3\\
%2w_3-w_1
%\end{align*}
%
i.e. integer linear combinations of the vectors   
$2w_1-w_2$,
$2w_2-w_3$,
$2w_3-w_1$.

Figure~\ref{fig_figure111} shows a tiling of the plane, where each fundamental tile consists of seven hexagons: one hexagon in the center together with its six surrounding hexagons. The barycenters of the central hexagons correspond exactly to elements of the sublattice $\sublattice{(1,1,1)}$. 
The equivalence relation $\cong_\kk$ then identifies vertices and edges via translations that transform one fundamental tile into another.   
\end{example}

\begin{figure}[htb]
    \centering
    %7 copies of the fundamental tile
    \include{figures/figure111}
    \caption{The classical Heawood graph $\heawoodGraph{(1,1,1)}$ as a quotient of the graph of the permutahedral tiling in dimension two.}
    \label{fig_figure111}
\end{figure}

%\begin{example}[$\kk=(2,3,2)$ for $d=2$]
%Another example, where $\kk=(2,3,2)$, is illustrated in \Cref{fig_fundamentaltile_translates}. 
%The vectors $w_1,w_2,w_3$ are the same as in the previous example, and the matrix is
%
%\begin{align*}
%M_{(2,3,2)}=
%\begin{pmatrix}
%    3  & -3 & \\ 
%       & 4 & -2 \\
%     -2 &   & 3   \\
%\end{pmatrix}
%\end{align*}
%The sublattice $\sublattice{(2,3,2)}$ consists of the integer linear combinations of 
%\begin{align*}
%3w_1-3w_2\\
%4w_2-2w_3\\
%3w_3-2w_1
%\end{align*}
%%
%Figure~\ref{fig_fundamentaltile_translates}  shows a tiling of the plane, where each fundamental tile gives a copy of the Heawood graph $\heawoodGraph{(2,3,2)}$, which is obtained by identifying the boundary of this tile to itself, via translations that transform one fundamental tile into another.  
%\end{example}

Our aim is to prove some structural and enumerative properties of the generalized Heawood graph. Our first result is the following.

\begin{theorem}\label{thm_heawoodgraph}
    The generalized Heawood graph $\heawoodGraph{\kk}$ is a vertex-transitive
    graph with~$d! D_\kk$ many vertices and $\frac{(d+1)!}{2}D_\kk$ many edges, where
    \begin{align}\label{eq_determinat}
    D_{\kk}= \det M_\kk        
    = \prod (k_i+1) -\prod{k_i}. 
    \end{align}
\end{theorem}

Similarly to the classical case, the generalized Heawood graph is the dual graph of a triangulated torus, for which a simple combinatorial formula for its number of faces can be explicitly given.   

We denote by $\stirling{n}{k}$ the Stirling number of the second kind, which counts the number of ways to partition a set of $n$ objects into $k$ non-empty subsets. 
These numbers can be explicitly calculated as 
\begin{align}
    \stirling{n}{k} = 
    \frac{1}{k!} \sum_{i=1}^{k} (-1)^{k-i}{\binom{k}{i}} i^n. 
\end{align}

\begin{theorem}\label{thm_maintheorem}
%Let $\kk=(k_1,\dots,k_{d+1})\in \N^{d+1}$ for some $d\geq 2$.
The generalized Heawood graph $\heawoodGraph{\kk}$ is the dual graph of a triangulation of a $d$-dimensional torus with $f$-vector $(f_0,f_1,\dots ,f_d)$ determined by
\begin{align}
f_i=i! \, \stirling{d+1}{i+1} \, D_{\kk}.    
\end{align}
In particular, 
\begin{align}
    f_0 = D_\kk, \qquad
    f_d = d!\, D_\kk, \qquad
    f_{d-1} = \frac{(d+1)!}{2}\, D_\kk.
\end{align}
\end{theorem}

Table~\ref{table_modified_stirling} shows the factor
$c(i,d):=f_i/D_\kk$ 
for some small values. 

\begin{table}[htb]
    \centering
    \begin{tabular}{|l|cccccc|}
    \hline
    \diagbox{$d$}{$i$} & $0$ & $1$ & $2$ & $3$ & $4$ & $5$\\
    \hline
    $2$ & $1$ & $3$ & $2$ &&&\\
    $3$ & $1$ & $7$ & $12$  & $6$ &&\\
    $4$ & $1$ & $15$ & $50$ & $60$ & $24$ &\\
    $5$ & $1$ & $31$ & $180$ & $390$ & $360$ & $120$\\
    \hline
    \end{tabular}
    \caption{The factor $c(i,d)$ for some small values of $i$ and $d$.}
    \label{table_modified_stirling}
\end{table}


\begin{example}[$d=2$]
We consider the classical Heawood graph, when $\kk=(1,1,1)$. 
The factor $D_{(1,1,1)}=2^3-1^3=7$ counts the number of hexagons in~\Cref{fig_heawoods_dimension2_a}. The $f$-vector of its dual 2-dimensional triangulated torus is 
\[
(1\cdot 7, 3\cdot 7, 2\cdot 7)=(7,21,14).
\]
Interpreting this in the graph setting, we have 7 hexagons, 21 edges, and 14 vertices. 

When $d=2$, with a general \(\kk\), we have $D_\kk$ many hexagons, $3D_\kk$ many edges, and $2D_\kk$ many vertices. 
Table~\ref{table_counting_dim2} shows these numbers for all the examples in~\Cref{fig_heawoods_dimension2}.

\begin{table}[htb]
    \centering
    \begin{tabular}{|l|ccc|}
    \hline
    \diagbox{$\kk$}{$i$} & 0 & 1 & 2 \\
    \hline
    $(1,1,1)$ & $1\cdot 7$ & $3\cdot 7$ & $2\cdot 7$\\
%    $(1,2,1)$ & $1\cdot 10$ & $3\cdot 10$ & $2\cdot 10$\\
    $(2,2,2)$ & $1\cdot 19$ & $3\cdot 19$ & $2\cdot 19$\\
%    $(2,2,3)$ & $1\cdot 24$ & $3\cdot 24$ & $2\cdot 24$\\
%    $(3,2,1)$ & $1\cdot 18$ & $3\cdot 18$ & $2\cdot 18$\\
    $(3,1,2)$ & $1\cdot 18$ & $3\cdot 18$ & $2\cdot 18$\\
    \hline
    \end{tabular}
    \caption{Number of hexagons, edges, and vertices for the Heawood graphs in~\Cref{fig_heawoods_dimension2}.}
    \label{table_counting_dim2}
\end{table}
\end{example}









\section{The affine arrangement and the permutahedral tiling}\label{sec_affineArrangement_permutahedralTiling}
In order to prove these results, it is useful to build on the connection with permutahedral tilings and their dual affine arrangements. 
We consider the collection of affine hyperplanes 
\[
H^k_{ij}= 
\{
\x\in \R^{d+1} :\ x_j-x_i=k
\} 
\]
for $1\leq i < j \leq d+1$ and $k\in \Z$.

The \defn{affine Coxeter arrangement} $\HHaffine_d$ of type $\widetilde A_d$ is the restriction of this arrangement to the hyperplane $V=\{\x\in \R^{d+1} :\ x_1+\dots +x_{d+1}=0\}$.
For $d=2$, this is the arrangement of affine hyperplanes of a triangular lattice, which is illustrated on the left of~\Cref{fig_triangularlattice_hexagonallattice}.

\begin{figure}[htb]
\centering
\include{figures/C2anddual}
    \caption{A finite piece of the simplicial complex $\complexAffine{2}$ of the affine Coxeter arrangement of type $\widetilde A_2$ (left). A finite piece of its dual tiling of space by permutahedra $\permutahedralTiling{2}$ (right).}
    \label{fig_triangularlattice_hexagonallattice}
\end{figure}

In general, the arrangement $\HHaffine_d$ decomposes the space $V$ into an infinite number of simplices, giving rise to an infinite simplicial complex that we denote by $\complexAffine{d}$. The vertices of this complex are the elements of
\begin{align}\label{eq_lattice_affine_one}
\latticeAffine{d} :=
\{
\x\in V :\ x_j-x_i \in \Z, \text{ for all } 1\leq i < j \leq d+1 
\}.    
\end{align}
This set is a lattice, which is known as the \defn{weight lattice} of type $A_d$. It is generated by integer linear combinations of the vectors $\widetilde w_1, \dots ,\widetilde w_{d+1}$ determined by $(d+1) \widetilde w_i = w_i$, as defined in~\eqref{eq_vector_wi}. They satisfy the relation
\begin{align}
\widetilde w_1 + \dots + \widetilde w_{d+1} = 0.    
\end{align}
%The weight lattice is isomorphic to the quotient 
%\begin{align}
%    \latticeAffine{d} \cong \Z^{d+1}/ (1,\dots,1).
%\end{align}
%
%
%For instance, for $d=2$ the vertices of the complex $\complexAffine{2}$ are the vertices of the triangular tiling, and are spanned by the vectors
%\begin{align*}
%    \widetilde w_1 &= \frac{1}{3} (2,-1,-1) \\
%    \widetilde w_2 &= \frac{1}{3} (-1,2,-1) \\
%    \widetilde w_3 &= \frac{1}{3} (-1,-1,2)
%\end{align*}
%subject to the relation $\widetilde w_1+\widetilde w_2+\widetilde w_3=0$, see~\Cref{fig_triangularlattice_hexagonallattice} (left).

For $d=2$, the dual of the triangular lattice is the hexagonal lattice, which is illustrated on the right of~\Cref{fig_triangularlattice_hexagonallattice}.
This generalizes to higher dimensions, where the dual of the complex $\complexAffine{d}$ is a combinatorial structure known as the permutahedral tiling. 

The \defn{permutahedron} $\perm{d}$ is the convex hull of all permutations of $[d+1]$:
\begin{align}
\perm{d} =
\conv \left\{
(i_1,\dots,i_{d+1}): \text{ for } \{i_1,\dots,i_{d+1}\}=[d+1] 
\right\} \subseteq \R^{d+1}.
\end{align}

The \defn{permutahedral tiling} $\permutahedralTiling{d}$ is the infinite tiling of the affine subspace
\begin{align}
\{
\x\in \R^{d+1}:\ x_1+\dots+x_{d+1}=1+\dots+(d+1)
\}    
\end{align}
whose tiles are translates
$\perm{d} + v$ of the permutahedron, for $v\in \lattice{d}$.
 An example for $d=2$ is shown on the right of~\Cref{fig_triangularlattice_hexagonallattice}.
% In~\Cref{fig_permutahedron3D}, we illustrate the $d=3$ dimensional permutahedron together with the four translation directions $w_1,w_2,w_3,w_4$. 



%\begin{figure}[htb]
%    \centering
%    \include{figures/figure232}
%    \caption{The Heawood graph $\heawoodGraph{(2,3,2)}$ as a quotient of the graph of the permutahedral tiling in dimension two. 
%    Translations of the fundamental tile $\fundamentaltile{(2,3,2)}$ give a tiling of space.}
%    \label{fig_fundamentaltile_translates}
%\end{figure}




%\begin{figure}[htb]
%    \centering
%\include{figures/figureWs}
%    \caption{The 3-dimensional permutahedron.}
%    \label{fig_permutahedron3D}
%\end{figure}








%\begin{figure}[htb]
%\centering
%%   This is the figure which shows four 1111 permutahedra stacked together. Temporarily removed so that compile times are quicker.
% \include{figures/figureFour1111}
%\caption{The fundamental tile  \(\fundamentaltile{(1,1,1,1)}\), and three translations of it with offsets $2w_1-w_2$, $2w_2-w_3$, and $2w_3-w_4$.}
%\label{fig_figureFour1111}
%\end{figure}

%\begin{figure}[htb]
%    \centering
%%   This is the figure which shows an expanded 1111 permutahedra. Temporarily removed so that compile times are quicker.
% \include{figures/figure1111expand}
%    \caption{The fundamental tile \(\fundamentaltile{(1,1,1,1)}\), expanded so that the interior is visible.}
%    \label{fig_figure1111expand}
%\end{figure}
%
%\begin{figure}[htb]
%    \centering
%%This is the figure which shows a 2223 collection of permutahedra. Temporarily removed so that compile times are quicker.
% \include{figures/figure2223expand}
%    \caption{The fundamental tile \(\fundamentaltile{(2,2,2,3)}\), expanded so that the interior is visible. The differently colored permutahedra indicate the \(w_i\) directions.}
%    \label{fig_figure2223expand}
%\end{figure}







\section{The triangulated torus and the Heawood complex}

\subsection{The triangulated torus}
We consider the \defn{sublattice} $\sublatticeAffine{\kk}\subset \latticeAffine{d}$ defined by
\begin{align}\label{eq_sublatticeAffine}
\sublatticeAffine{\kk} := 
\left\{ 
a_1\widetilde w_1+\dots + a_{d+1}\widetilde w_{d+1} :\   
\begin{array}{l}
    (a_1,\dots,a_{d+1}) = (b_1,\dots,b_{d+1}) M_{\kk}  \\ 
    \text{for some } b_1,\dots,b_{d+1}\in \Z
\end{array}
\right\}.
\end{align}
Its elements are integer linear combinations of the vectors $\widetilde w_1,\dots,\widetilde w_{d+1}$, whose vector of coefficients is an integer linear combination of the rows of the matrix $M_\kk$. 

We say that two faces $F,F'\in \complexAffine{d}$ are \defn{$\kk$-equivalent}, and write \mbox{$F\equivalent{\kk} F'$}, if  $F'=F+v$ for some $v\in \sublatticeAffine{\kk}$. 
That is, the face $F'$ is a translation of $F$ by $v\in \sublatticeAffine{d}$. 

\begin{definition}[The torus]
\label{def_torus}
%Let $\kk=(k_1,\dots,k_{d+1})\in \N^{d+1}$ be a sequence of positive integers for some $d\geq 2$. 
The \defn{quotient complex} 
$
\torus{\kk}= \complexAffine{d} / \sublatticeAffine{\kk}
$
is the simplicial complex of $\kk$-equivalent classes of faces of $\complexAffine{d}$. 
In other words,~$\torus{\kk}$ is the simplicial complex of faces of $\complexAffine{d}$ up to translation by vectors in $\sublatticeAffine{\kk}$.   
%A face class is contained in another if there is an element representative of the first that is contained in an element representative of the second.
\end{definition}

We define the \defn{fundamental vectors} with respect to $\kk$ as the elements of the set
\begin{align}\label{eq_fundamentalvectorsAffine}
\fundamentalvectorsAffine{\kk} = 
\left\{a_1\widetilde w_1+\dots + a_{d+1} \widetilde w_{d+1} :
\begin{array}{l}
    \ 0 \leq a_i \leq k_i\in \Z^{d+1}  \\ 
    \text{at least one } a_i = 0
\end{array}
\right\}.
\end{align}

\begin{lemma}\label{lem_quotient_size_affine}
The quotient $\latticeAffine{d}/\sublatticeAffine{\kk}$ is finite. Its cardinality is
\mbox{$
%|\latticeAffine{d}/\sublatticeAffine{\kk}| =
\det M_\kk
= \prod (k_i+1) -\prod{k_i}$}.
The fundamental vectors in $\fundamentalvectorsAffine{\kk}$ are element representatives of the classes of $\latticeAffine{d}/\sublatticeAffine{\kk}$. 
\end{lemma}

\begin{proposition}\label{prop_torus}
$\torus{\kk}$ is a triangulated $d$-dimensional torus on $D_\kk=\det M_\kk$ many vertices. 
\end{proposition}


The proof of this proposition is based on a parallelepiped domain of $\torus{\kk}$, which we explain in the longer version of this manuscript~\cite{ceballosdoolittle_heawood_2023}, see the first illustration in~\Cref{fig_domains}. 

%\begin{figure}[htb]
%\centering
%\include{figures/fig_permutahedraldomain}
%\caption{The parallelepiped domain and the permutahedron domain of~$\torus{(3,1,2)}$.}
%\label{fig_parallelepiped_permutahedron_domains}
%\end{figure}

\begin{figure}[htb]
\centering
\include{figures/fig_domains}
\caption{The parallelepiped domain and the permutahedron domain of~$\torus{(3,1,2)}$, and the fundamental tile and the permutahedron domain of~$\heawoodComplex{(3,1,2)}$.}
\label{fig_domains}
\end{figure}


We also provide a permutahedral domain, see the second illustration in~\Cref{fig_domains}, which leads to the following independent result.  

\begin{proposition}\label{prop_permutahedron_torus}
The permutahedron $\perm{d}$ with opposite facets identified by translation is a topological $d$-dimensional torus. 
\end{proposition}



\subsection{The Heawood complex}\label{sec_heawoodComplex}
We say that two faces $\B,\B'$ of the permutahedral tiling $\permutahedralTiling{d}$ are \defn{$\kk$-equivalent}, and write \mbox{$\B\equivalent{\kk} \B'$}, if 
$\B'=\B+v$ for some $v\in \sublattice{\kk}$.
That is, the face $\B'$ is a translation of $\B$ by a vector $v\in \sublattice{\kk}$. 

\begin{definition}[The Heawood complex]
\label{def_heawood_complex}
The \defn{Heawood complex} 
$
\heawoodComplex{\kk}= \permutahedralTiling{d} / \sublattice{\kk}
$
is the polytopal complex of $\kk$-equivalent classes of faces of $\permutahedralTiling{d}$. 
That is,~$\heawoodComplex{\kk}$ is the polytopal complex of faces of $\permutahedralTiling{d}$ up to translation by vectors in $\sublattice{\kk}$.   
%A face class is contained in another if there is an element representative of the first that is contained in an element representative of the second.
\end{definition}

We define 
\begin{align}\label{eq_fundamentalvectors}
\fundamentalvectors{\kk} = 
\left\{a_1 w_1+\dots + a_{d+1} w_{d+1} :
\begin{array}{l}
    \ 0 \leq a_i \leq k_i\in \Z^{d+1}  \\ 
    \text{at least one } a_i = 0
\end{array}
\right\}.
\end{align}

Since $w_i=(d+1)\widetilde w_i$, then the vectors in $\fundamentalvectors{\kk}$ are just the fundamental vectors in~$\fundamentalvectorsAffine{\kk}$, dilated by a factor of $d+1$. 
The \defn{fundamental tile} $\fundamentaltile{\kk}$ is the union of the permutahedra of the form $\perm{d}+v$ with $v\in \fundamentalvectors{\kk}$.
An example of the fundamental tile $\fundamentaltile{(1,1,1)}$, including six translations of it, is illustrated in Figure~\ref{fig_figure111}.

In general, translations of the fundamental tile $\fundamentaltile{\kk}$ by elements of the sublattice $\sublattice{\kk}$ tile space. Thus, the Heawood complex is the complex of faces of this fundamental tile, where the boundary is identified according to how the translations glue together, see also~\Cref{fig_permutahedraltiling3D}. 
%We also describe a permutahedral domain, which is shown in the fourth illustration of~\Cref{fig_domains}.

\begin{proposition}\label{prop_duality_heawood_torus}
The following hold:
\begin{enumerate}
    \item The Heawood graph $\heawoodGraph{\kk}$ is the edge graph of the Heawood complex~$\heawoodComplex{\kk}$.\label{prop_duality_heawood_torus_item1}
    \item The Heawood complex and the torus are dual complexes:  
    $\heawoodComplex{\kk} \cong \torus{\kk}^*$.
    \label{prop_duality_heawood_torus_item2}
    \item The Heawood graph $\heawoodGraph{\kk}$ is the dual graph of the torus $\torus{\kk}$.\label{prop_duality_heawood_torus_item3}
\end{enumerate}
\end{proposition}

This, together with~\Cref{prop_torus}, finishes part of the proof of our main Theorem~\ref{thm_maintheorem}. The proof of the remaining enumerative part can be found in the longer version of this manuscript~\cite{ceballosdoolittle_heawood_2023}. There, we also describe the automorphism groups of the triangulated torus \(\torus{\kk}\) and the generalized Heawood graph \(\heawoodGraph{\kk}\), and discuss about potential generalizations including the hyperbolic setting.

In view of~\Cref{prop_permutahedron_torus}, we finish with the following open question. 

\begin{question}
What is the topology of other families of polytopes with opposite facets identified by translation?
\end{question}

Natural families that fit into this context are
Permutahedra arising from finite Coxeter groups,
Postnikov’s generalized permutahedra obtained by removing some pairs of opposite facets of the classical permutahedron, and 
Zonotopes in general.
A small example of the first and the last is an octagon. Identifying opposite edges of an octagon leads to a topological 2-hole torus.

%
%\begin{figure}[htb]
%\centering
%\include{figures/fig_heawoodcomplex}
%\caption{The fundamental tile and the permutahedron domain of~$\heawoodComplex{(3,1,2)}$.}
%\label{fig_fundamental_tile_and_permutahedron_domain}
%\end{figure}









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