If a graph G, “looks” like a a template F at each node, within a specified neighborhood, then we can say G is compatible with the template F. This project explores which graphs are compatible with a set of given templates. This kind of problem is referred to as a tiling problem, and is studied using the tools of graph theory. Tilings of this form are of important relation to combinatorics, graph theory and computer science, and this piece was motivated by the survey of this topic in NKS, “Space and Time.” The rich connections from graph tiling to other areas of math and computer also inspired various lemmas that are applicable to graph tiling procedures also inspired the author to execute computational experiments offering a glimpse into statistical and algorithmic connections into template tiling. One distinct motivation for this project was the Wolfram Language framework for Graph Theory, which quickly allowed the author to debug and test new graph-theoretic ideas with minimal overhead.
Theory of Graph Tilings and Constrained Network Systems
Theory of Graph Tilings and Constrained Network Systems
A graph is defined to be a set , where is a set of vertices, and is a set of pairs of vertices in , which represent edges. is denoted the edge-set, and is denoted the vertex-set. A template containing half-edges has in its edge-set an unspecified pairing between one or more other vertices.
The following definition outlines the key principles of graph tilings for a template,, which can contain both edges and half-edges.
Definition 1.1: A graph tiling is consistent with template graph having radius , and centered at node if every vertex in has in its neighborhood the template .
We can extend this definition to find graphs consistent with one or more templates in the following way:
Definition 1.2: A graph tiling is consistent with a set of templates if at each vertex in , at least one template in , centered at and with radius is consistent with the neighborhood of .
Some illustrative examples are the following:
G
G(V,E)
V
E
V
E
V
T
The following definition outlines the key principles of graph tilings for a template,
T
Definition 1.1: A graph tiling
G
T
t
r
t
c
G
t
r
T
We can extend this definition to find graphs
G
Definition 1.2: A graph tiling
G
W
g
G
A
W
a
c
a
r
a
r
g
Some illustrative examples are the following:
◼
According to definition 1, is a graph consistent with the template
◼
The triangle graph template, for example with radius 2, and center node 1, and no half edges, is consistent with itself
We must also recall a simple definition that will improve clarity throughout this article:
Definition 1.3: A k-valent template is a template centered at a single node, often called “1”, and has k half-edges connected to this node.
Definition 1.3: A k-valent template is a template centered at a single node, often called “1”, and has k half-edges connected to this node.
Tilings with a single k-valent template.
Tilings with a single k-valent template.
We wanted to have a way to generate all of the graphs compatible with a k-valence template. One was to do this was with a deconstructive approach. We could generate all of the graphs of order < 6 (made easy computations on my computer system) and select the graphs which were consistent with our k-valence template. We did this by finding all connected subgraphs of . Recall the number of connected labeled subgraphs on vertices is given, for instance, by the coefficient in the generating function (Wilf). I then sorted these graphs up to isomorphism. This set is denoted graphs-two.
K
5
n
d
n
nk
n |
2 |
2
∑
k
d
k
n-k |
2 |
2
graphstwo=Select[DeleteDuplicates[Graph[VertexList@#,#]&/@Subsets[EdgeList[GraphUnion[CompleteGraph[5],Graph[{11,22,33,44,55}]]]],IsomorphicGraphQ],ConnectedGraphQ];
For any graph in our list “graphs-two,” we have to check the local neighborhood around each vertex in the graph, and determine whether all such neighborhoods with radius 1/2 are consistent with our template. To check for edges with radius 1/2, we subdivided each edge in the graph we were checking, and then check the resulting 1-neighborhood about each vertex.The edge subdivision scheme is as follows. For example, became . This procedure is named doubleEdge To understand why this works, given the graph { }, consider the differences in the three edge-splitting algorithms (double edge) represented by to , (triple edge) to , and doubleEdge into . Note that doubleEdge correctly identifies half-edge structure in loops
a
i
a
j
a
i
a
i,j,1
a
i,j,12
a
i,j,2
a
j
(2)
a
i
a
j
a
i
a
i,j
a
j
a
i
a
j
a
i
a
i,j,1
a
i,j,2
a
j
(2)
a
i
a
j
a
i
a
i,j,1
a
i,j,12
a
i,j,2
a
j
(2)
NeighborhoodGraph[#,1,1]&/@doubleEdge
,tripleEdge
,doubleEdgedoubleEdge
,
,
After extracting the 1/2 neighborhood around each vertex, we then checked that each neighborhood only contains elements such as our template element, which is a k-valent tile. This function is named generateValenceNetworkGraph.
To generate valid tilings with a template (order < 6), we can call generateValenceNetworkGraph
To generate valid tilings with a template (order < 6), we can call generateValenceNetworkGraph
generateValenceNetworkGraphs
,
,
,...
Tilings for Multiple Templates
Tilings for Multiple Templates
Now we modify the generate valence network function to check more than one neighborhood about each node. This will allow us to find graphs compatible with not only k-valent templates, but also more complex templates. As before, we complete edge-division using the above doubleEdge scheme. Now we must give the new function, doubleShiftedMultiTemplateTiling the center node of a template , its radius , and center node This function requires the following observation/conjecture:Conjecture 4.1: Assume we have a template T with radius and reference node . If all -neighborhoods around a graph node are isomorphic to the corresponding k-subtemplates, for then the -neighbourhood around the node is consistent with the template.The algorithm checks every vertex in a sample graph for validity of the above observation with a set of given templates. For template which contain nodes and edges, we must apply edge-subdivision to these tilings, and remove one edge from every edge where half-edges are needed. We feed generateTemplateNetworkGraphs this encoded version of a graph. Below are the tilings consistent with the templates {, the half edge connected to the loop, and the node with two half edges - encoded in the appropriate scheme
(2)
T
t
r
t
c
t
r
t
c
k
k{1,2,...,}
t
r
t
r
G
,
p=
,1,2,{
,1,1};generateTemplateNetworkGraphs[p]
,
,
,
,
,
,
,
,...
Graphs which are consistent with tile-sets seem to exhibit a periodicity correlated with graph size. This pattern spurred the following observations:
◼
The above structure of a closing loop, and a center strand is reminiscent of the structure of DNA. In the above case, two templates that would otherwise not be consistent with a large assortment of tilings together can form more complex structures.
◼
We give doubleShiftedMultiTemplateTiling the encoded radius of the template, representing a graph after edge subdivision, not the actual radius
◼
The fact that templates are comprised of edges and half-edges has lead us to the following representation for templates. We represent a template as a graph, in which each edge of the tile corresponds to an edge-vertex-edge-vertex-edge-vertex-edge structure and each half-edge corresponds to an edge-vertex-edge-vertex structure. The hanging (last) vertex in a half-edge representation captures the notion that the half-edge must eventually be connected to another half edge in order to create a proper edge. This vertex is the ‘glueing’ node between two half-edges when this happens.
Tilings with multiple valence templates
Tilings with multiple valence templates
Another implementation for generating valence tilings is to solve the system of equations
A·
1
b
0 | a[1,2] | a[1,3] | a[1,4] |
a[1,2] | 0 | a[2,3] | a[2,4] |
a[1,3] | a[2,3] | 0 | a[3,4] |
a[1,4] | a[2,4] | a[3,4] | 0 |
1 |
1 |
1 |
1 |
b1 |
b2 |
b3 |
b4 |
◼
the case is displayed above for a relevant example
n4
where is a symmetric adjacency matrix of the system and is the degree of each valence for ∈
This linear system corresponds to the adjacency matrix for a graph, of which in each row, there are precisely “1’s”, corresponding to a -valence.
We can execute this implementation for one or more valencies using Solve[constraints, variables] using generateSimpleTiling. Below, we find all of the graphs of order<5 consistent with a 2-valence and 3-valence templates. Now, we extend our line of thinking to larger templates.
A
b
i
b
i
+
Z
This linear system corresponds to the adjacency matrix for a graph
G
b
i
b
i
We can execute this implementation for one or more valencies using Solve[constraints, variables] using generateSimpleTiling. Below, we find all of the graphs of order<5 consistent with a 2-valence and 3-valence templates. Now, we extend our line of thinking to larger templates.
generateSimpleTemplate[{2,3},4]
,
,...
◼
View the project appendix or our “next steps” to explore how we could also do a similar implementation with Donald Knuth’s Algorithm X, as well as the FindClique function in the function documentation. Algorithm X and Find Clique algorithms perform these calculations with only the ability to find tilings with one valence, and at varying levels of processing efficiency. For example, Algorithm X is slower than Find Clique.
Impossibility Criteria for Graph Tilings
Impossibility Criteria for Graph Tilings
One easy criteria to determine if a graph has a tiling is to look at the number of 1/2 edges in a graph template.Lemma 5.1: For a graph consisting of nodes, each node consistent with a valence template, we must have be an integerFrom the handshaking lemma, we have 2E where is the number of edges in the graph, and is the number of the degree of node in the graph. For each valence node, k. Therefore, , so E is an integer. The handshaking lemma allows a user to drastically speed up code execution, as many cases of tiling by brute force are invalidated. This can be checked with the impossibleValenceTiling function.
n
k
nk
2
∑
i
d
i
E
d
i
i
k
d
i
nk2E
nk
2
impossibleValenceTiling[1001,347]
True
Another weak criteria for determining that we cannot tile a graph is Kuratowski’s Theorem. Namely, if a graph is planar, it cannot contain subgraphs of or . Therefore, we cannot tile planar graphs with templates containing or as subgraphsLemma 5.2: A planar graph G cannot be consistent with a tile-set whose elements have subgraphs or
K
3,3
K
5
K
3,3
K
5
K
3,3
K
5
◼
A future problem given by Stephen Wolfram is to determine the largest graph that can be formed using a simple set of templates.
Concluding Remarks
Concluding Remarks
Appendix 1: Statistical Properties of Random Tilings
Appendix 1: Statistical Properties of Random Tilings
Consider the following set, representative of the first few elements of graphstwo
Keywords
Keywords
◼
Graph Tiling
◼
Constrained Network Systems
◼
Graph Theory
◼
Half Edges
◼
Tile-set
◼
K-Valent
Acknowledgment
Acknowledgment
I would like to thank my project mentor, Sotiris Michos, for invaluable support and mentorship for this project, and many discussions about both theoretical and practical implementations of many ideas. I would also like to thank Bob Nachbar, for his precise insight into Wolfram Language framework, and help with showing me the key principles of Wolfram Language. Furthermore, I would like to thank Brad Klee, for his kindness, and for his many meetings with me discussing various algorithmic procedures, and tiling games, and additional support! Finally, I would like to thank Stephen Wolfram for the project idea, and project guidance throughout. I would also like to thank my friends at the summer school for their support and making a fun environment to be in.
References
References
◼
Graph Theory Reference: https://mathworld.wolfram.com/Graph.html
◼
NKS, Space and Time: https://www.wolframscience.com/nks/p482--the-relationship-of-space-and-time/
◼
Algorithm X: https://arxiv.org/pdf/cs/0011047.pdf