Realizability of Tropical
Plane Curves and Tropical
Incidence Geometry
vorgelegt von
M. Sc.
Ayush Kumar Tewari
an der Fakult¨at II – Mathematik und Naturwissenschaften
der Technischen Universit¨at Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
Dr.rer.nat.
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr. Peter K. Friz
Gutachter: Prof. Dr. Michael Joswig
Gutachterin: Prof. Dr. Hannah Markwig
Gutachter: Dr. Dhruv Ranganathan
Tag der wissenschaftlichen Aussprache: 07.12.2020
Berlin 2021
to my mother, my first teacher
Acknowledgements
This research work could not have been completed by help and guidance from many people,
whom I would like to acknowledge. Firstly, I would like to thank my supervisors Hannah
Markwig and Michael Joswig, for having regular discussions with me and helping me in
trying to start with the right questions and to make my way forward with the solutions. I
am also thankful to the respective institutes, i.e. Eberhard Karls Universit¨at T¨ubingen and
Technische Universit¨at Berlin, both of which hosted me as a doctoral student during the
duration of this work. I would also like to thank my various colleagues, management staff at
both these institutes for making my stay easy and fruitful.
I would like to thank the members of the Geometry group at Eberhard Karls Universit¨at
T¨ubingen, for helping me with getting accustomed to the new city and the university. I
am also thankful to colleagues in the Discrete Mathematics/Geometry group at TU Berlin,
especially Marta, Lars, Paco, Benjamin and Antje for her help with the logistics and for
helping me at various stages of my research work.
I would like to thank my parents, my sister and my friends Arka, Bikash and Soham Saha
for their constant support which immensely helped me while working on this project.
Abstract
Tropical plane curves are one of the building blocks in the study of tropical algebraic geometry.
A lot of work has been done to understand and establish connections between tropical and
classical algebraic geometry. The first step in this direction is to consider the case of smooth
tropical curves. This in turn comes with a nice connection to lattice polytopes and their
unimodular triangulations. This highly combinatorial setting helps to explore the algebro-
geometric aspects of tropical curves by trying to find when a smooth tropical curve is realizable.
This leads us to study the skeleton of a tropical curve, which is a metric graph that encodes
the combinatorial information regarding the curve. Our main goal here is to understand the
combinatorial nature of these skeletons and to try to find which graphs can occur as skeletons
of smooth tropical plane curves, and in this way, we come up with certain obstructions which
prevent a graph from being a skeleton of a tropical curve. We encounter a special class
of lattice polytopes, namely panoptigons, which help us in identifying a new criterion for
non-realizability of a graph as a skeleton.
Having studied about smooth tropical planar curves, in the latter section we move on to
the study of incidence of points and lines in the tropical plane and arrangements of tropical
lines. In the light of recent results exploring tropical point-line incidence, we establish a
tropical De-Bruijn Erd˝os theorem. We also study stable tropical lines and using projective
duality in the tropical plane, we find dual results concerning stable intersections. Utilizing
duality of tropical curves with subdivisions of Newton polytopes we also establish connections
between point-line geometry and the faces of subdivisions of Newton polytopes. With tropical
Sylvester-Gallai theorem and tropical De-Bruijn Erd˝os theorem, we discuss other results
which have been obtained about point-line geometry in the tropical plane and beyond.
4
Zusammenfassung
Tropische ebene Kurven bilden einen Teil des Fundaments der tropischen algebraischen
Geometrie. Die Verbindung zwischen klassischer und tropischer Geometrie zu untersuchen
und zu vertiefen ist Thema vieler aktueller Arbeiten. Der erste Schritt ist die Untersuchung
glatter tropischer Kurven mittels ihrer Verbindung mit unimodularen Triangulierungen
von Gitterpolytopen. In diesem kombinatorischen Rahmen l¨asst sich die Frage nach der
Realisierbarkeit tropischer Kurven stellen. Dies f¨uhrt uns zum Studium des Skeletts tropischer
Kurven, einem metrischen Graphen, der die kombinatorische Information der Kurve kodiert.
Wir wollen verstehen, welche Graphen als Skelett glatter tropischer Kurven auftreten k¨onnen.
Dadurch gelangen wir zu Bedingungen an einen Graphen, die ihn davon abhalten, Skelett
einer tropischen Kurve zu sein. Eine besondere Klasse von Gitterpolytopen, “panoptigons”,
hilft uns neue Kriterien f¨ur Nichtrealisierbarkeit eines Graphen als Skelett zu finden.
Nach den glatten tropischen Kurven besch¨aftigen wir uns mit der Inzidenz von Punkten und
Geraden in der tropischen Ebene, sowie Arrangements von tropischen Geraden. Basierend auf
j¨ungsten Ergebnissen ¨uber tropische Punkt-Geraden Inzidenz, leiten wir eine tropische Version
des De-Bruijn Erd˝os Theorems her. Außerdem untersuchen wir stabile tropische Geraden
und, verm¨oge projektiver Dualit¨at, bekommen wir duale Ergebnisse f¨ur stabile Schnitte.
Durch die Dualit¨at tropischer Kurven mit Unterteilungen von Newtonpolytopen k¨onnen wir
Verbindungen zwischen der Punkt-Geraden-Geometrie und den Seiten in der Unterteilung
des Newonpolytops herstellen. Unter dem Gesichtspunkt des tropischen Sylvester-Gallai
Theorems und des tropischen De-Bruijn Erd˝os Theorems erl¨autern wir andere Ergebnisse zur
Punkt-Geraden Geometrie in der tropischen Ebene und dar¨uber hinaus.
5
Contents
1 Introduction 1
2 Forbidden patterns in tropical plane curves 5
2.1 Lattice polygons and tropical plane curves . . . . . . . . . . . . . . . . . . . 5
2.2 Heavy Cycles and Sprawling Triangles . . . . . . . . . . . . . . . . . . . . . 8
2.3 Graph with a heavy cycle and two loops . . . . . . . . . . . . . . . . . . . . 14
2.4 Anti-honeycombs ................................. 16
2.5 Conclusion..................................... 19
3 Lattice visibility and Panoptigons 22
3.1 Preliminaries ................................... 22
3.2 Properties of lattice polygons . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 A classification of all panoptigons . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4 Maximal polygons of lattice width 3 or 4 . . . . . . . . . . . . . . . . . . . . 37
3.5 Big face graphs are not tropically planar . . . . . . . . . . . . . . . . . . . . 42
3.6 Panoptigon computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4 Point-line geometry in the tropical plane 54
4.1 Introduction.................................... 54
4.2 Classical incidence geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 A brief introduction to tropical geometry . . . . . . . . . . . . . . . . . . . . 56
4.4 Tropical incidence geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.5 FurtherPerspectives ............................... 82
Bibliography 84
i
List of Figures
2.1
Graph with a sprawling node (left), a crowded graph (center), and a TIE-fighter
graph (right). Each box represents some subgraph of positive genus. . . . . . 5
2.2
Anti-honeycomb triangulation ∆
(−2,4;−2,4;−2,4)
of genus 4 (left), its dual graph
(center), and the corresponding skeleton (right) . . . . . . . . . . . . . . . . 7
2.3 Graph with the heavy cycle C.......................... 9
2.4
Two possibilities for
S1
and
S2
, which are ruled out a posteriori in the proof of
Lemma 2.2.3. Left:
S1
and
S2
are parallel. Right:
S1
and
S2
intersect in a point.
10
2.5
A graph with a sprawling triangle;
e1
,
e2
,
e3
are cut edges;
G1
,
G2
,
G3
are
subgraphs of positive genus. . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.6 Heavy cycle with two loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.7
This illustrates Theorem 2.3.3: general sketch (left) and the case when
g
(
P′
)
≥
4 (right), which is impossible . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.8 Examples of non realizable graphs of genus 7 and 8 . . . . . . . . . . . . . . 16
2.9 Anti-honeycomb triangulation of genus 19 on the left, and the corresponding
skeletonontheright ............................... 18
2.10
Anti-honeycomb quadrangles of zigzag type and their skeleta; genus 3, 4 and 5.
18
2.11 The four genus 5 graphs that are not ruled out by any prior known criteria . 19
2.12
The eight trivalent planar graphs of genus 6, which are not tropically planar
[16], but which are not covered by Theorem 2.3.4. . . . . . . . . . . . . . . . 21
3.1
Three panoptigons, with a panoptigon point circled and lines of sight illustrated;
the middle polygon has a second panoptigon point, namely the bottom vertex 22
3.2
Two lattice polygons, one with a relaxed polygon with a non-lattice vertex
marked; and one with a collapsed edge in the relaxed (lattice) polygon . . . 25
3.3 The 14 genus 1 polygons with lattice width 2 . . . . . . . . . . . . . . . . . . 27
3.4
A regular unimodular triangulation of a polygon, the dual graph of the trian-
gulation, and the corresponding tropically planar skeleton . . . . . . . . . . . 28
3.5 Forbidden patterns in tropically planar graphs of genus g≥6......... 29
3.6 Hyperelliptic polygons of Types 1, 2, and 3 . . . . . . . . . . . . . . . . . . . 31
ii
3.7
Possible lattice points in
P
, with impossible points labelled by the argument
rulingthemout.................................. 35
3.8
Narrowing down possible points depending on the number of points at height
−
1
36
3.9 The lattice width 4 polygons with exactly one doubly interior point . . . . . 39
3.10
The starting 4-regular graph in the chain construction; the two choices for
resolving a 4-valent vertex; and the three chains of genus 3, up to isomorphism 43
3.11 The looped chains of genus 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.12 Two embeddings of a planar graph related by a flipping . . . . . . . . . . . . 44
3.13
The structure of a looped chain, where the bridge-less chains
Gi
have solid
edges and the edges
ei
are dotted; the boundaries of the
Gi
are bold, and are
the only possible choices of Cforaflipping................... 44
3.14 The loop of loops Lgfor 3 ≤g≤6 ....................... 45
3.15
Starts of triangulations that will yield the loop of loops as the dual tropical
skeleton ...................................... 46
3.16
A tropically planar big face graph of genus 11, with a regular unimodular
triangulation giving rise to it . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.17 The three non-hyperelliptic panoptigons from Proposition 3.6.1 . . . . . . . . 48
3.18 Possible interior polygons for Pint, and polygons that must contain P. . . . 49
3.19 All nonhyperelliptic panoptigons with lattice diameter at least 3 . . . . . . . 52
3.20
All non-hyperelliptic panoptigons with 12 or 13 lattice points, along with their
relaxedpolygons ................................. 53
4.1 Atropicalline................................... 57
4.2 An example of a tropical near pencil arrangement . . . . . . . . . . . . . . . 59
4.3 An example of a tropical near pencil . . . . . . . . . . . . . . . . . . . . . . 59
4.4 The infinite number of lines passing through the coaxial points p0and p1. . 60
4.5 A stable tropical line (L, p0, p1) ......................... 60
4.6 Newton polytope and tropicalization for trop(P1P2).............. 61
4.7 Stable line passing through two given points . . . . . . . . . . . . . . . . . . 63
4.9 Duality between stable lines and stable intersections . . . . . . . . . . . . . . 63
4.8 Point sets which do not determine an ordinary stable tropical line . . . . . . 63
4.10
A cell in the Newton Subdivision, which is dual to a tropical line arrangement [
8
]
65
4.11
All possible shapes of faces present in the Newton subdivision of a tropical
line arrangement; with the labelings having type of stable intersections on the
left along with the type of face that corresponds to it on the right . . . . . . 66
4.12
An example of a line arrangement with exactly
n
faces and three triangular faces
67
iii
4.13
Positions of cells in the Newton subdivision and the local line arrangement
dualtoit ..................................... 68
4.14
Positions of cell in the Newton subdivision and the local line arrangement dual
toit ........................................ 69
4.15 The non-adjacent semiuniform faces determined by a triangular face T. . . 70
4.16
Examples depicting local line arranagements dual to a triangular face with 1
or 2 semiuniform faces adjacent to it. . . . . . . . . . . . . . . . . . . . . . . 71
4.17
An example to illustrate the rearrangement when
T
is adjacent to semiuniform
faces......................................... 72
4.18
An example to illustrate the rearrangement when
T
is adjacent to five or six
edgednon-uniformfaces.............................. 74
4.19
All cases where
T
is adjacent to two or three four edged non uniform faces
along with the corresponding rearrangement L′. ................ 74
4.20
All possibilities for
T
, when it shares a semiuniform face with another triangular
face......................................... 77
4.21
Possibilities for
T
, when it shares semiuniform faces with exactly two other
triangularfaces .................................. 78
4.22
The case when
T
shares semiuniform with two other triangular faces, with one
of the determined faces being a hexagon . . . . . . . . . . . . . . . . . . . . 78
4.23
Possibilities for
T
, when it shares semiuniform faces with three other triangular
faces ........................................ 79
4.24
Possibilities for
T
, when it shares semiuniform faces with three other triangular
faces, involving a hexagonal face which Tshares with one other triangular face 79
4.25
Possibilities for
T
, when it shares semiuniform faces with three other triangular
faces, involving a hexagonal face which Tshares with two other triangular face 79
4.26
The case for
T
, when it shares two hexagonal faces with four other triangular
faces ........................................ 80
4.27
Possibilities for
T
, when it shares semiuniform faces with four other triangular
faces ........................................ 81
4.28 The cases where Tshares faces with five or six other triangular faces . . . . 81
4.29
All possible shapes of faces present in the Newton subdivision of a tropical
line arrangement; with the corresponding type in the tropical oriented matroid
ontheright .................................... 83
iv
Chapter 1
Introduction
Tropical geometry started gaining immense traction as a new sphere for research starting from
the early years of the current century. Although, research had been conducted regarding max
plus algebras in the preceding century, the impact of the topic was realized only some decades
later with immensely strong results like the fundamental theorem of tropical geometry, tropical
convexity, etc [
38
]. This was also enhanced with various applications found in economics
[
5
], optimization [
33
], string theory [
25
] etc. which has brought the study of this subject
at the cross hair of researchers from various fields of interest. It even offers something of
interest to the star wars aficionado (cf.TIE-fighter graph [
16
]). In this thesis we would be
considering the connections between discrete geometry and the study of tropical curves,
relating lattice polytopes, regular subdivisions and tropical curves. Tropical geometry thrives
on the connections between tropical curves and their dual Newton subdivisions. Hence, let
us get acquainted with what is a subdivision and the combinatorics related to it. In [
20
], a
polyhedral subdivision is defined as follows,
Definition 1.0.1.
Let
J
be a set of labels for the point configuration
V⊂Rd
. A collection
∆ of subsets of Jis a polyhedral subdivision of Vif it satisfies the following conditions
1. If C∈∆ and F≤C, then F∈∆ as well. (Closure property)
2. ∪C∈∆convV(C)⊇convV(J). (Union Property)
3.
If
C
=
C′
are two cells in ∆, then relint
V
(
C
)
∩
relint
V
(
C
) = Φ. (Intersection Property)
Atriangulation of
V
is a polyhedral subdivision all of whose cells are simplices. If that
subdivision is induced by a height function on V, it is called regular.
Tropical geometry is briefly the study of polynomials and the hypersurfaces defined by
them, over the tropical semiring (
R∪ ∞,⊕,⊙
), where the binary operations act on the
elements in the following way
1
x⊕y= max(x,y) and x⊙y=x+y
The tropical semiring can also be considered with a min-plus operation, however we
would be considering the max-plus operation in our case. A tropical polynomial is a tropical
analogue of a polynomial with the binary operations between monomials replaced with tropical
operations. The usual notion of vanishing which is studied in classical algebraic geometry
is replaced in the realm of tropical geometry with the notion of maxima (or minima) being
achieved at least twice. The corresponding vanishing sets are referred as tropical hypersurfaces.
These hypersurfaces imbibe a metric graph structure, with each vertex satisfying a balancing
condition. In this thesis we would be studying tropical planar curves which are hypersurfaces
corresponding to bi-variate tropical polynomials.
We now define the setup for smooth tropical planar curves, which we would be studying
in this work. Let
P
be a (convex) lattice polygon, i.e.,
P
is the convex hull of finitely many
points in
Z2
, and
V
=
P∩Z2
is the set of lattice points in
P
. We refer to the convex hull of
the interior points of
P
as the interior polygon of
P
, denoted
Pint
. If
dim
(
Pint
) = 2, we call
P
non-hyperelliptic; if
dim
(
Pint
)
≤
1, we call
P
hyperelliptic. Any function
h
:
V→R
can be
identified with a tropical polynomial as follows [10],
p(x, y) = ⨁︂
(i,j)∈V
h(i,j)⊙xi⊙yj
The tropical curve
C
corresponding to this tropical polynomial is dual to a regular
subdivision of V, which can be obtained by raising the lattice points in Vto corresponding
heights in
R3
, the heights being specified by the function
h
. We consider the upper convex hull
of the points in
V
and their corresponding heights and obtain the subdivision by projecting
back to
R2
. The maximal cells are obtained as images of facets of the upper convex hull
under projection [
10
]. In the planar case, such a regular subdivision is a triangulation if
all maximal cells are triangles. A triangulation ∆ of
V
is unimodular if each triangle in ∆
has normalized area one, i.e., Euclidean area
1
2
. This is the case if and only if ∆ uses all
points in
V
(by Pick’s Theorem [
44
]) . We refer a tropical planar curve dual to a unimodular
triangulation as a smooth tropical planar curve.
Any tropical plane curve
C
contains a trivalent, planar, minor
G
which has exactly
g
distinct cycles, and it is the smallest space to which the curve admits a deformation retract.
We refer to this graph as the skeleton of genus
g
of the tropical curve. Each skeleton has
2
g−
2 vertices and 3
g−
3 edges [
10
]. We also notice that skeleta of unimodular regular
triangulations of lattice polygons are termed as tropically planar or “troplanar” graphs in [
16
],
and we refer the tropical curves corresponding to a tropically planar skeleton as realizable
2
smooth tropical planar curve. We explain in Chapter 2.1 how this minor is obtained from a
tropical curve and how it relates to the dual unimodular triangulations.
Tropical curves have been studied previously since they occur as the simplest examples of
tropical hypersurfaces. Additionally, the moduli spaces associated with planar tropical curves,
Mplanar
g
enjoys intricate and important connections to moduli spaces in classical algebraic
geometry. An important aspect of study has been to analyze the cohomology of classical
spaces in algebraic geometry by using the connections with the moduli space of tropical
curves, as explored in [
15
]. In 2015, Brodsky et al [
10
] studied the moduli space of tropical
curves, for lower genera
g
= 3
,
4 and 5. This boiled down to studying the underlying skeletons
of all possible smooth tropical planar curves of a given genus. In there study, with the help
of a computational setup, they were able to find which trivalent planar graphs could occur as
skeletons for lower genera. There study showed that not all graphs can occur and one can try
to come up with combinatorial criteria to specify graphs which are forbidden from occurring
as skeletons. This approach was pushed to genus 7 in Coles et al [
16
], along with new criteria
for forbidden skeletons. However, these studies could not provide a complete classification
and as they involve computational enumeration of triangulations, therefore the results are
bounded by computational complexity, which increases rapidly as the genus increases. In
this thesis, we try to find answers to the questions which arose from [
10
] and [
16
] and in the
first chapter we provide two new criteria for graphs which are forbidden from occurring as
skeletons. This also leads us to studying highly symmetrical triangulations which we refer to
as anti-honeycomb. Also, with our results we are able to provide a full classification of all
curves for genus
g≤
5, independent of the previous computational setup, i.e., by eliminating
all graphs which fall under known criteria.
In the third chapter of this thesis, we study lattice visibility, which can be understood as the
search for lattice points inside polytopes which can be connected to all other lattice points via
a straight line, without any intermediate lattice point. Visible points inside lattice polytopes
have been studied previously based on applications relating to optimization and even in
theoretical physics [
28
]. In this thesis, we define a new class of lattice polygons panoptigons,
which have a lattice point which is visible to all other lattice points. We first show that there
are only finitely many panoptigons and enumerate all possible nonhyperelliptic panoptigons,
via a constructive proof and a computational enumeration. This study regarding lattice
polytopes was however inspired by questions concerning tropical curves, and we elaborate
this connection by establishing a new criteria namely big face graphs, which is based on the
enumeration of panoptigons. This provided us with a new criteria for skeletons apart from
crowded criterion, which does not involve a cut edge.
3
In the last chapter, we move on to the arrangement of the simplest example of tropical
curves, namely tropical line arrangements. We provide a definition for a stable tropical line
and establish the equivalence between previously known notions of stable tropical lines, and
using this definition we state and prove the tropical analogue of the classical De Beuijn
Erd˝os theorem, which establishes a lower bound on the number of lines determined by a set
of points. This is inspired by recent point-line incidence results proved in [
8
]. Hyperplane
arrangements have been studied previously in tropical geometry, entailing to connections
with tropical convexity [
21
], hence tropical line arrangements turn out to be the base case in
this scenario. Also, hyperplane arrangements have been studied in order to explore there
connections with subdivisions of dilated simplex and a notion of a tropical oriented matroid
is established in [
2
] in connection to hyperplane arrangements. In the light of all these results,
we establish the lower bound on the number of stable tropical lines determined by a set of
n
points in the tropical plane, hence a tropical De Bruijn Erd˝os theorem. With projective
duality, the result also translates to tropical line arrangements and stable intersections. The
proof of this result brings out the deep connections between faces of dual Newton subdivision
and corresponding stable intersections. We also state the connections of our result with the
study of tropical oriented matroids as specified in [2].
In summary, in this thesis we study which graphs can occur as skeletons of smooth tropical
planar curves; this classification provides us insights about the moduli space of tropical curves
and with our results we are able to provide a complete classification for lower genera. In
this process, we also discover a new class of lattice polygons, which helps us understand
lattice visibility in greater details, and in turn relates back to our study of tropical curves
by helping us to establish a new criteria for forbidden skeletons. Subsequently, we study
an active example of curves in the forms of tropical line arrangements and study point-line
incidence in the tropical plane.
4
Chapter 2
Forbidden patterns in tropical plane
curves
2.1 Lattice polygons and tropical plane curves
We start with a finite set of points
V⊂Rd
and recall that polyhedral subdivision of
V
is a
polyhedral complex which covers the convex hull
conv V
and uses (a subset of) the given
point set
V
as its vertices. Let
P
be a (convex) lattice polygon, and
V
=
P∩Z2
is the set of
lattice points in P.
Let ∆ be a (not necessarily unimodular) triangulation of
V
. The dual graph Γ = Γ(∆) is
the abstract graph whose nodes are the triangles of ∆; they form an edge in Γ if two triangles
share an edge in ∆. The dual graph is necessarily connected and planar, and each node has
degree at most three.
Figure 2.1: Graph with a sprawling node (left), a crowded graph (center), and a TIE-fighter
graph (right). Each box represents some subgraph of positive genus.
Next we describe a procedure to obtain the skeleton
G
from Γ. First, if there is a node of
degree one, we delete it together with the unique incident edge. We repeat this step until
no nodes of degree one are left. The remaining edges are nonredundant. Second, if there
is a node of degree two, we delete the node and join its neighbors by an edge. Again we
repeat until there are no more nodes of degree two. The resulting graph is the skeleton. By
5
construction the skeleton is a trivalent planar graph, and it does not depend on the ordering
in which the edge deletions and contractions are performed [
24
, Section 3.1.2]. In this way
each edge of
G
arises as an edge path in Γ. This yields a surjective map, which we denote
η
,
from the nonredundant edges of Γ onto the edges of
G
. Note that this contraction map
η
is
undefined for any edge which is redundant. This elementary description of the skeleton is
algorithmic in nature and serves our purposes.
Asplit is a subdivision of
V
with exactly two maximal cells; it is necessarily regular [
27
,
Lemma 3.5]. If
U
and
W
are the two maximal cells of a split, then the intersection
U∩W
is a common edge of the two convex polygons
U
and
W
. It spans the corresponding split
line. A set of splits of
V
is weakly compatible if there is a triangulation which simultaneously
refines them all. Moreover, a set of splits is (strongly) compatible if any two split lines do not
meet in the interior of
P
. Compatibility implies weak compatibility. The split lines of two
weakly compatible splits which are not strongly compatible must meet in a point in
V
, i.e.,
an interior lattice point of
P
. An edge
e
of the connected graph
G
is a cut edge if deleting
e
creates two connected components. Otherwise elies in some cycle of G.
The following three technical results are extracted from the proof of [
16
, Theorem 3.4],
where cut edges are called “bridges”.
Lemma 2.1.1.
Let
e
be a cut edge of
G
. Then
η−1
(
e
)comprises a single cut edge of Γ,
which is dual to an edge,
s
, of ∆. Moreover, the vertices of
s
lie on the boundary
∂P
, and
s
spans a split line of V.
Here the “vertices” are the two endpoints of the edge
s
. In the unimodular case these
are also the only lattice points contained in
s
. Our arguments below do not rely on the
uniqueness of the cut edge in
η−1
(
e
). It suffices to know that such edge (and its dual edge
s
)
exist.
Lemma 2.1.2.
Let
e
be an edge between
v1
and
v2
in a cycle,
C
of
G
. Furthermore, let
T1
and T2be triangles in ∆which correspond to v1and v2on the path η−1(e). Then T1and T2
share an interior lattice point of P, and this is dual to C.
Lemma 2.1.3.
Let
z∈V
be some lattice point in
P
with two incident triangles
T1
=
conv{z, a1, b1}
and
T2
=
conv{z, a2, b2}
both of which are in ∆. Further, let
Li
be the line
spanned by
ai
and
bi
, for
i
= 1
,
2. Suppose that
L1
and
L2
meet in some point, say
w
, such that
ai
is closer to
w
than
bi
, for
i
= 1
,
2. Then the interior of the quadrangle
conv{z, a1, w, a2}
does not contain a point in V, unless a1=a2=w.
With this we can take a small first step to our main results. Recall that Lemma 2.1.1
associates a split of Vto each cut edge of G.
6
Lemma 2.1.4. Splits corresponding to distinct cut edges are compatible.
Proof.
It suffices to consider pairs of splits. From Lemma 2.1.1 the cut edges
e1
and
e2
yields
two split lines,
S1
and
S2
, which may not be unique. Unless
S1
and
S2
are compatible, they
must meet in a point of the point configuration
V
, which does not lie on
∂P
, i.e., an interior
lattice point of
P
. Yet, by Lemma 2.1.1 the line
S1
(and similarly
S2
) contains precisely two
points of V, and neither lies in the interior.
We now recall the duality between unimodular triangulations of lattice polygons and
smooth tropical planar curves as discusssed in Chapter 1. We illustrate this duality with the
following example,
Example 2.1.5. We consider the anti-honeycomb triangle
A(−2,4; −2,4; −2,4) = conv{(2,2),(−2,0),(0,−2)},(2.1.1)
which occurs as
Q(4)
3
in [
10
]. The genus is
g
(
A(−2,4;−2,4;−2,4)
) = 4. We call the unimodular
triangulation ∆
(−2,4;−2,4;−2,4)
, shown in Figure 2.2 (left), the anti-honeycomb triangulation of
A(−2,4;−2,4;−2,4)
. Its skeleton, shown in Figure 2.2 (right) and called (303) in [
10
], features three
cut edges which correspond to three compatible splits of
A(−2,4;−2,4;−2,4)
. The triangulation
∆
(−2,4;−2,4;−2,4)
is regular, whence it defines a moduli cone of tropical plane curves. That
cone is 7-dimensional, while the entire moduli space
Mplanar
4
has dimension nine; see [
10
,
Table 4]. See Section 2.4 for a more comprehensive discussion of anti-honeycomb polygons,
their triangulations and the notation (2.1.1).
Figure 2.2: Anti-honeycomb triangulation ∆
(−2,4;−2,4;−2,4)
of genus 4 (left), its dual graph
(center), and the corresponding skeleton (right)
We now sketch the forbidden patterns which are known already. A node in
G
is sprawling
if its deletion leaves three connected components; cf. Figure 2.1 (left). This obstruction to
tropical planarity was identified in [
12
, Proposition 4.1] and [
10
, Proposition 8.3]. Note that
graphs with a sprawling node were called “sprawling” in [
10
] and [
16
]. A planar embedding
7
of a graph
G
is called crowded if either: there exist two bounded regions sharing at least two
edges; or, there exists a bounded region sharing an edge with itself. If all planar embeddings
of
G
are crowded, then
G
itself is said to be crowded. In [
40
, Lemma 3.5], it is shown that
crowded graphs can never be tropically planar. Additionally, [
40
, Corollary 3.7] describes a
family of crowded graphs, and this is depicted in Figure 2.1 (center). A graph is a TIE-fighter
if it looks like the one in Figure 2.1 (right). TIE-fighter graphs can never be tropically planar;
this was shown in [16, Theorem 3.4].
2.2 Heavy Cycles and Sprawling Triangles
Let
P
be a lattice polygon with precisely
g
interior lattice points. Moreover, let ∆ be a
unimodular triangulation of
P
with dual graph Γ = Γ(∆) and skeleton
G
(∆) =
G
. The
contraction map
η
sends nonredundant edges of Γ to edges of
G
. The
g
interior lattice points
of
P
bijectively correspond to the bounded regions of the planar graph
G
. By Euler’s formula
we have
g
=
m−n
+ 1, where
m
and
n
are the numbers of edges and nodes of
G
, respectively.
Our arguments in this section do not require ∆ to be regular. That is, our results extend to
a class of planar graphs, which is slightly more general than tropical plane curves.
Two lattice polygons,
P
and
Q
, are unimodularly equivalent if there is a lattice vector
α∈Z2
and an integer linear transformation
τ∈SL
(2
,Z
) such that
P
=
α
+
τ
(
Q
); cf. [
20
,
Section 9.3]. In that case, we have
P∩Z2
=
α
+
τ
(
Q∩Z2
), i.e., the lattice points are
transformed alike. The map x↦→ α+τ(x) is a unimodular transformation.
Lemma 2.2.1.
Assume that
P
contains a unimodular triangle with vertices
a, b, z
such that
neither
a
nor
b
is a vertex of
P
, and
z
is an interior lattice point. If
a
and
b
lie on
∂P
then
either aand blie on a common edge of Por the lattice point a+b−zis contained in P.
Proof.
Up to unimodular equivalence we may assume
a
= (1
,
0),
b
= (0
,
1) and
z
= (0
,
0). Let
L
and
M
be the lines spanned by the edges of
P
containing
a
and
b
, respectively. Suppose
that (1
,
1) is not contained in
P
. Since
P
is a lattice polygon, then the intersection of
P
with the positive orthant agrees with the unit triangle
abz
. This entails that
L
and
M
agree,
which means that L=Mdefines an edge of P, and this contains aas well as b.
Definition 2.2.2. We say that a cycle Cin a planar graph Gis heavy, if
1.
it has two nodes,
v1
and
v2
, such that
vi
is incident with a cut edge
ei
connecting
vi
with a subgraph Giof positive genus;
2.
and there is a third subgraph,
G3
, also of positive genus, which shares at least one node
with the cycle C; cf. Figure 2.3.
8
v2v1
C
e2e1
G3
G2G1
Figure 2.3: Graph with the heavy cycle C
In particular, a graph with a heavy cycle has genus at least four. From the classification
of hyperelliptic graphs in [
40
], we infer that a graph with a heavy cycle is not hyperelliptic.
Moreover, it follows from Lemma 2.1.1 that there are split lines,
S1
and
S2
, dual to the edges
e1
and
e2
of
G
. While the split lines may not be unique we just pick some. By Lemma 2.1.4
the splits
S1
and
S2
are compatible, and thus
P
decomposes into a union of three lattice
polygons
P1
,
P2
and
P′
such that ∆ induces triangulations of all three. In this way, we get
triangulations ∆
1
, ∆
2
and ∆
′
such that the component
Gi
is the skeleton of ∆
i
for
i
= 1
,
2,
and
G3∪C
is the skeleton of ∆
′
. The triangles in ∆
′
which are dual to
v1
and
v2
are denoted
T1
and
T2
, respectively. We refer to the polygon
P′
as the heavy component of
P
, and likewise
∆
′
is the heavy component of ∆. Expressed in the language of [
16
], the heavy component ∆
′
arises from ∆ via “bridge-reduction”.
The following lemma is the technical core of this chapter. Its proof is a bit cumbersome,
with several cases to distinguish. However, it is rather powerful as it delineates a fine border
between trivalent planar graphs which are realizable as skeleta of tropically planar curves
and those which are not.
Lemma 2.2.3.
Suppose that
G
has a heavy cycle with cut edges
e1
and
e2
as in Figure 2.3.
Then the triangles
T1
and
T2
in ∆share an edge [
z, w
], where
z
is the interior lattice point
dual to
C
, and the split lines
S1
and
S2
intersect in
w
, which is a vertex of
P′
, and which
lies in the boundary of P.
Before we enter the proof, we sketch an outline. The overall strategy is indirect, i.e.,
we will assume that
T1
and
T2
share a vertex but not an edge. Now the split lines from
Lemma 2.1.4 are either parallel or not; cf. Figure 2.4. In both cases we can exploit the
convexity of the four lattice polygons
P1
,
P2
,
P′
and
P
to arrive at contradictions. The
situation with intersecting split lines is the more difficult one, as it ramifies into sub-cases.
Proof.
By Lemma 2.1.2 the triangles
T1
and
T2
share a vertex
z
, which is the interior lattice
point in
P
dual to the heavy cycle
C
. Up to a unimodular transformation we may assume
that z= (0,0), and T1= conv{z, (1,0),(0,1)}.
9
T1
T2zp1
p2
q
r
s1
s2
P′
T1
T2
zp1
p2w
s1
s2
P′
Figure 2.4: Two possibilities for
S1
and
S2
, which are ruled out a posteriori in the proof of
Lemma 2.2.3. Left: S1and S2are parallel. Right: S1and S2intersect in a point.
We consider the point (1
,
1). We notice that if (1
,
1)
∈ P
, then by convexity of
P
, the
positive genus component attached to the split edge
s1
= [(1
,
0)
,
(0
,
1)] is squeezed between
the lines
y
= 0 and
y
= 1, which has no interior lattice points and we get a contradiction.
Therefore the point (1
,
1) lies in
P
. We want to show that (1
,
1) is an interior lattice point of
P1
(and
P
). First, since (1
,
0) is in the boundary and
z
is in the interior of
P
, there are no
interior lattice points on the ray (1
,
0) +
pos{
(1
,
0)
}
. Similarly, there are no interior lattice
points on (0
,
1) +
pos{
(0
,
1)
}
. However, since
G1
has positive genus at least one interior
lattice point of
P1
exists, and it must lie in the translated orthant (1
,
1) +
pos{
(1
,
0)
,
(0
,
1)
}
.
As (1
,
0) and (0
,
1) lie in
P1
it follows from the convexity of
P1
that (1
,
1) must be an interior
lattice point. Now consider the triangle
T2
=
conv{z,
(
α, β
)
,
(
γ, δ
)
}
where
α, β, γ, δ ∈Z
with
αδ −βγ = 1 .(2.2.1)
Suppose
T1
and
T2
do not share an edge. We are aiming for a contradiction, which then
establishes a proof of this lemma. Since (1
,
1)
∈int P1
the horizontal line (0
,
1) +
R
(1
,
0)
intersects
P′
only in (0
,
1). Similarly, the vertical line (1
,
0) +
R
(0
,
1) intersects
P′
only in
(1,0). As (α, β), (γ, δ), (1,0), and (0,1) are pairwise distinct this yields α, β, γ, δ ≤0.
First, suppose the split line
S2
is parallel to
S1
. As
T2
is a unimodular triangle
S2
is
the line through (
−
1
,
0) and (0
,−
1). Then,
S2
and
α, β, γ, δ ≤
0 forces
α
=
δ
=
−
1 and
β
=
γ
= 0. We consider the lattice points
q
= (
−
1
,
1) and
r
= (1
,−
1). As
P′
has positive
genus, it follows from Lemma 2.2.1 that either
q
or
r
is an interior lattice point of
P′
. By
symmetry we may assume
r∈int P′
. Then, the point
q
can either lie on the boundary of
P
or is not in
P
. Now the interval [(1
,
1)
,
(1
,−
1)] is the convex hull of two interior lattice
points of
P
, but it contains the boundary point
p1
in its relative interior. Hence we obtain a
contradiction.
10
We conclude that the split lines
S1
and
S2
intersect in some point
w
= (
ψ, ω
), as depicted
in the Figure 2.4. Since
T1
is fixed,
T1
and
T2
do not share an edge and
α, β, γ, δ ≤
0, we
obtain
ω≤
0. We use the labels from Figure 2.4 and intend to show that
w
lies in
∂P
.
Suppose the contrary. Then, due to Lemma 2.1.4, the point
w
must lie outside
P
. From
our choice of
w
we see that distance between the point
p1
:= (1
,
0) and
w
is lesser than the
distance between the points (0
,
1) and
w
. From
(2.2.1)
it follows that the distance between
p2
:= (
γ, δ
) and
w
is lesser than the distance between
w
and (
α, β
). Applying Lemma 2.1.3 we
infer that the interior of the quadrangle
conv{z, p1, w, p2}
does not contain an interior lattice
point of
P
. We realize that since the triangles
T1
and
T2
do not share an edge, and since
p1, p2∈∂P therefore in this case [p1, p2] is a boundary edge and the triangle conv{z, p1, p2}
belongs to ∆.
We now look at possible coordinates of the point
p2
= (
γ, δ
). Since the triangle
conv{z, p1, p2}
is unimodular and as
δ≤
0 we have
δ
=
−
1. Hence
p2
lies on the ray
{
(
γ, δ
)
:γ≤
0
, δ
=
−
1
}
. We consider some values of
γ
starting with the case of
γ
= 0. Then
(2.2.1)
implies that (
α, β
) is on the line
x
=
−
1, i.e.,
α
=
−
1. We explore the possible values
for β.
For
β
=
−
2 the split edge on the line
S2
would be
s2
= [(0
,−
1)
,
(
−
1
,−
2)]. This cannot
be as then
S2
would contain
p1
as a third boundary point, a contradiction to Lemma 2.1.1.
For
β
=
−
1 and
s2
= [(0
,−
1)
,
(
−
1
,−
1)], we realize that the polygon
P2
is bounded in the
rectangular strip between the parallel lines
y
=
x
and
y
=
x−
1. Yet there is no interior
lattice point between them, and this contradicts
G2
to have positive genus. Any other value
of β < −2 contradicts the convexity of Pat z. This rules out the possibility γ= 0.
The arguments for excluding the other values of
γ
are very similar. We summarize them
briefly. For
γ
=
−
1 we obtain
β
=
α
+ 1. Then either
s2
= [(
−
1
,−
1)
,
(
−
1
,
0)], and we obtain
ω
= 2
≥
0, which is absurd. Or
s2
= [(
−
1
,−
1)
,
(
−
2
,−
1)], whence
P2
is squeezed between
the lines 2
y
=
x
and 2
y
=
x−
1, which does not leave space for an interior lattice point. Or
s2
= [(
−
1
,−
1)
,
(
−
3
,−
2)], which then lies on the line spanned by the boundary edge [
p1, p2
].
Again, any other value of βon the line y=x+ 1, contradicts the convexity of Pat z.
Similarly, when
γ
=
−
2, we obtain 2
β
=
α
+ 1. Then either
s2
= [(
−
2
,−
1)
,
(
−
1
,
0)], and
we obtain
ω
= 1
≥
0, which is absurd. Or
s2
= [(
−
2
,−
1)
,
(
−
3
,−
1)], whence
P2
is squeezed
between the lines 3
y
=
x
and 3
y
=
x−
1, which does not leave space for an interior lattice
point. Or
s2
= [(
−
2
,−
1)
,
(
−
5
,−
2)], which then lies on the line spanned by the boundary
edge [
p1, p2
]. Again, any other value of
β
on the line 2
y
=
x
+ 1, contradicts the convexity of
Pat z.
The case
γ≤ −
3 is left. Then the point (
α, β
) lies on the line
−γy
=
x
+ 1. The
following three possibilities occur for the split edge
s2
. Either
s2
= [(
−
1
,
0)
,
(
γ, −
1)], and
11
e2
e3
e1
G3
G2G1
Figure 2.5: A graph with a sprawling triangle;
e1
,
e2
,
e3
are cut edges;
G1
,
G2
,
G3
are
subgraphs of positive genus.
we obtain
ω≥
0, forcing
ω
= 0. In this case we see that there is no edge to join between
the points (
−
1
,
0) and (0
,
1) such that the polygon
P
remains convex, which gives us
a contradiction. Or
s2
= [(
γ−
1
,−
1)(
γ, −
1)], whence
P2
is squeezed between the lines
(1
−γ
)
y
=
x
and (1
−γ
)
y
=
x−
1, which does not leave space for an interior lattice point.
Or
s2
= [(2
γ−
1
,−
2)
,
(
γ, −
1)], which then lies on the line spanned by the boundary edge
[p1, p2]. Any other value of βon the line −γy =x+ 1, contradicts the convexity of Pat z.
Therefore, finally, we conclude that there is no lattice point
p2
= (
γ, δ
) such that the
triangle
conv{z, p1, p2}
belongs to ∆. Hence, our initial assumption was wrong, and the
triangles
T1
and
T2
do share the edge [
z, w
], where
w
=
p1
=
p2
is the intersection of
S1
and
S2. Consequently, s1and s2are two distinct edges of P′, and so wis a vertex of P′.
We notice that the anti-honeycomb triangulation of genus 4 in Example 2.1.5 and Figure 2.2
is a positive example for the result in Lemma 2.2.3. For the three triangular cells containing
the split edges and sharing a common vertex, each pair of them has a common edge. In fact,
the specific shape of the heavy component in that example gives rise to another concept,
which covers a special case of Definition 2.2.2.
Definition 2.2.4.
We say that the planar graph
G
has a sprawling triangle if it has a cycle
with three nodes, each of which is also incident with a unique cut edge, such that at the
other end there is a subgraph of positive genus; cf. Figure 2.5.
It turns out that Example 2.1.5 is the only case where this occurs:
Theorem 2.2.5.
If
G
has a sprawling triangle then
g
= 4, and, up to unimodular equivalence,
we have
P=A(−2,4; −2,4; −2,4) and ∆ = ∆(−2,4; −2,4; −2,4) .
12
Proof.
We use the notation from Figure 2.5. Let
s1, s2
and
s3
be the split edges in ∆
corresponding to the cut edges
e1, e2
and
e3
. Using Lemma 2.2.3 on these three splits, we
obtain that each pair of them intersects in a point on
∂P
. This gives three lattice points
a, b, c
in the boundary of
P
such that each pair is joint by one of the three edges
s1, s2, s3
.
Let ∆
|abc
be the subcomplex of ∆ restricted to the lattice triangle
abc
. Its skeleton is the
sprawling triangle, whose genus is one. Hence there is a unique interior lattice point,
z
, of
P
contained in
abc
. It follows that the lattice triangle
abc
has normalized area three, and its
unimodular triangulation into
abz
,
acz
, and
bcz
forms the induced subcomplex ∆
|abc
. Those
maximal cells of ∆ are dual to the three nodes of the sprawling triangle of G.
As in the proof of Lemma 2.2.1 we may assume that a= (1,0), b= (0,1) and z= (0,0).
It then follows that
c
= (
−
1
,−
1). Directly from Definition 2.2.4 it follows that the line
ab
is dual to a cut edge in
G
and thus induces a split of ∆. All the interior lattice points
corresponding to a region of the subgraph
G1
must lie in the halfspace defined by
ab
which
does not contain
z
. Since
z
is the only interior lattice point of
P
which does not correspond
to a region of G1∪G2∪G3, the lattice points a,band cmust lie in the boundary of P.
Now Definition 2.2.4 requires the subgraphs
G1
,
G2
and
G3
to have positive genus. This
excludes the possibility that one of the three points
a, b, c
is a vertex of
P
. Thus they must
lie on pairwise distinct edges of
P
. Now we can apply Lemma 2.2.1 three times to learn that
the three lattice points
(1,0) + (0,1) −(0,0) = (1,1)
(1,0) + (−1,−1) −(0,0) = (0,−1)
(0,1) + (−1,−1) −(0,0) = (−1,0)
are contained in P.
Let
L, M, N
be the three lines spanned by the edges of
P
through
a, b, c
, respectively.
Suppose that (1
,
1) is a boundary point of
P
. Then, since
P
is lattice polygon, (1
,
1) is the
intersection point of
L
and
M
and thus a vertex of
P
. This contradicts the fact that
G1
has
positive genus, and it follows that (1
,
1) is an interior lattice point of
P
. By symmetry, also
(0,−1) and (−1,0) are interior lattice points of P.
Now the lattice point (1
,
2) is not contained in
P
because it would then need to lie on the
line
M
, together with (
−
1
,
0). But this cannot happen as (
−
1
,
0) was already identified as
an interior point of
P
. Similarly, (2
,
1) is not contained in
P
either. Yet this implies that the
intersection of the lines
L
and
M
lies strictly between the two parallel lines (1
,
0) +
λ
(1
,
1)
and (0
,
1) +
λ
(1
,
1). Thus there is at least one vertex of
P
, which must be a lattice point, on
the line (0,0) + λ(1,1). This forces (2,2) to lie in P.
Again the situation is symmetric, which is why also (
−
2
,
0) and (0
,−
2) lie in
P
. The
single choice left is that (2
,
2) as well as (
−
2
,
0) and (0
,−
2) are vertices of
P
, and
L, M, N
13
are the only facets. This establishes
P
=
conv{
(
−
2
,
0)
,
(0
,−
2)
,
(2
,
2)
}
. The claim about ∆
follows as there is only one way to extend the triangulation from the triangle
abc
to all of
P.
Remark 2.2.6.Contracting a sprawling triangle in a planar graph yields a graph with a
sprawling node, and this cannot be tropically planar. Therefore, Example 2.1.5 shows that
the class of tropically planar graphs is not minor closed; this was observed before [
16
, Figure
6].
2.3 Graph with a heavy cycle and two loops
Graphs with a sprawling triangle form special cases of graphs with a heavy cycle. Thus our
main technical result, Lemma 2.2.3, allowed us to derive decisive structural constraints for
triangulations whose skeleton has a sprawling triangle in Theorem 2.2.5. Now we are looking
into another special class of groups with a heavy cycle, aiming for a second structural result
on unimodular triangulations of lattice polygons.
Definition 2.3.1.
We say that a connected trivalent planar graph
G
has a heavy cycle with
two loops if it has the form as described in Figure 2.6, where the shaded region represents a
subgraph of positive genus.
v2v1
e2e1
C
G3
Figure 2.6: Heavy cycle with two loops
The latter is the special case of Definition 2.2.2, where
g
(
G1
) = 1 =
g
(
G2
). This type of
skeleton does actually occur.
Example 2.3.2.
The quadrangle
Q(5)
4
of genus 5, cf. [
10
, Figure 22], admits a (regular)
unimodular triangulation whose skeleton features a heavy cycle with two loops, cf. [
10
,
Figure 23].
Our aim in this section is to establish the following,
14
T1
z
w r
s1
s2
r′
P′
p2
p1
T1
z
w r
q
s1p1
Figure 2.7: This illustrates Theorem 2.3.3: general sketch (left) and the case when
g
(
P′
)
≥
4
(right), which is impossible
Theorem 2.3.3.
Suppose
G
is a graph with a heavy cycle
C
and two loops with cut edges,
e1
and
e2
, as in Figure 2.6. Then the heavy component
P′
can have at most three interior lattice
points, and these lie on the line spanned by the edge [
z, w
]
∈
∆, where
z
is the interior lattice
point dual to
C
, and
w
is the intersection point of the split edges
s1
and
s2
. In particular,
P′
is hyperelliptic and g≤5.
Proof.
It follows from Lemma 2.2.3 that the two triangles share the edge [
z, w
], where
w∈∂P
is the point where the two split edges meet. We will first show that the interior lattice points
of P′lie on the line spanned by [z, w].
As previously, we fix
T1
=
conv{
(0
,
0)
,
(0
,
1)
,
(1
,
0)
}
and use the labels from Figure 2.7; in
particular, we may assume that
w
= (0
,
1). Using Lemma 2.2.3 and the unimodularity of
T2
,
we realize that
p2
must lie on the line
x
=
−
1; so let
p2
= (
−
1
,−k
) for some integer
k
. We
use Lemma 2.2.1 on the points
z
= (0
,
0),
w
= (0
,
1) and
p1
= (1
,
0) and infer that the point
r
:= (1
,
1) is an interior lattice point of
P
; moreover it is the unique interior lattice point of
P1
. Similarly, we infer that the point
r′
:= (
−
1
,−k
+ 1) is the unique interior lattice point of
P2
. By considering the lines connecting the interior point
r
with the boundary points
p1
and
w
, respectively, we see that
k≥
0. The same argument shows that the entire polygon
P′
is
squeezed between the lines
x
= 1 and
x
=
−
1. In particular, the interior lattice points of
P′
lie on x= 0, which is the line spanned by zand w.
Next we will show that
g
(
P′
)
≤
3. We assume the contrary, i.e.,
g
(
P′
)
≥
4 Then, since all
interior lattice points of
P′
lie on the line
x
= 0, the point (0
,−
3) must be an interior lattice
point of P.
15
The vertical line
x
= 1 contains the point
p1
, which is a boundary point, and
r
, which
is an interior lattice point. It follows that there is a lattice point (1
, λ
) in the boundary of
P1
for
λ >
1; in particular, either (1
,
2)
∈P1
or the boundary edge at
w
passes through a
point in the open interval ((1
,
2)
,
(1
,
1)). Also, as (0
,−
3) is an interior point, no point in
∂P1
is present on the line
y
= 3
x−
3. We realize that in this case
P1
is contained in the
triangle
conv{p1, w,
(1
,
3)
}
. However, this triangle has no valid lattice point which could be a
vertex of
P1
; recall that (1
,
3) has been excluded; see Figure 2.7. This provides the desired
contradiction, and thus g(P′)≤3.
The above result is sharp as Example 2.3.2 shows. The following summarizes the known
obstructions to tropical planarity together with our new results.
Theorem 2.3.4.
A trivalent planar graph of genus
g≥
3is not tropically planar if one of
the following holds:
1. it contains a sprawling node, or
2. it contains a sprawling triangle and g≥5, or
3. it is crowded, or
4. it is a TIE-fighter, or
5.
it has a heavy cycle with two loops such that the interior lattice points of the heavy
component do not align with the intersection of the two split lines.
Figure 2.8: Examples of non realizable graphs of genus 7 and 8
For instance, the preceding result excludes the graphs in Figure 2.8.
2.4 Anti-honeycombs
The purpose of this section is to define a class of lattice polygons each of which admits a
special triangulation. This is motivated by Theorem 2.2.5, which characterizes one of these
16
triangulations. These triangulations show high degree of symmetry and the entire family
deserves some attention. Consider three families of parallel lines:
Lk={y=2x+k}, Mℓ={2y=x−ℓ}, Nm={y=−x+m},(2.4.1)
where
k, ℓ, m ∈Z
. By picking a sixtuple
π
= (
k, k′
;
ℓ, ℓ′
;
m, m′
), with
k < k′
,
ℓ < ℓ′
, and
m < m′
we obtain a polygon
Aπ
which is defined by three pairs of inequalities, where each
pair comes from one of the parallel families
(2.4.1)
. We call
Aπ
the anti-honeycomb polygon
of type
π
; in general, this is not a lattice polygon. The following characterizes when the
lines from the three families intersect at lattice points; we omit the proof, which is a direct
calculation.
Lemma 2.4.1. We have
1. Lk∧Mℓ∈Z2if and only if k−ℓis divisible by 3;
2. Lk∧Nm∈Z2if and only if k−mis divisible by 3;
3. Mℓ∧Nm∈Z2if and only if ℓ−mis divisible by 3.
The name comes about from the connection to the “honeycomb polygons” studied in [
10
,
pp. 10ff]. Note that not all of the six inequalities need to be facet defining, whence
Aπ
is a
hexagon, a pentagon, a quadrangle or a triangle. For instance,
A(k,−2k;k,−2k;k,−2k)= conv{(−k, −k),(0, k),(k, 0)}(2.4.2)
is a triangle, and its genus equals
g(A(k,−2k;k,−2k;k,−2k)) = 3k2−3k+ 2
2.
We fix a type
π
= (
k, k′
;
ℓ, ℓ′
;
m, m′
), and we let
V
=
Aπ∩Z2
be the set of lattice points
in Aπ. Intersecting with the shifted lattice
L=(︃−1
−1)︃+Z(︃2
1)︃+Z(︃1
2)︃
of index 3 we obtain a subset
V′
=
V∩L
of the lattice points in
Aπ
. The families of lines
(2.4.1)
yield weakly compatible splits of the point configuration
V′
, and they induce a triangulation
∆
′
π
of the lattice points in
V′
. Notice that all the points in
V\V′
lie in the interior
int Aπ
.
Since none of these lattice points lies on any of the lines
(2.4.1)
it follows that each of them
is contained in the interior of a unique triangle of ∆
′
π
. Employing stellar subdivisions at
the points in
V\V′
this yields a triangulation ∆
π
of
V
, which we call the anti-honeycomb
17
Figure 2.9: Anti-honeycomb triangulation of genus 19 on the left, and the corresponding
skeleton on the right
triangulation of type
π
. Figure 2.2, Example 2.1.5, and Theorem 2.2.5 are concerned with
the case
π
= (
−
2
,
4;
−
2
,
4;
−
2
,
4) of genus 4. Figure 2.9 shows a genus 19 anti-honeycomb
triangulation along with its corresponding skeleton for π= (4,−8; 4,−8; 4,−8).
The honeycomb curves yield moduli cones of maximal dimension 2
g
+ 1, where
g
is the
genus, cf. [
10
, Theorem 1]. In contrast the anti-honeycomb curves form a large family whose
moduli cones are much smaller. For instance, a direct
polymake
[
23
] computation shows that
the moduli cone of ∆
(4,−8;4,−8;4,−8)
is only 28-dimensional, whereas the upper bound 2
g
+ 1
equals 39.
Example 2.4.2. Two interesting classes of anti-honeycomb quadrangles are:
A(k,−2k;k,k−3; k,−2k)= conv{(−k, −k),(k, 0),(k−1,1),(1−k, 2−k)},
A(k,3−2k;k,k−3; k,−2k)= conv{(−k, −k),(k−2,−1),(k−1,1),(1−k, 2−k)}.
They arise from the triangle
A(k,−2k;k,−2k;k,−2k)
in
(2.4.2)
by imposing
Mk−3
and
L3−2k
, re-
spectively, as additional facets. The quadrangle
A(k,−2k;k,k−3;k,−2k)
is a lattice trapezoid of
genus 2
k−
1, while
A(k,3−2k;k,k−3;k,−2k)
is a lattice parallelogram of genus 2
k−
2. These
examples provide anti-honeycomb polygons of arbitrary genus. Additionally, their skeleta are
hyperelliptic, despite the fact that the interior lattice points do not lie on a line. The first
few cases are shown in Figure 2.10. Because of their shapes we call them anti-honeycomb
quadrangles of zigzag type.
Figure 2.10: Anti-honeycomb quadrangles of zigzag type and their skeleta; genus 3, 4 and 5.
18
The anti-honeycomb polygons of low genus can be found by directly inspecting the
possibilities of stacking copies of the elliptic “building block” A(1,−2;1,−2,1,−2).
Proposition 2.4.3.
The anti-honeycomb polygons of genus
g≤
6are unimodularly equivalent
to either quadrangles of zigzag type or to the triangle A(2,−4;2,−4;2,−4).
Up to an affine transformation, which is not a lattice transformation, the three families
of lines in
(2.4.1)
form a Coxeter hyperplane arrangement of type
A
˜2
. This generalizes to
arbitrary dimensions, and so does the construction of the anti-honeycomb triangulations.
The resulting anti-honeycomb polytopes are affine images of the “alcoved polytopes” of Lam
and Postnikov [37].
2.5 Conclusion
We would now want to list all conclusions that we inferred with our results regarding the
status of tropically planar graphs. The classification of the tropically planar graphs of genus
g≤5 was obtained in [10]. Theorem 2.3.4 now allows for a combinatorial characterization:
Corollary 2.5.1.
A trivalent planar graph of genus
g≤
5is tropically planar if and only if
none of the obstructions in Theorem 2.3.4 occurs.
Proof.
The trivalent graphs of low genus have been classified in [
4
]. For
g
= 3 there are five
such graphs, one of which has a sprawling node; the other four are tropically planar [
10
,
Theorem 5.1]. For
g
= 4 there are 17 graphs: one is non-planar, three have a sprawling node,
the remaining 13 are tropically planar [10, Theorem 7.1]. This was known before.
There are exactly 71 trivalent graphs of genus 5. Among them only 52 are planar without
a sprawling node [
10
]. Of these 14 were ruled out by explicit computations [
10
], which leaves
38 tropically planar graphs of genus 5. One of the key contributions of [
16
, Figure 8] is to
obtain obstructions to tropical planarity, which rules out another ten, which are crowded or
TIE-fighters.
abcd
Figure 2.11: The four genus 5 graphs that are not ruled out by any prior known criteria
19
As our new contribution we can now discuss the remaining four graphs, which are shown
in Figure 2.11. Firstly, we observe that all of these exhibit a heavy cycle. The graph labeled
“a” has a heavy cycle with two loops, but the component away from the two loops is not
hyperelliptic; i.e., it is ruled out by Theorem 2.3.3. The second graph, labeled “b” also has
a heavy cycle with two loops, the component (of genus 3) away from the two loops is even
hyperelliptic. However, we see that the interior point zdual to the heavy cycle would lie in
between the other two interior lattice points in the hyperelliptic polygon dual to the genus 3
component; the latter contradicts Theorem 2.3.3, which says that the interior lattice points
in the genus 3 component should lie below
z
on the line spanned by
z
and
w
, where
w
is the
point of intersection of the two splits. Thus “b” is ruled out by Theorem 2.3.3, too. The
graphs labeled “c” and “d” feature sprawling triangles, whence they are taken care of by
Theorem 2.2.5. This completes our combinatorial characterization of the tropically planar
graphs of genus at most five.
For genus 6, there are 388 trivalent graphs altogether, 354 of which are planar [
4
]. In [
16
]
it was shown that 152 tropically planar graphs of genus 6 remain. There are 28 graphs which
are non-realizable and could not be ruled out using any prior known criteria; cf. [
16
, Figure
17]. Out of these 28 graphs, 19 have a heavy cycle with two loops and can be ruled out using
Theorem 2.3.3 because the genus is too high. One of the remaining graphs has a sprawling
triangle, and thus excluded by Theorem 2.2.5. We are left with eight graphs of genus 6, which
are shown in Figure 2.12; for these we are not aware of any a priori obstruction. There are
672 troplanar graphs of genus 7 according to [
16
, Table 1]; however, the full list does not
seem to be available.
We now discuss some other recent advances that were made in the study of troplanar
graphs. In [
16
, Theorem 4.2], it is shown that as the genus
g
grows asymptotically large,
then the number of troplanar graphs tends to 0. This helps us understand that the complete
classification that we obtain in 2.3.4 for genus upto five, is something which can not be
replicated for arbitrarily large genus, as the family of distinct forbidden patterns would
keep getting larger, and this helps us appreciate the completeness of the result. Also, in
[
17
], a closed formula for computing the dimension of
M∆
for a non-hyperelliptic lattice
polygon is obtained, which earlier could only be computed via computer-aided computations.
It complements the computation we did to compute the dimension of the antihoneycomb
triangulation in Figure 2.9 via
polymake
. Also, in [
17
], it is shown that for a non-hyperelliptic
lattice polygon Pthe following holds,
dim (MP) = dim (MP)
20
a b c d
e f gh
Figure 2.12: The eight trivalent planar graphs of genus 6, which are not tropically planar
[16], but which are not covered by Theorem 2.3.4.
where
MP
is the moduli space of non-degenerate curves defined over
P
and
MP
denotes
the closure of the set of all metric graphs that are the skeleton of a smooth tropical curve
with Newton polygon
P
. In ongoing work, we are trying to find all the possible values of
the dimension of
MP
and to obtain a closed formula to compute the dimension of
M∆
for a
non-maximal hyperelliptic polygon.
Another possible avenue for further exploration could be to know how the tropically plane
curves of a fixed genus fit into the moduli space of all tropical curves. For genus 3 this was
recently answered in terms of modifications by Hahn et al. [26].
Results of the presented work in this chapter have been published in - Michael Joswig and
Ayush Kumar Tewari. “Forbidden patterns in tropical plane curves” Beitr¨age zur Algebra
und Geometrie / Contributions to Algebra and Geometry, Aug 2020 [
34
]. Licensed under a
Creative Commons Attribution 4.0 International License.
21
Chapter 3
Lattice visibility and Panoptigons
3.1 Preliminaries
A lattice point in
R2
is any point with integer coordinates, and a lattice polygon is any
polygon whose vertices are lattice points. We say that two distinct lattice points
p
= (
a, b
)
and
q
= (
c, d
) are visible to one another if the line segment
pq
contains no lattice points
besides
p
and
q
, or equivalently if
gcd
(
a−c, b −d
) = 1; by convention we say that any
p
is
visible from itself. Points visible from the origin
O
= (0
,
0) are called visible points, with all
other points being called invisible. The properties of visible and invisible points have been
subject to a great deal of study over the past century, as surveyed in [
9
,
§
10.4]. The question
of which structures can appear among visible points, invisible points, or some prescribed
combination thereof was studied in [
28
], where it was proved that one can find a copy of any
convex lattice polygon (indeed, any arrangement of finitely many lattice points) consisting
entirely of invisible points.
Figure 3.1: Three panoptigons, with a panoptigon point circled and lines of sight illustrated;
the middle polygon has a second panoptigon point, namely the bottom vertex
In this chapter we pose and answer a somewhat complementary question: which con-
vex lattice polygons including the origin contain only visible lattice points? We define a
panoptigon
1
to be a convex lattice polygon
P
containing a lattice point
p
such that all other
1
This name is modeled off of panopticon, an architectural design that allows for one position to observe all
others. It comes from the Greek word panoptes, meaning “all seeing”.
22
lattice points in
P
are visible from
p
. We call such a point
p
apanoptigon point for
P
. Thus
up to translation, a panoptigon is a convex lattice polygon containing the origin such that
every point in
P∩Z2
is a visible point. Three panoptigons are pictured in Figure 3.1, each
with a panoptigon point and its lines of sight highlighted; note that the panoptigon point
need not be unique.
One can quickly see that there exist infinitely many panoptigons; for instance, the triangles
with vertices at (0
,
0), (1
,
0), and (
a,
1) are panoptigons for any value of
a
. However, this
is not an interesting family of examples since any two of these triangles are equivalent, the
definition of which we recall below.
Definition 3.1.1.
Aunimodular transformation is an integer linear map
t
:
R2→R2
that
preserves the integer lattice
Z2
; any such map is of the form
t
(
p
) =
Ap
+
b
, where
A
is a
2
×
2 integer matrix with determinant
±
1 and
b∈Z2
is a translation vector. We say that
two lattice polygons
P
and
Q
are equivalent if there exists a unimodular triangulation
t
such
that t(P) = Q.
It turns out that there are infinitely many panoptigons even up to equivalence: note that
the triangle with vertices at (0
,
0), (0
,−
1), and (
b, −
1) is a panoptigon for every positive
integer
b
, and any two such triangles are pairwise inequivalent since they have different
areas. We can obtain nicer results if we stratify polygons according to the lattice width of
a polygon
P
, the minimum integer
w
such that there exists a polygon
P′
equivalent to
P
in the horizontal strip
R×
[0
, w
]. Although there are infinitely many panoptigons of lattice
widths 1 and 2, we can still classify them completely, as presented in Lemmas 3.3.1 and 3.3.2.
Once we reach lattice width 3 or more, we obtain the following powerful result.
Theorem 3.1.2. Let Pbe a panoptigon with lattice width lw(P)≥3. Then |P∩Z2| ≤ 13.
Since there are only finitely many lattice polygons with a fixed number of lattice points
up to equivalence [
36
, Theorem 2], it follows that there are only finitely many panoptigons
P
with
lw
(
P
)
≥
3. In section 3.6 we detail computations to enumerate all such lattice
polygons. This allows us to determine that there exactly 73 panoptigons of lattice width 3
or more. One is the triangle of degree 3, which has a single interior lattice point; and the
other 72 are non-hyperelliptic, meaning that the convex hull of their interior lattice points is
two-dimensional.
As an application of our classification of panoptigons, we prove new results about tropically
planar graphs [
16
]. We prove a new criterion for ruling out certain graphs from being tropically
planar, notable in that the graphs it applies to are 2-edge-connected, unlike those ruled out
by most existing criteria; this resolves an open question posed in [
16
,
§
5]. We say that a
23
planar graph
G
is a big face graph if for every planar embedding of
G
, there is a bounded
face sharing an edge with all other bounded faces.
Theorem 3.1.3. If Gis a big face graph of genus g≥14, then Gis not tropically planar.
The idea behind the proof of this theorem is as follows. If a big face graph
G
is tropically
planar, then it is dual to a regular unimodular triangulation of a lattice polygon
P
. One of
the interior lattice points
p
of
P
must be connected to all the other interior lattice points, so
that the bounded face dual to
p
can share an edge with all other bounded faces. Thus, the
convex hull of the interior lattice points of
P
must be a panoptigon. If that panoptigon has
lattice width 3 or more, then it can have at most 13 lattice points, and so
G
cannot have
g≥14.
For the case that the lattice width of the interior panoptigon is smaller, we need an
understanding of which polygons of lattice width 1 or 2 can appear as the interior lattice
points of another lattice polygon. We obtain this in Propositions 3.4.1 and 3.4.5, and can
once again bound the genus of
G
. In fact, if we are willing to rely on our computational
enumeration of all panoptigons with lattice width at least 3, then we can improve this result
to say that big face graphs of genus
g≥
12 are not tropically planar. We will see that this
bound is sharp.
In Section 3.2 we present background on lattice polygons, including a description of all
polygons of lattice width at most 2. In Section 3.3 we classify all panoptigons. In Section
3.4 we classify all maximal polygons of lattice width 3 or 4. Finally, in Section 3.5 we prove
Theorem 3.1.3. Our computational results are then summarized in section 3.6.
3.2 Properties of lattice polygons
In this section we recall important terminology and results regarding lattice polygons. This
includes the notion of maximal polygons, and of lattice width. Throughout we will assume
that Pis a two-dimensional convex lattice polygon, unless otherwise stated.
The genus of a polygon
P
is the number of lattice points interior to
P
. A key fact is that
for fixed
g≥
1, there are only finitely many lattice polygons of genus
g
, up to equivalence [
13
,
Theorem 9]. We say a lattice polygon
P
is a maximal polygon if it is maximal with respect
to containment among all lattice polygons containing the same set of interior lattice points.
In the case that
P
is non-hyperelliptic, there is a strong relationship between
P
and
Pint
.
Let
τ1, . . . , τn
be the one-dimensional faces of a (two-dimensional) lattice polygon
Q
. Then
Qcan be defined as an intersection of half-planes:
Q=
n
⋂︂
i=1
Hτi,
24
where
Hτ
=
{
(
x, y
)
∈R2|aτx
+
bτy≤cτ}
is the set of all points on the same side of
the line containing
τ
as
Q
. Without loss of generality, we assume that
aτ, bτ, cτ∈Z
with
gcd(aτ, bτ) = 1. With this convention, we define
H(−1)
τ={(x, y)∈R2:aτx+bτy≤cτ+ 1},
and from there we define the relaxed polygon of Qas
Q(−1) :=
n
⋂︂
i=1
H(−1)
τi.
We can think of
Q(−1)
as the polygon we would get by “moving out” the edges of
Q
. It is
worth remarking that
Q(−1)
need not be a lattice polygon. We denote
Q(−1) ∩ H(−1)
τi
as
τ(−1)
i
.
It is not necessarily the case that
τ(−1)
i
is a one-dimensional face of
Q(−1)
; however, if
Q(−1)
is a lattice polygon, then
Q(−1) ∩τ(−1)
i
must contain at least one lattice point, as proved in
[
17
, Lemma 2.2]. Examples where
Q(−1)
is not a lattice polygon, and where
Q(−1)
is a lattice
polygon but an edge has collapsed, are illustrated in Figure 3.2. There is a very important
case when we are guaranteed to have that
Q(−1)
is a lattice polygon, namely when
Q
=
Pint
for some non-hyperelliptic lattice polygon P.
Figure 3.2: Two lattice polygons, one with a relaxed polygon with a non-lattice vertex marked;
and one with a collapsed edge in the relaxed (lattice) polygon
Proposition 3.2.1
([
35
],
§
2.2)
.
Let
P
be a non-hyperelliptic lattice polygon, with interior
polygon
Pint
. Then
P(−1)
int
is a lattice polygon containing
P
whose interior polygon is also
Pint
.
In particular, P(−1)
int is the unique maximal polygon with interior polygon Pint.
If we are given a polygon
Q
and we wish to know if there exists a lattice polygon
P
with
Pint
=
Q
, it therefore suffices to compute the relaxed polygon
Q(−1)
, and to check whether its
vertices have integral coordinates. This might fail because two adjacent edges
τi
and
τi+1
of
Q
are relaxed to intersect at a non-integral vertex of
Q(−1)
; we also might have that some
τ(−1)
i
is completely lost, which cannot happen when
Q(−1)
is a lattice polygon by [
17
, Lemma
2.2]. Careful consideration of these obstructions will be helpful in classifying the maximal
polygons of lattice widths 3 and 4 in Section 3.4.
An important tool in studying lattice polygons is the notion of lattice width. Let
P
be a
non-empty lattice polygon, and let
v
=
⟨a, b⟩
be a lattice direction with
gcd
(
a, b
) = 1. The
25
width of
P
with respect to
v
is the smallest integer
d
for which there exists
m∈Z
such that
the strip
m≤ay −bx ≤m+d
contains
P
. We denote this
d
as
w
(
P, v
). The lattice width of
P
is the minimal width over
all possible choices of v:
lw(P) = min
vw(P, v).
Any
v
which achieves this minimum is called a lattice width direction for
P
. Equivalently,
lw
(
P
) is the smallest
d
such that there exists a lattice polygon
P′
equivalent to
P
with
P′⊂R×[0, d].
We recall the following result connecting the lattice widths of a polygon and its interior
polygon. Let Td= conv((0,0),(d, 0),(0, d)) denote the standard triangle of degree d.
Lemma 3.2.2
(Theorem 4 in [
14
])
.
For a lattice polygon
P
we have
lw
(
P
) =
lw
(
Pint
) + 2,
unless Pis equivalent to Tdfor some d≥2, in which case lw(P) = lw(Pint) + 3 = d.
The following result tells us precisely which polygons have lattice width 1 or 2. It is a
slight reworking of a result due to [35], also presented in [13, Theorem 10]
Theorem 3.2.3.
Let
P
be a two-dimensional lattice polygon. If
lw
(
P
) = 1, then
P
is
equivalent to
Ta,b := conv((0,0),(0,1),(a, 1),(b, 0))
for some a, b ∈Zwith 0≤a≤band b≥1.
If
lw
(
P
) = 2, then up to equivalence either
P
=
T2
; or
g
(
P
) = 1 and
P
=
T3
(all
such polygons are illustrated in Figure 3.3); or
g
(
P
)
≥
2. In the latter case we have
1
6(g+ 3)(2g2+ 15g+ 16) polygons, sorted into three types:
•Type 1:
(0,0)
(i, 0)
(1,2)
(1 + 2g−i, 2)
where g≤i≤2g.
•Type 2:
(0,0)
(i, 0)
(1,2)
(1 + j, 2)
(g+ 1,1)
where 0≤i≤gand 0≤j≤i; or g < i ≤2g+ 1 and 0≤j≤2g−i+ 1
26
•Type 3:
(0,0)
(i, 0)
(k, 2)
(k+j, 2)
(g+ 1,1)
(0,1)
where 0
≤k≤g
+ 1 and 0
≤i≤g
+ 1
−k
and 0
≤j≤i
; or 0
≤k≤g
+ 1 and
g+ 1 −k < i ≤2g+ 2 −2kand 0≤j≤2g−i−2k+ 1
Figure 3.3: The 14 genus 1 polygons with lattice width 2
Proof.
The classification proved in [
35
] was similar, except with polygons sorted by genus
(
g
= 0,
g
= 1, and
g≥
2 with all interior lattice points collinear) rather than by lattice width.
We can translate their work into the desired result as follows.
For
lw
(
P
) = 1, we know
P
has no interior lattice points, so
g
= 0; all polygons of genus 0
besides
T2
have lattice width 1. By [
35
] all genus 0 polygons besides
T2
are equivalent to
Ta,b
for some a, b ∈Zwith 0 ≤a≤band b≥1.
For
lw
(
P
) = 2, we deal with the three cases of
g
= 0,
g
= 1, and
g≥
2. If
g
= 0, then the
only polygon of lattice width 2 is
T2
. If
P
is a polygon with genus
g
= 1, then by Lemma
3.2.2 we know that
lw
(
P
) =
lw
(
Pint
) + 2 = 0 + 2 = 2 unless
P
is equivalent to
Td
for some
d
.
The only value of
d
such that
Td
has genus 1 is
d
= 3, so every genus 1 polygon except
T3
has lattice width 2.
Finally, suppose
P
is a polygon of lattice width 2 and genus
g≥
2. Since
lw
(
Td
) =
d
and
g
(
T2
) = 0, we know
P
=
Td
for any
d
, and so
lw
(
Pint
) =
lw
(
P
)
−
2 = 2
−
2 = 0. It follows that
all the
g
interior lattice points of
P
must be collinear, and so
P
is hyperelliptic. Conversely, if
P
is a hyperelliptic polygon of genus
g≥
2, by definition the interior polygon
Pint
has lattice
width 0. Since no triangle
Td
has genus
g≥
2 with all its interior points collinear we may
apply Lemma 3.2.2 to conclude that
lw
(
P
) =
lw
(
Pint
) + 2 = 2. This means that for polygons
of genus
g≥
2, being hyperelliptic is equivalent to having lattice width 2. Combined with
the classification of hyperelliptic polygons in [35], this completes the proof.
27
A counterpart of lattice width is lattice diameter. Following [
6
], the lattice diameter
ℓ
(
P
)
is the length of the longest lattice line segment contained in the polygon P:
ℓ(P) = max{|L∩P∩Z2| − 1 : Lis a line}.
We define a lattice diameter direction
⟨a, b⟩
to be one such that there exists a line
L
with
slope vector
⟨a, b⟩
with
|L∩P∩Z2|−
1 =
ℓ
(
P
). We remark that there exist other works where
lattice diameter is defined as the largest number of collinear lattice points in the polygon
P
[
1
]; this is simply one more than the convention we set above. The following result relates
ℓ(P) to lw(P).
Theorem 3.2.4 ([6], Theorem 3).We have lw(P)≤ ⌊4
3ℓ(P)⌋+ 1.
Assume for the remainder of the section that
P
is a lattice polygon of genus
g≥
2. We
recall the skeleton
G
associated to a unimodular traingulation ∆ of
P
. An example of a
regular unimodular triangulation, the dual graph, and the tropically planar skeleton are
pictured in Figure 3.4. Note that there is a one-to-one correspondence between the interior
lattice points of
P
and the bounded faces of
G
in this embedding, where two faces of
G
share
an edge if and only if the corresponding interior lattice points are connected by an edge in ∆.
Figure 3.4: A regular unimodular triangulation of a polygon, the dual graph of the triangula-
tion, and the corresponding tropically planar skeleton
It is worth remarking that we could still construct a graph
G
from a non-regular triangu-
lation. The reason that we insist that ∆ is regular is so that the graph
G
appears as a subset
of a smooth tropical plane curve, which is a balanced 1-dimensional polyhedral complex that
is dual to a regular unimodular triangulation of a lattice polygon; see [
38
]. (Indeed, the
regularity is necessary if we wish to endow a skeleton with the structure of a metric graph,
with lengths assigned to its edges, as explored in [
10
] and [
17
].) Most of the results that
we prove in this chapter, and that we recall for the remainder of this section, also hold if
we expand to graphs that arise as dual skeleta of any unimodular triangulation of a lattice
polygon.
28
The first Betti number of a tropically planar graph, also known as its genus
2
, is equal
to the number of interior lattice points of the lattice polygon
P
giving rise to it. It is also
equal to the number of bounded faces in any planar embedding of the graph. A systematic
method of computing all tropically planar graphs of genus
g
was designed and implemented
in [
10
] for
g≤
5. The algorithm is brute-force, and works by considering all maximal lattice
polygons of genus
g
, finding all regular unimodular triangulations of them, and computing
the dual skeleta. These computations were pushed up to
g
= 7 in [
16
]. In general there is
no known method of checking whether an arbitrary graph is tropically planar short of this
massive computation.
A fruitful direction in the study of tropically planar graphs has been finding properties or
patterns that are forbidden in such graphs, an example of which is discussed in the previous
chapter. Since the graph before skeletonization is dual to a unimodular triangulation of a
polygon, any tropically planar graph is 3-regular, connected, and planar. Several additional
constraints are summarized in the following result.
Theorem 3.2.5
([
12
], Proposition 4.1; [
16
], Theorem 3.4; [
34
], Theorems 10 and 14)
.
Suppose
that
G
is a 3-regular graph of genus
g
of one of the forms illustrated in Figure 3.5, where
each gray box represents a subgraph of genus at least 1. If
G
is tropically planar, then it must
have either the third or fourth forms, with
g
= 4 for the third form and
g≤
5in the fourth
form. In particular, if g≥6, then Gis not tropically planar.
Figure 3.5: Forbidden patterns in tropically planar graphs of genus g≥6
The proofs of all these results rely on the observation that any cut-edge in a tropically
planar graph must arise from a split in the dual unimodular triangulation that divides the
polygon into two polygons of positive genus. For planar graphs that are 2-edge-connected
and thus have no cut-edges, the only known general criterion to rule out tropical planarity is
the notion of crowdedness [
40
]. However, crowded graphs are ones that cannot be dual to any
2
This terminology comes from [
3
] and is motivated by algebraic geometry; it is unrelated to the notion of
graph genus defined in terms of embeddings on surfaces. The first Betti number of a graph is also sometimes
called its cyclomatic number.
29
triangulation of any point set in
R2
, regardless of whether or not the point set comes from
a convex lattice polygon; thus it is not especially interesting that crowded graphs are not
tropically planar. In Section 3.5 we will find a family of 2-edge-connected, 3-regular planar
graphs that are not crowded but are still not tropically planar, the first known such examples.
3.3 A classification of all panoptigons
Let
P
be a convex lattice polygon. Recall from the introduction that
P
is a panoptigon if
there is lattice point
p∈P∩Z2
such that every other point in
P∩Z2
is visible from
p
. In
this section we will classify all panoptigons, stratified by a combination of genus and lattice
width. We begin with the panoptigons of genus 0.
Lemma 3.3.1.
Let
P
be a panoptigon of genus 0. Then
P
is one of the following polygons,
up to lattice equivalence:
(0,0)
(2,0)
(0,2)
(0,0)
(0,1)
(a, 1)
(b, 0)
where 0≤a≤min{2, b}.
Proof.
By [
35
], any genus 0 polygon is equivalent either to the triangle
T2
, or to the (possibly
degenerate) trapezoid
Ta,b
where 0
≤a≤b
and 1
≤b
. The triangle of degree 2 is a panoptigon,
as any non-vertex lattice point can see every other lattice point. For
Ta,b
, we note that if
a≥
3 then the polygon is not a panoptigon: each lattice point
p
is on a row with at least 3
other lattice points, not all of which can be visible from
p
since the 4 (or more) points in
that row are collinear. However, if
a≤
2, then a point
p
can be chosen on the top row that
can see the other
a
points on the top row, as well as all points on the bottom row. Thus
Ta,b
is a panoptigon if and only if a≤2.
For polygons with exactly one interior lattice point, there is no obstruction to being a
panoptigon.
Lemma 3.3.2. If Pis a polygon of genus 1, then Pis a panoptigon.
Proof.
Let
p
be the unique interior lattice point of
P
, and let
q
be any other lattice point of
P
. Since
g
(
P
) = 1, the point
q
must be on the boundary. By convexity, the line segment
pq
must have its relative interior contained in the interior of the polygon, and so the line
segment does not intersect
∂P
outside of
q
. Since
p
is the only interior lattice point, we have
30
that the only lattice points of
pq
are its endpoints. It follows that
q
is visible from
p
for all
q∈P∩Z2− {p}. We conclude that Pis a panoptigon with panoptigon point p.
We now consider hyperelliptic polygons of genus
g≥
2. We will characterize precisely
which of these are panoptigons based on the classification of them in Theorem 3.2.3 into
Types 1, 2, and 3. Any hyperelliptic polygon can be put into one of these forms in the
horizontal strip
R×
[0
,
2]; thus we may say a lattice point (
a, b
) of such a polygon is at height
b, where every point is either at height 0, height 1, or height 2.
Lemma 3.3.3.
Let
P
be a hyperelliptic polygon of genus
g≥
2, transformed so that it of
one of the forms presented in Theorem 3.2.3. Then Pis a panoptigon if and only if
•Pis of Type 1, with g≤3; or
•Pis of Type 2, either with g≤2, or with j= 0 and 0≤i≤1; or
•P
is of Type 3, either with
j
= 0 and
i≤
2, with
k
odd if
i
= 0 and
k
even if
i
= 2; or
with i= 0 and j≤2, and kodd if j= 0 and keven if j= 2.
For the reader’s convenience we recall the polygons of Types 1, 2, and 3 in Figure 3.6.
(0,0)
(i, 0)
(1,2)
(1 + 2g−i, 2)
(0,0)
(i, 0)
(1,2)
(1 + j, 2)
(g+ 1,1)
(0,0)
(i, 0)
(k, 2)
(k+j, 2)
(g+ 1,1)
(0,1)
Figure 3.6: Hyperelliptic polygons of Types 1, 2, and 3
Proof.
We start by making the following observations. If
p
= (
a, b
) is a panoptigon point
for a hyperelliptic polygon
P
, then there must be at most 3 points at height
b
; and if there
are exactly 3, then
p
must be the middle such point. We also make several remarks in
the case that
b∈ {
0
,
2
}
. There are no obstructions to a point at height
b
seeing a point
at height 1, so we will not concern ourselves with this. Choose
b′∈ {
0
,
2
}
distinct from
b
,
and suppose height
b′
has 2 or more lattice points; then two of those points have the form
q
= (
a, b′
) and
q′
= (
a
+ 1
, b′
). We claim that
p
cannot view both
q
and
q′
. Writing
p
= (
a, b
),
the midpoints of the line segments
pq
and
pq′
have coordinates
(︁a+a′
2,1)︁
and
(︁a+a′+1
2,1)︁
,
respectively. Exactly one of
a+a′
2
and
a+a′+1
2
is an integer, meaning that either
q
or
q′
is not
visible from
p
. So, if
p
= (
a, b
) is a panoptigon point at height
b∈ {
0
,
2
}
, there must be
exactly one lattice point
q
= (
a′, b′
) at height
b′∈ {
0
,
2
}
with
b′
=
b
; moreover, we must have
that a−a′is odd.
We are ready to determine the possibilities for a hyperelliptic panoptigon
P
of genus
g≥2, sorted by type.
31
•
Let
P
be a hyperelliptic polygon of Type 1. If
g≤
3, then we may choose
p
= (
a,
1)
that can see every other point at height 1, as well as all points at heights 0 and 2;
in this case
P
is a panoptigon. If
g≥
4, then there are at least 4 points at height 1.
Moreover, the number of points at height 0 is
i
+ 1 where
g≤i≤
2
g
, and we have
i
+ 1
≥
5 since
g≥
4. Thus it is impossible to have at most 3 points at one height and
1 at another. This means that for g≥4, Pcannot be a panoptigon
•
Let
P
be a hyperelliptic polygon of Type 2. If
g
= 2, then
P
has exactly three points
at height 1, and we can choose the middle point as a panoptigon point. Now assume
g≥
3; we cannot choose a panoptigon point at height 1, since there are
g
+ 1
≥
4 points
at that height. To avoid having 4 points on both the top and bottom rows we need
0
≤i≤g
and 0
≤j≤i
; and one of
i
and
j
must be 0, so we need
j
= 0 since
j≤i
.
From there we need at most 3 lattice points on the bottom row, so 0
≤i≤
2. If
i
= 2,
then the only possible panopticon point is the middle one on the bottom row, namely
(1
,
0); but this point cannot see (1
,
2), a contradiction. Thus 0
≤i≤
1; note that in
either case (0,0) can serve as a panoptigon point.
•
Finally, let
P
be a hyperelliptic polygon of Type 3. We cannot have a panoptigon
point at height 1, since there are at least
g
+ 2
≥
4 points at that height. If there is
a panoptigon point at height 0, then we must have at most 3 points at height 0 and
exactly one point at height 2; that is, we must have
j
= 0 and
i≤
2. Moreover, we
need to verify that way may choose a panoptigon point at height 0 that can see the
unique point at height 2; this can always be done if
i
= 1, but if
j
= 0 then we need
k
odd (the only possible panoptigon point is then (0
,
0)), and if
j
= 2 we need
k
even
(the only possible panoptigon point is then (1
,
0)). A similar argument shows that we
can choose a panoptigon point at height 2 if and only if
i
= 0 and
j≤
2, with
k
odd if
j= 0 and keven if j= 2.
As with the lattice width 1 panoptigons, we find infinitely many lattice width 2 panoptigons,
namely those of Type 2 with j= 0 and 0 ≤i≤1, and those of Type 3.
We have now classified all hyperelliptic panoptigons, and have found that there are
infinitely many of lattice width 1 and infinitely many of lattice width 2. Our last step is
to understand non-hyperelliptic panoptigons; with the exception of the triangle
T3
, this is
equivalent to panoptigons of lattice width 3 or more. We are now ready to prove that the
total number of lattice points of such a panoptigon is at most 13.
32
Proof of Theorem 3.1.2.
Let us consider the lattice diameter
ℓ
(
P
) of
P
. We know by [
1
,
Theorem 1] that
|P∩Z2| ≤
(
ℓ
(
P
) + 1)
2
, so if
ℓ
(
P
)
≤
2 we have
|P∩Z2| ≤
9. Thus we may
assume ℓ(P)≥3.
Perform an
SL2
(
Z
) transformation so that
⟨
1
,
0
⟩
is a lattice diameter direction for
P
,
and translate the polygon so that the origin
O
= (0
,
0) is a panoptigon point. Thus
P∩Z2
consists of Oand a collection of visible points.
Since
ℓ
(
P
)
≥
3 and
⟨
1
,
0
⟩
is a lattice diameter direction, we know that the polygon
P
must contain 4 lattice points of the form (
a, b
), (
a
+ 1
, b
), (
a
+ 2
, b
), and (
a
+ 3
, b
). We claim
that
b∈ {−
1
,
1
}
. Certainly
b
= 0, since there are only three such points allowed in
P
: (0
,
0)
and (
±
1
,
0). We also know that
b
cannot be even: any set
Z× {
2
k}
has every second point
invisible from the origin.
Suppose for the sake of contradiction that the points (
a, b
), (
a
+ 1
, b
), (
a
+ 2
, b
), and
(
a
+ 3
, b
) are in
P
with
b
odd and
b≥
3 (a symmetric argument will hold for
b≤ −
3).
Consider the triangle
T
=
conv
(
O,
(
a, b
)
,...,
(
a
+ 3
, b
)). By convexity,
T⊂P
. Consider the
line segment
T∩L
, where
L
is the line defined by
y
=
b−
1. The length of this line segment
is 3
−1
b
, and since
b≥
3 this is strictly greater than 2. Any line segment of length 2 at height
b−
1 will intersect at least two lattice points. But since
b−
1 is even and
b−
1
≥
2, at least
one of these lattice points is not visible from
O
. Such a lattice point must be contained in
T
,
and therefore in P, a contradiction. Thus we have that b=±1.
Rotating our polygon 180
◦
degrees if necessary, we may assume that
b
=
−
1, so that the
points (
a, −
1)
,...,
(
a
+ 3
,−
1) are contained in
P
. It is possible that the number
k
of lattice
points on the line defined by y=−1 is more than 4; up to relabelling, we may assume that
(
a, −
1)
,...,
(
a
+
k−
1
,−
1) are lattice points in
P
while (
a−
1
,−
1) and (
a
+
k, −
1) are not,
where
k≥
4. Applying a shearing transformation
(︃1a+ 1
0 1 )︃
, we may further assume that
the points at height −1 are precisely (−1,−1),...,(k−2,−1).
We will now make a series of arguments that rule out many lattice points from being
contained in
P
. The end result of these constraints is pictured in Figure 3.7, with points
labelled by the argument that rules them out.
(i)
The polygon
P
has (regular) width at least 3 at height
−
1, and width strictly smaller
than 2 at heights 2 and
−
2, since it cannot contain two consecutive lattice points at
those heights. It follows from convexity that the width of the polygon is strictly smaller
than 1 at height
−
3, and that the polygon cannot have any lattice points at all at
height
−
4. It also follows that the polygon cannot have a nonnegative width at height
8. Thus every lattice point (x, y) in the polygon satisfies −3≤y≤7.
33
(ii)
We can further restrict the possible heights by showing that there can be no lattice
points at height
−
3. Suppose there were such a point (
x, −
3) in
P
. Consider the
triangle
conv
((
x, −
3)
,
(
−
1
,−
1)
,
(2
,−
1)). This triangle has area 3, so by Pick’s Theorem
[
44
] the triangle satisfies 3 =
g
+
b
2−
1, or 4 =
g
+
b
2
, where
g
and
b
are the number of
interior lattice points an boundary lattice points of the triangle, respectively. The 4
lattice points at height
−
1 contribute 2 to this sum, and the one lattice point at height
−
3 contributes
1
2
to this sum, meaning that the lattice points at height
−
2 contribute
3
2
to this sum. It follows that there must be at least two lattice points at height
−
2; but
this is a contradiction, since at least one of these points will be invisible from
O
. We
conclude that
P
cannot contain a lattice point of the form (
x, −
3), and thus
y≥ −
2
for all lattice points (x, y)∈P.
(iii)
We know that the lattice point (
−
2
,
0) is not in
P
since it is not visible from
O
. If there
is any lattice point of the form (
x, y
) with
y≥
1 and
y≤ −x−
2, then the triangle
conv
(
O,
(
−
1
,−
1)
,
(
x, y
)) will contain (
−
2
,
0). Thus no such lattice point (
x, y
) can exist
in P.
(iv)
No point of the form (
x, y
) with
x≥
2 and
y≥
0 may appear in
P
: this would force
the point (2,0) to appear, as it would lie in the triangle conv(O, (2,−1),(x, y)).
(v)
There are now only finitely many allowed lattice points (
x, y
) with
y≥
1, namely those
with
−y−
1
≤x≤
2 and 1
≤y≤
7. For each such point, we consider the triangle
conv
((
x, y
)
,
(
−
1
,−
1)
,
(
−
1
,
3)). We claim that only the 13 choices of (
x, y
) pictured in
Figure 3.7. that do not introduce a forbidden point. To see this, we note that the points
(0
,
2), (
−
2
,
2) and (
−
2
,
4) are all forbidden. The point (0
,
2) rules out (
x, y
) with
x
= 1
and
y≥
5; with
x
= 0 and
y≥
2; with
x
=
−
1 and
y≥
4; ant with
x
=
−
2 and
y≥
5.
For
x
=
−
2, the points (
−
2
,
2) and (
−
2
,
4) are already ruled out. For all remaining
points with
x≤ −
3, every point besides (
−
3
,
2), (
−
4
,
3), and (
−
5
,
3) introduces the
point (−2,2) or (−2,4) or both. This establishes our claim.
(vi)
By assumption, we know there are no lattice points of the form (
x, −
1) where
x≤ −
2.
It follows that there are also no lattice points of the form (
x, −
2) where
x≤ −
4, since
(−1,−2) would lie in the convex hull of such a point with Oand (2,−1).
(vii)
We will now use the fact that we have assumed that
P
satisfies
lw
(
P
)
≥
3. We cannot
have that
P
is contained in the strip
−
2
≤y≤
0, so there must be at least one point
(
x, y
) with
y≥
1. If there is a point of the form (
x′,−
1) with
x′≥
6, then we would
have that
conv
((
x, y
)
,
(
x′,−
1)
,
(
−
1
,−
1)) contains the point (2
,
0), which is invisible.
34
Thus we can only have points (
x′,−
1) if
−
1
≤x≤
5. A similar argument shows that
Pcan only contain a point (x, −2) if xis odd with −3≤x≤9.
(i)
(iii)
y= 8
y=−3
(ii)
(iv)
(v)
(vi)
(vii)
Figure 3.7: Possible lattice points in
P
, with impossible points labelled by the argument
ruling them out
We have now narrowed the possible lattice points in our polygon down to the 30 lattice
points in Figure 3.7, five of which we know appear in
P
. For every such point (
x, y
), there
does indeed exist a polygon
P
with
lw
(
P
)
≥
3 containing (
x, y
) as well as the five prescribed
points such that
P∩Z2
is a subset of the 30 allowed points, so we cannot narrow down any
further.
One way to finish the proof is by use of a computer to determine all possible subsets of
the 25 points that can be added to our initial 5 points to yield a polygon of lattice width at
least 3; we would then simply check the largest number of lattice points. We have carried
out this computation, and present the results in section 3.6. We also present the following
argument, which will complete our proof without needing to rely on a computer.
First we split into four cases, depending on the number
k
of lattice points at height
−
1:
4, 5, 6, or 7. When there are more than 4, we can eliminate more of the candidate points
(
x, y
) with
y≥
1 or
y
=
−
2; the sets of allowable points in these four cases are illustrated in
Figure 3.8. In each case we will argue that our polygon Phas at most 13 lattice points.
•
Suppose
k
= 4. There are 20 possible points at height
−
1 or above; since there is at
most one point at height
−
2, it suffices to show that we can fit no more than 12 lattice
points at height −1 or above into a lattice polygon.
35
Figure 3.8: Narrowing down possible points depending on the number of points at height
−
1
First suppose the point (
−
5
,
4) is in
P
. This eliminates 9 possible points from appearing
in
P
, yielding at most 20
−
9 + 1 = 12 lattice points total in
P
. Leaving out (
−
5
,
4) but
including (
−
4
,
3) similarly eliminates 9 possible points. Including (
−
2
,
3) eliminates 8;
including (
−
1
,
3) and leaving out (
−
2
,
3) eliminates 8; including (1
,
4) eliminates 9; and
including (1
,
3) and leaving out (1
,
4) eliminates 9. In all these cases, we can conclude
that Phas at most 13 lattice points in total.
The only remaining case is that all lattice points of
P
have heights between
−
2 and 2.
The polygon can have at most one lattice point at height
−
2, at most one lattice point
at height 2, and some assortment of the 11 total points with heights between
−
1 and 1.
Once again, Pcan have at most 13 lattice points.
•
Suppose
k
= 5. If
P
includes the point (
−
4
,
3), then it cannot include (
−
2
,
3), (
−
1
,
2),
or (0
,
1). Combined with the fact that
P
can only have one lattice point at height
−
2, this leaves
P
with at most 13 total lattice points. A similar argument holds if
P
includes the point (
−
2
,
3). If
P
contains neither (
−
4
,
3) nor (
−
2
,
3), then it has at
most 1 point at height 3, at most one point at height
−
2, and some collection of the 11
points between. Thus Phas at most 13 lattice points.
•
Suppose
k
= 6. Since
P
has at most one lattice point at height
−
2, and only 12 points
are allowed outside of that height, Phas at most 13 lattice points total.
•
Suppose
k
= 7. Since
P
has at most one lattice point at height
−
2, and only 11 points
are allowed outside of that height, Phas at most 12 lattice points total.
We conclude that |P∩Z2| ≤ 13.
36
As detailed in section 3.6, we enumerated all non-hyperelliptic polygons containing the five
prescribed points from the previous proof, along with some subset of the other 25 permissible
points. The end result was 69 non-hyperelliptic panoptigons of lattice diameter 3 or more, up
to equivalence. In the same section we show that there are 3 non-hyperelliptic panoptigons
with lattice diameter at most 2, yielding a grand total of 72 non-hyperelliptic panoptigons. If
we instead wish to count panoptigons of lattice width at least 3, this count becomes 73 due
to the inclusion of T3.
We remark that it is possible to give a much shorter proof that there are only finitely
many non-hyperelliptic panoptigons. Suppose that
P
is a panoptigon of lattice diameter
ℓ
(
P
)
≥
7. By the same argument that started our previous proof, we may assume without
loss of generality that
P
has (0
,
0) as a panoptigon point as well as eight or more lattice points
at height
−
1. If
P
contains a point of the form (
x, y
) where
y≥
2, then the line segment
P∩L
where
L
is the
x
-axis must have length at least 7
(︂1−1
y+1 )︂≥
7
(︁1−1
2+1 )︁
=
14
3>
4.
As such
P
must contain at least 4 points at height 0, impossible since there are only 3 visible
points at this height. Similarly
P
can have no lattice points at height 1: these would force
the inclusion of either (2
,
0) or (
−
2
,
0). Finally, if
P
contains a point of the form (
x, y
) where
y≤ −
3, then the line segment
P∩L′
where
L′
is the horizontal line at height
−
2 must have
width at least 7
(︂1−1
|y|−1)︂≥
7
(︁1−1
3−1)︁
=
7
2>
3. As such we know that
P
must contain at
least 3 lattice points at height
−
2, impossible since no two consecutive points at that height
are both visible. Thus we know that
P
only has lattice points at heights 0,
−
1, and
−
2,
and so is a hyperelliptic polygon. This means that if
P
is a non-hyperelliptic panoptigon, it
must have
ℓ
(
P
)
≤
6. Since
|P∩Z2| ≤
(
ℓ
(
P
) + 1)
2
, it follows that if
P
is a non-hyperelliptic
panoptigon then it must have at most (6 + 1)
2
= 49 lattice points; there are any finitely many
such polygons. In principle one could enumerate all such polygons with at most 49 lattice
points as in [
13
] and check which are panoptigons; this would be much less efficient than the
computation led to by our longer proof.
3.4 Maximal polygons of lattice width 3 or 4
In this section we will characterize all maximal polygons of lattice width 3 or 4. By Lemma
3.2.2, this will allow us to determine which polygons of lattice width 1 or 2 can be the interior
polygon of some lattice polygon. This will be helpful in Section 3.5, when we will need to
know which of the infinitely many panoptigons of lattice width at most 2 can be an interior
polygon.
For lattice width 3, we do have the triangle
T3
as an exceptional case; all other polygons
with lattice width 3 must have an interior polygon of lattice width 1.
37
Proposition 3.4.1.
Let
P
be a maximal polygon. Then
P
has lattice width 3if and only if
up to equivalence we either have
P
=
T3
, or
P
=
T(−1)
a,b
where
a≥1
2b−
1,0
≤a≤b
, and
b≥1, and where Ta,b =T1.
Proof.
If
P
is equivalent to
T3
, then it has lattice width 3 as desired. If
P
is equivalent to
some other Td, then Phas lattice width d= 3, and so need not be considered.
Now assume
P
is not equivalent to
Td
for any
d
, so that
P
has lattice width 3 if and only
if
Pint
has lattice width 1 by Lemma 3.2.2. This is the case if and only if
Pint
is equivalent to
Ta,b
for some
a, b ∈Z
where 0
≤a≤b
and
b≥
1 (where
Ta,b
=
T1
) by Theorem 3.2.3. Thus
to prove our claim, it suffices by Proposition 3.2.1 to show that
T(−1)
a,b
is a lattice polygon if
and only if a≥1
2b−1.
We set the following notation to describe
Ta,b
. Starting with the face connecting (0
,
0)
and (0
,
1) and moving counterclockwise, label the faces of
Ta,b
as
τ1
,
τ2
,
τ3
, and
τ4
(where
τ4
does not appear if a= 0).
Pushing out the faces, we find that
τ(−1)
1
lies on the line
x
=
−
1,
τ(−1)
2
on the line
y
=
−
1,
τ(−1)
3
on the line
x
+ (
b−a
)
y
=
b
+ 1, and
τ(−1)
4
on the line
y
= 2. Note that working
cyclically, we have
τ(−1)
i∩τ(−1)
i+1
is a lattice point: we get the points (
−
1
,−
1), (2
b−a
+ 1
,
1),
(2
a−b
+ 1
,
2), and (
−
1
,
2). Thus if these are the vertices of
T(−1)
a,b
, then
T(−1)
a,b
is a lattice
polygon. Certainly (
−
1
,−
1) and (2
b−a
+1
,
1) appear in
T(−1)
a,b
. The points (2
a−b
+1
,
2) and
(
−
1
,
2) will appear as (not necessarily distinct) vertices of
T(−1)
a,b
if and only if 2
a−b
+ 1
≥ −
1;
that is, if and only if
a≥1
2b−
1. Thus in the case that
a≥1
2b−
1, we have that
T(−1)
a,b
is a
lattice polygon with vertices at (−1,−1), (2b−a+ 1,−1), (2a−b+ 1,2), and (−1,2).
If on the other hand
a < 1
2b−
1, then
τ(−1)
4
is not a face of
T(−1)
a,b
, and so one of the vertices
of
T(−1)
a,b
is
τ(−1)
1∩τ(−1)
3
. These faces intersect at the point
(︁b+2
b−a,−1)︁
, where we may divide
by
b−a
since
a < 1
2b−
1 and so
a
=
b
. Note that
b−a > b −1
2b
+ 1 =
1
2
(
b
+ 2). It follows
that that
b+2
b−a<
2, and certainly
b+2
b−a>
1, so
(︁b+2
b−a,−1)︁
is not a lattice point. We conclude
that T(−1)
a,b is a lattice polygon if and only if a≥1
2b−1, thus completing our proof.
The explicitness of this result, combined with the fact that
g(︂T(−1)
a,b )︂
=
a
+
b
+ 2, allows
us to count the number of maximal polygons
P
of genus
g
with lattice width 3. First, note
that there are
⌊︁g−2
2⌋︁
choices of
Ta,b
with
g
lattice points: with our assumption that
a≤b
, we
can choose
a
to be any number from 1 up to
⌊︁g−2
2⌋︁
, and
b
is determined from there. Next, we
will exclude those choices of
a
that yield
a < 1
2b−
1, or equivalently
a≤1
2b−3
2
since
a, b ∈Z
.
Given that
a
+
b
=
g
, this is equivalent to
a≤1
2
(
g−a
)
−3
2
, or
3
2a≤1
2g−3
2
, or
a≤g
3−
1.
Thus the number of polygons we must exclude from the total count
⌊︁g−2
2⌋︁
is
⌊︁g
3⌋︁−
1. We
conclude that the number of maximal polygons of genus gwith lattice width 3 is
⌊︃g−2
2⌋︃−⌊︂g
3⌋︂+ 1
38
when g≥4 (which allows us to ignore T3).
We now wish to classify maximal polygons
P
of lattice width 4. One possibility is that
P
is
T4
. Other than this example, the interior polygon
Pint
must have lattice width 2. Note
that if
g
(
Pint
) = 0, then
Pint
=
T2
; this has relaxed polygon
T5
, which has lattice width 5 and
so is not under consideration. If
g
(
Pint
) = 1, then
Pint
is one of the polygons in Figure 3.3.
It turns out that all of these can be relaxed to a lattice polygon, each of which has lattice
width 4; these polygons are illustrated in Figure 3.9.
Figure 3.9: The lattice width 4 polygons with exactly one doubly interior point
Now we deal with the most general case of polygons with
lw
(
P
) = 4, namely those where
Pint
has lattice width 2 and genus
g′≥
2. Thus
Pint
must be one of the
1
6
(
g
+3)(2
g2
+15
g
+16)
hyperelliptic polygons presented in Theorem 3.2.3. We must now determine which of these
hyperelliptic polygons
Q
have a relaxed polygon
Q(−1)
that has lattice points for vertices.
We do this over three lemmas, which consider the polygons of Type 1, Type 2, and Type 3
separately.
Lemma 3.4.2.
If
Q
is of Type 1, then the relaxed polygon
Q(−1)
is a lattice polygon if and
only if i≤3g+1
2.
Proof.
Let
τ1
,
τ2
,
τ3
, and
τ4
denote the four one-dimensional faces of
Q
, proceeding counter-
clockwise starting from the face connecting (0
,
0) and (1
,
2) (note that
τ4
does not appear
as a one-dimensional face if
i
= 2
g
). Consider the relaxed faces
τ(−1)
1
,
τ(−1)
2
,
τ(−1)
3
, and
τ(−1)
4
.
These lie on the lines
−
2
x
+
y
= 1,
y
=
−
1, 2
x
+ (2
i−
2
g−
1)
y
= 2
i
+ 1, and
y
= 3.
Proceeding cyclically, the intersection points
τ(−1)
i∩τ(−1)
i+1
of these relaxed faces are (
−
1
,−
1),
(2
i−g, −
1), (3
g−
2
i
+ 2
,
3), and (1
,
3). All these points are lattice points, so if they are
indeed the vertices of Pint then Q(−1) is a lattice polygon.
The one situation in which our relaxed polygon will not have all lattice points is if
τ(−1)
1
and
τ(−1)
3
intersect at a height strictly below 3, cutting off the face
τ(−1)
4
and yielding a vertex
with
y
coordinate strictly between 2 and 3. These faces intersect at
(︂g+1
2(i−g),i+1
i−g)︂
, which
has
y
-coordinate strictly smaller than 3 if and only if
i+1
i−g<
3, which can be rewritten as
39
i
+ 1
<
3
i−
3
g
, or as
3g+1
2< i
. Thus when
i≤3g+1
2
, our relaxed polygon is a lattice polygon;
and when i > 3g+1
2, it is not.
Lemma 3.4.3.
If
Q
is of Type 2, then the relaxed polygon
Q(−1)
is a lattice polygon if and
only if i≥g
2+ 1 and j≥g−1
2.
Proof.
Label the faces of
Q
cyclically as
τ1
,
τ2
,
τ3
,
τ4
, and
τ5
. Due to the form of the slopes of
these faces, the relaxed face
τ(−1)
i
will intersect the relaxed face
τ(−1)
i+1
at a lattice point; this
is true for
τ1
with
τ2
and
τ5
by computation, and for any horizontal line with a face of slope
1
/k
for some integer
k
. Similarly, we are fine with the intersections of
τ(−1)
3
and
τ(−1)
4
: these
will always intersect at the lattice point (
g
+ 2
,
1). Thus the only way the relaxed polygon
will fail to have lattice vertices is if certain edges are lost while pushing out. Considering the
normal fan of
Q
, this leads to two possible cases for
Q
to not be integral: if the face
τ(−1)
2
is
lost, and if the face τ(−1)
5is lost.
First we consider the case that
τ(−1)
2
is lost due to
τ(−1)
1
and
τ(−1)
3
intersecting at a point
with
y
-coordinate strictly between 0 and
−
1; note that this can only happen when
i < g
. The
face
τ(−1)
1
is on the line
−
2
x
+
y
= 1, and
τ(−1)
3
is on the line
x−
(
g
+ 1
−i
)
y
=
i
+ 1. These
intersect at
(︂−g+2
2g−2i+1 ,−2i+3
2g−2i+1 )︂
. Note that
−2i+3
2g−2i+1 >−
1 is equivalent to
2i+3
2g−2i+1 <
1,
which in turn is equivalent to 2
i
+ 3
<
2
g−
2
i
+ 1. This simplifies to
i < g
2
+ 1. Thus we
have a collapse of τ(−1)
2that introduces a non-lattice vertex point if and only if i < g
2+ 1.
Now we consider the case that
τ(−1)
5
is lost due to
τ(−1)
1
and
τ(−1)
4
intersecting at a point
with
y
-coordinate strictly between 2 and 3. The face
τ(−1)
4
lies on the line with equation
x
+ (
g−j
)
y
= 2
g−j
+ 2. This intersects
τ(−1)
1
at
(︂g+2
2g−2j+1 ,4g−2j+5
2g−2j+1 )︂
. Having
4g−2j+5
2g−2j+1 <
3 is
equivalent to 4
g−
2
j
+ 5
<
6
g−
6
j
+ 3, which can be rewritten as 4
j <
2
g−
2, or
j < g−1
2
.
Thus we have a collapse of
τ(−1)
5
that introduces a non-lattice vertex point if and only if
j < g−1
2.
We conclude that Q(−1) is a lattice polygon if and only if i≥g
2+ 1 and j≥g−1
2
Lemma 3.4.4.
If
Q
is of Type 3, then the relaxed polygon
Q(−1)
is a lattice polygon if and
only if i≥g/2and j≥g/2.
Proof.
Label the faces of
Q
cyclically as
τ1, . . . , τ6
, where
τ1
is the face containing the lattice
points (
k,
2) and (0
,
1) (with the understanding that some faces might not appear if one or
more of
i
,
j
and
k
are equal to 0). If the faces
τ(−1)
1, . . . , τ(−1)
6
are all present in the polygon
P(−1)
, then they intersect at lattice points by the arguments from the previous proof. Thus
we need only be concerned with the following cases: where
τ(−1)
3
collapses due to
τ(−1)
2
and
40
τ(−1)
4
intersecting at a point (
x, y
) with 0
> y > −
1; and where
τ(−1)
6
collapses due to
τ(−1)
5
and τ(−1)
1intersecting at a point (x, y) with 2 < y < 3.
First we consider τ(−1)
2and τ(−1)
4. We have that τ(−1)
2lies on the line defined by x=−1,
and that
τ(−1)
4
lies on the line defined by
x−
(
g
+ 1
−i
)
y
=
i
+ 1. These lines intersect
at (
−
1
,−i+2
g+1−i
). The
y
-coordinate is strictly greater than
−
1 when
i+2
g+1−i<
1, i.e. when
i
+ 1
< g
+ 1
−i
, which can be rewritten as
i < g
2
. Thus we lose
τ(−1)
3
to a non-lattice vertex
precisely when i < g
2.
Now we consider
τ(−1)
5
and
τ(−1)
1
. We have that
τ(−1)
1
lies on the line
x−ky
=
−k
+ 1,
unless
k
= 0 in which case it lies on the line
x
=
−
1; and that
τ(−1)
5
lies on the line
x
+ (
g
+ 1
−k−j
)
y
= 2
g
+ 2
−k−j
. In the event that
k
= 0, these intersect at
(︂gk+g−j+1
g−j+1 ,2g−j+1
g−j+1 )︂
, which has
y
-coordinate strictly smaller than 3 when
2g−j+1
g−j+1 <
3, or
equivalently if 2
g−j
+ 1
<
3
g−
3
j
+ 1, or equivalently if
j < g
2
. For the
k
= 0 case, the
intersection point becomes
(︂−1,2g−j+3
g−j+1 )︂
, which has
y
-coordinate strictly smaller than 3 when
2g−j+3
g−j+1 <
3, or equivalently when 2
g−j
+ 3
<
3
g−
3
j−
3
k
+ 3, or equivalently when
j < g
2
.
Thus we have a non-lattice vertex due to τ(−1)
5collapsing precisely when j < g
2.
We conclude that Q(−1) is a lattice polygon if and only if i≥g/2 and j≥g/2.
Combining Lemmas 3.4.2, 3.4.3, and 3.4.4 and the preceding discussion, we have the
following classification of maximal polygons with lattice width 4.
Proposition 3.4.5.
Let
P
be a maximal polygon of lattice width 4. Then up to lattice
equivalence,
P
is either
T4
; one of the 14 polygons in Figure 3.9; or
Q(−1)
, where
Q
is a
hyperelliptic polygon satisfying the conditions of Lemma 3.4.2, 3.4.3, or 3.4.4.
The most important consequence of Propositions 3.4.1 and 3.4.5 is that we can determine
which panoptigons of lattice width 1 or lattice width 2 are interior polygons of some lattice
polygon. We summarize this with the following result.
Corollary 3.4.6.
Let
Q
be a panoptigon with
lw
(
Q
)
≤
2such that
Q(−1)
is lattice polygon.
Then |Q∩Z2| ≤ 11.
Proof.
If
lw
(
Q
) = 1 with
Q(−1)
a lattice polygon, then
Q
must be the trapezoid
Ta,b
with
0
≤a≤b
,
b≥
1, and
a≥b
2−
1 by Proposition 3.4.1. In order for
Ta,b
to be a panoptigon,
we need
a≤
2 by Lemma 3.3.1, so 2
≥b
2−
1, implying
b≤
6. It follows that
|Q∩Z2|
=
a+b+ 2 ≤2 + 6 + 2 = 10.
Now assume
lw
(
Q
) = 2 with
Q(−1)
a lattice polygon. If
Q
has genus 0 then it is
T2
, and
has 6 lattice points. If
Q
has genus 1 then it is one of the polygons in Figure 3.3, and so
has at most 9 lattice points. Outside of these situations, we know that
Q
is a hyperelliptic
41
panoptigon of genus
g≥
2 as characterized in Lemma 3.3.3. We deal with two cases: where
Qhas a panoptigon point at height 1, and where it does not.
In the first case, we either have
g
= 2 with
Q
of Type 1 or Type 2, or
g
= 3 with
Q
of
Type 1. A hyperelliptic polygon of Type 1 has (
i
+ 1) + (1 + 2
g−i
) = 2
g
+ 2 boundary points.
A hyperelliptic polygon of Type 2 has
i
+
j
+ 3 boundary points. If
Q
is of Type 1, then it
has in total 3
g
+ 2
≤
11 lattice points. If
Q
is of Type 2, then
i
+
j≤
2
g
+ 1 = 2
·
2 + 1 = 5,
implying that Qhas a total of i+j+ 3 + g≤5 + 3 + 2 = 10 lattice points.
In the second case, we know that
Q
must have at most 3 points at height 0 or 2, and
exactly 1 point at the other height. First we claim that
Q
cannot be of Type 1: there are
2
g
+ 2
≥
6 boundary points, all at height 0 or 2, and
Q
can have at most 4 points total at
those heights. For Types 2 and 3, we know by Lemmas 3.4.3 and 3.4.4 that either
i≥g
2
+ 1
and
j≥g−1
2
, or
i≥g
2
and
j≥g
2
. At least one of
i
and
j
must equal 0 to allow for a single
point at height 0 or height 2, so these inequalities are impossible for
g≥
2. Thus
Q
cannot
have Type 2 or Type 3 either, and this case never occurs.
We conclude that if
Q
is a panoptigon of lattice width 1 or 2 such that
Q(−1)
is a lattice
polygon, then |Q∩Z2| ≤ 11.
3.5 Big face graphs are not tropically planar
Let
G
be a planar graph. Recall that we say that
G
is a big face graph if for any planar
embedding of G, there exists a bounded face that shares an edge with every other bounded
face. Our main examples of big face graphs will come from the following construction. First
we recall the construction of a chain of genus
g
from [
10
,
§
6]. Start with
g
cycles in a row,
connected at
g−
1 vertices which are 4-valent. We will resolve each of these 4-valent vertices
to result in two 3-valent vertices in one of two ways. Let
v
be a vertex, incident to the edges
e1, e2, f1, f2
where
e1
and
e2
are part of one cycle and
f1
and
f2
are part of another. We will
remove
v
and replace it with two connected vertices
v1
and
v2
, and we will either connect
v1
to
e1
and
f1
and
v2
to
e2
and
f2
; or we will connect
v1
to
e1
and
e2
and
v2
to
f1
and
f2
. Any
graph obtained from making such a choice at each vertex is then called a chain. Figure 3.10
illustrates, for
g
= 3, the starting 4-regular graph; the two ways to resolve a 4-valent vertex;
and the resulting chains of genus 3. We remark that although there are 2
×
2 = 4 ways to
choose the vertex resolutions, two of them yield isomorphic graphs, giving us 3 chains of
genus 3 up to isomorphism. Note that for every genus, there is exactly one chain that is
bridge-less, i.e. 2-edge-connected.
42
e1
e2
f1
f2
v
e1
e2
f1
f2
v1
v2
e1
e2
f1
f2
v1
v2
%
&
Figure 3.10: The starting 4-regular graph in the chain construction; the two choices for
resolving a 4-valent vertex; and the three chains of genus 3, up to isomorphism
Given a chain of genus
g
, we construct a looped chain of genus
g
+ 1 by adding an edge
from the first cycle to the last one. The looped chains of genus 4 corresponding to the chains
of genus 3 are illustrated in Figure 3.11. For larger genus, we remark that two non-isomorphic
chains can give rise to isomorphic looped chains.
Figure 3.11: The looped chains of genus 4
In order to argue that any looped chain is a big face graph, we recall the following
useful result. By a special case of Whitney’s 2-switching theorem [
39
, Theorem 2.6.8], if
G
is a 2-connected graph, then any other planar embedding can be reached, up to weak
equivalence
3
, from the standard embedding by a sequence of flippings. A flipping of a planar
embedding finds a cycle
C
with only two vertices
v
and
w
incident to edges exterior to
C
,
and then reverses the orientation of
C
and all vertices and edges interior to
C
to obtain a
new embedding. This process is illustrated in Figure 3.12, where
C
is the highlighted cycle
v−a−b−w−d−v.
Lemma 3.5.1. Any looped chain is a big face graph.
3
Weak equivalence means two graph embeddings have the same facial structure, although possibly with
different unbounded faces.
43
v
w
C
a
b
c
d
→
v
a
b
c
w
d
Figure 3.12: Two embeddings of a planar graph related by a flipping
Proof.
In the standard embedding of a looped chain as in Figure 3.11, there are (at least)
two faces that share an edge with all other faces: one bounded and one unbounded. Since any
looped chain is 2-connected, any other embedding can be reached, up to weak equivalence,
by a sequence of flippings. It thus suffices to show that the standard embedding of a looped
chain is invariant under flipping.
Consider the standard embedding of a looped chain
G
, and assume that
C
is a cycle in
G
that has exactly two vertices
v
and
w
incident to edges exterior to
C
. Let
C
denote the set
of all vertices in or interior to
C
. Since
G
is trivalent and
C
is 2-regular, we know that
v
and
w
are each incident to exactly one edge, say
e
for
v
and
f
for
w
, that is exterior to
C
. We
now deal with two possibilities: that C=V(G), and that C⊊V(G).
If
C
=
V
(
G
), then
e
=
f
, and the only possibility is that
v
and
w
are the vertices added
to a chain
H
to build the looped chain
G
; that
H
is the bridge-less chain; and that
C
is
the outside boundary of
H
in its standard embedding. Flipping with respect to
C
does not
change the embedding of this graph.
G1
G2
G3
G4
G5
e5
e1
e2
e3
e4
Figure 3.13: The structure of a looped chain, where the bridge-less chains
Gi
have solid edges
and the edges
ei
are dotted; the boundaries of the
Gi
are bold, and are the only possible
choices of Cfor a flipping
If
C⊊V
(
G
), then
{e, f}
forms a 2-edge-cut for
G
, separating it into
C
and
CC
. Consider
the structure of
G
: it is a collection of 2-edge-connected graphs
G1, . . . , Gk
, namely a collection
44
of bridge-less chains, connected in a loop by edges
e1, . . . , ek
, where
ei
connects
Gi
and
Gi+1
,
working modulo
k
; see Figure 3.13 for this labelling scheme. We claim that
e, f ∈ {e1, . . . , ek}
.
If not, then without loss of generality
e
is in some bridge-less chain
Gi
. If
f∈E
(
Gj
) for
j
=
i
, then the graph remains connected; the same is true if
f∈ {e1, . . . , ek}
. So we would
need
f
to also be in
Gi
. By the structure of the looped chain, we would need the removal of
e
and
f
to disconnect
Gi
into multiple components, at least one of which is not incident to
ei
or
ei+1
; however, this is impossible based on the structure of a bridge-less chain. It follows
that
e
and
f
must be among
e1, . . . , ek
. The only way to choose a pair
{e, f}
from among
e1, . . . , ek
so that they are the only exterior edges incident to the boundary of a cycle
C
is if
they are incident to the same bridge-less chain
Gi
; that is, if up to relabelling we have
e
=
ei
and
f
=
ei+1
for some
i
. Thus
C
and its interior constitutes one of the bridge-less chains
Gi
.
But flipping a bridge-less chain does not change the embedding of our (unlabelled) graph,
completing the proof.
Figure 3.14: The loop of loops Lgfor 3 ≤g≤6
We summarize the connection between big face graphs and panoptigons in the following
lemma.
Lemma 3.5.2.
Suppose that
G
is a tropically planar big face graph arising from a polygon
P. Then Pint is a panoptigon.
This is not an if-and-only-if statement, since not all triangulations of
P
connect a point
of
Pint
to all other points of
Pint
; for instance, the chain of genus 3 with two bridges is not a
big face graph, but by [10, §5] it arises from T4whose interior polygon is a panoptigon.
Proof.
Let ∆ be a regular unimodular triangulation of
P
such that
G
is the skeleton of the
dual graph of ∆. The embedding of
G
arising from this construction must have a bounded
face
F
bordering all other faces. By duality, we know that
F
corresponds to an interior lattice
point pof P. Since Fshares an edge with all other bounded faces, dually pis connected to
each other interior point of
P
by a primitive edge in ∆. Thus
Pint
is a panoptigon, with
p
a
panoptigon point for it.
45
One common example of a looped chain of genus
g
is the loop of loops
Lg
, obtained by
connecting g−1 bi-edges in a loop. This is illustrated in Figure 3.14 for gfrom 3 to 6. For
low genus, the loop of loops is tropically planar. Figure 3.15 illustrates polygons of genus
g
for 3
≤g≤
10 along with collections of edges emanating from an interior point; when
completed to a regular unimodular triangulation
4
, they will yield
Lg
as the dual tropical
skeleton. Thus
Lg
is tropically planar for
g≤
10. Another example of a tropically planar
looped chain, this one of genus 11, is pictured in Figure 3.16, along with a regular unimodular
triangulation of a polygon giving rise to it. Since the theta graph of genus 2 is also tropically
planar [
10
, Example 2.5] and is a big face graph, there exists at least one tropically planar
big face graph of genus
g
for 2
≤g≤
11. We are now ready to prove that this does not hold
for g≥14.
Figure 3.15: Starts of triangulations that will yield the loop of loops as the dual tropical
skeleton
Figure 3.16: A tropically planar big face graph of genus 11, with a regular unimodular
triangulation giving rise to it
Proof of Theorem 3.1.3.
Let
G
be a tropically planar big face graph, and let
P
be a lattice
polygon giving rise to it. By Lemma 3.5.2,
Pint
is a panoptigon. If
lw
(
Pint
)
≤
2, then
g
=
|Pint ∩Z2| ≤
11 by Corollary 3.4.6. If
lw
(
Pint
)
≥
3, then
g
=
|Pint ∩Z2| ≤
13 by Theorem
3.1.2. Either way, we may conclude that the genus of Gis at most 13.
4
One way to see that this can be accomplished is to use a placing triangulation [
20
,
§
3.2.1], where the
highlighted panoptigon point is placed first and the other lattice points are placed in any order.
46
It follows, for instance, that no looped chain of genus g≥14 is tropically planar.
If we are willing to rely on our computational enumeration of all non-hyperelliptic
panoptigons, we can push this further: there does not exist a tropically planar big face graph
for
g≥
12, and this bound is sharp. We have already seen in Figure 3.16 that there exists a
tropically planar big face graph of genus 11. To see that none have higher genus, first note
that if
Pint
is a panoptigon with 12 or 13 lattice points, then
Pint
must be non-hyperelliptic by
Corollary 3.4.6. Thus
Pint
must be one of the 15 non-hyperelliptic panoptigons with 12 lattice
points, or one of the 8 non-hyperelliptic panoptigons with 13 lattice points, as presented in
section 3.6. However, for each of these polygons
Q
, we have verified computationally that
Q(−1)
is not a lattice polygon; see Figure 3.20. Thus no lattice polygon of genus
g≥
12 has
an interior polygon that is also a panoptigon. It follows from Lemma 3.5.2 that no big face
graph of genus larger than 11 is tropically planar.
We close with several possible directions for future research.
•
For any lattice point
p
, let
vis
(
p
) denote the set of all lattice points visible to
p
(including
p
itself). Given a convex lattice polygon
P
, define its visibility number to
be the minimum number of lattice points in
P
needed so that we can see every lattice
point from one of them:
V(P) = min {︄|S|:S⊂P∩Z2and P∩Z2⊂⋃︂
p∈S
vis(p)}︄.
Thus
P
is a panoptigon if and only if
V
(
P
) = 1. Classifying polygons of fixed visibility
number
V
(
P
), or finding relationships between
V
(
P
) and such properties as genus
and lattice width, could be interesting in its own right, and could provide new criteria
for determining whether graphs are tropically planar; for instance, the prism graph
Pn
=
K2×Cn
can only arise from a polygon
P
with
V
(
P
)
≤
2. This question is in
some sense a lattice point version of the art gallery problem.
•
We can generalize from two-dimensional panoptigons to
n
-dimensional panoptitopes,
which we define to be convex lattice polytopes containing a lattice point
p
from which all
the polytope’s other lattice points are visible. A few of our results generalize immediately;
for instance, the proof of Lemma 3.3.2 works in
n
-dimensions, so any polytope with
exactly one interior lattice point is a panoptitope. A complete classification of
n
-
dimensional panoptitopes for
n≥
3 will be more difficult than it was in two-dimensions,
especially since it is no longer the case that there are finitely many polytopes with a
fixed number of lattice points. Results about panoptitopes would also have applications
in tropical geometry; for instance, an understanding of three-dimensional panoptitopes
would have implications for the structure of tropical surfaces in R3.
47
•
To any lattice polygon we can associate a toric surface [
18
]. An interesting question
for future research would be to investigate those toric surfaces that are associated to
panoptigons, or more generally toric varieties associated to panoptitopes.
3.6 Panoptigon computations
From the proof of Theorem 3.1.2, we know that any panoptigon of lattice width and lattice
diameter both at least 3 must be equivalent to a polygon consisting of some subset of the
thirty lattice points pictured in Figure 3.7, where the points (0
,
0), (
−
1
,−
1), (0
,−
1), (1
,−
1),
and (2
,−
1) must be included. Using
polymake
[
23
], we ran through all possible convex
polygons consisting only of these 30 points. Ruling out those without interior lattice points
or with all lattice points collinear, we found a total of 215 distinct polygons, some of which
were equivalent under a unimodular transformation. These 215 polygons are available as the
collection “Non-hyperelliptic Panoptigons” in polyDB [
42
] at
https://db.polymake.org
.
Eliminating redundant copies, we find that there are a total of 69 non-hyperelliptic panoptigons
of lattice width and lattice diameter both at least 3, up to lattice equivalence. We list all
nonhyperelliptic panoptigons with lattice diameter at least 3 in Figure 3.19. The panoptigons
with 12 or 13 lattice points appear in Figure 3.20, along with their relaxed polygons. Each
relaxed polygon has at least one non-lattice vertex, marked by a square. The computation
of these relaxed polygons verifies that no non-hyperelliptic panoptigon with 12 or 13 lattice
points is the interior polygon of a lattice polygon.
To complete an enumeration of all non-hyperelliptic panoptigons of genus
g≥
3, it remains
to find those panoptigons
P
that have lattice diameter smaller than 3. We accomplish this
with the following proposition.
Proposition 3.6.1.
Let
P
be a non-hyperelliptic panoptigon of lattice diameter at most 2.
Then up to lattice equivalence
P
is either the triangle
conv
((0
,
1)
,
(0
,
3)
,
(4
,
0)), the quadrilateral
conv((1,0),(2,0),(3,1),(0,3)), or the quadrilateral conv((0,1),(0,2),(2,3),(3,0)).
These three polygons are illustrated in Figure 3.17.
Figure 3.17: The three non-hyperelliptic panoptigons from Proposition 3.6.1
48
Proof.
Since
P
is non-hyperelliptic, we know that
lw
(
P
)
≥
3. Note that we cannot have
ℓ
(
P
) = 1, since then we would have
lw
(
P
)
≤ ⌊4
3ℓ
(
P
)
⌋
+ 1 = 2. Thus
ℓ
(
P
) = 2. It follows that
lw
(
P
)
≤ ⌊4
3ℓ
(
P
)
⌋
+1=2+1=3, so
lw
(
P
) = 3. We know
P
is not
T3
since
T3
is hyperelliptic, so
we know that the interior polygon
Pint
must have lattice width 1. It follows that
Pint
must be
a trapezoid of height 1, and since
ℓ
(
P
) = 2 that trapezoid must have at most 3 lattice points
at each height; thus
Pint
=
Ta,b
where 0
≤a≤b≤
2. It follows that
P
must be contained in
one of the polygons pictured in Figure 3.18; these are the maximal polygons associated to the
candidates for
Pint
. In order to refer to the lattice points of these polygons with coordinates,
we will assume that each is positioned to have the lower left corner at the origin (0,0).
Figure 3.18: Possible interior polygons for Pint, and polygons that must contain P
We claim that
P
cannot have
T0,2T1,2
, or
T2,2
as its interior polygon. In each of those
cases, note that
P
automatically has 3 interior points at height 1; since
ℓ
(
P
) = 2, there can
be no boundary lattice points at height 1. In order for boundary lattice points at height 0 to
connect to boundary lattice points at height greater than 1, the points (1
,
0) and (4
,
0) must
be included; but then there are 4 collinear lattice points at height 0, contradicting
ℓ
(
P
) = 2.
Now suppose
Pint
=
T1,1
. Note that no boundary point of the 3
×
3 square can see
all interior points, so any panoptigon point
q
must be an interior point. Without loss of
generality, assume that it is
q
= (1
,
1), meaning that the points (1
,
3), (3
,
1), and (3
,
3) cannot
be included in
P
. Among the two points (2
,
3) and (3
,
2), at least one must be included to
allow for the desired interior polygon. By symmetry we may assume that (2
,
3) is included.
There cannot be any other points at height 3, so (2
,
3) must be a vertex of
P
and connect
to a boundary point of the form (0
, b
); the only possible such point is (0
,
2). It then follows
that (3
,
2) cannot be included, since this would yield 4 collinear points at height 2. Thus
P
has an edge connecting (2
,
3) to (3
,
0). The point (2
,
0) cannot appear in
P
since there are
already three points with
x
-coordinate equal to 2, so (3
,
0) must be connected to (0
,
1). At
this point, we know that
P
=
conv
((0
,
1)
,
(0
,
2)
,
(2
,
3)
,
(3
,
0)). This is indeed a panoptigon of
lattice width 3 and lattice diameter 2.
Finally we will deal with the case where
Pint
=
T0,1
. We deal with several possibilities for
the (not necessarily unique) panoptigon point qof P.
49
•
Suppose
q
is an interior lattice point of
P
. By symmetry we may assume
q
= (1
,
1), so
the lattice points (3
,
1) and (1
,
3) cannot be included. Since there must at least one
lattice point at height 3 or above, either (0
,
3) or (0
,
4) (or both) must be included. If it
is only (0
,
4) and not (0
,
3), then the points (1
,
0) and (3
,
0) must be included, yielding
the polygon
conv
((1
,
0)
,
(3
,
0)
,
(0
,
4)). Otherwise, (0
,
3) is in
P
. Since (0
,
3), (1
,
2), and
(2
,
1) are all lattice points of
P
, the point (3
,
0) cannot be included. Now, at least one
lattice point from the diagonal edge must be included, namely (4
,
0), (2
,
2), or (0
,
4);
in fact, it must be exactly one, since otherwise (1
,
3) or (3
,
1) would be introduced by
convexity. If
P
contains (0
,
4) or (2
,
2) and no other points along that edge, then it
must also contain (3
,
0), which we have already ruled out. Thus
P
contains (4
,
0), and
as it does not contain (3
,
0) it must have an edge connecting (4
,
0) to (0
,
1). At this
point there is a single possibility for
P
, namely
P
=
conv
((0
,
1)
,
(0
,
3)
,
(4
,
0)). This
polygon is equivalent to the previous one, so we need only include one. This panoptigon
does indeed have lattice diameter 2.
•
Now we deal with the case that the panoptigon point is a boundary point. Since the
panoptigon point must see all three interior points, it must either be a vertex of
T4
or
the midpoint of one of the edges. Up to symmetry, we may thus assume that
q
is either
(0
,
0) or (2
,
0). If
q
= (0
,
0), then the point (1
,
3) must be included; otherwise we would
need (0
,
3), which is not visible to (0
,
0). Similarly (1
,
3) is included, but then (2
,
2) is
included by convexity, and this point is not visible to (0,0), a contradiction.
If
q
= (2
,
0), then there are 1, 2, or 3 points at height 0. If there is only
q
, then the
points (0
,
1) and (3
,
1) must be included, contradicting
ℓ
(
P
) = 2. If there are 2 points,
we will assume by symmetry that the two points are (1
,
0) and (2
,
0). The lattice
point (3
,
1) must then be included and the point (0
,
1) must not be included; the only
remaining point to include from the face on the line
x
= 0 is (0
,
3). No other lattice
points can be included, so then
P
=
conv
((1
,
0)
,
(2
,
0)
,
(3
,
1)
,
(0
,
3)). Finally, if there
are 3 points at height 0 they must be (1
,
0), (2
,
0), and (3
,
0). But now neither (0
,
3)
nor (1
,
3) may be included since
ℓ
(
P
) = 2. Since (0
,
4) is not visible from
q
, there are
no points in
P
with height greater than 2, a contradiction to
T0,1
being the interior
polygon of P.
We conclude that the only non-hyperelliptic panoptigons
P
with
ℓ
(
P
)
≤
2 are the three
claimed.
Combined with our computation, this gives us the following count.
50
Corollary 3.6.2. Up to lattice equivalence, there are 72 non-hyperelliptic panoptigons.
The explicitness of our enumeration allows us to find the largest lattice width of any
panoptigon: by Lemma 3.2.2, the lower right triangle in Figure 3.20 has lattice width 5, and
all the other panoptigons have lattice width 4 or less.
Results of the presented work in this chapter have been published in - Ralph Morrison
and Ayush Kumar Tewari. “Convex lattice polygons with all lattice points visible”, Discrete
Mathematics [41].
51
Figure 3.19: All nonhyperelliptic panoptigons with lattice diameter at least 3
52
Figure 3.20: All non-hyperelliptic panoptigons with 12 or 13 lattice points, along with their
relaxed polygons
53
Chapter 4
Point-line geometry in the tropical
plane
4.1 Introduction
Point-line geometry has been studied for a long time, and it mainly deals with the question
of incidence, i.e. when a point meets a line. There are many classical results established
about the incidence of points and lines in projective and affine planes like the Sylvester-Gallai
theorem, de-Bruijn Erd˝os theorem, Szemeredi-Trotter theorem, Beck’s theorem etc. In recent
times, there has been a lot of development in generalising these classical results, like [
29
]
surveys the work done on generalizations of de-Bruijn Erd˝os theorem. In a recent study in
[30], tropical lines present in a fixed plane are also studied.
Since tropical geometry provides a piecewise linear model of point line geometry, many
incidence geometric results have also been proved in it. In [
8
] a tropical version of Sylvester-
Gallai theorem and Motzkin-Rabin theorem is established along with the universality theorem.
In [
47
] the term geometric construction is coined , in order to identify all the types of classical
incidence geometric results which can have a tropical analogue. Even in [
45
] and [
46
] a
tropical version of Pappus theorem is discussed along with classical point-line configurations.
Another aspect is the relation to oriented matroids, and as mentioned in [
8
], it is elaborated in
[
2
], in the context of hyperplane arrangements and how they correspond to tropical oriented
matroids and how these matroids encode incidence information about point-line structures in
the tropical plane. The fact that the tropical plane allows projective duality, facilitates much
of the above mentioned results.
In this chapter, we start with some basic notions of point line geometry and specifically
the point-line geometry in the tropical plane. Subsequently, using the results obtained in
[
8
] and by introducing the notion of stable tropical lines we state a tropical counterpart to
de-Bruijn-Erd˝os theorem. We also establish the equivalence between a much general notion
54
of stability for curves, in [
47
], and the stable lines that we define in our work. We find that
tropicalization of generic lifts of points determines the stable tropical line passing through
them. We establish the duality between stable lines and stable intersections and provide a
full classification of the faces that they correspond to in the dual Newton subdivision. With
this setup, we prove the tropical analogue of de-Bruijn-Erd˝os theorem,
Theorem 4.1.1
(Tropical de-Bruijn-Erd˝os Theorem)
.
Let
S
denote a set of points in the
tropical plane. Let v(v≥4) denote the number of points in S, and let bdenote the number
of stable tropical lines determined by these points. Then,
1. b≥v−3
2. if b=v−3, then Sforms a tropical near-pencil.
The definitions and the results required to state and prove Theorem 4.1.1 are elaborated
in the latter parts of this chapter.
4.2 Classical incidence geometry
In classical incidence geometry a linear space is defined in the following manner [22],
Definition 4.2.1.
Afinite linear space is a pair (
X, B
), where
X
is a finite set and
B
is a
set of proper subsets of X, such that
1. every unordered pair of elements of Xoccur in a unique B∈ B.
2. Every B∈ B has cardinality at least two.
Essentially, a linear space is a point-line incidence structure, in which any two points lie
on a unique line.
Example 4.2.2.
Consider
L
= (
X, B
), where
X
is the set of points in the Euclidean plane
and Bis the set of lines determined by X.
Another important definition about lines is,
Definition 4.2.3.
A line which passes through exactly two points is called an ordinary line.
Erd˝os and de-Bruijn, came up with a theorem about point-line arrangements in a linear
space [19], which is established in [7] and stated in Theorem 4.2.4.
55
Theorem 4.2.4
(de-Bruijn-Erd˝os Theorem)
.
Let
S
= (
X, B
)be a linear space. Let
v
denote
the number of points in
S
(=
|X|
), and
b
denote the number of lines determined by these
points (= |B|,b > 1). Then
1. b≥v,
2.
if
b
=
v
, any two lines have a point in common. In case (2), either one line has
v−
1
points and all others have two points, or every line has
k
+ 1 points and every point is
on k+ 1 lines, k≥2.
For a more general treatment and recent developments, one can read [
29
], where enu-
merative results like the above have been discussed in a more general setting of geometric
lattices.
Theorem 4.2.4 clearly is a very general statement, and in the case for points and lines in
the Euclidean plane, the bound on the number of lines is attained when points are in a near
-pencil configuration and the proof follows by induction and invoking Theorem 4.2.5.
Theorem 4.2.5
(Sylvester-Gallai Theorem)
.
Given a finite collection of points in the Eu-
clidean plane, such that not all of them lie on one line, then there exists a line which passes
through exactly two of the points.
4.3 A brief introduction to tropical geometry
Tropical geometry can be defined as the study of geometry over the tropical semiring
T
= (
R∪ {−∞}
, max, +). A
tropical polynomial p
(
x1, . . . , xn
) is defined as a linear
combination of tropical monomials with operations as the tropical addition and tropical
multiplication.
p(x1, . . . , xn) = a⊙x1i1x2i2. . . xnin⊕b⊙x1j1x2j2. . . xnjn⊕. . .
With the above definitions, we see that a tropical polynomial is a function
p
:
Rn−→ R
given by maximum of a finite set of linear functions.
Definition 4.3.1.
The
hypersurface V
(
p
) of
p
is is the set of all points
w∈Rn
at which
the maximum is attained at least twice. Equivalently, a point
w∈Rn
lies in
V
(
p
) if and only
if pis not linear at w.
The tropical polynomial defining a tropical line is given as
p(x, y) = a⊙x⊕b⊙y⊕c, where a, b, c ∈R,
56
(c−a, c−b)
Figure 4.1: A tropical line
and the corresponding hypersurface is the corner locus defined by the above polynomial,
which is a collection of three half rays emanating from the point (
c−a, c −b
) in the primitive
directions of (−1,0),(0,−1) and (1,1) (Refer [38]).
Now we look at the intersections of lines in the tropical plane. As is evident from the
setup, tropical lines can intersect over a half ray. However, two tropical lines have a unique
stable intersection, where a stable intersection is the limit of points of intersection of nearby
lines which have a unique point of intersection, within a suitable
ϵ
, with the limit being taken
as
ϵ
tends to 0 [
38
]. We refer the reader to [
38
] for further details about stable intersections
in full generality. We also define the two types of stable intersections which we encounter in
the case of tropical line arrangements,
Definition 4.3.2.
A stable intersection in a tropical line arrangement is called stable inter-
section of first kind if no vertex of any line from the line arrangement is present at the point
of intersection.
Definition 4.3.3.
A stable intersection in a tropical line arrangement is called stable inter-
section of second kind if the vertex of a line from the line arrangement is present at the point
of intersection.
An important observation is the projective duality which exists in the tropical plane [
8
],
which means that given a set of points
P
, there exists a incidence preserving map
ϕ
which
maps
P
to its dual set of tropical lines
L
, where for each point
P∈ P
,
ϕ
(
P
) =
l
with
−P
as
the vertex of the line l∈ L.
The support of a tropical polynomial is the collection of the exponents of the monomials
which have a finite coefficient. The convex hull of the exponents in the support of a tropical
polynomial defines a Newton polytope. We recall the definition of regular subdivisions from
Chapter 1 . There exists a duality between a tropical curve
T
, defined by a tropical polynomial
p
, and the subdivision of the Newton polygon corresponding to
p
, induced by the coefficients
of the tropical polynomial
p
. For further details about the description of this duality, the
reader can refer to [38, Chapter 3] and [11, Proposition 2.5].
57
For a comprehensive study in a general setting, we analyze the underlying field
K
. A
valuation on
K
is a map
val
:
K→R∪ {∞}
such that it follows the following three axioms
[38],
1. val(a) = ∞if and only if a= 0;
2. val(ab) = val(a) + val(b);
3. val(a+b)≥min{val(a), val(b)}for all a, b ∈K.
An important example of a field with a non-trivial valuation is the field of Puiseux series
over a arbitrary field
k
, represented as
K
=
k{{t}}
. The elements in this field are formal
power series
k(t) = k1ta1+k2ta2+k3ta3. . . ,
where each
ki∈k, ∀i
and
a1< a2< a3< ....
are rational numbers with a common
denominator. This field has a natural valuation
val
:
k{{t}} → R
given by taking a nonzero
element
k
(
t
)
∈k{{t}}∗
, (where
k{{t}}∗
represents the non zero element in the field
k{{t}}
)
and mapping it to the lowest exponent a1in the series expansion of k(t) [38].
It is an important observation that the valuation on the field of Puiseux series mimics the
operations of a tropical semiring in essence and for further discussions one can think of the
underlying field for the computations to be a Puiseux series with non-trivial valuation. So
points which are considered in the plane, would have lifts residing in corresponding field of
Puiseux series and the map which maps these lifts back to the points is the tropicalization
map. For a polynomial
f
=
∑︁u∈Nn+1 cuxu
, where the coefficients are from the field with a
non-trivial valuation, the tropicalization of fcan be defined as [38],
trop(f)(w) = max{−val(cu) + w·u:u∈Nn+1 and cu= 0}
We refer the reader to [38] for further details about this map.
Atropical line arrangement is a finite collection of distinct tropical lines in R2.
Definition 4.3.4.
A tropical line arrangement
L
is said to be a tropical near-pencil arrange-
ment if in the dual Newton subdivision, for all triangular faces present in the subdivision; at
least one of the edges of the triangular face lies on the boundary of the Newton polygon.
Definition 4.3.5.
A set of points
N
in the tropical plane, is said to form a tropical near-pencil
if the dual tropical line arrangement is a tropical near pencil arrangement.
58
(a) A tropical near pencil arrangement (b) The corresponding dual subdivision
Figure 4.2: An example of a tropical near pencil arrangement
(a) Point set with stable tropi-
cal line
(b) Dual tropical near pencil
line arrangement
(c) Dual subdivision to the line
arrangement
Figure 4.3: An example of a tropical near pencil
For a tropical line arrangement with lines
l1, . . . , ln
with corresponding tropical polynomials
being
f1, . . . , fn
the tropical line arrangement, as a union of tropical hypersurfaces, is defined
by the polynomial,
f=f1·f2. . . ·fn
The dual Newton subdivision corresponding to the tropical line arrangement is the Newton
subdivision dual to the tropical hypersurface defined by the tropical polynomial
f
(cf. [
31
]).
We realize that stable intersections of first kind correspond to parallelograms and hexagons in
the dual Newton subdivision and stable intersections of second kind correspond to irregular
cells with four, five or six edges in the dual Newton subdivision.
For an elaborate description of dual Newton subdivisions, corresponding to tropical line
arrangements, the reader is advised to refer to [8, Section 2.3].
4.4 Tropical incidence geometry
The behaviour of point-line structures in the tropical plane is distinct from the Euclidean
case, specifically with the appearance of coaxial points.
Definition 4.4.1.
Two points are said to be coaxial if they lie on the same axis of a tropical
line containing them [8].
A recent result in [8] proves the tropical version of the Sylvester Gallai Theorem,
59
p0
p1
Figure 4.4: The infinite number of lines passing through the coaxial points p0and p1
p0
p1
Figure 4.5: A stable tropical line (L, p0, p1)
Theorem 4.4.2
(Tropical Sylvester-Gallai)
.
Any set of four or more points in the tropical
plane determines at least one ordinary tropical line.
An important observation is that if we consider a point set with no two points being
coaxial, then there is a unique line passing through any two points , and therefore the
point-line incidence structure in this case forms a linear space. Hence, we can invoke the
classical de-Bruijn-Erd˝os theorem to conclude that such a set of
n
points determines at least
nlines.
With the existence of a Tropical Sylvester-Gallai theorem, it is quite natural to explore
the possibility of a tropical version of the de-Bruijn-Erd˝os theorem, i.e., a lower bound on
the number of tropical lines determined by a
n
point set in the tropical plane. However, the
number of lines determined by coaxial points are infinite in this setting. For the question of
counting lines to be well posed, we would like to be in a scenario where a finite set of points
determine a finite set of lines. Hence, rather than counting the number of lines as shown in
Figure 4.4, we count a special class of lines, namely stable tropical lines.
Definition 4.4.3.
Consider (
L, p1, . . . , pn
)
,
(
n≥
2) where
L
is a tropical line with the points
(p1, . . . , pn) on the line L, then (L, p1, . . . , pn), is called stable if
1. either Lis the unique line passing through the pi’s, or
2. one of the points p1, . . . , pnis the vertex of L.
Now we show that this restriction on the counting of lines, turns out to be quite general
as these stable lines turn out to be the tropicalization of the line passing through generic lifts
of the points.
60
−u′
−u′
−v
0
(−u′,v)
(−u, v)
Figure 4.6: Newton polytope and tropicalization for trop(P1P2)
Proposition 4.4.4.
Given two coaxial points
p1
= (
−u, −v
),
p2
= (
−u′,−v′
)
∈K2
, pick lifts
P1
= (
a1tu
+
. . .
,
b1tv
+
. . .
)and
P2
= (
a2tu′
+
. . .
,
b2tv
+
. . .
)over
K{{t}}
. If
b1
=
b2
, then
trop(P1P2)is the stable tropical line through p1and p2.
Proof.
Since we assume that the two points,
p1
and
p2
are coaxial, we take
v
=
v′
which
would imply that the two points are coaxial in the (−1,0) primitive direction.
An equation of a line in the plane is
ax
+
by
=
c
. So if the lifts
P1
and
P2
lie on this line,
then they satisfy this equation
a(a1tu+. . .) + b(b1tv+. . .) = c(4.4.1)
a(a2tu′+. . .) + b(b2tv+. . .) = c(4.4.2)
Without loss of generality we assume
u > u′
and
a
= 1. So subtracting the two equations
gives us
−a2tu′+O(tu′) + b((b1−b2)tv+O(tv)) = 0
=⇒b=a2tu′+O(tu′)
(b1−b2)tv+O(tv)
=⇒c=a2tu′+. . . +(a2tu+O(tu′))·(b2tv+...)
(b1−b2)(tv)+...)
Therefore
val
(
c
) =
−u′
and
val
(
b
) =
−u′−v
, and we get the Newton polytope and the
tropicalization as shown in Figure 4.6,
which is a stable tropical line passing through p1= (−u′,−v) and p2= (−u, −v).
The result for two points being coaxial in the other two primitive directions also follows
with a similar computation.
Alternatively, in [
47
] in Section 2.2 a notion of a stable curve though a set of
n
points is
introduced. The definition of a stable curve in [47] is as follows
61
Definition 4.4.5.
The stable curve of support
I
passing through
{q1, . . . , qδ−1}
is the curve
defined by the polynomial
f
= “
∑︁i∈Iaixi1yi2
”, where the coordinates
ai
of
f
are the stable
solutions to the linear system imposed by passing through the points qj.
where for a curve
H
given by a polynomial
f
, the support is the set of tuples of
i∈Zn
such that
ai
appears in
f
,
δ
(
I
) denotes the number of elements in
I
and the stable solution
for a set of tropical linear forms is the common solution for all the linear forms, which is also
stable under small perturbations of the coefficients of the linear forms [46][45].
So let us consider the above case for tropical lines and try to see the equivalent definitions
of stable lines through two points according to [47].
The linear form that represents a tropical line in the tropical plane is given by
a⊙x⊕b⊙y⊕c(4.4.3)
So the support in this case is a set of 3-tuples of
Z3
and
δ
(
I
) = 3. We take two arbitrary
points in the (-1,0) direction of a tropical line
P1
= (
−u, v
) and
P2
= (
−u′, v
), where
u
and
u′
both are positive and
u′≤u
. Now let us compute the stable line passing through
P1
and
P2in the setup of [47].
The tropical linear system obtained by plugging in the points in 4.4.3 is as follows
{︃a⊙(−u)⊕b⊙v⊕c= 0
a⊙(−u′)⊕b⊙v⊕c= 0
Now the stable solution of the above tropical linear system provides the coefficients for
the linear form which defines the stable line passing through the two given points. The
corresponding coefficient matrix is given as
C=[︃−u v 0
−u′v0]︃.
With the help of explicit computations for calculating stable solutions of tropical linear
systems elaborated in [
46
] and [
45
], in the case above, we find that the stable solution is
given by (
|O1|t
:
|O2|t
:
|O3|t
) = (
v
:
−u′
:
−u′
+
v
) and hence the linear form representing
the stable line through P1and P2is given as
v⊙x⊕ −u′⊙y⊕ −u′+v(4.4.4)
This is a tropical line with vertex (α, β) satisfying
α+v=−u′+v=⇒α=−u′and β−u′=−u′+v=⇒β=v.
Hence, we get the stable line shown in Figure 4.7.
The computation for a two point configuration in the other two primitive directions also
follows in the same manner.
62
(−u′,−v)
(−u,−v)
Figure 4.7: Stable line passing through two given points
x
y
−4−3−2−1 0 1 2 3 4
−4
−3
−2
−1
0
1
2
3
4
x
y
−4−3−2−1 0 1 2 3 4
−4
−3
−2
−1
0
1
2
3
4
Figure 4.9: Duality between stable lines and stable intersections
So as is evident from the above discussion, taking two points on any one of the rays of a
tropical line, we see that the definition of a stable line in [47] coincides with 4.4.3.
An important observation here is that the Sylvester-Gallai Theorem fails if we restrict
ourselves to stable tropical lines. Figure 4.8 shows explicit examples of sets of points in
the tropical plane with
n
= 4 and 5 points such that these point sets do not determine an
ordinary stable tropical line.
n = 4 n = 5
Figure 4.8: Point sets which do not determine an ordinary stable tropical line
Proposition 4.4.6.
Given a
n
-point set
P
in the tropical plane, the number of stable lines
determined by
P
is equal to the number of stable intersections obtained in the corresponding
dual line arrangement.
Proof.
Consider an arbitrary stable tropical line (
L, p1, p2. . . pn
). By definition, either the
points
p1, p2. . . pn
uniquely determine
L
or one of the points amongst the
p′
is
is the vertex
of the line
L
. We first consider the case when the points
p1, p2...,pn
determine the line
uniquely, and in this case there must be at least two non coaxial points present on the line
L
,
63
and we realize that under duality, the reflection of the vertex of the line
L
with respect to
the origin corresponds to a unique stable intersection obtained in the dual line arrangement,
illustrated in the Figure 4.9. This implies a one to one correspondence between stable lines
determined by such points and the stable intersections obtained in the dual line arrangement.
Also, if one of the points amongst the
p′
is
is the vertex of the stable tropical line
L
, then
we again oberve that the reflection of the the vertex of the line
L
with respect to the origin,
corresponds to a unique stable intersection in the dual line arrangement, illustrated in the
Figure 4.9. Hence, we see a one to one correspondence between stable tropical lines and the
number of stable intersections in the dual line arrangement.
We realize that this duality between stable intersections and stable lines is a bit stronger;
if the stable line is the unique line passing through the points on it, then the vertex of the
line corresponds to a stable intersection of first kind and if the stable line has one of the
points as a vertex, then the vertex corresponds to a stable intersection of second kind.
Proposition 4.4.6 illustrates the fact that stable tropical lines are in fact dual to stable
intersections of tropical lines.
Proposition 4.4.6 leads on to the following corollary.
Corollary 4.4.7.
For a given tropical line arrangement
L
in the tropical plane, the number of
stable intersections equals the number of non-triangular faces in the dual Newton subdivision
corresponding to the tropical line arrangement.
Proof.
Since all stable intersections are obtained as intersections of two or more rays, each
point of intersection has at least four or more rays emanating from it in the primitive directions.
This corresponds through duality to faces with at least four edges or more and the only other
faces which contribute in the dual Newton subdivision are triangular faces which are not dual
to stable intersections. Hence, the number of stable intersections in the line arrangement is
equal to the number of non-triangular faces in the dual Newton subdivision.
With this duality established, let us look at the total number of faces, which we denote
as t, present in a dual Newton subdivision of a tropical line arrangement of ntropical lines,
where
n
remains fixed for our discussion. Firstly, there is a trivial lower bound of
n
on
t
,
since the
n
vertices of the tropical lines contribute at least
n
faces in the corresponding
Newton subdivision. Also
t
is bounded above by the number
(︁n
2)︁
+
n
, which is the number of
faces when any two lines in the line arrangement intersect transversally at a unique point [
8
].
Therefore, tsatisfies the following inequality
64
n≤t≤(︃n
2)︃+n
We recall that stable intersection of first kind correspond to parallelograms and hexagons
in the dual Newton subdivision and stable intersections of second kind correspond to irregular
cells with four, five or six edges in the dual Newton subdivision. A common description of all
the faces appearing in a dual Newton subdivision is described in the Figure 4.10 also present
in [8],
w3
w2+c
w1
w3+c
w2
w1+c
Figure 4.10: A cell in the Newton Subdivision, which is dual to a tropical line arrangement
[8]
where
w1, w2
and
w3
are the number of lines, which are coaxial in the three primitive
directions, and
c
represents the number of lines centered at the point dual to the face in the
tropical line arrangement. A Newton subdivision with faces of the shape described in Figure
4.10, is called a linear Newton subdivision and if the only faces occurring in a linear Newton
subdivision are triangles, parallelograms and hexagons, then such a subdivision is called a
semiuniform subdivision [8].
We refer to faces in the shapes of parallelograms and hexagons as semiuniform faces and
faces dual to stable intersections of second kind as non-uniform faces.
Figure 4.11 shows all the possible shapes of cells present in the dual Newton subdivision
of a tropical line arrangement; in the figure for all semiuniform faces, for each edge length
parameter we consider
wi
= 1 and for all non-uniform faces we take
c
= 1. For higher values
of
w′
is
and
c
the shapes remain the same however the edge lengths corresponding to each
parameter get elongated according to the values described in Figure 4.10.
We move on to discuss one of the extremal cases for the values of
t
, which is the case
when t=n.
Lemma 4.4.8.
Let
L
be a tropical line arrangement of n lines, having exactly
n
faces in the
corresponding dual Newton subdivision, then
L
has no stable intersections of first kind in the
tropical line arrangement.
Proof.
We start with a tropical line arrangement
L
of
n
tropical lines, such that it has exactly
n
faces. We continue by contradiction, assuming that there does exist a stable intersection of
65
2nd ↔Non-uniform
2nd ↔Non-uniform 2nd ↔Non-uniform
2nd ↔Non-uniform 2nd ↔Non-uniform
2nd ↔Non-uniform 2nd ↔Non-uniform
1st ↔Semi-uniform 1st ↔Semi-uniform
1st↔Semi-uniform 1st↔Semi-uniform
Figure 4.11: All possible shapes of faces present in the Newton subdivision of a tropical line
arrangement; with the labelings having type of stable intersections on the left along with the
type of face that corresponds to it on the right
66
first kind in the line arrangement
L
. However, since there are at least
n
faces contributed by
the
n
vertices of the
n
tropical lines, and the face corresponding to a stable intersection of
first kind is not one of them, therefore this would imply that the total number of faces in the
dual Newton subdivision corresponding to
L
has at least
n
+ 1 faces, which is a contradiction
to the fact that Lhas nfaces in the dual Newton subdivision. Hence, the proof.
We look at an example of a nline arrangement with exactly nfaces.
l1
l2
l3
l4ln
Figure 4.12: An example of a line arrangement with exactly
n
faces and three triangular faces
The example depicted in Figure 4.12 shows a tropical line arrangement of
n
tropical
lines
{l1, l2, l3, l4, . . . , ln}
, such that the total number of faces in the corresponding Newton
subdivision is
n
, and it has exactly three triangular faces located at the corners of the Newton
polygon.
We use (
vmax
)
t
to represent the maximum number of triangular faces present in a Newton
subdivision corresponding to a tropical line arrangement with total number of faces in the
Newton subdivision being equal to t.
Lemma 4.4.9.
Let
L
be a tropical line arrangement of
n
tropical lines such that the dual
Newton subdivision
N
has exactly
n
faces, then the maximum number of triangular faces in
Nis 3, i.e., (vmax)n= 3 .
Proof.
As can be seen from Figure 4.12, there are explicit tropical line arrangements of
n
tropical lines with
n
faces in the dual Newton subdivision with exactly 3 triangular faces. We
proceed by contradiction, and assume that (
vmax
)
n>
3. With (
vmax
)
n>
3, we can conclude
that there does exist at least one triangular face
T
in the interior of the Newton polygon, i.e.,
when no edges of
T
lie on the boundary of the Newton polygon or exactly one edge of
T
lies
on the boundary of the Newton polygon. We first consider the case when
T
is in the relative
interior of the Newton polygon, i.e., when no edges of
T
lie on the boundary of the Newton
polygon .
Let us consider the three faces
C1, C2
and
C3
that share an edge with the triangular face
T
and we consider an example of the local line arrangement around
T
as depicted in the
Figure 4.13.
67
C1
C2
C3
T
A
B
C
D
E
F
l0
l1l2
l3
Figure 4.13: Positions of cells in the Newton subdivision and the local line arrangement dual
to it
In the figure we see that the points
D
,
E
and
F
represent the vertices of the tropical
lines
l1, l2
and
l3
which are present at the stable intersections of second kind at these points,
dual to the cells
C1, C2
and
C3
in
N
. Also
l0
represents the line dual to the triangular face
T
. Also, by Lemma 4.4.8 we know that no stable intersections of first kind are present in the
line arrangement.
In the local picture, we obtain three stable intersections of first kind at the points
A, B
and
C
. Since these points are stable intersections and by Lemma 4.4.8 we know we can not
have any stable intersections of first kind therefore there must exist a line with its vertex
at these points. Let us consider one of these intersections,
A
. The points
D
,
A
and
F
are
represented as (x1, y1),(x2, y2) and (x3, y3), then it is easy to see that
x1< x2< x3
This helps to conclude that if there is a tropical line present with vertex at A, then it
would either intersect the lines
l0
and
l3
at two points, or meet the vertex of the line
l0
.
There cannot be a line with vertex at A meeting the vertex of the line
l0
as that would
contradict the fact that the face corresponding to
l0
is a triangular face
T
in
N
. So we
continue with the other case when the line has the vertex at A and intersects the lines
l0
and
l3
at two points. But there cannot be a tropical line present at A with two points of
intersection with the lines
l0
and
l3
, as that would contradict the fact that the cells
C1, C2
and
C3
corresponding to the stable intersections at
D
,
E
and
F
, share an edge with the triangular
face
T
. Hence, there cannot be a tropical line with a vertex at
A
, and therefore
A
has to be a
stable intersection of first kind, which contradicts Lemma 4.4.8. The same argument follows
for the other two points of intersections,
B
and
C
. However, this is a contradiction to the
Lemma 4.4.8. Another observation is that for all possibilities of non-uniform faces (arising
from stable intersections of second kind) surrounding
T
, we obtain points of intersections
in similar positions as
A
,
B
and
C
which establishes the existence of at least three stable
intersections of first kind, and hence gives a contradiction. Therefore, this shows that it is
not possible to place a triangular face in the relative interior of the Newton polygon.
68
C2
C1T
A
B
C
l0
l1l2
Figure 4.14: Positions of cell in the Newton subdivision and the local line arrangement dual
to it
The other possible case is when the triangular face intersects the boundary of the Newton
polygon in exactly one edge. Without loss of generality, we take the triangular face to be
intersecting with one of the edges of the Newton polygon as depicted in the Figure 4.14 and
we look at the local line arrangement around the triangular face T.
We argue in the same way as we did in the previous case, and realize that by Lemma
4.4.8,
C1
and
C2
in Figure 4.14 are non-uniform faces. Also, we see that in Figure 4.14 the
points
B
and
C
represent the vertices of the tropical lines
l1
and
l2
which are present at the
stable intersection of second kind at these points, dual to the cells
C1
and
C2
in
N
. Here
l0
represents the line dual to the triangular face T.
In the local picture, we obtain a stable intersection of first kind at the point
A
. If the
points
B
,
A
and
C
are represented as (
x1, y1
)
,
(
x2, y2
) and (
x3, y3
), then it is easy to see that
x1< x2< x3
This helps to conclude that if there is a tropical line present with vertex at
A
, then it
would either intersect the line
l0
, or meet the vertex of the line
l0
. There cannot be a line
with vertex at
A
meeting the vertex of the line
l0
as that would contradict the fact that the
face corresponding to
l0
is a triangular face
T
in
N
. So we continue with the other case
when the line has the vertex at
A
and intersects the lines
l0
. But there cannot be a tropical
line present at this intersection as that would contradict the fact that the cells
C1
and
C2
corresponding to the stable intersections of second kind at
B
and
C
share an edge with the
triangular face
T
. Hence, there cannot be a tropical line with a vertex at
A
, and therefore
A
has to be a stable intersection of first kind, which contradicts Lemma 4.4.8. It is easy to
verify that this contradiction occurs for all possibilities of non-uniform faces (arising from
stable intersections of second kind), which can be adjacent to T.
Therefore, the only places left to place a triangular face in the Newton polygon, are the
three corners, and hence the maximum number of triangular faces that can be obtained is
three, i.e., (vmax)n= 3.
69
T
S1
S2S3
Figure 4.15: The non-adjacent semiuniform faces determined by a triangular face T
Using Lemma 4.4.9 we obtain Corollary 4.4.10,
Corollary 4.4.10.
Let
L
be a tropical line arrangement of
n
lines, such that
t
=
n
and let
v
denote the number of triangular faces present in the dual Newton subdivision N. Then
n−v≥n−3
Remark 4.4.11.An important inference is that for tropical line arrangements of
n
lines, with
n
faces in the dual Newton subdivision, they occur in four distinct classes. Each class is
represented by the number of triangular faces at the corners, which varies between 0
,
1
,
2 and
3.
With Lemma 4.4.9, we know the bound on the number of stable intersections of an
n
line
arrangement with exactly
n
faces in the corresponding dual Newton subdivision. We now
move on to the more general situation.
We now define what it means for a semiuniform face to be determined by a triangular
face T.
Definition 4.4.12.
A semiuniform face
S
in a dual Newton subdivision is said to be
determined by a triangular face Tif,
1. Sis adjacent to T, i.e., Tand Sshare an edge, or
2. Sis located as the faces S1, S2or S3depicted in the Figure 4.15
Here the shapes and location of these three semiuniform faces has to be exactly the same
as shown in the figure in order for the faces to be determined by the triangular face
T
. We
also note that edge lengths of these faces need not be unit length, and they could be elongated
depending on the lattice length parameters
wi
and
c
of the adjacent faces to
T
. We also note
that a triangular face determines at most six semiuniform faces; at most three adjacent to it
and at most three non adjacent to it.
We note that as a consequence of the definition, the determined faces
S1, S2
or
S3
cannot
be hexagonal faces. Also, as a consequence of the definition, two triangular faces cannot have
common non-adjacent determined faces.
70
C
B
A
1 semiuniform face adjacent
CB
A
2 semiuniform faces adjacent
Figure 4.16: Examples depicting local line arranagements dual to a triangular face with 1 or
2 semiuniform faces adjacent to it.
With the above definitions, we look at the number of semiuniform faces determined
by a triangular face depending on the location of the triangular face in the dual Newton
subdivision.
Theorem 4.4.13.
Let
L
be a tropical line arrangement of
n
lines and let
N
be its dual
Newton subdivision. If Tis a triangular face in N(excluding the corners), then
1. T
determines at least three seminuniform faces if
T
is in the relative interior of the
Newton polygon; i.e., when no edges of Tlie on the boundary of the Newton polygon.
2. T
determines at least one seminuniform face if
T
is at the boundary of the Newton
polygon; i.e, when one of the edges of Tlie on the boundary of the Newton polygon.
Proof.
We continue with the discussion in the Lemma 4.4.9. As we see in Figure 4.13, it is
shown that a triangular face
T
, which is not adjacent to a semiuniform face, determines at
least three semiuniform faces if
T
is in the interior and at least one semiuniform face if
T
is
located at the boundary. However, semiuniform faces might also occur as faces adjacent to
the triangular face. Therefore, when we consider the triangular face
T
in the interior, then
T
can be adjacent to either one, two or at most three semiuniform faces. We know that if
T
is
adjacent to semiuniform faces at all edges, then there are at least three semiuniform faces
determined by
T
in the subdivision, trivially. Now we consider the case, when the triangular
face is adjacent to two semiuniform faces. In this case, the location of the triangular face,
implies existence of at least one non-adjacent semiuniform faces. Similarly, in the case when
the triangular face is adjacent to one semiuniform face, at least two non-adjacent semiuniform
faces are obtained. Both these cases are illustrated through an example in the Figure 4.16.
Hence if a triangular face is in the interior of the Newton polygon, then it implies the existence
of at least three semiuniform faces.
Similarly, if we consider the case when the triangular face
T
is located at the boundary,
then if there are semiuniform faces adjacent to
T
at one or two edges, then there exists at least
one semiuniform face in the subdivision, trivially. If
T
is not adjacent to any semiuniform
71
T
P
Figure 4.17: An example to illustrate the rearrangement when
T
is adjacent to semiuniform
faces.
faces, then we see in Figure 4.14, that
T
determines at least one semiuniform face. Hence,
we can conclude that if a triangular face is at the boundary then it determines at least one
semiuniform face.
We now move on to count the total number of semiuniform face determined by the
triangular faces. Since two or more triangular faces can determine common semiuniform
faces, therefore the total count need not be a direct sum of determined faces of all triangular
faces.
With an abuse of notation we denote
T
to be a triangular face and
n
(
T
) represent the
number of semiuniform faces determined by the triangular face
T
. Hence,
n
(
T1∪... ∪Tm
)
denotes the total number of semiuniform faces determined by the triangular faces
T1, ..., Tm
.
Theorem 4.4.14.
Let
L
be a tropical line arrangement of
n
lines and
N
be its dual Newton
subdivision, with
T1. . . Tm
being the triangular faces in
N
(excluding the corners) and
k
be
the number of stable intersections of first kind. Then,
k≥n(T1∪T2. . . ∪Tm)≥m
Proof.
We proceed with induction on
m
, with the base case being
m
= 1. We see that in
this case, by Theorem 4.4.13, we know that the unique triangle present in the interior of
N
determines at least one semiuniform face, therefore
k≥n(T)≥1
Firstly, we consider a subdivision
N
with
m
triangular faces in the interior. We now show
that for any such subdivision
N
, we can always construct a subdivision
N′
, such that
N′
has
exactly
m−
1 triangular faces, via a rearrangement of
L
to
L′
. We consider a triangular
face
T
in
N
, dual to
l′
in
L
, which we rearrange to obtain a stable intersection in order to
construct the subdivision
N′
. We go through the following cases based on the types of faces
adjacent to Tin N,
72
1.
If
T
has at least one semiuniform face adjacent to it, dual to a stable intersection of
first kind P.
We move the vertex of the line
l′
, dual to
T
, along with coaxial lines towards
P
, such
that the vertex of
l′
is superimposed on the point
P
, illustrated in the Figure 4.17. If during
the rearrangement, any rays of the lines coaxial to
l′
meet the vertex of another line, which
might result in a reduction in the total number of triangular faces, we can consider a local
perturbation of the vertex of such a line, along the half ray, and in this way we can prevent
such a situation. In this way we obtain a subdivision
N′
with exactly
m−
1 triangular faces,
via a local rearrangement. We also notice that the determined semiuniform face dual to the
point Pin N, ceases to exist in N′, since the vertex of l′gets superimposed on P.
2.
If
T
is adjacent only to non-uniform faces, with at least one of the adjacent non-uniform
faces being five or six edged.
If
T
is adjacent to non-uniform faces in
N
, then by the definition of determined faces from
the Figure 4.15, we realize that
T
determines uniquely at least one non-adjacent semiuniform
face dual to a stable intersection of first kind
P
, in
N
. We move the vertex of the line
l′
dual
to
T
(along with any coaxial lines to
l′
if there exist any), illustrated in Figure 4.18, such that
it meets the half ray of another line in
L
and there is an effective decrease in the number of
triangular faces by 1 (in our example we assume P2to be the face which has to be a five or
six edged face). We show the location of lines coaxial to
l′
(if present) by a dotted arrow
along the ray of coaxiality in the rearrangement. If during the rearrangement, any rays of the
lines coaxial to
l′
meet the vertex of another line, which might result in the reduction in the
total number of triangular faces, we can consider a local perturbation of the vertex of such a
line, along the half ray, and in this way we can prevent such a situation. Hence in this way
we construct a subdivision
N′
with exactly
m−
1 triangular faces, via a local rearrangement.
We also observe that the determined semiuniform face dual to
P
in
N
no more remains a
determined semiuniform face in
N′
, because firstly by the definition of determined faces, the
face dual to
P
cannot be a hexagon. Additionally, out of the four edges of the face dual to
P
, only at two edges can it be adjacent to triangular faces, and we realize that in
N′
at both
these edges, the face is adjacent to non-triangular faces. Hence, the face dual to
P
cannot be
a determined face by virtue of being adjacent to a triangular face in
N′
. Also, it can neither
be a non-adjacent determined face, since the face dual to
P
was the unique non-adjacent
determined face with respect to T, and the triangular face Tno longer exists in N′.
3. If Tis adjacent to only four-edged non-uniform faces.
73
T P
P1
P2
P
P1
P2
Figure 4.18: An example to illustrate the rearrangement when
T
is adjacent to five or six
edged non-uniform faces.
Firstly, by the definition of determined faces from the Figure 4.15, we realize that
T
determines uniquely at least one non-adjacent semiuniform face dual to a stable intersection
of first kind
P
in
N
. We notice that in this case, we cannot obtain
N′
by the movement of
just
l′
and its coaxial lines since it results in an increase in the number of triangular faces.
However, we observe that with a local rearrangement of
l′
along with its neighbouring lines
which are coaxial to
l′
, we can obtain
N′
. When
T
is adjacent to three or two such four
edged faces, the local rearrangement is illustrated in Figure 4.19. In the first case we see that
no lines can be present inside the hexagon
Pl1Ql3Rl2
, where we abuse the notation to denote
li
as the vertex of the line
li, i ∈ {
1
,
2
,
3
}
, because that would contradict the adjacency of the
faces dual to vertices of l1, l2,l3and T. Also other lines coaxial to any of the li’s (if present)
are depicted by dotted arrows in the figure.
P
Q
R
T
l1
l2
l3
l2
l1
l3
P
T
l1
l2
l2
l1
Figure 4.19: All cases where
T
is adjacent to two or three four edged non uniform faces along
with the corresponding rearrangement L′.
Essentially, one can think of this rearrangement as moving the line
l3
and
l2
along with
the coaxial lines (if present) on the half rays not shared with
l′
, such that the vertices of
l2
and
l3
lie on the segments
Ql1
and
Pl1
respectively and one of the rays from each
l3
and
l2
meets the vertex of
l′
. In this way we obtain a subdivision
N′
with one less triangular face.
74
Once again if during the rearrangement, any rays of the lines coaxial to
l′
meet the vertex of
another line, which might result in the reduction in the total number of triangular faces, we
can consider a local perturbation of the vertex of such a line, along the half ray, and in this
way we can prevent such a situation. A similar argument works for the remaining case in
Figure 4.19. Also, we realize that the face dual to
P
ceases to exist as we go from
N
to
N′
,
and this is illustrated in the Figure 4.19.
Hence, we see that in all cases for any subdivision
N
we can perform a rearrangement
of
L
to
L′
, to obtain a subdivision
N′
with exactly
m−
1 triangular faces. Also, we notice
that as we change from
N
to
N′
, there always exists a determined semiuniform face, dual
to a stable intersection of first kind (
P
), which either ceases to exist in
N′
(Case (1) and
(3)) or does not remain a determined semiuniform face in
N′
(Case (2)). Hence, there
exists a determined semiuniform face in
N
, which can never contribute to the total count of
determined semiuniform faces in
N′
. We now invoke the induction hypothesis for
N′
with
m−1 triangular faces and we obtain,
k≥n(T1∪T2. . . ∪Tm−1)≥m−1
Since, the face dual to
P
cannot contribute to the
m−
1 faces determined by triangular
faces present in N′. Hence for N, we have
n(T1∪T2. . . ∪Tm)≥n(T1∪T2. . . ∪Tm−1) + 1 ≥m−1 + 1 ≥m
Therefore, we realize that for all cases, given a subdivision Nwith mtriangular faces,
k≥n(T1∪T2. . . ∪Tm)≥m
Hence, the proof.
Theorem 4.4.15.
If
L
is a tropical line arrangement of
n
tropical lines, then it determines
at least n−3stable intersections.
Proof.
We try to look at all possible places where triangular faces occur in a Newton
subdivision. If
v
is the number of triangular faces present in a subdivision, then we can write
vas
v=p+q
where
p
be the number of triangular faces present in the interior of the Newton polygon,
i.e., triangular faces which are adjacent to at least two or more faces in the subdivision
and
q
be the number of triangular faces present at the corners of the Newton polygon, i.e.,
75
triangular faces which are adjacent to exactly one other face in the subdivision. It is easy to
see that
q∈ {
0
,
1
,
2
,
3
}
. Then the lower bound on the number of semiuniform faces, which
are determined by these triangular faces, is
p
(by Theorem 4.4.14). Therefore if
k
is the total
number of faces corresponding to stable intersections of first kind, then
k≥p
Also, the number of stable intersections of second kind
h
=
n−v
(since triangular faces
and faces corresponding to stable intersections of second kind are contributed by vertices of
lines, hence their sum is equal to n).
Therefore, the total number of stable intersections bis given as
b=n−v+k≥n−p−q+p=n−q≥n−3
Hence, b≥n−3.
Theorem 4.4.16.
Let
L
be a tropical line arrangement of
n
tropical lines and let
N
be its
dual Newton subdivision. If
L
determines
n−
3stable intersections, then there are three
triangular faces present at the corners of the Newton polygon and
N
can not have any
triangular faces in the relative interior of the Newton polygon.
Proof.
If
L
determines
n−
3 stable intersections, it is the case when the bound from Theorem
4.4.15 is sharp, which happens when the following equalities hold true
q= 3 (4.4.5)
and
k=n(T1∪T2. . . ∪Tm) = m(4.4.6)
The first equality implies that there must be three triangular faces present at the corners
of the Newton polygon.
We now assume to the contrary, that triangular faces do exist in the relative interior.
We consider one such triangular face
T
in the relative interior of the Newton polygon. We
consider all possible cases for T, where it can share faces with other triangular faces in N,
1. If Tdoes not share any semiuniform faces with any other triangular face in N.
76
T
TαTTαT
Tα
T
Tα
Figure 4.20: All possibilities for
T
, when it shares a semiuniform face with another triangular
face
By theorem 4.4.13 we know that any triangular face in the relative interior determines at
least three semiuniform face. Then
k=n((T1∪T2. . . ∪Tm−1)∪T) = n(T1∪T2. . . ∪Tm−1) + n(T)
≥m−1 + 3 = m+ 2
which gives a contradiction to the equation 4.4.6.
2. If Tshares a semiuniform face with exactly one other triangular face Tαin N.
All possible cases for T, upto symmetry, are listed in Figure 4.20.
We realize that in all such cases, when we consider all possible adjacent faces to
T
, for
all of them
n
(
T
) = 4, and none of the
m−
2 triangular faces apart from
T
and
Tα
, can
determine the four faces determined by
T
, because that would contradict the fact that
T
can
share faces with exactly one other triangular face. Also, by Theorem 4.4.14, for the
m−
2
triangular faces apart from Tand Tα,
n(T1∪T2. . . ∪Tm−2)≥m−2
therefore,
k=n(T1∪T2. . . ∪Tm)≥n(T1∪T2. . . ∪Tm−2) + n(T)≥m−2 + 4 = m+ 2
which again gives a contradiction to the equation 4.4.6.
We also remark that for this case and all subsequent cases, semiuniform faces which are
parallelograms, and are determined by two different triangular faces, can not have edge lengths
greater than one, since they share one edge, per pair of parallel edges, with a triangular face,
whose edges always have unit lattice length. Hence, for all cases, the parallelogram faces
are of unit lattice length. However, for hexagonal faces, edges not adjacent with triangular
faces, can be of lattice length greater than one, although this does not change the count of
determined faces for
T
, i.e.,
n
(
T
), rather it only enlarges the lengths of the edges adjacent
to the hexagonal face. Hence, in our considerations, we would consider all hexagonal faces
having unit lattice length.
77
T
Tα
TβTα
T
Tβ
Tα
T
Tβ
Tα
T
Tβ
Tα
T
Tβ
Tα
TTβ
Tα
T
TβT
Tα
TβTα
T
Tβ
Figure 4.21: Possibilities for
T
, when it shares semiuniform faces with exactly two other
triangular faces
Tβ
TTα
Tβ
T
Tα
Tβ
T
Tα
Tβ
T
Tα
Figure 4.22: The case when
T
shares semiuniform with two other triangular faces, with one
of the determined faces being a hexagon
3.
If
T
shares a semiuniform face with exactly two other triangular faces
Tα
and
Tβ
in
N
.
All possible cases for T, upto symmetry, are listed in Figure 4.21 and Figure 4.22.
We realize that in all cases in Figure 4.21, when we consider all possible adjacent faces for
T
,
n
(
T
) = 5, and for the first case in Figure 4.22,
n
(
T
) = 4, while for all others in Figure 4.22,
n
(
T
) = 5. Also none of the
m−
3 triangular faces apart from
T
,
Tα
and
Tβ
, can determine
the faces determined by
T
, because that would contradict the fact that
T
can share faces
with only two other triangular faces. By Theorem 4.4.14, for the
m−
3 triangular faces apart
from T,Tαand Tβ, we have
n(T1∪T2. . . ∪Tm−3)≥m−3
therefore,
k=n(T1∪T2. . . ∪Tm)≥n(T1∪T2. . . ∪Tm−3) + n(T)≥m−3 + 4 = m+ 1
which again gives a contradiction to the equation 4.4.6.
4.
If
T
shares a semiuniform face with exactly three other triangular faces
Tα
,
Tβ
and
Tγ
in N.
All possible cases for
T
, upto symmetry, are listed in Figure 4.23, Figure 4.24 and Figure
4.25.
78
T
Tα
Tβ
Tγ
T
Tα
Tβ
Tγ
T
Tα
Tβ
Tγ
T
TαTβ
Tγ
T
TαTβ
Tγ
T
TαTβ
Tγ
T
TαTβ
Tγ
T
TαTβ
Tγ
T
Tα
Tβ
Tγ
T
TαTβ
Tγ
Figure 4.23: Possibilities for
T
, when it shares semiuniform faces with three other triangular
faces
T
Tα
Tβ
Tγ
Tα
T
Tβ
Tγ
Tα
T
Tβ
Tγ
Tα
T
TβTγ
Tα
T
Tβ
Tγ
Tα
TTβ
Tγ
Tα
T
Tβ
Tγ
T
Tα
Tβ
Tγ
Tα
TβTTγ
Figure 4.24: Possibilities for
T
, when it shares semiuniform faces with three other triangular
faces, involving a hexagonal face which Tshares with one other triangular face
Tβ
T
Tγ
Tα
Tβ
T
Tγ
Tα
Tβ
T
Tγ
Tα
Tβ
T
TγTα
Figure 4.25: Possibilities for
T
, when it shares semiuniform faces with three other triangular
faces, involving a hexagonal face which Tshares with two other triangular face
79
S1S2
S3S4
TTα
Tβ
TγTφ
Figure 4.26: The case for
T
, when it shares two hexagonal faces with four other triangular
faces
We realize that in all cases in Figure 4.23 and 4.24,
n
(
T
) = 6, and for all the cases in
Figure 4.25,
n
(
T
) = 5. Also, none of the
m−
4 triangular faces apart from
T
,
Tα
,
Tβ
and
Tγ
, can determine the faces determined by
T
, because that would contradict the fact that
T
can share faces with only three other triangular faces. By Theorem 4.4.14, for the
m−
4
triangular faces apart from T,Tα,Tβand Tγ,
n(T1∪T2. . . ∪Tm−4)≥m−4
therefore,
k=n(T1∪T2. . . ∪Tm)≥n(T1∪T2. . . ∪Tm−4) + n(T)≥m−4 + 5 = m+ 1
which again gives a contradiction to the equation 4.4.6.
5.
If
T
shares a semiuniform face with exactly four other triangular faces
Tα
,
Tβ
,
Tγ
and
Tϕin N.
All possible cases for T, upto symmetry, are listed in Figure 4.26 and Figure 4.27.
We realize that for the case in Figure 4.26,
n
(
T
) = 5. However, due to the arrangements
of the faces, some of the faces are fixed and are bound to appear in the subdivision, which
we show as
S1, S2, S3
and
S4
in the Figure 4.26. Amongst these faces,
S4
is a face which
can not be determined by
T, Tα, Tβ, Tϕ
and
Tγ
. Additionally, we observe that it can also
not be determined by any of the remaining
m−
5 triangular faces in
N
since it has no free
edges which could be adjacent to a triangular face. This implies that the dual point to
S4
contributes to the count of stable intersections of first kind
k
, although it is not determined
by any triangular face in N. This gives a contradiction to the following equality
k=n(T1∪T2. . . ∪Tm)
in 4.4.6.
80
T
TφTα
Tβ
Tγ
T
TφTα
Tβ
Tγ
T
Tα
Tβ
Tγ
Tφ
Tα
T
Tβ
Tγ
Tφ
Tα
T
Tβ
Tγ
Tφ
Tα
T
TβTγ
Tφ
Tα
T
Tβ
Tγ
Tφ
Tα
TTβ
Tγ
Tφ
Tα
T
Tβ
TγTφ
T
Tα
Tβ
TγTφ
Tα
TβTTγ
Tφ
Figure 4.27: Possibilities for T, when it shares semiuniform faces with four other triangular
faces
S′
T
TβTγ
Tα
TθTλ
S′
T
TβTγ
Tα
TθTλ
S′
T
TβTγ
Tα
Tφ
TθTλ
Figure 4.28: The cases where Tshares faces with five or six other triangular faces
For the other cases in Figure 4.27,
n
(
T
) = 6. None of the
m−
5 triangular faces apart
from
T
,
Tα
,
Tβ, Tγ
and
Tϕ
, can determine the faces determined by
T
, because that would
contradict the fact that
T
can share faces with only four other triangular faces. By Theorem
4.4.14, for the m−5 triangular faces apart from T,Tα,Tβand Tγ,
n(T1∪T2. . . ∪Tm−5)≥m−5
therefore,
k=n(T1∪T2. . . ∪Tm)≥n(T1∪T2. . . ∪Tm−5) + n(T)≥m−5 + 6 = m+ 1
which again gives a contradiction to the equation 4.4.6.
The remaining three cases illustrated in Figure 4.28 can also be eliminated by a similar
argument, since in all these cases we obtain a semiuniform face
S′
, which cannot be determined
by a triangular face, which gives a contradiction to the equation 4.4.6.
Hence, we completed all cases and we infer that the presence of a triangular face in the
relative interior contradicts the sharpness of the bound. Hence, the proof.
81
Remark 4.4.17.We note that the converse of Theorem 4.4.16 does not hold true, meaning
that if
L
is a tropical near-pencil arrangement, then it does not imply that the number of
stable intersections equals n−3, an example of which is illustrated in Figure 4.2.
Now we have established the required setup to state the tropical versions of the de-Bruijn
Erd˝os Theorem,
Theorem 4.4.18
(Dual Tropical de Bruijn-Erd˝os Theorem)
.
Let
L
be a tropical line arrange-
ment of
n
(
n≥
4) tropical lines in the plane. Let
b
denote the number of stable intersections
determined by L. Then,
1. b≥n−3
2. if b=n−3, then Lis a tropical near-pencil arrangement.
With the duality elaborated in 4.4.6, we can now state the main theorem,
Theorem 4.4.19
(Tropical de Bruijn-Erd˝os Theorem)
.
Let
S
denote a set of points in the
tropical plane. Let v(v≥4) denote the number of points in S, and let bdenote the number
of stable tropical lines determined by these points. Then,
1. b≥v−3
2. if b=v−3, then Sforms a tropical near-pencil.
4.5 Further Perspectives
In [2] a type of a point is defined as follows,
Definition 4.5.1.
A (
n, d
)type is a
n
tuple
A
= (
A1, . . . , An
) of nonempty subsets of
[
d
] :=
{
1
,
2
, . . . , d}
. The
Ai
’s are called coordinates of
A
, 1
, . . . , n
are called the positions and
1, . . . , d are called the directions.
which assigns a tuple to each point in the plane based on its location with respect to
a collection of hyperplanes, which in our case are lines and so
d
= 3 in this case. It might
be interesting to look into the derivation of our results in terms of these types. Figure
4.29, depicts the types corresponding to all the various faces that are present in a linear
Newton subdivision. The
′∗′
in the tuples represents a singleton, while the coordinates which
have multiple elements may not occur consecutively, but they can be made consecutive, by
rearranging the way we count the lines in the arrangement. We can obtain the type for a
face
P
with edge lengths greater than one, by assigning copies of the directions 12
,
13 or 23
82
(∗, . . . , 123,∗,...,∗)
(∗, . . . , 123,23,∗,...,∗)
(∗, . . . , 123,12,∗,...,∗)
(∗,. . . , 123,13,∗,...,∗)
(∗, . . . , 123,23,13,...,∗)
(∗,. . . , 123,12,13,...,∗)
(∗, . . . , 123,23,12,...,∗)
(∗, . . . , 123,23,13,12,...,∗)
(∗, . . . , 12,23,13,...,∗)
(∗,. . . , 12,13,∗,...,∗)
(∗,. . . , 23,12,...,∗)
(∗, . . . , 23,13,...,∗)
Figure 4.29: All possible shapes of faces present in the Newton subdivision of a tropical line
arrangement; with the corresponding type in the tropical oriented matroid on the right
depending on the direction of coaxiality of other lines with the vertex of the line dual to
P
. Such an analysis could help in trying to look for generalizations of our results in higher
dimensions.
Also there has been a lot of interest in the study of tropical lines present in tropical cubic
surfaces owing to the existence of classical results such as the famous 27 lines on a cubic
surface, which has provided detailed analysis about lines embedded in surfaces and is explored
widely in [43] and [32], and one can try to generalize our results to higher dimensions using
techniques from their work.
Results of the presented work in this chapter have been published in - Ayush Kumar Tewari.
“Point-line geometry in the tropical plane”, arXiv preprint. Submitted for further publication
[48].
83
Bibliography
[1]
Eberth Alarcon. An extremal result on convex lattice polygons. Discrete Math., 190(1-
3):227–234, 1998.
[2]
Federico Ardila and Mike Develin. Tropical hyperplane arrangements and oriented
matroids. Mathematische Zeitschrift, 262(4):795–816, 2009.
[3]
Matthew Baker and Serguei Norine. Riemann-Roch and Abel-Jacobi theory on a finite
graph. Adv. Math., 215(2):766–788, 2007.
[4] Alexandru T Balaban. Chemical applications of graph theory. Academic Press, 1976.
[5]
Elizabeth Baldwin and Paul Klemperer. Understanding preferences:“demand types”,
and the existence of equilibrium with indivisibilities. Econometrica, 87(3):867–932, 2019.
[6]
Imre B´ar´any and Zolt´an F¨uredi. On the lattice diameter of a convex polygon. Discrete
Math., 241(1-3):41–50, 2001. Selected papers in honor of Helge Tverberg.
[7]
Lynn M Batten and Lynn Margaret Batten. Combinatorics of finite geometries. Cam-
bridge University Press, 1997.
[8]
Milo Brandt, Michelle Jones, Catherine Lee, and Dhruv Ranganathan. Incidence
geometry and universality in the tropical plane. Journal of Combinatorial Theory, Series
A, 159:26–53, 2018.
[9]
Peter Brass, William OJ Moser, and J´anos Pach. Research problems in discrete geometry.
Springer Science & Business Media, 2006.
[10]
Sarah Brodsky, Michael Joswig, Ralph Morrison, and Bernd Sturmfels. Moduli of tropical
plane curves. Res. Math. Sci., 2(4), 2015.
[11]
Erwan Brugall´e, Ilia Itenberg, Grigory Mikhalkin, and Kristin Shaw. Brief introduction
to tropical geometry, 2015. Preprint arXiv:1502.05950.
84
[12]
Dustin Cartwright, Andrew Dudzik, Madhusudan Manjunath, and Yuan Yao. Embed-
dings and immersions of tropical curves. Collect. Math., 67(1):1–19, 2016.
[13]
Wouter Castryck. Moving out the edges of a lattice polygon. Discrete & Computational
Geometry, 47(3):496–518, Apr 2012.
[14]
Wouter Castryck and Filip Cools. Newton polygons and curve gonalities. J. Algebraic
Combin., 35(3):345–366, 2012.
[15]
Melody Chan, Søren Galatius, and Sam Payne. Tropical curves, graph complexes, and
top weight cohomology of Mg, 2018. Preprint arXiv:1805.10186.
[16]
Desmond Coles, Neelav Dutta, Sifan Jiang, Ralph Morrison, and Andrew Scharf. Tropi-
cally planar graphs, 2019. Preprint arXiv:1908.04320v3.
[17]
Desmond Coles, Neelav Dutta, Sifan Jiang, Ralph Morrison, and Andrew Scharf.
The moduli space of tropical curves with fixed Newton polygon, 2020. Preprint
arXiv:2002.10874.
[18]
David A. Cox, John B. Little, and Henry K. Schenck. Toric varieties, volume 124 of
Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2011.
[19]
Nicolaas G de Bruijn and Paul Erd¨os. On a combinatorial problem. Proceedings of
the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te
Amsterdam, 51(10):1277–1279, 1948.
[20]
Jes´us A. De Loera, J¨org Rambau, and Francisco Santos. Triangulations, volume 25 of
Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, 2010. Structures
for algorithms and applications.
[21]
Mike Develin and Bernd Sturmfels. Tropical convexity. Documenta Mathematica, 9:1–27,
2004.
[22]
Paul Erd¨os, Ronald C Mullin, Vera T S´os, and Douglas R Stinson. Finite linear spaces
and projective planes. Discrete Mathematics, 47:49–62, 1983.
[23]
Ewgenij Gawrilow and Michael Joswig.
polymake
: a framework for analyzing convex
polytopes. In Polytopes—combinatorics and computation (Oberwolfach, 1997), volume 29
of DMV Sem., pages 43–73. Birkh¨auser, Basel, 2000.
[24]
Gary Gordon and Jennifer McNulty. Matroids: a geometric introduction. Cambridge
University Press, 2012.
85
[25]
Mark Gross. Tropical geometry and mirror symmetry. Number 114. American Mathe-
matical Soc., 2011.
[26]
Marvin Anas Hahn, Hannah Markwig, Yue Ren, and Ilya Tyomkin. Tropicalized quartics
and canonical embeddings for tropical curves of genus 3. International Mathematics
Research Notices, 2019. Published online, doi:10.1093/imrn/rnz084.
[27]
Sven Herrmann and Michael Joswig. Splitting polytopes. M¨unster J. Math, 1:109–141,
2008.
[28]
Fritz Herzog and B. M. Stewart. Patterns of visible and nonvisible lattice points. Amer.
Math. Monthly, 78:487–496, 1971.
[29]
June Huh, Botong Wang, et al. Enumeration of points, lines, planes, etc. Acta
Mathematica, 218(2):297–317, 2017.
[30]
Philipp Jell, Hannah Markwig, Felipe Rinc´on, and Benjamin Schr¨oter. Tropical lines in
planes and beyond, 2020. Preprint arXiv:2003.02660.
[31] Michael Joswig. Essentials of Tropical Combinatorics. Online Draft, 2020. Web Draft.
[32]
Michael Joswig, Marta Panizzut, and Bernd Sturmfels. The schl¨afli fan. Discrete &
Computational Geometry, 64(2):355–381, Sep 2020.
[33]
Michael Joswig and Benjamin Schr¨oter. The tropical geometry of shortest paths, 2019.
Preprint arXiv:1904.01082.
[34]
Michael Joswig and Ayush Kumar Tewari. Forbidden patterns in tropical plane curves.
Beitr¨age zur Algebra und Geometrie / Contributions to Algebra and Geometry, Aug 2020.
Postprint/Accepted manuscript, doi:10.1007/s13366-020-00523-6.
[35]
R. Koelman. The number of moduli of families of curves on a toric surface. PhD thesis,
Katholieke Universiteit de Nijmegen, 1991.
[36]
Jeffrey C. Lagarias and G¨unter M. Ziegler. Bounds for lattice polytopes containing a
fixed number of interior points in a sublattice. Canad. J. Math., 43(5):1022–1035, 1991.
[37]
Thomas Lam and Alexander Postnikov. Alcoved polytopes. I. Discrete Comput. Geom.,
38(3):453–478, 2007.
[38]
Diane Maclagan and Bernd Sturmfels. Introduction to tropical geometry, volume 161.
American Mathematical Soc., 2015.
86
[39]
Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins series in the
mathematical sciences. Johns Hopkins University Press, 2001.
[40]
Ralph Morrison. Tropical hyperelliptic curves in the plane. Journal of Algebraic
Combinatorics, 2020. Published online, doi:10.1007/s10801-019-00933-3.
[41]
Ralph Morrison and Ayush Kumar Tewari. Convex lattice polygons with all lattice points
visible. Discrete Mathematics, 344(1):112161, 2021. Postprint/Accepted manuscript,
doi:10.1016/j.disc.2020.112161.
[42]
Andreas Paffenholz. polydb: a database for polytopes and related objects. In Algorithmic
and experimental methods in algebra, geometry, and number theory, pages 533–547.
Springer, Cham, 2017.
[43]
Marta Panizzut and Magnus Dehli Vigeland. Tropical lines on cubic surfaces, 2007.
Preprint arXiv:0708.3847.
[44]
Georg Pick. Geometrisches zur zahlenlehre. Sitzungsberichte des deutschen
naturwissenschaftlich-medicinischen Vereines f¨ur B¨ohmen Lotos in Prag (Neue Folge),
19:311–319, 1899.
[45]
Jurgen Richter-Gebert, Bernd Sturmfels, and Thorsten Theobald. First steps in tropical
geometry. Contemporary Mathematics, 377:289–318, 2005.
[46]
Luis Felipe Tabera. Tropical constructive pappus’ theorem. International Mathematics
Research Notices, 2005(39):2373–2389, 2005.
[47]
Luis Felipe Tabera et al. Tropical plane geometric constructions: a transfer technique in
tropical geometry. Revista Matem´atica Iberoamericana, 27(1):181–232, 2011.
[48]
Ayush Kumar Tewari. Point-line geometry in the tropical plane, 2020. Preprint
arXiv:2006.04425.
87
