Mixing
Triangular grids on a torus
up vote
4
down vote
favorite
Definitions
The torus that we consider is the flat representation given by the quotient $mathbb{C}/mathbb{Z}[i]$, or equivalently as the set
$$
tau = {, (x, y) in mathbb{R}^{2} : 0 leq x, y leq 1 ,}
$$
with the points $(x, y), (x+1, y), (x, y+1)$ identified. The 3D torus is not of interest here.
Consider the torus as a subset of $mathbb{R}^{2}$. Then a line is what we would usually consider a straight line in $mathbb{R}^{2}$, with the identification of edges possibly splitting the line into many segments bounded by the boundary of the torus. For example, the following (left) image is the line of gradient $4/3$ on the torus that passes through $(0,0)$. The right image is twelve tilings of the flat representation to show where each segment on the left comes from.
A partitioning of the torus is an arrangement of lines on the torus. These lines must extend from boundary to boundary, as above.
A triangular grid is a partitioning of the torus by three sets of parallel lines such that every vertex has degree $6$ and every face is a triangle. We may assume the lines to be horizontal, vertical, and of a rational slope if necessary. One example of a triangular grid is given below, followed by five partitions that are allowed on the torus.
It is important that there are exactly three distinct gradients that the lines can have, and that the lines continue from boundary to boundary. For example, the flat representation of the {"Circulant", {9, {1, 2, 3}}} graph (taken from Ed Pegg's answer below) does not fit the requirements of a triangular grid as the lines do not have exactly three different gradients. This is not an allowed partition either as not all lines extend from boundary to boundary.
Useful Identities
Let every intersection of lines induce a vertex, let each line segment between connected vertices be an edge, and let the closed interior of at least two incident edges be a face. Let $V, E, F$ be the number of vertices, edges, and faces that the torus is partitioned into, respectively. It is well known that the Euler characteristic of the torus is zero, so
$$
V - E + F = 0.tag{1}
$$
Let $d(v)$ denote the degree of the vertex $v$ (which must be even, by construction). It is also well known that summing the degrees of all vertices gives
$$
2E = sum d(v).tag{2}
$$
Let $F_{s}$ denote the number of faces with $s > 1$ edges. When there are no loops in the graph, a simple counting argument shows that
$$
2E = sum_{s geq 2} sF_{s}.tag{3}
$$
It is also trivial that $F = sum_{s geq 2} F_{s}$.
Lemma -- Question
We start with a simple lemma:
Lemma. Consider a partitioning of the torus into $V$ vertices, $E$ edges, and $F$ faces that form a triangular grid. Then
$$
E = 3V qquadtext{and}qquad F = 2V.
$$
Proof. Every face has $3$ edges, so $F = F_{3}$. By $(3)$, we have
$$
2E = sum_{sgeq 2}sF_{s} = 3F_{3} = 3F.
$$
By $(1)$, we have $V - E + F = 0$ so that $3F - 3E = -3V$. We have a system of simultaneous equations, namely
$$
3F - 2E = 0 qquadtext{and}qquad 3F - 3E = -3V.
$$
Solving this gives $E = 3V$ and $F = 2V$ as required.$qquadsquare$
My question is the following.
Is the converse of the Lemma true? That is, if some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?
I have not yet been able to find a counter-example. In the proof of the converse, I want to prove that $d(v) = 6$ for all vertices $v$, and that $F_{3} = F$ with $F_{i} = 0$ for all $i neq 3$.
I have noticed that we cannot have any faces with more than $6$ edges so that the $s$ index only runs between $2$ and $6$, but there still seem to be too many variables to do anything (namely, each of the vertex degrees and the five $F_{s}$ for $s in [2, 6]capmathbb{Z}$).
geometry graph-theory algebraic-topology
asked Aug 15 at 20:34
Bill Wallis
2,2292926
add a comment |
up vote
4
down vote
favorite
Definitions
The torus that we consider is the flat representation given by the quotient $mathbb{C}/mathbb{Z}[i]$, or equivalently as the set
$$
tau = {, (x, y) in mathbb{R}^{2} : 0 leq x, y leq 1 ,}
$$
with the points $(x, y), (x+1, y), (x, y+1)$ identified. The 3D torus is not of interest here.
Consider the torus as a subset of $mathbb{R}^{2}$. Then a line is what we would usually consider a straight line in $mathbb{R}^{2}$, with the identification of edges possibly splitting the line into many segments bounded by the boundary of the torus. For example, the following (left) image is the line of gradient $4/3$ on the torus that passes through $(0,0)$. The right image is twelve tilings of the flat representation to show where each segment on the left comes from.
A partitioning of the torus is an arrangement of lines on the torus. These lines must extend from boundary to boundary, as above.
A triangular grid is a partitioning of the torus by three sets of parallel lines such that every vertex has degree $6$ and every face is a triangle. We may assume the lines to be horizontal, vertical, and of a rational slope if necessary. One example of a triangular grid is given below, followed by five partitions that are allowed on the torus.
It is important that there are exactly three distinct gradients that the lines can have, and that the lines continue from boundary to boundary. For example, the flat representation of the {"Circulant", {9, {1, 2, 3}}} graph (taken from Ed Pegg's answer below) does not fit the requirements of a triangular grid as the lines do not have exactly three different gradients. This is not an allowed partition either as not all lines extend from boundary to boundary.
Useful Identities
Let every intersection of lines induce a vertex, let each line segment between connected vertices be an edge, and let the closed interior of at least two incident edges be a face. Let $V, E, F$ be the number of vertices, edges, and faces that the torus is partitioned into, respectively. It is well known that the Euler characteristic of the torus is zero, so
$$
V - E + F = 0.tag{1}
$$
Let $d(v)$ denote the degree of the vertex $v$ (which must be even, by construction). It is also well known that summing the degrees of all vertices gives
$$
2E = sum d(v).tag{2}
$$
Let $F_{s}$ denote the number of faces with $s > 1$ edges. When there are no loops in the graph, a simple counting argument shows that
$$
2E = sum_{s geq 2} sF_{s}.tag{3}
$$
It is also trivial that $F = sum_{s geq 2} F_{s}$.
Lemma -- Question
We start with a simple lemma:
Lemma. Consider a partitioning of the torus into $V$ vertices, $E$ edges, and $F$ faces that form a triangular grid. Then
$$
E = 3V qquadtext{and}qquad F = 2V.
$$
Proof. Every face has $3$ edges, so $F = F_{3}$. By $(3)$, we have
$$
2E = sum_{sgeq 2}sF_{s} = 3F_{3} = 3F.
$$
By $(1)$, we have $V - E + F = 0$ so that $3F - 3E = -3V$. We have a system of simultaneous equations, namely
$$
3F - 2E = 0 qquadtext{and}qquad 3F - 3E = -3V.
$$
Solving this gives $E = 3V$ and $F = 2V$ as required.$qquadsquare$
My question is the following.
Is the converse of the Lemma true? That is, if some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?
I have not yet been able to find a counter-example. In the proof of the converse, I want to prove that $d(v) = 6$ for all vertices $v$, and that $F_{3} = F$ with $F_{i} = 0$ for all $i neq 3$.
I have noticed that we cannot have any faces with more than $6$ edges so that the $s$ index only runs between $2$ and $6$, but there still seem to be too many variables to do anything (namely, each of the vertex degrees and the five $F_{s}$ for $s in [2, 6]capmathbb{Z}$).
geometry graph-theory algebraic-topology
asked Aug 15 at 20:34
Bill Wallis
2,2292926
add a comment |
up vote
4
down vote
favorite
up vote
4
down vote
favorite
Definitions
The torus that we consider is the flat representation given by the quotient $mathbb{C}/mathbb{Z}[i]$, or equivalently as the set
$$
tau = {, (x, y) in mathbb{R}^{2} : 0 leq x, y leq 1 ,}
$$
with the points $(x, y), (x+1, y), (x, y+1)$ identified. The 3D torus is not of interest here.
Consider the torus as a subset of $mathbb{R}^{2}$. Then a line is what we would usually consider a straight line in $mathbb{R}^{2}$, with the identification of edges possibly splitting the line into many segments bounded by the boundary of the torus. For example, the following (left) image is the line of gradient $4/3$ on the torus that passes through $(0,0)$. The right image is twelve tilings of the flat representation to show where each segment on the left comes from.
A partitioning of the torus is an arrangement of lines on the torus. These lines must extend from boundary to boundary, as above.
A triangular grid is a partitioning of the torus by three sets of parallel lines such that every vertex has degree $6$ and every face is a triangle. We may assume the lines to be horizontal, vertical, and of a rational slope if necessary. One example of a triangular grid is given below, followed by five partitions that are allowed on the torus.
It is important that there are exactly three distinct gradients that the lines can have, and that the lines continue from boundary to boundary. For example, the flat representation of the {"Circulant", {9, {1, 2, 3}}} graph (taken from Ed Pegg's answer below) does not fit the requirements of a triangular grid as the lines do not have exactly three different gradients. This is not an allowed partition either as not all lines extend from boundary to boundary.
Useful Identities
Let every intersection of lines induce a vertex, let each line segment between connected vertices be an edge, and let the closed interior of at least two incident edges be a face. Let $V, E, F$ be the number of vertices, edges, and faces that the torus is partitioned into, respectively. It is well known that the Euler characteristic of the torus is zero, so
$$
V - E + F = 0.tag{1}
$$
Let $d(v)$ denote the degree of the vertex $v$ (which must be even, by construction). It is also well known that summing the degrees of all vertices gives
$$
2E = sum d(v).tag{2}
$$
Let $F_{s}$ denote the number of faces with $s > 1$ edges. When there are no loops in the graph, a simple counting argument shows that
$$
2E = sum_{s geq 2} sF_{s}.tag{3}
$$
It is also trivial that $F = sum_{s geq 2} F_{s}$.
Lemma -- Question
We start with a simple lemma:
Lemma. Consider a partitioning of the torus into $V$ vertices, $E$ edges, and $F$ faces that form a triangular grid. Then
$$
E = 3V qquadtext{and}qquad F = 2V.
$$
Proof. Every face has $3$ edges, so $F = F_{3}$. By $(3)$, we have
$$
2E = sum_{sgeq 2}sF_{s} = 3F_{3} = 3F.
$$
By $(1)$, we have $V - E + F = 0$ so that $3F - 3E = -3V$. We have a system of simultaneous equations, namely
$$
3F - 2E = 0 qquadtext{and}qquad 3F - 3E = -3V.
$$
Solving this gives $E = 3V$ and $F = 2V$ as required.$qquadsquare$
My question is the following.
Is the converse of the Lemma true? That is, if some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?
I have not yet been able to find a counter-example. In the proof of the converse, I want to prove that $d(v) = 6$ for all vertices $v$, and that $F_{3} = F$ with $F_{i} = 0$ for all $i neq 3$.
I have noticed that we cannot have any faces with more than $6$ edges so that the $s$ index only runs between $2$ and $6$, but there still seem to be too many variables to do anything (namely, each of the vertex degrees and the five $F_{s}$ for $s in [2, 6]capmathbb{Z}$).
geometry graph-theory algebraic-topology
asked Aug 15 at 20:34
Bill Wallis
2,2292926
Definitions
The torus that we consider is the flat representation given by the quotient $mathbb{C}/mathbb{Z}[i]$, or equivalently as the set
$$
tau = {, (x, y) in mathbb{R}^{2} : 0 leq x, y leq 1 ,}
$$
with the points $(x, y), (x+1, y), (x, y+1)$ identified. The 3D torus is not of interest here.
Consider the torus as a subset of $mathbb{R}^{2}$. Then a line is what we would usually consider a straight line in $mathbb{R}^{2}$, with the identification of edges possibly splitting the line into many segments bounded by the boundary of the torus. For example, the following (left) image is the line of gradient $4/3$ on the torus that passes through $(0,0)$. The right image is twelve tilings of the flat representation to show where each segment on the left comes from.
A partitioning of the torus is an arrangement of lines on the torus. These lines must extend from boundary to boundary, as above.
A triangular grid is a partitioning of the torus by three sets of parallel lines such that every vertex has degree $6$ and every face is a triangle. We may assume the lines to be horizontal, vertical, and of a rational slope if necessary. One example of a triangular grid is given below, followed by five partitions that are allowed on the torus.
It is important that there are exactly three distinct gradients that the lines can have, and that the lines continue from boundary to boundary. For example, the flat representation of the {"Circulant", {9, {1, 2, 3}}} graph (taken from Ed Pegg's answer below) does not fit the requirements of a triangular grid as the lines do not have exactly three different gradients. This is not an allowed partition either as not all lines extend from boundary to boundary.
Useful Identities
Let every intersection of lines induce a vertex, let each line segment between connected vertices be an edge, and let the closed interior of at least two incident edges be a face. Let $V, E, F$ be the number of vertices, edges, and faces that the torus is partitioned into, respectively. It is well known that the Euler characteristic of the torus is zero, so
$$
V - E + F = 0.tag{1}
$$
Let $d(v)$ denote the degree of the vertex $v$ (which must be even, by construction). It is also well known that summing the degrees of all vertices gives
$$
2E = sum d(v).tag{2}
$$
Let $F_{s}$ denote the number of faces with $s > 1$ edges. When there are no loops in the graph, a simple counting argument shows that
$$
2E = sum_{s geq 2} sF_{s}.tag{3}
$$
It is also trivial that $F = sum_{s geq 2} F_{s}$.
Lemma -- Question
We start with a simple lemma:
Lemma. Consider a partitioning of the torus into $V$ vertices, $E$ edges, and $F$ faces that form a triangular grid. Then
$$
E = 3V qquadtext{and}qquad F = 2V.
$$
Proof. Every face has $3$ edges, so $F = F_{3}$. By $(3)$, we have
$$
2E = sum_{sgeq 2}sF_{s} = 3F_{3} = 3F.
$$
By $(1)$, we have $V - E + F = 0$ so that $3F - 3E = -3V$. We have a system of simultaneous equations, namely
$$
3F - 2E = 0 qquadtext{and}qquad 3F - 3E = -3V.
$$
Solving this gives $E = 3V$ and $F = 2V$ as required.$qquadsquare$
My question is the following.
Is the converse of the Lemma true? That is, if some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?
I have not yet been able to find a counter-example. In the proof of the converse, I want to prove that $d(v) = 6$ for all vertices $v$, and that $F_{3} = F$ with $F_{i} = 0$ for all $i neq 3$.
I have noticed that we cannot have any faces with more than $6$ edges so that the $s$ index only runs between $2$ and $6$, but there still seem to be too many variables to do anything (namely, each of the vertex degrees and the five $F_{s}$ for $s in [2, 6]capmathbb{Z}$).
geometry graph-theory algebraic-topology
geometry graph-theory algebraic-topology
asked Aug 15 at 20:34
Bill Wallis
2,2292926
asked Aug 15 at 20:34
Bill Wallis
2,2292926
edited Aug 17 at 17:37
asked Aug 15 at 20:34
Bill Wallis
2,2292926
asked Aug 15 at 20:34
Bill Wallis
2,2292926
asked Aug 15 at 20:34
Bill Wallis
2,2292926
2,2292926
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
NEW: Up to 20 vertices, all sextic toroidal graphs can be represented as triangular grids.
NEW: Consider the following toroidal graph:
In a triangular grid embedding each of the 6 spokes connects to the opposing spoke. if you follow a path with this graph you end up with the path crossing itself. Therefore it is not a triangular grid.
My torus from Is there a simpler single polygon toroid? has 12 vertices, 24 faces, 36 edges, meeting the criteria. But the vertices have valence 5 and 7, which is impossible for a triangular grid. The converse of the lemma is false.
The ring of 8 octahedra, with 24 vertices, 48 faces, 72 edges is another counterexample. Some of the valences are 8, impossible for a triangular grid.
Make the question a bit friendlier.
Is there a toroidal sextic graph which is not a triangular grid?
$K_7$ is a toroidal grid. The grid has a signature of $(1,1,1)$. This is the number of lines in each parallel class. Also the $7_{1,2,3}$ circulant graph.
The 16-cell graph is a triangular grid graph. The grid has a signature of $(1,1,2)$. Also the $8_{1,2,3}$ circulant graph.
The {"CompleteTripartite", {3, 3, 3}} graph is a triangular grid graph. The grid has a signature of $(3,3,3)$. Also the $9_{1,2,4}$ circulant graph.
The {"Circulant", {9, {1, 2, 3}}} graph is a triangular grid graph. The grid has a signature of $(1,1,3)$.
The other two 9-vertex sextic graphs may not be toroidal.
The Paley 13 graph is toroidal on a triangular grid. Notice that edge differences are all in $(1, 3, 4, 9, 10, 12)$, the values that are squares in $GF(13)$. The grid has a signature of $(1,1,1)$. Also the $13_{1,3,4}$ circulant graph.
All of the grids so far have been circulant graphs, which suggests a construction method for these triangular grids. Here are the distinct sextic circulant graphs up to 17 vertices.
Above, for 7,8,9 vertices we have a sequence that starts 1,1,2. That seems to be sequence A129033. $(1, 1, 2, 1, 1, 4, 2, 2, 4, 5, 2, ...)$. That matches surftri counts, also mentioned at Generating Triangulations.
Not all triangular grid graphs are circulant, with the Shrikhande graph being one example.
Sextic triangular toroidal graphs don't have a combinatorial explosion. It seems worthwhile to completely classify the circulant and Shrikhande-like cases beyond 17 vertices for A129033.
answered Aug 15 at 21:03
Ed Pegg
9,68432590
add a comment |
up vote
1
down vote
I suppose your faces are polygons, with at least three edges. Each face has
at least three edges, and each edge must be in exactly two faces. Thus
$2Ege 3F$ with equality iff each edge is a triangle. So your conditions
force every face to be a triangle.
Now the question is what is a "triangular grid"? The minimum triangulation
of a torus has $14$ faces and looks, at least to me, nothing like a grid.
And in the grid you've drawn, you can take a pair of adjacent triangles,
merge them into a quadrilateral, and then split the quadrilateral into
triangles in the "other way". Doing this repeatedly will disrupt the
apparent grid structure.
answered Aug 15 at 20:45
Lord Shark the Unknown
97k958128
For my purposes, a triangular grid is the grid obtained by arranging three sets of parallel lines so that each vertex has a degree of $6$ (much like isometric graph paper and any affine transform of it). By taking two sets to be horizonal and vertical, we can enclose an area by a square and identify edges to get the torus and grid I described above. I imagine that this triangulation is different to any triangulation in the literature.
– Bill Wallis
Aug 15 at 20:54
The important thing is that there are exactly three direction/gradients that any line can have. This excludes the disruption you propose (I hope).
– Bill Wallis
Aug 15 at 20:58
This answer turns out to be wrong, $K_7$ on a torus does correspond to a triangular grid.
– Ed Pegg
Aug 15 at 21:04
@BillWallis: Your last comment does not exclude this answer. Your question asks: "If some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?" and the construction in this question shows that the answer is "no". Your question did not contain any requirements about "lines". In fact, in the context of a partitioning that satisfies the hypotheses of your question, I'm not even sure what one might mean by "lines".
– Lee Mosher
Aug 16 at 4:42
@LeeMosher Actually, the way that I defined triangular grids in the second paragraph of the post intended to show the requirement about lines, and confirmed that a line is straight if it is straight on the flat representation. The 3D case is not important for my purposes. I agree that there is some ambiguity about what a line is and how exactly the triangular grids may be constructed, so I shall edit the question.
– Bill Wallis
Aug 16 at 9:05
|
show 2 more comments
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
NEW: Up to 20 vertices, all sextic toroidal graphs can be represented as triangular grids.
NEW: Consider the following toroidal graph:
In a triangular grid embedding each of the 6 spokes connects to the opposing spoke. if you follow a path with this graph you end up with the path crossing itself. Therefore it is not a triangular grid.
My torus from Is there a simpler single polygon toroid? has 12 vertices, 24 faces, 36 edges, meeting the criteria. But the vertices have valence 5 and 7, which is impossible for a triangular grid. The converse of the lemma is false.
The ring of 8 octahedra, with 24 vertices, 48 faces, 72 edges is another counterexample. Some of the valences are 8, impossible for a triangular grid.
Make the question a bit friendlier.
Is there a toroidal sextic graph which is not a triangular grid?
$K_7$ is a toroidal grid. The grid has a signature of $(1,1,1)$. This is the number of lines in each parallel class. Also the $7_{1,2,3}$ circulant graph.
The 16-cell graph is a triangular grid graph. The grid has a signature of $(1,1,2)$. Also the $8_{1,2,3}$ circulant graph.
The {"CompleteTripartite", {3, 3, 3}} graph is a triangular grid graph. The grid has a signature of $(3,3,3)$. Also the $9_{1,2,4}$ circulant graph.
The {"Circulant", {9, {1, 2, 3}}} graph is a triangular grid graph. The grid has a signature of $(1,1,3)$.
The other two 9-vertex sextic graphs may not be toroidal.
The Paley 13 graph is toroidal on a triangular grid. Notice that edge differences are all in $(1, 3, 4, 9, 10, 12)$, the values that are squares in $GF(13)$. The grid has a signature of $(1,1,1)$. Also the $13_{1,3,4}$ circulant graph.
All of the grids so far have been circulant graphs, which suggests a construction method for these triangular grids. Here are the distinct sextic circulant graphs up to 17 vertices.
Above, for 7,8,9 vertices we have a sequence that starts 1,1,2. That seems to be sequence A129033. $(1, 1, 2, 1, 1, 4, 2, 2, 4, 5, 2, ...)$. That matches surftri counts, also mentioned at Generating Triangulations.
Not all triangular grid graphs are circulant, with the Shrikhande graph being one example.
Sextic triangular toroidal graphs don't have a combinatorial explosion. It seems worthwhile to completely classify the circulant and Shrikhande-like cases beyond 17 vertices for A129033.
answered Aug 15 at 21:03
Ed Pegg
9,68432590
add a comment |
up vote
2
down vote
accepted
NEW: Up to 20 vertices, all sextic toroidal graphs can be represented as triangular grids.
NEW: Consider the following toroidal graph:
In a triangular grid embedding each of the 6 spokes connects to the opposing spoke. if you follow a path with this graph you end up with the path crossing itself. Therefore it is not a triangular grid.
My torus from Is there a simpler single polygon toroid? has 12 vertices, 24 faces, 36 edges, meeting the criteria. But the vertices have valence 5 and 7, which is impossible for a triangular grid. The converse of the lemma is false.
The ring of 8 octahedra, with 24 vertices, 48 faces, 72 edges is another counterexample. Some of the valences are 8, impossible for a triangular grid.
Make the question a bit friendlier.
Is there a toroidal sextic graph which is not a triangular grid?
$K_7$ is a toroidal grid. The grid has a signature of $(1,1,1)$. This is the number of lines in each parallel class. Also the $7_{1,2,3}$ circulant graph.
The 16-cell graph is a triangular grid graph. The grid has a signature of $(1,1,2)$. Also the $8_{1,2,3}$ circulant graph.
The {"CompleteTripartite", {3, 3, 3}} graph is a triangular grid graph. The grid has a signature of $(3,3,3)$. Also the $9_{1,2,4}$ circulant graph.
The {"Circulant", {9, {1, 2, 3}}} graph is a triangular grid graph. The grid has a signature of $(1,1,3)$.
The other two 9-vertex sextic graphs may not be toroidal.
The Paley 13 graph is toroidal on a triangular grid. Notice that edge differences are all in $(1, 3, 4, 9, 10, 12)$, the values that are squares in $GF(13)$. The grid has a signature of $(1,1,1)$. Also the $13_{1,3,4}$ circulant graph.
All of the grids so far have been circulant graphs, which suggests a construction method for these triangular grids. Here are the distinct sextic circulant graphs up to 17 vertices.
Above, for 7,8,9 vertices we have a sequence that starts 1,1,2. That seems to be sequence A129033. $(1, 1, 2, 1, 1, 4, 2, 2, 4, 5, 2, ...)$. That matches surftri counts, also mentioned at Generating Triangulations.
Not all triangular grid graphs are circulant, with the Shrikhande graph being one example.
Sextic triangular toroidal graphs don't have a combinatorial explosion. It seems worthwhile to completely classify the circulant and Shrikhande-like cases beyond 17 vertices for A129033.
answered Aug 15 at 21:03
Ed Pegg
9,68432590
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
NEW: Up to 20 vertices, all sextic toroidal graphs can be represented as triangular grids.
NEW: Consider the following toroidal graph:
In a triangular grid embedding each of the 6 spokes connects to the opposing spoke. if you follow a path with this graph you end up with the path crossing itself. Therefore it is not a triangular grid.
My torus from Is there a simpler single polygon toroid? has 12 vertices, 24 faces, 36 edges, meeting the criteria. But the vertices have valence 5 and 7, which is impossible for a triangular grid. The converse of the lemma is false.
The ring of 8 octahedra, with 24 vertices, 48 faces, 72 edges is another counterexample. Some of the valences are 8, impossible for a triangular grid.
Make the question a bit friendlier.
Is there a toroidal sextic graph which is not a triangular grid?
$K_7$ is a toroidal grid. The grid has a signature of $(1,1,1)$. This is the number of lines in each parallel class. Also the $7_{1,2,3}$ circulant graph.
The 16-cell graph is a triangular grid graph. The grid has a signature of $(1,1,2)$. Also the $8_{1,2,3}$ circulant graph.
The {"CompleteTripartite", {3, 3, 3}} graph is a triangular grid graph. The grid has a signature of $(3,3,3)$. Also the $9_{1,2,4}$ circulant graph.
The {"Circulant", {9, {1, 2, 3}}} graph is a triangular grid graph. The grid has a signature of $(1,1,3)$.
The other two 9-vertex sextic graphs may not be toroidal.
The Paley 13 graph is toroidal on a triangular grid. Notice that edge differences are all in $(1, 3, 4, 9, 10, 12)$, the values that are squares in $GF(13)$. The grid has a signature of $(1,1,1)$. Also the $13_{1,3,4}$ circulant graph.
All of the grids so far have been circulant graphs, which suggests a construction method for these triangular grids. Here are the distinct sextic circulant graphs up to 17 vertices.
Above, for 7,8,9 vertices we have a sequence that starts 1,1,2. That seems to be sequence A129033. $(1, 1, 2, 1, 1, 4, 2, 2, 4, 5, 2, ...)$. That matches surftri counts, also mentioned at Generating Triangulations.
Not all triangular grid graphs are circulant, with the Shrikhande graph being one example.
Sextic triangular toroidal graphs don't have a combinatorial explosion. It seems worthwhile to completely classify the circulant and Shrikhande-like cases beyond 17 vertices for A129033.
answered Aug 15 at 21:03
Ed Pegg
9,68432590
NEW: Up to 20 vertices, all sextic toroidal graphs can be represented as triangular grids.
NEW: Consider the following toroidal graph:
In a triangular grid embedding each of the 6 spokes connects to the opposing spoke. if you follow a path with this graph you end up with the path crossing itself. Therefore it is not a triangular grid.
My torus from Is there a simpler single polygon toroid? has 12 vertices, 24 faces, 36 edges, meeting the criteria. But the vertices have valence 5 and 7, which is impossible for a triangular grid. The converse of the lemma is false.
The ring of 8 octahedra, with 24 vertices, 48 faces, 72 edges is another counterexample. Some of the valences are 8, impossible for a triangular grid.
Make the question a bit friendlier.
Is there a toroidal sextic graph which is not a triangular grid?
$K_7$ is a toroidal grid. The grid has a signature of $(1,1,1)$. This is the number of lines in each parallel class. Also the $7_{1,2,3}$ circulant graph.
The 16-cell graph is a triangular grid graph. The grid has a signature of $(1,1,2)$. Also the $8_{1,2,3}$ circulant graph.
The {"CompleteTripartite", {3, 3, 3}} graph is a triangular grid graph. The grid has a signature of $(3,3,3)$. Also the $9_{1,2,4}$ circulant graph.
The {"Circulant", {9, {1, 2, 3}}} graph is a triangular grid graph. The grid has a signature of $(1,1,3)$.
The other two 9-vertex sextic graphs may not be toroidal.
The Paley 13 graph is toroidal on a triangular grid. Notice that edge differences are all in $(1, 3, 4, 9, 10, 12)$, the values that are squares in $GF(13)$. The grid has a signature of $(1,1,1)$. Also the $13_{1,3,4}$ circulant graph.
All of the grids so far have been circulant graphs, which suggests a construction method for these triangular grids. Here are the distinct sextic circulant graphs up to 17 vertices.
Above, for 7,8,9 vertices we have a sequence that starts 1,1,2. That seems to be sequence A129033. $(1, 1, 2, 1, 1, 4, 2, 2, 4, 5, 2, ...)$. That matches surftri counts, also mentioned at Generating Triangulations.
Not all triangular grid graphs are circulant, with the Shrikhande graph being one example.
Sextic triangular toroidal graphs don't have a combinatorial explosion. It seems worthwhile to completely classify the circulant and Shrikhande-like cases beyond 17 vertices for A129033.
answered Aug 15 at 21:03
Ed Pegg
9,68432590
edited yesterday
answered Aug 15 at 21:03
Ed Pegg
9,68432590
answered Aug 15 at 21:03
Ed Pegg
9,68432590
answered Aug 15 at 21:03
Ed Pegg
9,68432590
9,68432590
add a comment |
add a comment |
up vote
1
down vote
I suppose your faces are polygons, with at least three edges. Each face has
at least three edges, and each edge must be in exactly two faces. Thus
$2Ege 3F$ with equality iff each edge is a triangle. So your conditions
force every face to be a triangle.
Now the question is what is a "triangular grid"? The minimum triangulation
of a torus has $14$ faces and looks, at least to me, nothing like a grid.
And in the grid you've drawn, you can take a pair of adjacent triangles,
merge them into a quadrilateral, and then split the quadrilateral into
triangles in the "other way". Doing this repeatedly will disrupt the
apparent grid structure.
answered Aug 15 at 20:45
Lord Shark the Unknown
97k958128
For my purposes, a triangular grid is the grid obtained by arranging three sets of parallel lines so that each vertex has a degree of $6$ (much like isometric graph paper and any affine transform of it). By taking two sets to be horizonal and vertical, we can enclose an area by a square and identify edges to get the torus and grid I described above. I imagine that this triangulation is different to any triangulation in the literature.
– Bill Wallis
Aug 15 at 20:54
The important thing is that there are exactly three direction/gradients that any line can have. This excludes the disruption you propose (I hope).
– Bill Wallis
Aug 15 at 20:58
This answer turns out to be wrong, $K_7$ on a torus does correspond to a triangular grid.
– Ed Pegg
Aug 15 at 21:04
@BillWallis: Your last comment does not exclude this answer. Your question asks: "If some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?" and the construction in this question shows that the answer is "no". Your question did not contain any requirements about "lines". In fact, in the context of a partitioning that satisfies the hypotheses of your question, I'm not even sure what one might mean by "lines".
– Lee Mosher
Aug 16 at 4:42
@LeeMosher Actually, the way that I defined triangular grids in the second paragraph of the post intended to show the requirement about lines, and confirmed that a line is straight if it is straight on the flat representation. The 3D case is not important for my purposes. I agree that there is some ambiguity about what a line is and how exactly the triangular grids may be constructed, so I shall edit the question.
– Bill Wallis
Aug 16 at 9:05
|
show 2 more comments
up vote
1
down vote
I suppose your faces are polygons, with at least three edges. Each face has
at least three edges, and each edge must be in exactly two faces. Thus
$2Ege 3F$ with equality iff each edge is a triangle. So your conditions
force every face to be a triangle.
Now the question is what is a "triangular grid"? The minimum triangulation
of a torus has $14$ faces and looks, at least to me, nothing like a grid.
And in the grid you've drawn, you can take a pair of adjacent triangles,
merge them into a quadrilateral, and then split the quadrilateral into
triangles in the "other way". Doing this repeatedly will disrupt the
apparent grid structure.
answered Aug 15 at 20:45
Lord Shark the Unknown
97k958128
For my purposes, a triangular grid is the grid obtained by arranging three sets of parallel lines so that each vertex has a degree of $6$ (much like isometric graph paper and any affine transform of it). By taking two sets to be horizonal and vertical, we can enclose an area by a square and identify edges to get the torus and grid I described above. I imagine that this triangulation is different to any triangulation in the literature.
– Bill Wallis
Aug 15 at 20:54
The important thing is that there are exactly three direction/gradients that any line can have. This excludes the disruption you propose (I hope).
– Bill Wallis
Aug 15 at 20:58
This answer turns out to be wrong, $K_7$ on a torus does correspond to a triangular grid.
– Ed Pegg
Aug 15 at 21:04
@BillWallis: Your last comment does not exclude this answer. Your question asks: "If some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?" and the construction in this question shows that the answer is "no". Your question did not contain any requirements about "lines". In fact, in the context of a partitioning that satisfies the hypotheses of your question, I'm not even sure what one might mean by "lines".
– Lee Mosher
Aug 16 at 4:42
@LeeMosher Actually, the way that I defined triangular grids in the second paragraph of the post intended to show the requirement about lines, and confirmed that a line is straight if it is straight on the flat representation. The 3D case is not important for my purposes. I agree that there is some ambiguity about what a line is and how exactly the triangular grids may be constructed, so I shall edit the question.
– Bill Wallis
Aug 16 at 9:05
|
show 2 more comments
up vote
1
down vote
up vote
1
down vote
I suppose your faces are polygons, with at least three edges. Each face has
at least three edges, and each edge must be in exactly two faces. Thus
$2Ege 3F$ with equality iff each edge is a triangle. So your conditions
force every face to be a triangle.
Now the question is what is a "triangular grid"? The minimum triangulation
of a torus has $14$ faces and looks, at least to me, nothing like a grid.
And in the grid you've drawn, you can take a pair of adjacent triangles,
merge them into a quadrilateral, and then split the quadrilateral into
triangles in the "other way". Doing this repeatedly will disrupt the
apparent grid structure.
answered Aug 15 at 20:45
Lord Shark the Unknown
97k958128
I suppose your faces are polygons, with at least three edges. Each face has
at least three edges, and each edge must be in exactly two faces. Thus
$2Ege 3F$ with equality iff each edge is a triangle. So your conditions
force every face to be a triangle.
Now the question is what is a "triangular grid"? The minimum triangulation
of a torus has $14$ faces and looks, at least to me, nothing like a grid.
And in the grid you've drawn, you can take a pair of adjacent triangles,
merge them into a quadrilateral, and then split the quadrilateral into
triangles in the "other way". Doing this repeatedly will disrupt the
apparent grid structure.
answered Aug 15 at 20:45
Lord Shark the Unknown
97k958128
answered Aug 15 at 20:45
Lord Shark the Unknown
97k958128
answered Aug 15 at 20:45
Lord Shark the Unknown
97k958128
answered Aug 15 at 20:45
Lord Shark the Unknown
97k958128
97k958128
For my purposes, a triangular grid is the grid obtained by arranging three sets of parallel lines so that each vertex has a degree of $6$ (much like isometric graph paper and any affine transform of it). By taking two sets to be horizonal and vertical, we can enclose an area by a square and identify edges to get the torus and grid I described above. I imagine that this triangulation is different to any triangulation in the literature.
– Bill Wallis
Aug 15 at 20:54
The important thing is that there are exactly three direction/gradients that any line can have. This excludes the disruption you propose (I hope).
– Bill Wallis
Aug 15 at 20:58
This answer turns out to be wrong, $K_7$ on a torus does correspond to a triangular grid.
– Ed Pegg
Aug 15 at 21:04
@BillWallis: Your last comment does not exclude this answer. Your question asks: "If some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?" and the construction in this question shows that the answer is "no". Your question did not contain any requirements about "lines". In fact, in the context of a partitioning that satisfies the hypotheses of your question, I'm not even sure what one might mean by "lines".
– Lee Mosher
Aug 16 at 4:42
@LeeMosher Actually, the way that I defined triangular grids in the second paragraph of the post intended to show the requirement about lines, and confirmed that a line is straight if it is straight on the flat representation. The 3D case is not important for my purposes. I agree that there is some ambiguity about what a line is and how exactly the triangular grids may be constructed, so I shall edit the question.
– Bill Wallis
Aug 16 at 9:05
|
show 2 more comments
For my purposes, a triangular grid is the grid obtained by arranging three sets of parallel lines so that each vertex has a degree of $6$ (much like isometric graph paper and any affine transform of it). By taking two sets to be horizonal and vertical, we can enclose an area by a square and identify edges to get the torus and grid I described above. I imagine that this triangulation is different to any triangulation in the literature.
– Bill Wallis
Aug 15 at 20:54
The important thing is that there are exactly three direction/gradients that any line can have. This excludes the disruption you propose (I hope).
– Bill Wallis
Aug 15 at 20:58
This answer turns out to be wrong, $K_7$ on a torus does correspond to a triangular grid.
– Ed Pegg
Aug 15 at 21:04
@BillWallis: Your last comment does not exclude this answer. Your question asks: "If some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?" and the construction in this question shows that the answer is "no". Your question did not contain any requirements about "lines". In fact, in the context of a partitioning that satisfies the hypotheses of your question, I'm not even sure what one might mean by "lines".
– Lee Mosher
Aug 16 at 4:42
@LeeMosher Actually, the way that I defined triangular grids in the second paragraph of the post intended to show the requirement about lines, and confirmed that a line is straight if it is straight on the flat representation. The 3D case is not important for my purposes. I agree that there is some ambiguity about what a line is and how exactly the triangular grids may be constructed, so I shall edit the question.
– Bill Wallis
Aug 16 at 9:05
For my purposes, a triangular grid is the grid obtained by arranging three sets of parallel lines so that each vertex has a degree of $6$ (much like isometric graph paper and any affine transform of it). By taking two sets to be horizonal and vertical, we can enclose an area by a square and identify edges to get the torus and grid I described above. I imagine that this triangulation is different to any triangulation in the literature.
– Bill Wallis
Aug 15 at 20:54
For my purposes, a triangular grid is the grid obtained by arranging three sets of parallel lines so that each vertex has a degree of $6$ (much like isometric graph paper and any affine transform of it). By taking two sets to be horizonal and vertical, we can enclose an area by a square and identify edges to get the torus and grid I described above. I imagine that this triangulation is different to any triangulation in the literature.
– Bill Wallis
Aug 15 at 20:54
The important thing is that there are exactly three direction/gradients that any line can have. This excludes the disruption you propose (I hope).
– Bill Wallis
Aug 15 at 20:58
The important thing is that there are exactly three direction/gradients that any line can have. This excludes the disruption you propose (I hope).
– Bill Wallis
Aug 15 at 20:58
This answer turns out to be wrong, $K_7$ on a torus does correspond to a triangular grid.
– Ed Pegg
Aug 15 at 21:04
This answer turns out to be wrong, $K_7$ on a torus does correspond to a triangular grid.
– Ed Pegg
Aug 15 at 21:04
@BillWallis: Your last comment does not exclude this answer. Your question asks: "If some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?" and the construction in this question shows that the answer is "no". Your question did not contain any requirements about "lines". In fact, in the context of a partitioning that satisfies the hypotheses of your question, I'm not even sure what one might mean by "lines".
– Lee Mosher
Aug 16 at 4:42
@BillWallis: Your last comment does not exclude this answer. Your question asks: "If some partitioning of the torus has $V$ vertices, $E$ edges, and $F$ faces such that $E = 3V$ and $F = 2V$, then is it true that the partition is necessarily a triangular grid?" and the construction in this question shows that the answer is "no". Your question did not contain any requirements about "lines". In fact, in the context of a partitioning that satisfies the hypotheses of your question, I'm not even sure what one might mean by "lines".
– Lee Mosher
Aug 16 at 4:42
@LeeMosher Actually, the way that I defined triangular grids in the second paragraph of the post intended to show the requirement about lines, and confirmed that a line is straight if it is straight on the flat representation. The 3D case is not important for my purposes. I agree that there is some ambiguity about what a line is and how exactly the triangular grids may be constructed, so I shall edit the question.
– Bill Wallis
Aug 16 at 9:05
@LeeMosher Actually, the way that I defined triangular grids in the second paragraph of the post intended to show the requirement about lines, and confirmed that a line is straight if it is straight on the flat representation. The 3D case is not important for my purposes. I agree that there is some ambiguity about what a line is and how exactly the triangular grids may be constructed, so I shall edit the question.
– Bill Wallis
Aug 16 at 9:05
|
show 2 more comments
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2884077%2ftriangular-grids-on-a-torus%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
