Periodic graph (geometry)
Encyclopedia
A Euclidean graph
(i.e., a graph embedded in some Euclidean space
) is periodic if there exists a basis
of that Euclidean space whose corresponding translations
induce symmetries of that graph (i.e., application of any such translation to the graph embedded in the Euclidean space leaves the graph unchanged). A Euclidean graph is uniformly discrete
if there is a minimal distance between any two vertices. Periodic graphs are closely related to tessellations of space (or honeycombs) and the geometry of their symmetry groups, hence to geometric group theory
, as well as to discrete geometry
and the theory of polytope
s, and similar areas.
Much of the effort in periodic graphs is motivated by applications to natural science and engineering, particularly of three dimensional crystal nets to crystal engineering
, crystal prediction (design)
, and modeling crystal behavior. Periodic graphs have also been studied in modeling very-large-scale integration (VLSI) circuits.
is a pair (V, E), where V is a set of points (sometimes called vertices or nodes) and E is a set of edges (sometimes called bonds), where each edge joins two vertices. While an edge connecting two vertices u and v is usually interpreted as the set { u, v }, an edge is sometimes interpreted as the line segment
connecting u and v so that the resulting structure is a CW complex
. There is a tendency in the polyhedral and chemical literature to refer to geometric graphs as nets (contrast with polyhedral nets
), and the nomenclature in the chemical literature differs from that of graph theory. Most of the literature focuses on periodic graphs that are uniformly discrete
in that there exists e > 0 such that for any two distinct vertices, their distance apart is |u – v| > e.
and Arthur Schoenflies. The problem was generalized in David Hilbert’s Eighteenth Problem
, and the Fyodorov–Schoenflies Theorem was generalized to higher dimensions by Ludwig Bieberbach.
The Fyodorov–Schoenflies theorem asserts the following. Suppose that one is given a Euclidean graph in 3-space such that the following are true:
Then the Euclidean graph is periodic in that the vectors of translations in its symmetry group span the underlying Euclidean space, and its symmetry group is a crystallographic space group
.
The interpretation in science and engineering is that since a Euclidean graph representing a material extending through space must satisfy conditions (1), (2), and (3), non-crystalline substances from quasicrystal
s to glasses must violate (4). However, in the last quarter century, quasicrystals have been recognized to share sufficiently many chemical and physical properties with crystals that there is a tendency to classify quasicrystals as “crystals” and to adjust the definition of “crystal” accordingly.
. Two periodic graphs are often called topologically equivalent if they are isomorphic, although not necessarily homotopic. Even though the graph isomorphism problem is polynomial time reducible
to crystal net topological equivalence (making topological equivalence a candidate for being “computationally intractable” in the sense of not being polynomial time computable), a crystal net is generally regarded as novel if and only if no topologically equivalent net is known. This has focused attention on topological invariants.
One invariant is the array of minimal cycles
(often called rings in the chemistry literature) arrayed about generic vertices and represented in a Schlafli symbol. The cycles of a crystal net are related to another invariant, that of the coordination sequence (or shell map in topology ), which is defined as follows. First, a distance sequence from a vertex v in a graph is the sequence n1, n2, n3, ..., where ni is the number of vertices of distance i from v. The coordination sequence is the sequence s1, s2, s3, ..., where si is the weighted mean of the i-th entries of the distance sequences of vertices of the (orbits of the) crystal nets, where the weights are the asymptotic proportion of vertices of each orbit. The cumulative sums of the coordination sequence is denoted the topological density, and the sum of the first ten terms (plus 1 for the zero-th term) – often denoted TD10 – is a standard search term in crystal net databases.
Another invariant arises from the relationship between tessellations and Euclidean graphs. If we regard a tessellation as an assembly of (possibly polyhedral) solid regions, (possibly polygonal) faces, (possibly linear) curves, and vertices – that is, as a CW-complex
– then the curves and vertices form a Euclidean graph (or 1-skeleton
) of the tessellation. (In addition, the adjacency graph of the tiles induces another Euclidean graph.) If there are finitely many prototile
s in the tessellation, and the tessellation is periodic, then the resulting Euclidean graph will be periodic. Going in the reverse direction, the prototiles of a tessellation whose 1-skeleton is (topologically equivalent to) the given periodic graph, one has another invariant, and it is this invariant that is computed by the computer program TOPOS.
One of the major systematic crystal net enumeration algorithms extant is based on the representation of tessellations by a generalization of the Schläfli symbol by Boris Delauney and Andreas Dress, by which any tessellation (of any dimension) may be represented by a finite structure, which we may call a Dress–Delaney symbol. Any effective enumerator of Dress–Delaney symbols can effectively enumerate those periodic nets that correspond to tessellations. The three-dimensional Dress–Delaney symbol enumerator of Delgado-Friedrichs et al. has predicted several novel crystal nets that were later synthesized. Meanwhile, a two-dimensional Dress–Delaney enumerator generating tessellations for two dimensional hyperbolic space
that was surgically dissected and wrapped around a known crystal net has generated many novel crystal nets.
Another extant enumerator is currently focused on generating plausible crystal nets of zeolite
s. The extension of the symmetry group to 3-space permits the characterization of a fundamental domain
(or region) of 3-space, whose intersection with the net induces a subgraph which, in general position, will have one vertex from each orbit of vertices. This subgraph may or may not be connected, and if a vertex lies on an axis of rotation or some other fixed point of some symmetry of the net, the vertex may necessarily lie on the boundary of any fundamental region. In this case, the net may be generated by applying the symmetry group to the subgraph in the fundamental region.
Other programs have been developed that similarly generate copies of an initial fragment and glue them into a periodic graph
Geometric graph theory
In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs...
(i.e., a graph embedded in some Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
) is periodic if there exists a basis
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
of that Euclidean space whose corresponding translations
Translation (geometry)
In Euclidean geometry, a translation moves every point a constant distance in a specified direction. A translation can be described as a rigid motion, other rigid motions include rotations and reflections. A translation can also be interpreted as the addition of a constant vector to every point, or...
induce symmetries of that graph (i.e., application of any such translation to the graph embedded in the Euclidean space leaves the graph unchanged). A Euclidean graph is uniformly discrete
Discrete space
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points are "isolated" from each other in a certain sense.- Definitions :Given a set X:...
if there is a minimal distance between any two vertices. Periodic graphs are closely related to tessellations of space (or honeycombs) and the geometry of their symmetry groups, hence to geometric group theory
Geometric group theory
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act .Another important...
, as well as to discrete geometry
Discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles,...
and the theory of polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
s, and similar areas.
Much of the effort in periodic graphs is motivated by applications to natural science and engineering, particularly of three dimensional crystal nets to crystal engineering
Crystal engineering
Crystal engineering is the design and synthesis of molecular solid-state structures with desired properties, based on an understanding and exploitation of intermolecular interactions. The two main strategies currently in use for crystal engineering are based on hydrogen bonding and coordination...
, crystal prediction (design)
Crystal structure prediction
Crystal structure prediction is the calculation of the crystal structures of solids from first principles. Reliable methods of predicting the crystal structure of a compound, based only on its molecular structure, has been a goal of the physical sciences since the 1950s...
, and modeling crystal behavior. Periodic graphs have also been studied in modeling very-large-scale integration (VLSI) circuits.
Basic formulation
A Euclidean graphGeometric graph theory
In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs...
is a pair (V, E), where V is a set of points (sometimes called vertices or nodes) and E is a set of edges (sometimes called bonds), where each edge joins two vertices. While an edge connecting two vertices u and v is usually interpreted as the set { u, v }, an edge is sometimes interpreted as the line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
connecting u and v so that the resulting structure is a CW complex
CW complex
In topology, a CW complex is a type of topological space introduced by J. H. C. Whitehead to meet the needs of homotopy theory. This class of spaces is broader and has some better categorical properties than simplicial complexes, but still retains a combinatorial naturethat allows for...
. There is a tendency in the polyhedral and chemical literature to refer to geometric graphs as nets (contrast with polyhedral nets
Net (polyhedron)
In geometry the net of a polyhedron is an arrangement of edge-joined polygons in the plane which can be folded to become the faces of the polyhedron...
), and the nomenclature in the chemical literature differs from that of graph theory. Most of the literature focuses on periodic graphs that are uniformly discrete
Discrete space
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points are "isolated" from each other in a certain sense.- Definitions :Given a set X:...
in that there exists e > 0 such that for any two distinct vertices, their distance apart is |u – v| > e.
Obtaining periodicity
The identification and classification of the crystallographic space groups took much of the Nineteenth century, and the confirmation of the completeness of the list was finished by the theorems of Yevgraf FyodorovYevgraf Fyodorov
Yevgraf Stepanovich Fyodorov, sometimes spelled Evgraf Stepanovich Fedorov , was a Russian mathematician, crystallographer, and mineralogist....
and Arthur Schoenflies. The problem was generalized in David Hilbert’s Eighteenth Problem
Hilbert's problems
Hilbert's problems form a list of twenty-three problems in mathematics published by German mathematician David Hilbert in 1900. The problems were all unsolved at the time, and several of them were very influential for 20th century mathematics...
, and the Fyodorov–Schoenflies Theorem was generalized to higher dimensions by Ludwig Bieberbach.
The Fyodorov–Schoenflies theorem asserts the following. Suppose that one is given a Euclidean graph in 3-space such that the following are true:
- It is uniformly discrete in that there exists e > 0 such that for any two distinct vertices, their distance apart is |u – v| > e.
- It fills space in the sense that for any plane in 3-space, there exist vertices of the graph on both sides of the plane.
- Each vertex is of finite degreeDegree (graph theory)In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
or valency.
- There are finitely many orbits of vertices under the symmetry group of the geometric graph.
Then the Euclidean graph is periodic in that the vectors of translations in its symmetry group span the underlying Euclidean space, and its symmetry group is a crystallographic space group
Space group
In mathematics and geometry, a space group is a symmetry group, usually for three dimensions, that divides space into discrete repeatable domains.In three dimensions, there are 219 unique types, or counted as 230 if chiral copies are considered distinct...
.
The interpretation in science and engineering is that since a Euclidean graph representing a material extending through space must satisfy conditions (1), (2), and (3), non-crystalline substances from quasicrystal
Quasicrystal
A quasiperiodic crystal, or, in short, quasicrystal, is a structure that is ordered but not periodic. A quasicrystalline pattern can continuously fill all available space, but it lacks translational symmetry...
s to glasses must violate (4). However, in the last quarter century, quasicrystals have been recognized to share sufficiently many chemical and physical properties with crystals that there is a tendency to classify quasicrystals as “crystals” and to adjust the definition of “crystal” accordingly.
Mathematics and computation
Much of the theoretical investigation of periodic graphs has focused on the problems of generating and classifying them.Classification problems
Most of the work on classification problems has focused on three dimensions, particularly on the classification of crystal nets, i.e., of periodic graphs that could serve as descriptions or designs for placement of atoms or molecular objects, with bonds indicated by edges, in a crystal. One of the more popular classification criteria is graph isomorphism, not to be confused with crystallographic isomorphismIsomorphism (crystallography)
In crystallography crystals are described as isomorphous if they are closely similar in shape. Historically crystal shape was defined by measuring the angles between crystal faces with a goniometer...
. Two periodic graphs are often called topologically equivalent if they are isomorphic, although not necessarily homotopic. Even though the graph isomorphism problem is polynomial time reducible
Polynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction...
to crystal net topological equivalence (making topological equivalence a candidate for being “computationally intractable” in the sense of not being polynomial time computable), a crystal net is generally regarded as novel if and only if no topologically equivalent net is known. This has focused attention on topological invariants.
One invariant is the array of minimal cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
(often called rings in the chemistry literature) arrayed about generic vertices and represented in a Schlafli symbol. The cycles of a crystal net are related to another invariant, that of the coordination sequence (or shell map in topology ), which is defined as follows. First, a distance sequence from a vertex v in a graph is the sequence n1, n2, n3, ..., where ni is the number of vertices of distance i from v. The coordination sequence is the sequence s1, s2, s3, ..., where si is the weighted mean of the i-th entries of the distance sequences of vertices of the (orbits of the) crystal nets, where the weights are the asymptotic proportion of vertices of each orbit. The cumulative sums of the coordination sequence is denoted the topological density, and the sum of the first ten terms (plus 1 for the zero-th term) – often denoted TD10 – is a standard search term in crystal net databases.
Another invariant arises from the relationship between tessellations and Euclidean graphs. If we regard a tessellation as an assembly of (possibly polyhedral) solid regions, (possibly polygonal) faces, (possibly linear) curves, and vertices – that is, as a CW-complex
CW complex
In topology, a CW complex is a type of topological space introduced by J. H. C. Whitehead to meet the needs of homotopy theory. This class of spaces is broader and has some better categorical properties than simplicial complexes, but still retains a combinatorial naturethat allows for...
– then the curves and vertices form a Euclidean graph (or 1-skeleton
N-skeleton
In mathematics, particularly in algebraic topology, the n-skeleton of a topological space X presented as a simplicial complex refers to the subspace Xn that is the union of the simplices of X of dimensions m ≤ n...
) of the tessellation. (In addition, the adjacency graph of the tiles induces another Euclidean graph.) If there are finitely many prototile
Prototile
In the mathematical theory of tessellations, a prototile is one of the shapes of a tile in a tessellation.A tessellation of the plane or of any other space is a cover of the space by closed shapes, called tiles, that have disjoint interiors. Some of the tiles may be congruent to one or more others...
s in the tessellation, and the tessellation is periodic, then the resulting Euclidean graph will be periodic. Going in the reverse direction, the prototiles of a tessellation whose 1-skeleton is (topologically equivalent to) the given periodic graph, one has another invariant, and it is this invariant that is computed by the computer program TOPOS.
Generating periodic graphs
There are several extant periodic graph enumeration algorithms, including modifying extant nets to produce new ones, but there appear to be two major classes of enumerators.One of the major systematic crystal net enumeration algorithms extant is based on the representation of tessellations by a generalization of the Schläfli symbol by Boris Delauney and Andreas Dress, by which any tessellation (of any dimension) may be represented by a finite structure, which we may call a Dress–Delaney symbol. Any effective enumerator of Dress–Delaney symbols can effectively enumerate those periodic nets that correspond to tessellations. The three-dimensional Dress–Delaney symbol enumerator of Delgado-Friedrichs et al. has predicted several novel crystal nets that were later synthesized. Meanwhile, a two-dimensional Dress–Delaney enumerator generating tessellations for two dimensional hyperbolic space
Hyperbolic geometry
In mathematics, hyperbolic geometry is a non-Euclidean geometry, meaning that the parallel postulate of Euclidean geometry is replaced...
that was surgically dissected and wrapped around a known crystal net has generated many novel crystal nets.
Another extant enumerator is currently focused on generating plausible crystal nets of zeolite
Zeolite
Zeolites are microporous, aluminosilicate minerals commonly used as commercial adsorbents. The term zeolite was originally coined in 1756 by Swedish mineralogist Axel Fredrik Cronstedt, who observed that upon rapidly heating the material stilbite, it produced large amounts of steam from water that...
s. The extension of the symmetry group to 3-space permits the characterization of a fundamental domain
Fundamental domain
In geometry, the fundamental domain of a symmetry group of an object is a part or pattern, as small or irredundant as possible, which determines the whole object based on the symmetry. More rigorously, given a topological space and a group acting on it, the images of a single point under the group...
(or region) of 3-space, whose intersection with the net induces a subgraph which, in general position, will have one vertex from each orbit of vertices. This subgraph may or may not be connected, and if a vertex lies on an axis of rotation or some other fixed point of some symmetry of the net, the vertex may necessarily lie on the boundary of any fundamental region. In this case, the net may be generated by applying the symmetry group to the subgraph in the fundamental region.
Other programs have been developed that similarly generate copies of an initial fragment and glue them into a periodic graph
See also
- Periodic graphs as models of crystals for design.