\documentclass[finalversion]{FPSAC2023}
\articlenumber{19}

\usepackage{tabu}
\usepackage{makecell}

\usepackage{mathrsfs}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{proposition}{Proposition}
\newtheorem{question}{Question}
\newtheorem{problem}{Problem}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}

\DeclareMathOperator{\traj}{traj}
\DeclareMathOperator{\midp}{mid}
\DeclareMathOperator{\cyc}{cyc}
\DeclareMathOperator{\area}{area}
\DeclareMathOperator{\perim}{perim}
\DeclareMathOperator{\len}{length}

\newcommand{\CD}[1]{\textcolor{red}{\textsf{#1}}}

\newcommand{\dfn}[1]{\textcolor{blue}{\emph{#1}}}


\title[Triangular-Grid Billiards and Plabic Graphs]{Triangular-Grid Billiards and Plabic Graphs}

\author[Colin Defant and Pakawut Jiradilok]{Colin Defant\thanks{\href{mailto:colindefant@gmail.com}{colindefant@gmail.com}. Supported by the National Science Foundation under Award No.\ 2201907 and by a Benjamin Peirce Fellowship at Harvard University.}\addressmark{1} \and 
Pakawut Jiradilok\thanks{\href{mailto:pakawut@mit.edu}{pakawut@mit.edu}. Supported by Elchanan Mossel's Vannevar Bush Faculty Fellowship ONR-N00014-20-1-2826 and by Elchanan Mossel's Simons Investigator award (622132).}\addressmark{1}}


\address{\addressmark{1}Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA
}

\abstract{Given a polygon $P$ in the triangular grid, we obtain a permutation $\pi_P$ via a natural billiards system in which beams of light bounce around inside of $P$. The different cycles in $\pi_P$ correspond to the different trajectories of light beams. We prove that \[\area(P)\geq 6\cyc(P)-6\quad\text{and}\quad\perim(P)\geq\frac{7}{2}\cyc(P)-\frac{3}{2},\] where $\area(P)$ and $\perim(P)$ are the (appropriately normalized) area and perimeter of $P$, respectively, and $\cyc(P)$ is the number of cycles in $\pi_P$. The inequality concerning $\area(P)$ is tight, and we characterize the polygons $P$ satisfying $\area(P)=6\cyc(P)-6$. These results can be reformulated in the language of Postnikov's plabic graphs as follows. Let $G$ be a connected reduced plabic graph with essential dimension $2$. Suppose $G$ has $n$ marked boundary points and $v$ (internal) vertices, and let $c$ be the number of cycles in the trip permutation of $G$. Then we have \[v\geq 6c-6\quad\text{and}\quad n\geq\frac{7}{2}c-\frac{3}{2}.\] We end with a discussion of numerous ideas for future work. }


\keywords{triangular grid, billiards, plabic graph, essential dimension, trip permutation, cycle}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{BilliardsBib.bib}

\renewbibmacro{in:}{}


\begin{document}

\maketitle

\section{Introduction}

In this extended abstract of the article \cite{DJ}, we introduce a natural class of billiards systems that surprisingly appear to be new. While traditional billiards systems exhibit continuous behavior that is best analyzed from a geometric or analytic point of view, our systems are constrained so that they are essentially combinatorial. Indeed, we will reformulate these systems in terms of trip permutations of Postnikov's plabic graphs. Nevertheless, our proof methods require a heavy dose of Euclidean geometry. These new billiards systems lead to several promising open problems and ideas for future work, some of which we will discuss. 

\section{Triangular-Grid Billiards}
Consider the infinite triangular grid in the plane, scaled so that each equilateral triangular grid cell has side length $1$ and oriented so that some of the grid lines are horizontal. We refer to the sides of these grid cells as \dfn{panes} because we will imagine that each pane either allows light to pass through it (like a window pane) or reflect off of it (like a mirror pane). Define a \dfn{grid polygon} to be a (not necessarily convex) polygon whose boundary is a union of panes. We assume that the boundary of a grid polygon (viewed as a closed curve) does not intersect itself. Suppose $P$ is a grid polygon whose boundary panes are $b_1,\ldots,b_n$, listed clockwise. Pick some boundary pane $b_{i}$, and emit a colored beam of light from the midpoint of $b_i$ into the interior of $P$ so that the light beam forms a $60^\circ$ angle with $b_i$ and travels either northeast, southeast, or west (depending on the orientation of $b_i$). The light beam will travel through the interior of $P$ until reaching the midpoint of a different boundary pane $b_{\pi(i)}$, which it will meet at a $60^\circ$ angle. This defines a permutation $\pi=\pi_P\colon[n]\to[n]$ (where $[n]:=\{1,\ldots,n\}$) called the \dfn{billiards permutation} of $P$. For example, if $P$ is the grid polygon in \cref{FigBill1}, then the cycle decomposition of $\pi_P$ is \[(1\,3\,32\,26\,6\,30\,2\,33\,25\,12\,14\,9\,21\,19\,29\,28\,4\,31)(5\,24\,13\,10\,20\,27)(7\,22\,23\,15\,17)(8\,11\,18\,16).\] 

\begin{figure}[ht]
  \begin{center}\includegraphics[height=7cm]{BilliardsPIC2}
  \end{center}
  \caption{A grid polygon $P$ with $33$ boundary panes. The billiards permutation $\pi_P$ has $4$ cycles. We have colored the $4$ different trajectories with different colors.}\label{FigBill1}
\end{figure}

Let us imagine that the boundary panes of $P$ are mirrors (and all other panes are transparent windows). When the light beam emitted from $b_i$ reaches $b_{\pi(i)}$, it will bounce off in such a way that the reflected beam forms a $60^\circ$ angle with $b_{\pi(i)}$. This reflected beam will then travel to $b_{\pi^2(i)}$, where it will bounce off at a $60^\circ$ angle and continue on to $b_{\pi^3(i)}$, and so on. We will be interested in the cycles of $\pi$. Given points $p$ and $p'$ in the plane, let us write $[p,p']$ for the line segment whose endpoints are $p$ and $p'$. Let $\midp(s)$ denote the midpoint of a line segment $s$. If $c=(i_1\,i_2\cdots i_r)$ is a cycle of $\pi$, then we define the \dfn{trajectory} of $c$ to be  \[\traj(c)=\bigcup_{j=1}^r[\midp(b_{i_j}),\midp(b_{\pi(i_j)})].\] The description of $\pi$ in terms of light beam billiards is convenient because we can imagine that the beams of light corresponding to different cycles have different colors; thus, we will use different colors to draw different trajectories (see \cref{FigBill1}). 


The investigation of billiards in planar regions is a classical and much-beloved topic in both dynamical systems and recreational mathematics. However, the typical questions considered in previous works concern systems where the beams of light can have arbitrary initial positions and arbitrary initial directions. In contrast, our setup imposes a great deal of rigidity by requiring each beam of light to start at the midpoint of a boundary pane and begin its journey in a direction that forms a $60^\circ$ angle with that boundary pane.  Although several traditional dynamically-flavored billiards problems (such as determining the existence of periodic trajectories) become trivial or meaningless under our rigid conditions, our setting affords some fascinating combinatorial/geometric questions. 

The major players in our story are the following quantities associated with a grid polygon $P$. The \dfn{perimeter} of $P$, denoted $\perim(P)$, is simply the number of boundary panes of $P$. We define the \dfn{area} of $P$, denoted $\area(P)$, to be the number of triangular grid cells in $P$.\footnote{Thus, our area measure is just the Euclidean area multiplied by the normalization factor $4/\sqrt 3$.} We write $\cyc(P)$ for the number of cycles in the associated permutation $\pi_P$, which is the same as the number of different light beam trajectories in the associated billiards system. Our main theorems address the following extremal question concerning the possible relationships between these quantities: How big must $\area(P)$ and $\perim(P)$ be in comparison with $\cyc(P)$?  

\begin{theorem}[\cite{DJ}]\label{thm:area}
If $P$ is a grid polygon, then \[\area(P)\geq 6\cyc(P)-6.\]
\end{theorem}

\begin{theorem}[\cite{DJ}]\label{thm:perim}
If $P$ is a grid polygon, then \[\perim(P)\geq \frac{7}{2}\cyc(P)-\frac{3}{2}.\]
\end{theorem}

The inequality in \cref{thm:area} is tight, and we can characterize the grid polygons that achieve equality. Define a \dfn{unit hexagon} to be a grid polygon that is a regular hexagon of side length $1$. Let us construct a sequence of grid polygons $(P_k)_{k\geq 1}$ as follows. First, let $P_1$ be a unit hexagon. For $k\geq 2$, let $P_k=P_{k-1}\cup Q_{k}$, where $Q_{k}$ is a unit hexagon such that $P_{k-1}\cap Q_{k}$ is a single pane. We call a grid polygon $P_k$ obtained in this manner a \dfn{tree of unit hexagons}; see \cref{FigBill2} for an example with $k=9$. It is not difficult to prove by induction that $\cyc(P_k)=k+1$ for all $k\geq 1$. Thus, $\area(P_k)=6k=6\cyc(P_k)-6$. 

\begin{figure}[ht]
\begin{center}\includegraphics[height=5.76cm]{BilliardsPIC3}
  \end{center}
  \caption{A tree of unit hexagons $P_9$ with $\cyc(P_9)=10$, $\area(P_9)=54$, and $\perim(P_9)=38$.}\label{FigBill2}
\end{figure}

\begin{theorem}[\cite{DJ}]\label{thm:equality}
If $P$ is a grid polygon, then $\area(P)=6\cyc(P)-6$ if and only if $P$ is a tree of unit hexagons. 
\end{theorem}

On the other hand, we believe that \cref{thm:perim} is not tight. After drawing several examples of grid polygons, we have arrived at the following conjecture. 

\begin{conjecture}[\cite{DJ}]\label{conj:4n-2}
If $P$ is a grid polygon, then \[\perim(P)\geq 4\cyc(P)-2.\]
\end{conjecture}


If \cref{conj:4n-2} is true, then it is tight. Indeed, if $P_k$ is a tree of unit hexagons as described above, then $\perim(P_k)=4k+2=4\cyc(P_k)-2$. 

Of fundamental importance in our analysis of the billiards system of a grid polygon $P$ are the \dfn{triangular trajectories} of $P$, which are just the trajectories of the $3$-cycles in $\pi_P$. One of the crucial ingredients in the proofs of Theorems~\ref{thm:area}--\ref{thm:equality} is the following result, which we deem to be noteworthy on its own.  

\begin{theorem}[\cite{DJ}]\label{thm:HypothesisA}
Let $P$ be a grid polygon, and let $c$ be a cycle of size $m$ in $\pi_P$. Then the trajectory $\traj(c)$ intersects at most $m-2$ triangular trajectories of $P$ (excluding $\traj(c)$ itself if $m=3$).
\end{theorem}

Suppose we take a single trajectory in the billiards system of a grid polygon $P$. This trajectory is a union of several line segments. If we delete the points where two of these line segments intersect, then we will cut the trajectory into several open line segments that we call the \dfn{fragments} of the trajectory. Fragments end up being crucial in our proofs of the above theorems. After writing the article \cite{DJ}, we proved that the number of fragments of a trajectory is always divisible by $3$. The challenge to prove this divisibility result will appear soon in the \emph{Problems and Solutions} section of the American Mathematical Monthly, so we will not spoil the solution here. 

\section{Plabic Graphs}\label{subsec:plabic} 

A \dfn{plabic graph} is a planar graph $G$ embedded in a disc such that each vertex is colored either black or white. We assume that the boundary of the disc has $n$ marked points labeled clockwise as $b_1^*,\ldots,b_n^*$ so that each $b_i^*$ is connected via an edge to exactly one vertex of $G$. Following \cite{LamPostnikov}, we will also assume that every vertex of $G$ is incident to exactly $3$ edges, including edges connected to the boundary of the disc (the study of general plabic graphs can be reduced to this case). In his seminal article \cite{Postnikov}, Postnikov introduced plabic graphs---along with several other families of combinatorial objects---in order to parameterize cells in the totally nonnegative Grassmannian. These graphs have now found remarkable applications in a variety of fields such as cluster algebras, knot theory, polyhedral geometry, scattering amplitudes, and shallow water waves \cite{Arkani1, Fomin, Galashin, Kodama, LamPostnikov, Lukowski, Parisi, Shende}. 

Imagine starting at a marked boundary point $b_i^*$ and traveling along the unique edge connected to $b_i^*$. Each time we reach a vertex, we follow the \emph{rules of the road} by turning right if the vertex is black and turning left if the vertex is white. Eventually, we will reach a marked boundary point $b_{\pi(i)}^*$. The path traveled is called the \dfn{trip} starting at $b_i^*$. Considering the trips starting at all of the different marked boundary points yields a permutation $\pi=\pi_G:[n]\to[n]$ called the \dfn{trip permutation} of $G$. We say $G$ is \dfn{reduced} if it has the minimum number of faces among all plabic graphs with the same trip permutation. \cref{FigBill3} shows a reduced plabic graph $G$ whose trip permutation is the cycle $\pi_G=(1\,3\,5\,2\,4)$. 

\begin{figure}[ht]
\begin{center}\includegraphics[height=6.067cm]{BilliardsPIC4}
  \end{center}
  \caption{A reduced plabic graph whose trip permutation is the cycle $(1\,3\,5\,2\,4)$. The fact that $\pi_G(1)=3$ is illustrated by the red trip starting at $b_1^*$ and ending at $b_3^*$. Similarly, $\pi_G(5)=2$ because the green trip starting at $b_5^*$ ends at $b_2^*$.}\label{FigBill3}
\end{figure}

Given a grid polygon $P$, one can obtain a reduced plabic graph $G(P)$ via a planar dual construction. Let us say an equilateral triangle with a horizontal side is \dfn{right-side up} (respectively, \dfn{upside down}) if its horizontal side is on its bottom (respectively, top). We refer to this property of a triangle (right-side up or upside down) as its \dfn{orientation}. Place a black (respectively, white) vertex at the center of each right-side up (respectively, upside down) equilateral triangular grid cell inside of $P$. Whenever two such grid cells share a side, draw an edge between the corresponding vertices. Finally, encompass $P$ in a disc, draw a marked point $b_i^*$ on the boundary of the disc corresponding to each boundary pane $b_i$ of $P$, and draw an edge from $b_i^*$ to the vertex drawn inside the unique grid cell that has $b_i$ as a side. (See \cref{FigBill4}.) 

\begin{figure}[ht]
  \begin{center}\includegraphics[height=5.7cm]{BilliardsPIC5}\qquad \includegraphics[height=5.7cm]{BilliardsPIC7}\qquad\includegraphics[height=5.7cm]{BilliardsPIC6}
  \end{center}
  \caption{On the left is a grid polygon $P$ overlaid with the corresponding plabic graph $G(P)$. The middle image shows the trajectories in the billiards system of $P$ to illustrate that its billiards permutation is $\pi_{P}=(1\,7\,4\,3\,5\,9)(2\,6\,8)$. The right image shows the trips of $G(P)$ to illustrate that its trip permutation is $\pi_{G(P)}=(1\,7\,4\,3\,5\,9)(2\,6\,8)$.  }\label{FigBill4}
\end{figure}

It is immediate from the relevant definitions that the trip permutation $\pi_{G(P)}$ is equal to the billiards permutation $\pi_P$. For example, if $P$ and $G(P)$ are as in \cref{FigBill4}, then $\pi_P=\pi_{G(P)}$ is the permutation with cycle decomposition $(1\,7\,4\,3\,5\,9)(2\,6\,8)$. 

In the recent paper \cite{LamPostnikov}, Lam and Postnikov introduced \emph{membranes}, which are certain triangulated $2$-dimensional surfaces embedded in a Euclidean space. The definition of a membrane relies on a choice of an irreducible root system, and most of the discussion in \cite{LamPostnikov} centers around membranes of type $A$. They discussed how type $A$ membranes are in a sense dual to plabic graphs, and they further related type $A$ membranes to the theory of cluster algebras. A membrane is \dfn{minimal} if it has the minimum possible surface area among all membranes with the same boundary; Lam and Postnikov showed how to associate a reduced plabic graph $G(M)$ to each minimal type $A$ membrane $M$. They then defined the \dfn{essential dimension} of a reduced plabic graph $G_0$ to be the smallest positive integer $d$ such that there exists a minimal membrane $M$ of type~$A_d$ with $G(M)=G_0$. They proved that if $G_0$ has $n$ marked boundary points, then the essential dimension of $G_0$ is at most $n-1$, with equality holding if and only if there exists $k\in[n-1]$ such that $\pi_{G_0}(i)=i+k\pmod{n}$ for all $i\in[n]$ (this is equivalent to saying that $G_0$ corresponds to the top cell in the totally nonnegative Grassmannian $\text{Gr}_{k,n}^{\geq 0}$). Other than this result, there is essentially nothing known about essential dimensions of plabic graphs. Our original motivation for this project was to initiate the investigation of essential dimensions by studying plabic graphs of essential dimension $2$ in detail. 


Consider the class of triangulated surfaces in the triangular grid that can be obtained by iteratively wedging grid polygons. In other words, $Q$ is in this class if there are grid polygons $P_1,\ldots,P_k$ such that $P_{i+1}\cap(P_1\cup\cdots\cup P_i)$ is a single point for all $i\in[k-1]$ and such that $Q=P_1\cup\cdots \cup P_k$. In this case, we call the grid polygons $P_1,\ldots,P_k$ the \dfn{components} of $Q$. See \cref{FigBill5}. As mentioned in \cite{LamPostnikov}, the class we have just described is the same as the class of membranes of type $A_2$.  Such a membrane $M$ is automatically minimal (since it is determined by its boundary). In order to understand these membranes and their associated reduced plabic graphs, it suffices to understand grid polygons and their associated reduced plabic graphs. Indeed, the reduced plabic graphs associated to the components of $M$ are basically the same as the connected components of the reduced plabic graph associated to $M$; thus, restricting our focus to grid polygons is the same as restricting our focus to connected plabic graphs. Furthermore, if $M=P$ is a grid polygon, then the definition that Lam and Postnikov gave for the reduced plabic graph $G(M)$ associated to $M$ (viewed as a membrane) is exactly the same as the definition that we gave in \cref{subsec:plabic} for the reduced plabic graph $G(P)$ associated to $P$ (viewed as a grid polygon). In other words, understanding plabic graphs of essential dimension $2$ and their trip permutations is equivalent to understanding grid polygons and their billiards permutations.

\begin{figure}[ht]
  \begin{center}\includegraphics[height=3.873cm]{BilliardsPIC8}
  \end{center}
  \caption{A membrane of type $A_2$ with $5$ components.}\label{FigBill5}
\end{figure}

As a consequence of the preceding discussion, we can reformulate \cref{thm:area,thm:perim} in the language of plabic graphs. 

\begin{corollary}[\cite{DJ}]\label{cor:plabic}
Let $G$ be a connected reduced plabic graph with essential dimension $2$. Suppose $G$ has $n$ marked boundary points and $v$ vertices, and let $c$ be the number of cycles in the trip permutation $\pi_G$. Then \[v\geq 6c-6\quad\text{and}\quad n\geq\frac{7}{2}c-\frac{3}{2}.\] 
\end{corollary}

\section{Reflections and Next Directions}\label{sec:conclusion}

We believe our work just scratches the surface of rigid combinatorial billiards systems and their connections with plabic graphs and membranes. In this section, we discuss several variations and potential avenues for future research. 

\subsection{Perimeter vs. Cycles}
Recall \cref{conj:4n-2}, which says that $\perim(P)\geq 4\cyc(P)-2$ for every grid polygon $P$. The grid polygons $P$ satisfying $\perim(P)=4\cyc(P)-2$ seem more sporadic and unpredictable than the equality cases of \cref{thm:area} (see \cref{FigBill8}), which are just the trees of unit hexagons by \cref{thm:equality}. This gives a heuristic hint as to why \cref{conj:4n-2} is more difficult to prove than \cref{thm:area}. 

\begin{figure}[ht]
  \begin{center}\includegraphics[height=3.808cm]{BilliardsPIC11}\qquad\qquad\includegraphics[height=4.549cm]{BilliardsPIC12}
  \end{center}
  \caption{Two grid polygons with perimeter $18$, each of which has $5$ cycles in its billiards system.}\label{FigBill8}
\end{figure}

\subsection{Other Families of Plabic Graphs} 

Let $G$ be a connected reduced plabic graph with $n$ marked boundary points and $v$ vertices, and let $c$ be the number of cycles in the trip permutation $\pi_G$. \cref{cor:plabic} provides inequalities that say how large $n$ and $v$ must be relative to $c$ in the case when $G$ has essential dimension $2$. One can ask for similar inequalities when $G$ is taken from some other interesting family of plabic graphs. One natural candidate for such a family is the collection of plabic graphs of essential dimension $3$; we refer to \cite{LamPostnikov} for further details concerning the definition. It is also natural to consider plabic graphs that can be obtained from polygons in other planar grids besides the triangular grid; \cref{FigBill12} shows some examples (in these examples, we dismiss our earlier assumption that all vertices in a plabic graph are trivalent). 

\begin{figure}[ht]
  \begin{center}\includegraphics[height=4.7cm]{BilliardsPIC19}\qquad\includegraphics[height=4.7cm]{BilliardsPIC18}\qquad\includegraphics[height=4.7cm]{BilliardsPIC20}
  \end{center}
  \caption{Plabic graphs obtained from polygons in different planar grids.}\label{FigBill12}
\end{figure}

If $G$ is a plabic graph obtained from the square grid (as on the left of \cref{FigBill12}), then it is not too difficult to prove that $v\geq 3c-2$ and that $n\geq 4c$; moreover, these bounds are tight. 

%\subsection{Higher Dimensions}
%It is natural to try extending our triangular-grid billiards systems into higher-dimensional spaces. Let us briefly propose one possible way to do this. 

%Let $\mathcal H_d'$ be the Coxeter arrangement of type~$\widetilde A_d$. This is the collection of hyperplanes of the form $\{(x_1,\ldots,x_{d+1})\in\mathbb R^{d+1}:x_i-x_j=k\}$ for some distinct $i,j\in[d+1]$ and some $k\in\mathbb Z$. We identify $\mathbb R^{d+1}/\text{span}\{(1,\ldots,1)\}$ with $\mathbb R^d$ and let $\mathcal H_d$ be the hyperplane arrangement in $\mathbb R^d$ obtained by taking the images of the hyperplanes in $\mathcal H_{d}'$ under the natural quotient map $\mathbb R^{d+1}\to\mathbb R^{d+1}/\text{span}\{(1,\ldots,1)\}$. The closures of the connected components of $\mathbb R^d\setminus\bigcup_{H\in\mathcal H_d}H$ are simplices called \dfn{alcoves}. When $d=2$, alcoves are the same as the triangular grid cells. 

%Let $P\subseteq\mathbb R^d$ be a simply connected polyhedral region formed as a union of alcoves. Let $Z_P$ be the union of all line segments of the form $[p,p']$ such that $p$ and $p'$ are the centroids of two different facets of a single alcove contained in $P$. Let $V$ be the set of points on the boundary of $P$ that are centroids of alcoves. Define a graph $\Omega_P$ with vertex set $V$ in which distinct vertices $v$ and $v'$ are adjacent if and only if the line segment $[v,v']$ is contained in $Z_P$. When $d=2$, the set $Z_P$ is the union of the trajectories of the billiards system of $P$, and the number of connected components of $\Omega_P$ is $\cyc(P)$. It would be interesting to obtain results in the same vein as Theorems~\ref{thm:area}--\ref{thm:equality} by relating the number of alcoves in $P$ (a measure of volume) and the number of vertices of $\Omega_P$ (a measure of surface area) to the number of connected components of $\Omega_P$. 


\subsection{Regions with Holes}\label{subsec:holes} 

Suppose $Q$ is a region in the triangular grid obtained from a grid polygon by cutting out some number of polygonal holes. We can define the billiards system for $Q$ in the same way that we defined it for a grid polygon. It would be interesting to obtain analogues of Theorems~\ref{thm:area}, \ref{thm:perim}, \ref{thm:equality}, and~\ref{thm:HypothesisA} in this more general setting. The resulting analogues of \cref{thm:area,thm:perim} might need to incorporate the genus of $Q$. Indeed, \cref{FigBill9} shows a region $Q$ with genus $1$ for which the inequalities in \cref{thm:area,thm:perim} are false as written. 

\begin{figure}[ht]
  \begin{center}\includegraphics[height=3.058cm]{BilliardsPIC14}
  \end{center}
  \caption{Trajectories in a triangular grid region of genus $1$. }\label{FigBill9}
\end{figure}

\subsection{Higher Dimensions}
Nathan Williams has suggested the following natural way to use algebra to extend our billiards systems into higher dimensions. 

Let $\mathcal H_d'$ be the Coxeter arrangement of type~$\widetilde A_d$. This is the collection of hyperplanes $H_{i,j}^k:=\{(x_1,\ldots,x_{d+1})\in\mathbb R^{d+1}:x_i-x_j=k\}$ such that $i,j\in[d+1]$ are distinct and $k\in\mathbb Z$. We identify $\mathbb R^{d+1}/\text{span}\{(1,\ldots,1)\}$ with $\mathbb R^d$ and let $\mathcal H_d$ be the hyperplane arrangement in $\mathbb R^d$ obtained by taking the images of the hyperplanes in $\mathcal H_{d}'$ under the natural quotient map $\mathbb R^{d+1}\to\mathbb R^{d+1}/\text{span}\{(1,\ldots,1)\}$. The closures of the connected components of $\mathbb R^d\setminus\bigcup_{H\in\mathcal H_d}H$ are called \dfn{alcoves}. When $d=2$, alcoves are the same as the triangular grid cells. 

For $1\leq i\leq d$, let $s_i\colon\mathbb R^d\to\mathbb R^d$ be the reflection through (the image in the quotient of) the hyperplane $H_{i,i+1}^0$. Let $s_0$ be the reflection through (the image in the quotient of) $H_{1,d+1}^1$. Then $s_0,s_1,\ldots,s_d$ are the simple reflections generating the affine symmetric group $\widetilde S_{d+1}$. Note that if $X$ is an alcove and $0\leq i\leq d$, then the region $s_i\cdot X$ obtained by applying the reflection $s_i$ to $X$ is also an alcove. This defines a free transitive action of $\widetilde S_{d+1}$ on the set of alcoves, so we can identify $\widetilde S_{d+1}$ with the set of alcoves. 

Let us fix a finite set $P\subseteq\widetilde S_{d+1}$; we can think of $P$ as a finite set of alcoves. For $w\in P$ and $j\in\mathbb Z/(d+1)\mathbb Z$, let \[\tau_j(w)=\begin{cases} ws_j & \mbox{if }ws_j\in P \\ w & \mbox{if }ws_j\not\in P. \end{cases}\] Define $\varphi\colon P\times (\mathbb Z/(d+1)\mathbb Z)\to P\times (\mathbb Z/(d+1)\mathbb Z)$ by $\varphi(w,j)=(\tau_j(w),j+1)$. We call an orbit of the map $\varphi$ a \dfn{trajectory} of $P$. 

Each pair $(w,j)\in P\times (\mathbb Z/(d+1)\mathbb Z)$ encodes the alcove $w$ together with a ``direction'' given by $j$. Applying $\varphi$ moves us one step in this direction unless doing so would take us out of $P$; in the latter case, we stay at $w$ and change direction. If $d=2$ and $P$ is a region in the triangular grid, then the trajectories defined using $\varphi$ correspond precisely to the trajectories in the billiards system of $P$. 

It would be interesting to understand the relationship between the number of alcoves in $P$ and the number of trajectories of $P$ when $d>2$. One might hope to obtain an inequality relating these quantities for arbitrary $d$. \Cref{thm:area} relates these quantities when $d=2$ under the assumption that $P$ is simply connected (this assumption makes the problem different but not necessarily easier). In this more general setting, it could be simpler to remove the hypothesis that $P$ is simply connected (and thus consider regions with holes, as in \Cref{subsec:holes}).

\subsection{Random and Infinite Billiards Systems}
We would like to formulate a notion of a \emph{random billiards system} so that one can ask about the expected number of trajectories. However, there are several possible random models one could consider, and it is not clear which is the best. 

One potential random model of an \emph{infinite} billiards system is as follows. Fix a probability $p\in(0,1)$. Choose a random set $P$ of grid cells in the triangular grid by adding each grid cell into $P$ with probability $p$ so that all choices are independent. The set $P$ is a region that is almost surely disconnected and of infinite area. We can define trajectories just as we did for polygons, except these trajectories might be infinite. It would be very interesting to understand the distribution of trajectory lengths in this random billiards system. Suppose we start with a specific fixed grid cell $\Delta$. Given that $\Delta\in P$, what is the probability that the trajectory that travels west through $\Delta$ is infinite?

\subsection{Cyclic Billiards Systems}
It would be interesting to obtain estimates for the number of grid polygons $P$ such that $\cyc(P)=1$.  



\printbibliography

\end{document}