# Fine Mixed Subdivisions of a Dilated Triangle

Yuan Yao  and  Fedir Yudin<EMAIL_ADDRESS>
###### Abstract.

An upward equilateral triangle of side $n$ can be partitioned into $n$ unit
upward equilateral triangles and $\frac{n(n-1)}{2}$ unit rhombi with
$60^{\circ}$ and $120^{\circ}$ angles. In this paper, we focus on
understanding such partitions with a fixed arrangement of unit triangles. We
formulate a criterion for such a partition being unique, identify a set of
operations that connects all such partitions, and determine which parts are
common to all such partitions. Additionally, we discuss an operation that
connects all possible partitions with different arrangements of triangles.

Both authors were supported by the MIT Math Department’s Supervised UROP
(UROP+).

##  1\. Introduction

Consider an equilateral triangle of side $n$. Suppose that we cut out $n$
upward unit equilateral triangles, and attempt to tile the rest with unit
60-120 rhombi (formed by gluing two unit equilateral triangles together). This
results in a _fine mixed subdivision_ of the triangle, sometimes also called a
_rhombus tiling of a holey triangle_ ([1]).

Figure 1. A fine mixed subdivision of an equilateral triangle of side length
5.

In [1], Ardila and Billey described the condition of the positions of the
holes for which the tiling is possible via a “spread-out condition” (see
Theorem 2.3). In this paper, we focus on extending our understanding of the
tilings with any given set of hole positions beyond their existence. Sections
3-6 explore the structure of the set of tilings for a fixed arrangement of
triangular holes, and Section 7 discusses an operation that moves the holes
and connects all possible tilings.

##  2\. Preliminaries

For convenience, we will use “upward” and “downward” to describe the
orientation of equilateral triangles. (The equilateral triangles in Figure 1
are all upwards.)

######  Definition 2.1 ([5], Definition 3.1).

A _fine mixed subdivision_ of an upward equilateral triangle of side length
$n$ is a partition into $n$ upward unit equilateral triangles (holes) and
$\binom{n}{2}$ unit 60-120 rhombi.

(From now on, we will simply use “rhombus” to refer to a unit 60-120 rhombus.
We will also drop the “equilateral” adjective for triangles as all triangles
in this paper will be equilateral.)

Suppose we’re given a set of triangular holes and what to find out whether
there is a fine mixed subdivision with this set of holes. Note that every
upward triangle $T$ of side $k$ consists of $k$ more upward unit triangles
than downward unit triangles. Also, note that a rhombus covers an equal number
of upward and downward triangles in $T$ if it does not intersect the boundary
of $T$, and covers one upward triangle if it intersects the boundary of $T$.
Hence, there are at most $k$ triangular holes that lie in $T$. Turns out, if
this condition is satisfied for every $T$, then the desired fine mixed
subdivision exists.

######  Definition 2.2.

We will say that an arrangement of $n$ upward unit triangular holes in an
upward triangle of side $n$ is _spread-out_ if every upward grid triangle of
size $k$ contains at most $k$ holes. We will also refer to the side length of
such a triangle as its _size_.

######  Theorem 2.3 ([1], Theorem 6.2).

An arrangement of holes is a part of some fine mixed subdivision if and only
if it’s spread-out.

######  Definition 2.4.

For an arrangement of triangular holes, we say an upward triangle of side
length $k$ is _saturated_ if it contains exactly $k$ triangular holes.

######  Lemma 2.5.

If a triangle is saturated, then no rhombus can intersect its boundary in any
tiling.

###### Proof.

Consider a saturated triangle $T$. A rhombus covers an equal number of upward
and downward triangles in $T$ if it does not intersect the boundary of $T$,
and covers one upward triangle if it intersects the boundary of $T$. Since the
number of upward triangles in $T$ covered by a rhombus is equal to the number
of downward triangles in $T$ covered by a rhombus, no rhombus can intersect
the boundary of $T$. ∎

##  3\. Uniqueness of Tiling

Suppose we are given an arrangement of unit triangular holes and would like to
tile the rest with rhombi. If $T$ is a saturated triangle for the given
arrangement, by Lemma 2.5 this problem can be separated into two independent
sub-problems: tiling $T$ and tiling the region outside $T$. Thus, it makes
sense to consider a more general problem, where the triangular holes do not
necessarily have unit side length.

More precisely, consider an upward triangle $\Delta$ of side length $n$
divided into $n^{2}$ unit triangles, and suppose that we cut out several
disjoint upward triangular holes whose sides sum to $n$.

Figure 2. A tiling with some holes whose side lengths are greater than 1.

We say a set of triangles $S$ with disjoint interiors is _spread-out_ if for
any upward triangle $T$ inside $\Delta$,

$\sum_{s\in S}\text{size}(s\cap T)\leq\text{size}(T).$

Call $T$ _saturated_ (by $S$) if equality holds. Note that all elements of $S$
are saturated triangles themselves.

Similarly to the case of unit triangular holes, one may prove that if
$\Delta\setminus\cup_{s\in S}s$ is tileable with rhombi, then $S$ is spread-
out. If we replace all triangles in $S$ with upward unit triangles in their
bottom rows, we get a spread-out arrangement of unit triangles, so $S$ being
spread-out is sufficient for $\Delta\setminus\cup_{s\in S}s$ to be tileable
with rhombi.

For upward grid triangles $s_{1}$, $s_{2}$, denote by $s_{1}\vee s_{2}$ the
minimal upward triangle that contains both $s_{1}$ and $s_{2}$. Note that if
saturated triangles $s_{1},s_{2}\in S$ intersect at exactly one point, then
$s_{1}\vee s_{2}$ is saturated, and there is only one way to tile $(s_{1}\vee
s_{2})\setminus(s_{1}\cup s_{2})$. Also, no other triangles in $S$ can
intersect $s_{1}\vee s_{2}$ in their interiors. Therefore, there is an obvious
bijection between tilings of $\Delta$ with holes $S$ and tilings of $\Delta$
with holes $S\setminus\\{s_{1},s_{2}\\}\cup(s_{1}\vee s_{2})$.

Figure 3. Two touching saturated triangles $s_{1}$ and $s_{2}$ and the unique
way to tile $(s_{1}\vee s_{2})\setminus(s_{1}\cup s_{2})$.

Consider any set $S$ of triangular holes and a saturated triangle $T$. Let $A$
be the set of triangles in $S$ completely outside $T$, $B$ be the set of
triangles in $S$ completely inside $T$, and $\\{s_{1},s_{2},\dots,s_{k}\\}$ be
the rest of triangles in $S$.

For each $i$, let $p_{i}=T\cap s_{i}$, and pick $q_{i}$ such that
$s_{i}=p_{i}\vee q_{i}$. Note that a tiling of $\Delta$ with holes $S$
corresponds to a tiling of $\Delta$ with holes holes
$A\cup\\{T\\}\cup\\{q_{1},q_{2},\dots q_{k}\\}$ and a tiling of $T$ with holes
$B\cup\\{p_{1},p_{2},\dots p_{k}\\}$.

Suppose that we start with some arrangement of holes and begin performing
changes of the following type: two triangles $s_{1}$, $s_{2}$ touching at a
point can be replaced with $s_{1}\vee s_{2}$. Eventually, we will get an
arrangement of triangular holes that are pairwise not touching. If this
arrangement consists of a single hole coinciding with the big triangle, then
the original arrangement of holes has a unique tiling. We claim that the
converse is also true.

######  Theorem 3.1.

Let $S$ be a spread-out set of triangles. If no two triangles in $S$
intersect, then $\Delta\setminus\cup_{s\in S}s$ is tileable in at least two
ways.

######  Corollary 3.2.

A spread-out set $S$ of $n$ unit triangles induces a unique tiling of a
triangle of side length $n$ if and only if one can repeatedly replace two
elements $s_{1},s_{2}$ of $S$ such that $s_{1}\cap s_{2}$ is a single point
with $s_{1}\vee s_{2}$ until there is only one element, which is the entire
triangle.

######  Remark 3.3.

The number of uniquely tile-able spread-out arrangements for $n=1,2,\dots$ is

$1,3,16,122,1188,\dots.$

This is sequence A295928 on OEIS, which counts the number of triangular
matrices $\\{T_{i,j}\mid 1\leq i,j\leq n,i+j\leq n+1\\}$ with exactly $n$
$1$-entries (and the rest being $0$’s) such that one can repeatedly replace
triples of the form $(T_{i,j},T_{i+1,j},T_{i,j+1})$ with exactly two $1$’s
with all $1$’s until the entire matrix only contain $1$’s. It is not difficult
to see that this description is the same as our condition.

We will delay the proof of Theorem 3.1 until the end of the next section.

######  Definition 3.4 ([5], Section 1.1).

A polyhedral subdivision is _regular_ if it can be realized as the projection
of lower faces of a polytope.

In [1], the authors additionally conjectured that any spread-out arrangement
of unit triangles can be completed into a _regular_ fine mixed subdivision.
This has been disproved by Yoo with a counterexample in $n=6$, where there are
two possible fine mixed subdivisions but neither is regular (see Section 8.1
of [2]). We argue that this is in a sense the “minimal” counterexample.

######  Proposition 3.5.

If a spread-out arrangement of unit triangles induces a unique fine mixed
subdivision, then this subdivision is regular.

###### Proof sketch.

Based on the uniqueness condition, it suffices to show that if two triangles
$s_{1}$ and $s_{2}$ touch and each has a regular subdivision, then $s_{1}\vee
s_{2}$ also has a regular subdivision. We use a different condition of
regularity that applies to fine mixed subdivisions of dilated triangles:

######  Lemma 3.6 ([3], Theorem 1, paraphrased).

A fine mixed subdivision of a triangle of side length $n$ is regular if and
only if its corresponding tropical pseudoline arrangement can be realized as a
tropical line arrangement.

Here we omit the definition of tropical (pseudo)lines, and instead present an
example in Figure 4 for an intuitive understanding.

Figure 4. A fine mixed subdivision with its tropical pseudoline arrangement
drawn in magenta, along with its realization (in purple and orange). The
purple and orange triangles correspond to $s_{1}$ and $s_{2}$ in the proof,
respectively.

From Lemma 3.6 we can assume that $s_{1}$ and $s_{2}$ each correspond to some
tropical line arrangement $T_{1}$ and $T_{2}$. Assume without loss of
generality that $T_{2}$’s top vertex is touching $T_{1}$’s bottom edge, as
shown in Figure 4. In this case, we can shrink $T_{2}$ and place all of its
vertices between the two downward rays of $T_{1}$ that correspond to the two
sides of the point $s_{1}\cap s_{2}$, and sufficiently far below so that the
leftward and rightward arms of $T_{2}$ are all below $T_{1}$’s. It is not
difficult to see that this gives a realization of the unique tiling of
$s_{1}\vee s_{2}$. ∎

##  4\. A Graph Representation of Fine Mixed Subdivision

Consider some fine mixed subdivison. Note that it divides the plane into
regions: triangular holes, rhombi, and the outside region. Consider the graph
$G$ whose vertices are these regions, and where there is an edge $a\rightarrow
b$ if and only if $a$ contains an upward triangle adjacent to a downward
triangle contained by $b$. We say that $G$ is the graph corresponding to the
original fine mixed subdivison.

Figure 5. A fine mixed subdivision and the corresponding graph.

Note that that all vertices corresponding to rhombi have indegree and
outdegree equal to $2$; each vertex corresponding to a triangular hole of side
$k$ has outdegree $3k$ and indegree $0$; and the vertex corresponding to the
outside region has outdegree $0$ and indegree $3n$.

Consider any cycle of the graph. This cycle must consist of rhombi that occupy
a sequence of triangles where each next one touches the previous and the last
one touches the first one. Then this sequence of triangles can be tiled in
another way. We will call replacing one of these tilings with the other one a
“cycle flip”.

Figure 6. A cycle flip.

######  Lemma 4.1.

Consider any fine mixed subdivision $\mathcal{F}$, and let $a$ and $b$ be two
rhombi such that $a\rightarrow b$ is an edge of its corresponding graph. Let
$c$ be the rhombus formed by the upward triangle of $a$ and the downward
triangle of $b$. Then there exists a fine mixed subdivision with the same
arrangement of triangular holes as $\mathcal{F}$ and using $c$ if and only if
$a$ is reachable from $b$ in the graph corresponding to $\mathcal{F}$.

###### Proof.

If $a$ is reachable from $b$, then there is a simple cycling containing the
edge $a\rightarrow b$. After flipping this cycle, we get the desired fine
mixed subdivision.

Suppose that there is a fine mixed subdivision $\mathcal{G}$ using $c$. Build
a sequence of rhombi as follows: let $f_{1}=a$. Let $g_{1}$ be the rhombus in
$\mathcal{G}$ containing the downward triangle of $f_{1}$. Let $f_{2}$ be the
rhombus in $\mathcal{F}$ containing the upward triangle of $g_{1}$. Let
$g_{2}$ be the rhombus in $\mathcal{G}$ containing the downward triangle of
$f_{2}$, and so on. Since $f_{i}$ uniquely determines $f_{i-1}$ and $f_{i+1}$,
there is an index $k>1$ such that $f_{k}=f_{1}$. Then vertices
$a=f_{1},f_{2},f_{3},\dots f_{k-1}=b$ form an cycle in the graph corresponding
to $\mathcal{F}$, as desired. ∎

This gives us another criterion for the uniqueness of a tiling: any tiling is
unique for its arrangement of triangles if and only if the corresponding graph
has no oriented cycles.

The notion of a cycle flip also gives us a simple way to prove Theorem 3.1.

###### Proof of Theorem 3.1.

Consider a spread-out arrangement where no two trianglular holes touch, and
any rhombus $a$ of some tiling. We claim that there is at least one rhombus
$b$ such that the graph contains the edge $a\leftarrow b$. Indeed, each of the
two edges going into $a$ is coming from either a triangle or a rhombus; if
both come from a triangle then the two triangles are touching. Thus, we can
construct an infinite sequence or edges $a_{1}\leftarrow a_{2}\leftarrow
a_{3}\leftarrow\dots$, so there must be a cycle in the graph, and we can
perform a cycle flip, giving us a second tiling. ∎

##  5\. GD Flips

Using the the idea from the proof of Lemma 4.1, we see that any two fine mixed
subdivisions with the same arrangement of triangular holes differ by several
cycle flips. Additionally, if we place $3$ unit triangles in the corners and
one triangle of side $n-3$ in the middle we get an arrangement of triangular
holes that admits only two fine mixed subdivisions, where only one cycle flip
is possible. (See Figure 7.)

Figure 7. An arrangement of triangles admitting exactly two fine mixed
subdivisions for $n=6$.

######  Definition 5.1.

For $n\geq 3$, consider the region obtained by removing three corner unit
triangles from a triangle of side $n$, as well as removing a triangle of side
$n-3$ in the middle. There are two configurations of rhombi that tile this
region. Let the _Clockwise GD_ (CW-GD) of size $n-3$ be the configuration
where vertical rhombi (the ones without horizontal edges) go along the left
side of the triangle, and let _Counter-clockwise GD_ (CCW-GD) be the other
one.111This name is inspired by the (pre-2020) Google Drive logo. A _GD flip_
consists of replacing a CW-GD with a CCW-GD. In particular, a GD flip is a
cycle flip.

Figure 8. GD flips of size 0 and 2.

It turns out that these types of flips are the only ones we need to connect
all tilings with the same arrangement of holes.

######  Theorem 5.2.

Any two tilings with the same arrangement of triangles are connected by a
sequence of GD flips and their inverses.

######  Lemma 5.3.

A tiling has a clockwise cycle if and only if it has a CW-GD.

###### Proof.

Take a minimal clockwise cycle $C$ (in terms of enclosed area).

First, we claim that there are no edges going from a rhombus strictly inside
$C$ to a rhombus of $C$. Suppose there is such an edge $a\rightarrow b$.
Without loss of generality, we may assume that this the boundary between $a$
and $b$ is horizontal, that is, $a$ is directly below $b$. Then we can
construct a sequence of rhombi starting with $b,$ $a$ where each next rhombus
is directly below the previous one. Eventually, this sequence must hit $C$
again. Thus, we’ve constructed a path surrounded by $C$ connecting two
vertices of $C$. This path creates a clockwise cycle smaller than $C$, which
is a contradiction.

Now consider the polygon surrounded by $C$. Note that if we traverse it
clockwise, its edges can only go in three directions, corresponding to
traversing an upward triangle in clockwise direction. This means that all
internal angles of this polygon are equal to $60^{\circ}$ or $300^{\circ}$. If
some is equal to $300^{\circ}$, then only one of the triangles surrounding can
belong to $C$, which is impossible. Since all angles of the polygon are equal
to $60^{\circ}$, it has to be a triangle, so $C$ is a CW-GD, as desired. ∎

Figure 9. A clockwise cycle that contains a smaller clockwise cycle.

###### Proof of Theorem 5.2.

Suppose that we begin with some tiling and start performing GD flips while
possible. Since the number of vertical rhombi does not change after a GD flip,
and the sum of $x$-coordinates of their centers decreases with every GD flip,
we must eventually stop. Note that there is at most one tiling with no
clockwise cycles: if there were two, they would differ by several cycle flips,
so one of them would have a clockwise cycle. This shows that starting from any
tiling, we can get to the unique tiling with no clockwise cycles by performing
GD flips, and then back to any other tiling by performing their inverses. ∎

We can construct the unique tiling with no clockwise cycles more explicitly:

######  Proposition 5.4.

If in the process of sliding triangles (see [4], Section 3) we slide the
triangle left whenever possible, we end up with a tiling that has no CW-GD.

###### Proof.

Suppose there is a CW-GD. Then its topmost rhombus arose from us sliding a
triangle to the right when we could slide it to the left. ∎

##  6\. Segments Forced by Holes

Given a fixed arrangement of triangular holes, it is natural to ask if there
is a tiling of the remaining region including a certain rhombus. This is
equivalent to determining if a certain segment of the triangular grid is
forced to be a part of the tiling. Note that Lemma 2.5 shows that all segments
belonging to a boundary of a saturated triangle are forced, and Lemma 4.1
shows that a segment between two rhombi is forced if and only if they belong
to different connected components.

Given a fined mixed subdivision with corresponding graph $G$, consider the
subgraph of $G$ induced by vertices corresponding to rhombi. In this graph,
pick a strongly connected component that has no edges going in from other
strongly connected components. Let $A$ be the set of rhombi in this component,
as well as all saturated triangles adjacent to them. Note that in $G$, there
are no edges going from a vertex outside $A$ into a vertex in $A$.

Consider the union of regions corresponding to vertices of $A$, which clearly
is connected. Consider the polygon $P$ that is the outside boundary of this
region. This polygon, when traversed clockwise, can only have edges going in
the directions corresponding to traversing an upward triangle in clockwise
direction. It is also not difficult to see that all outward-pointing corners
of $P$ must be part of saturated triangles, or else the rhombi occupying those
corners cannot be part of the initial strongly connected component.

Figure 10. A polygon $P$ traversed clockwise and the corresponding triangle
$T$ (dashed).

Let $T$ be the smallest upward triangle containing $P$. Note that if $X$ and
$Y$ are the topmost vertices of $P$ on left and right sides of $T$,
respectively, then the distance from $X$ to $Y$ along the boundary of $P$ is
not less than the distance from $X$ to $Y$ along the boundary of $T$ (in both
cases, we are traversing polygons clockwise). Indeed, every unit segment on
the path from $X$ to $Y$ along the boundary of $P$ increases the
$x$-coordinate by at most $\frac{1}{2}$, and each unit segment on the path
from $X$ to $Y$ along the boundary of $T$ increases the $x$-coordinate by
exactly $\frac{1}{2}$. Similarly, if $Z$ is the bottommost vertex of $P$ on
the right side of $T$, the distance from $Y$ to $Z$ along the boundary of $P$
is not less that the distance from $Y$ to $Z$ along the boundary of $T$. This
shows that $\text{perimeter}(P)\geq\text{perimeter}(T)$.

However, note that every unit segment on the boundary of $P$ corresponds to an
edge going from a vertex in $A$ to a vertex not in $A$, and there are no edges
going from a vertex not in $A$ into a vertex in $A$, so the total outdegree of
vertices of $A$ larger than the total indegree of vertices in $A$ by at least
$\text{perimeter}(P)$. This means that the sum of sizes of triangular holes in
$A$ is at least $\text{perimeter}(P)/3\geq\text{size}(T)$. Since all these
triangular holes lie entirely inside $T$, all inequalities must turn into
equalities, and $T$ is saturated.

In particular, all segments on the boundary of $P$ between $X$ and $Y$ must go
down-right or up-right, and all segments on the boundary of $P$ between $Y$
and $Z$ must go down-right. This implies that $T\setminus P$ consists of three
regions containing three vertices of $T$, and there is only one way to tile
these regions.

This also implies that $A$ is simply connected – if $A$ had “holes”, then
there would be edges going from vertices of $A$ to vertices in the holes, so
the difference of total out- and in-degrees of vertices of $A$ would be
strictly greater than $\text{perimeter}(P)$.

Now, we may replace $T$ with a triangular hole and repeat the process. This
results in the following categorization of the forced segments:

######  Theorem 6.1.

Given a set of triangular holes, the boundaries of saturated triangles are
forced, and remaining forced segments come from repeated placing rhombi in the
three corners of saturated triangles until obstructed by holes.

For example, in Figure 10, one can place rhombi in the regions $T\setminus P$,
and the obstruction come from the fact that the outward-pointing corners of
$P$ are all holes. This also gives a poly-time algorithm for determining the
forced segments, even though the number of possible tilings may be
exponential.

##  7\. Trapezoid Flips

######  Definition 7.1.

A _trapezoid flip_ consists of replacing a triangle and an adjacent rhombus
with a different triangle and an adjacent rhombus occupying the same
trapezoid.

Figure 11. A trapezoid flip.

It is known that _all_ fine mixed subdivisions of a dilated triangle can be
connected by such flips.

######  Proposition 7.2 ([5], Corollary 4.5).

Any two fine mixed subdivisions are connected by at most $\frac{2n(n-1)}{3}$
trapezoid flips.

###### Proof.

For any triangle hole $s$, let $h_{1}(s),$ $h_{2}(s)$, and $h_{3}(s)$ denote
the distances from sides $s$ to the parallel sides of the big triangle. Note
that for any triangle $s$ with $h_{i}(s)>0$, there is a trapezoid flip that
decreases $h_{i}(s)$ by $1$. Then the distance from a fine mixed subdivision
with triangle set $S$ to the unique fine mixed subdivision with all triangles
at the bottom is at most $\sum_{s\in S}h_{i}(s).$ Then the distance between
two fine mixed subdivisions with triangle sets $S_{1}$ and $S_{2}$ is at most
$\sum_{s\in S_{1}}h_{i}(s)+\sum_{s\in S_{2}}h_{i}(s).$ Since for any $s$ we
have $h_{1}(s)+h_{2}(s)+h_{3}(s)=n-1,$ the sum of this expression over
$i=1,2,3$ is equal to $2n(n-1)$, so for some choice of $i$ its at most
$\frac{2n(n-1)}{3}$, as desired.

∎

We show that this bound is tight up to terms of order $O(n)$.

######  Proposition 7.3.

Place a triangle of side $n$ over a grid of unit hexagons. Consider two fine
mixed subdivisions, where one is obtained by tiling each hexagon in clockwise
manner and the other obtained by tiling each hexagon in counterclockwise
manner (trimming off half of each rhombus that intersects the boundary of the
triangle). At least $\frac{2n^{2}}{3}-n-O(1)$ trapezoid flips are needed to
change from one tiling to the other.

Figure 12. Two tilings that require many trapezoid flips to connect, with
common hexagon boundaries highlighted in red.

###### Proof.

For each rhombus in the final tiling, consider the last trapezoid flip
involving this rhombus. Since these flips are all distinct and the two tilings
have no rhombi in common, this gives us $\frac{n^{2}-n}{2}$ distinct trapezoid
flips.

For each hexagon, consider the first trapezoid flip involving some rhombus
inside this hexagon in the initial tiling. These flips are clearly pairwise
distinct. Additionally, they result in a rhombus that does not belong to any
hexagon, so these moves are distinct from the previously considered
$\frac{n^{2}-n}{2}$. Note that there are $\frac{n^{2}}{6}-\frac{n}{2}-O(1)$
hexagons lying inside the triangle. Therefore, we have
$\frac{n^{2}-n}{2}+\frac{n^{2}}{6}-\frac{n}{2}-O(1)=\frac{2n^{2}}{3}-n-O(1)$
distinct trapezoid flips, as desired. ∎

##  8\. Further Questions

The rhombus tilings of a hexagon with sides $a,b,c,a,b,c$ are in bijection
with $3$-dimensional Young tableaux that fit in a $a\times b\times c$ box. A
GD flip of size $0$ in this case is also known as a _hexagon flip_ , and
corresponds to removing a cube.

Figure 13. A GD flip of size $0$ (note that this is rotated by $60^{\circ}$
counterclockwise relative to conventions in the rest of the paper for ease of
visualization).

Tilings of regions that may contain triangular holes of some fixed orientation
correspond to similar structures in certain $3$-dimensional manifolds. It
might be interesting to find an analog of Young tableaux that can help with
understanding fine mixed subdivisions of triangles.

Figure 14. A GD flip of nonzero size appears to correspond to removing some
non-Euclidean polyhedron.

One attempt of studying this correspondence is by looking at what we called
the _depth function_. Fix a direction parallel to one of the lines of the
triangle grid. For any node $p$ of the triangular grid, consider the ray
starting at $p$ and going in the chosen direction, and let $d(p)$ denote the
number of rhombi whose short diagonals belong to that ray. Note that the
values of $d$ at neighboring nodes differ by at most one, and that a GD flip
changes the values of $d$ of nodes in the triangle surrounded by the flip by
one, and does not change all other values of $d$.

Note that the unique tiling with no clockwise cycles corresponds to a
structure where no polyhedron can be removed, i.e., the “empty” one.
Similarly, the unique tiling with no counterclockwise cycles corresponds to a
structure where no polyhedron can be added, i.e., the “full” one. For each
node, the difference of values of $d$ for full and empty configurations
corresponds to how “thick” the region that we’re filling with polyhedra is at
that point.

## References

  * [1] Frederico Ardila and Sara Billey, Flag arrangements and triangulations of products of simplices, _Advances in Mathematics_. 214 (2007), no. 2, 495–524.
  * [2] Federico Ardila and Cesar Ceballos, Acyclic Systems of Permutations and Fine Mixed Subdivisions of Simplices. _Discrete & Computational Geometry_, 49 (2011): 485-510.
  * [3] Mike Develin and Bernd Strumfels, Tropical convexity. _Documenta Math._ , 9 (2004): 1-27.
  * [4] Derek Liu and Yuan Yao, Arrangement of Simplices in Fine Mixed Subdivisions, PRIMES (2022), https://math.mit.edu/research/highschool/primes/materials/2022/Liu-Yao.pdf.
  * [5] Francisco Santos, The Cayley trick and triangulations of products of simplices. _Contemporary Mathematics_ 374 (2005): 151-178.