Periodic graph (geometry)

Last updated October 26, 2023

A Euclidean graph (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). Equivalently, a periodic Euclidean graph is a periodic realization of an abelian covering graph over a finite graph.^[1]^[2] 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 polytopes, 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.^[3]

Basic formulation

A Euclidean graph 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.^[4] 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.

From the mathematical view, a Euclidean periodic graph is a realization of an infinite-fold abelian covering graph over a finite graph.

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 Evgraf Fedorov and Arthur Schoenflies.^[5] The problem was generalized in David Hilbert's eighteenth Problem, and the Fedorov–Schoenflies Theorem was generalized to higher dimensions by Ludwig Bieberbach.^[6]

The Fedorov–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 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.

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 quasicrystals 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.^[7]

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 isomorphism. 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 Schläfli symbol. The cycles of a crystal net are related^[8] to another invariant, that of the coordination sequence (or shell map in topology^[9]), which is defined as follows. First, a distance sequence from a vertex v in a graph is the sequence n₁, n₂, n₃, ..., where n_i is the number of vertices of distance i from v. The coordination sequence is the sequence s₁, s₂, s₃, ..., where s_i 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. See^[10]^[11] for a mathematical aspect of topological density which is closely related to the large deviation property of simple random walks.

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 prototiles 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.^[12]

Generating periodic graphs

There are several extant periodic graph enumeration algorithms, including modifying extant nets to produce new ones,^[13] but there appear to be two major classes of enumerators.

One of the major systematic crystal net enumeration algorithms extant^[14] 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,^[15] 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.^[16] Meanwhile, a two-dimensional Dress–Delaney enumerator generating reticulations of two-dimensional hyperbolic space that is surgically dissected and wrapped around a triply periodic minimal surface such as the Gyroid, Diamond or Primitive, has generated many novel crystal nets.^[17]^[18]

Another extant enumerator is currently focused on generating plausible crystal nets of zeolites. 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.^[19] Other programs have been developed that similarly generate copies of an initial fragment and glue them into a periodic graph^[20]

Related Research Articles

In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.

<span class="mw-page-title-main">Polyhedron</span> 3D shape with flat faces, straight edges and sharp corners

In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.

A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called tiles, with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of geometries.

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, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Arrangement of lines</span> Subdivision of the plane by lines

In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

In mathematics, an abstract polytope is an algebraic partially ordered set which captures the dyadic property of a traditional polytope without specifying purely geometric properties such as points and lines.

Euclidean plane tilings by convex regular polygons have been widely used since antiquity. The first systematic mathematical treatment was that of Kepler in his Harmonices Mundi.

<span class="mw-page-title-main">Diamond cubic</span> Type of crystal structure

In crystallography, the diamond cubic crystal structure is a repeating pattern of 8 atoms that certain materials may adopt as they solidify. While the first known example was diamond, other elements in group 14 also adopt this structure, including α-tin, the semiconductors silicon and germanium, and silicon–germanium alloys in any proportion. There are also crystals, such as the high-temperature form of cristobalite, which have a similar structure, with one kind of atom at the positions of carbon atoms in diamond but with another kind of atom halfway between those.

The cubic honeycomb or cubic cellulation is the only proper regular space-filling tessellation in Euclidean 3-space made up of cubic cells. It has 4 cubes around every edge, and 8 cubes around each vertex. Its vertex figure is a regular octahedron. It is a self-dual tessellation with Schläfli symbol {4,3,4}. John Horton Conway called this honeycomb a cubille.

In geometry, a honeycomb is a space filling or close packing of polyhedral or higher-dimensional cells, so that there are no gaps. It is an example of the more general mathematical tiling or tessellation in any number of dimensions. Its dimension can be clarified as n-honeycomb for a honeycomb of n-dimensional space.

In geometry, a vertex is a point where two or more curves, lines, or edges meet or intersect. As a consequence of this definition, the point where two lines meet to form an angle and the corners of polygons and polyhedra are vertices.

In geometry, a uniform tiling is a tessellation of the plane by regular polygon faces with the restriction of being vertex-transitive.

In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold into topological disks such that every flag can be transformed into any other flag by a symmetry of the decomposition. Regular maps are, in a sense, topological generalizations of Platonic solids. The theory of maps and their classification is related to the theory of Riemann surfaces, hyperbolic geometry, and Galois theory. Regular maps are classified according to either: the genus and orientability of the supporting surface, the underlying graph, or the automorphism group.

<span class="mw-page-title-main">Toshikazu Sunada</span> Japanese mathematician (born 1948)

Toshikazu Sunada is a Japanese mathematician and author of many books and essays on mathematics and mathematical sciences. He is professor emeritus of both Meiji University and Tohoku University. He is also distinguished professor of emeritus at Meiji in recognition of achievement over the course of an academic career. Before he joined Meiji University in 2003, he was professor of mathematics at Nagoya University (1988–1991), at the University of Tokyo (1991–1993), and at Tohoku University (1993–2003). Sunada was involved in the creation of the School of Interdisciplinary Mathematical Sciences at Meiji University and is its first dean (2013–2017). Since 2019, he is President of Mathematics Education Society of Japan.

<span class="mw-page-title-main">Periodic graph (crystallography)</span>

In crystallography, a periodic graph or crystal net is a three-dimensional periodic graph, i.e., a three-dimensional Euclidean graph whose vertices or nodes are points in three-dimensional Euclidean space, and whose edges are line segments connecting pairs of vertices, periodic in three linearly independent axial directions. There is usually an implicit assumption that the set of vertices are uniformly discrete, i.e., that there is a fixed minimum distance between any two vertices. The vertices may represent positions of atoms or complexes or clusters of atoms such as single-metal ions, molecular building blocks, or secondary building units, while each edge represents a chemical bond or a polymeric ligand.

Mathematics is a broad subject that is commonly divided in many areas that may be defined by their objects of study, by the used methods, or by both. For example, analytic number theory is a subarea of number theory devoted to the use of methods of analysis for the study of natural numbers.

In geometry, John Horton Conway defines architectonic and catoptric tessellations as the uniform tessellations of Euclidean 3-space with prime space groups and their duals, as three-dimensional analogue of the Platonic, Archimedean, and Catalan tiling of the plane. The singular vertex figure of an architectonic tessellation is the dual of the cell of the corresponding catoptric tessellation, and vice versa. The cubille is the only Platonic (regular) tessellation of 3-space, and is self-dual. There are other uniform honeycombs constructed as gyrations or prismatic stacks which are excluded from these categories.

In geometry and crystallography, the Laves graph is an infinite and highly symmetric system of points and line segments in three-dimensional Euclidean space, forming a periodic graph. Three equal-length segments meet at 120° angles at each point, and all cycles use ten or more segments. It is the shortest possible triply periodic graph, relative to the volume of its fundamental domain. One arrangement of the Laves graph uses one out of every eight of the points in the integer lattice as its points, and connects all pairs of these points that are nearest neighbors, at distance $. It can also be defined, divorced from its geometry, as an abstract undirected graph, a covering graph of the complete graph on four vertices.$

In three-dimensional hyperbolic geometry, an ideal polyhedron is a convex polyhedron all of whose vertices are ideal points, points "at infinity" rather than interior to three-dimensional hyperbolic space. It can be defined as the convex hull of a finite set of ideal points. An ideal polyhedron has ideal polygons as its faces, meeting along lines of the hyperbolic space.

References

↑ Sunada, T. (2012), "Lecture on topological crystallography", Japan. J. Math., 7: 1–39, doi:10.1007/s11537-012-1144-4, S2CID 255312584
↑ Sunada, T. (2012), Topological Crystallography With a View Towards Discrete Geometric Analysis, Surveys and Tutorials in the Applied Mathematical Sciences, vol. 6, Springer
↑ Cohen, E.; Megiddo, N. (1991), "Recognizing properties of periodic graphs", Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift (PDF), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 135–146, doi:10.1090/dimacs/004/10, ISBN 9780821865934 , retrieved August 15, 2010
↑ Delgado-Friedrichs, O.; O’Keeffe, M. (2005), "Crystal nets as graphs: Terminology and definitions", Journal of Solid State Chemistry, 178 (8): 2480–2485, Bibcode:2005JSSCh.178.2480D, doi:10.1016/j.jssc.2005.06.011
↑ Senechal, M. (1990), "A brief history of geometrical crystallography", in Lima-de-Faria, J. (ed.), Historical Atlas of Crystallography, Kluwer, pp. 43–59
↑ Vinberg, E. B.; Shvartsman, O. V. (1993), "Discrete Groups of Motions of Spaces of Constant Curvature", in Vinberg, E. B. (ed.), Geometry II: Spaces of Constant Curvature, Springer-Verlag
↑ Senechal, M. (1995), Quasicrystals and Geometry, Cambridge U. Pr., p. 27
↑ Eon, J. G. (2004), "Topological density of nets: a direct calculation", Acta Crystallogr. A, 60 (Pt 1): 7–18, Bibcode:2004AcCrA..60....7E, doi:10.1107/s0108767303022037, PMID 14691323.
↑ Aste, T. (1999), "The Shell Map", in Sadoc, J. F.; Rivier, N. (eds.), THE SHELL MAP: The structure of froths through a dynamical map, Foams and Emulsions, Kluwer, pp. 497–510, arXiv: cond-mat/9803183 , Bibcode:1998cond.mat..3183A
↑ M. Kotani and T. Sunada "Geometric aspects of large deviations for random walks on crystal lattices" In: Microlocal Analysis and Complex Fourier Analysis (T. Kawai and K. Fujita, Ed.), World Scientific, 2002, pp. 215–237.
↑ Kotani, M.; Sunada, T. (2006), "Large deviation and the tangent cone at infinity of a crystal lattice", Math. Z., 254 (4): 837–870, doi:10.1007/s00209-006-0951-9, S2CID 122531716
↑ Blatov, V. A.; Proserpio, D. M., TOPOS Program package for topological analysis of crystal structures , retrieved August 15, 2010
↑ Earl, D. J.; Deem, M. W. (2006), "Toward a Database of Hypothetical Zeolite Structures", Ind. Eng. Chem. Res., 45 (16): 5449–5454, doi:10.1021/ie0510728, S2CID 40620797
↑ Delgado Friedrichs, O.; Dress, A. W. M.; Huson, D. H.; Klinowski, J.; Mackay, A. L. (12 Aug 1999), "Systematic enumeration of crystalline networks", Nature, 400 (6745): 644–647, Bibcode:1999Natur.400..644D, doi:10.1038/23210, S2CID 4388277.
↑ Dress, A.; Delgado Friedrichs, O.; Huson, D. (1995), "An algorithmic approach to tilings", in Charles J., Colbourn; Ebadollah S., Mahmoodian (eds.), Combinatorics Advances: Papers from the Twenty-fifth Annual Iranian Mathematics Conference (AIMC25) held at Sharif University of Technology, Tehran, March 28–31, 1994, Mathematics and its Applications, vol. 329, Kluwer, pp. 111–119, doi:10.1007/978-1-4613-3554-2_7
↑ Nouar, Farid; Eubank, Jarrod F.; Bousquet, Till; Wojtas, Lukasz; Zaworotko, Michael J.; Eddaoudi, Mohamed (2008), "Supermolecular Building Blocks (SBBs) for the Design and Synthesis of Highly Porous Metal-Organic Frameworks", Journal of the American Chemical Society, 130 (6): 1833–1835, doi:10.1021/ja710123s, PMID 18205363
↑ Ramsden, S.J.; Robins, V.; Hyde, S. (2009), "3D euclidean nets from 2D hyperbolic tilings: Kaleidoscopic examples", Acta Crystallogr. A, 65 (Pt 2): 81–108, Bibcode:2009AcCrA..65...81R, doi: 10.1107/S0108767308040592 , PMID 19225190.
↑ EPINET: Euclidean Patterns in Non-Euclidean Tilings , retrieved January 30, 2013
↑ Treacy, M.M. J.; Rivin, I.; Balkovsky, E.; Randall, K. H.; Foster, M. D. (2004), "Enumeration of periodic tetrahedral frameworks. II. Polynodal graphs" (PDF), Microporous and Mesoporous Materials, 74 (1–3): 121–132, doi:10.1016/j.micromeso.2004.06.013 , retrieved August 15, 2010.
↑ LeBail, A. (2005), "Inorganic structure prediction with GRINSP", J. Appl. Crystallogr., 38 (2): 389–395, doi: 10.1107/S0021889805002384