Periodic graph (geometry): Difference between revisions
Add: isbn, series, chapter, title. | Use this tool. Report bugs. | #UCB_Gadget |
|||
(46 intermediate revisions by 27 users not shown) | |||
Line 1: | Line 1: | ||
{{Other uses|Periodic graph (disambiguation){{!}}Periodic graph}} |
{{Other uses|Periodic graph (disambiguation){{!}}Periodic graph}} |
||
A [[Geometric graph theory|Euclidean graph]] (a graph embedded in some [[Euclidean space]]) is '''periodic''' if there exists a [[Basis (linear algebra)|basis]] of that Euclidean space whose corresponding [[Translation (geometry)|translations]] induce [[Symmetry groups|symmetries]] of that graph (i.e., application of any such translation to the graph embedded in the Euclidean space leaves the graph unchanged). |
A [[Geometric graph theory|Euclidean graph]] (a graph embedded in some [[Euclidean space]]) is '''periodic''' if there exists a [[Basis (linear algebra)|basis]] of that Euclidean space whose corresponding [[Translation (geometry)|translations]] induce [[Symmetry groups|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.<ref>{{Citation |
||
|last = Sunada |
|||
|first = T. |
|||
|author-link=Toshikazu Sunada |
|||
|title = Lecture on topological crystallography |
|||
|journal = Japan. J. Math. |
|||
|volume = 7 |
|||
|pages = 1–39 |
|||
|year = 2012 |
|||
|doi=10.1007/s11537-012-1144-4 |
|||
|s2cid = 255312584 |
|||
}}</ref><ref>{{Citation |
|||
|last = Sunada |
|||
|first = T. |
|||
|title = Topological Crystallography With a View Towards Discrete Geometric Analysis |
|||
|series = Surveys and Tutorials in the Applied Mathematical Sciences |
|||
|volume = 6 |
|||
|publisher = Springer |
|||
|year = 2012 |
|||
}}</ref> A Euclidean graph is [[discrete space|uniformly discrete]] if there is a minimal distance between any two vertices. Periodic graphs are closely related to [[Tessellation of space|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 |
Much of the effort in periodic graphs is motivated by applications to natural science and engineering, particularly of [[three-dimensional]] [[crystal net]]s to [[crystal engineering]], [[Crystal structure prediction|crystal prediction (design)]], and modeling crystal behavior. Periodic graphs have also been studied in modeling [[Vlsi|very-large-scale integration (VLSI)]] circuits.<ref>{{Citation|last1 = Cohen|first1 = E.|author1-link=Edith Cohen|last2 = Megiddo|first2 = N.| title=Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift | chapter=Recognizing properties of periodic graphs | series=DIMACS Series in Discrete Mathematics and Theoretical Computer Science |author2-link=Nimrod Megiddo |volume = 4|year = 1991|pages = 135–146|url = http://theory.stanford.edu/~megiddo/pdf/RecognizingX.pdf|accessdate = August 15, 2010|doi = 10.1090/dimacs/004/10|isbn = 9780821865934}}</ref> |
||
==Basic formulation== |
==Basic formulation== |
||
A [[Geometric graph theory|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 (mathematics)|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 [[Net (polyhedron)|polyhedral nets]]), and the nomenclature in the chemical literature differs from that of graph theory.<ref>{{Citation |
A [[Geometric graph theory|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 (mathematics)|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 [[Net (polyhedron)|polyhedral nets]]), and the nomenclature in the chemical literature differs from that of graph theory.<ref>{{Citation |
||
| |
|last1 = Delgado-Friedrichs |
||
| |
|first1 = O. |
||
|last2 = O’Keeffe |
|last2 = O’Keeffe |
||
|first2 = M. |
|first2 = M. |
||
|title = Crystal nets as graphs: Terminology and definitions |
|title = Crystal nets as graphs: Terminology and definitions |
||
|journal = |
|journal = Journal of Solid State Chemistry |
||
|volume = 178 |
|volume = 178 |
||
|pages = 2480–2485 |
|pages = 2480–2485 |
||
|year = 2005 |
|year = 2005 |
||
|url = http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WM2-4GNCY5Y-1&_user=10&_coverDate=08%2F31%2F2005&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=b66e45cb98a89cd42092d3c6d54b8620 |
|||
|accessdate = August 15, 2010 |
|||
|doi = 10.1016/j.jssc.2005.06.011 |
|doi = 10.1016/j.jssc.2005.06.011 |
||
|issue = 8|bibcode = 2005JSSCh.178.2480D |
|||
|issue = 8}}</ref> Most of the literature focuses on periodic graphs that are [[discrete space|uniformly discrete]] in that there exists ''e'' > 0 such that for any two distinct vertices, their distance apart is |''u'' – ''v''| > ''e''. |
|||
}}</ref> Most of the literature focuses on periodic graphs that are [[discrete space|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=== |
===Obtaining periodicity=== |
||
The identification and classification of the crystallographic space groups took much of the |
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 [[Schoenflies|Arthur Schoenflies]].<ref>{{Citation |
||
|first = M. |
|first = M. |
||
|last = Senechal |
|last = Senechal | authorlink = Marjorie Senechal |
||
|editor-last = Lima-de-Faria |
|editor-last = Lima-de-Faria |
||
|editor-first = J. |
|editor-first = J. |
||
|contribution = A brief history of geometrical crystallography |
|contribution = A brief history of geometrical crystallography |
||
| |
|title = Historical Atlas of Crystallography |
||
|year = 1990 |
|year = 1990 |
||
|pages = 43–59 |
|pages = 43–59 |
||
|publisher = Kluwer}}</ref> The problem was generalized in [[Hilbert's eighteenth problem|David |
|publisher = Kluwer}}</ref> The problem was generalized in [[Hilbert's eighteenth problem|David Hilbert's eighteenth Problem]], and the Fedorov–Schoenflies Theorem was generalized to higher dimensions by [[Ludwig Bieberbach]].<ref>{{Citation |
||
| |
|first1 = E. B. |
||
| |
|last1 = Vinberg |
||
|first2 = O. V. |
|first2 = O. V. |
||
|last2 = Shvartsman |
|last2 = Shvartsman |
||
Line 38: | Line 58: | ||
|editor-first = E. B. |
|editor-first = E. B. |
||
|contribution = Discrete Groups of Motions of Spaces of Constant Curvature |
|contribution = Discrete Groups of Motions of Spaces of Constant Curvature |
||
| |
|title = Geometry II: Spaces of Constant Curvature |
||
|year = 1993 |
|year = 1993 |
||
|publisher = Springer-Verlag}}</ref> |
|publisher = Springer-Verlag}}</ref> |
||
The Fedorov–Schoenflies theorem asserts the following. Suppose that one is given a Euclidean graph in 3-space such that the following are true: |
The Fedorov–Schoenflies theorem asserts the following. Suppose that one is given a Euclidean graph in 3-space such that the following are true: |
||
<ol> |
|||
# 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 (graph theory)|degree]] or '''valency'''. |
|||
# There are finitely many orbits of vertices under the symmetry group of the geometric graph. |
|||
</ol> |
|||
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 [[Space group|crystallographic space group]]. |
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 [[Space group|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 [[Glass# |
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 [[Glass#Formation from a supercooled liquid|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.<ref>{{Citation |
||
|last = Senechal |
|last = Senechal |
||
|first = M. |
|first = M. | authorlink = Marjorie Senechal |
||
|title = Quasicrystals and Geometry |
|title = Quasicrystals and Geometry | title-link = Quasicrystals and Geometry |
||
|publisher = Cambridge U. Pr. |
|publisher = Cambridge U. Pr. |
||
|year = 1995 |
|year = 1995 |
||
Line 63: | Line 83: | ||
===Classification problems=== |
===Classification problems=== |
||
Most of the work on classification problems has focused on three dimensions, particularly on the classification of [[Periodic Graphs (Crystallography)|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 [[Isomorphism (crystallography)|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 reduction|polynomial time reducible]] to crystal net topological equivalence (making topological equivalence a candidate for being |
Most of the work on classification problems has focused on three dimensions, particularly on the classification of [[Periodic Graphs (Crystallography)|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 [[Isomorphism (crystallography)|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 reduction|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#Polynomial time|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 [[Cycle (graph theory)|cycles]] (often called ''rings'' in the chemistry literature) arrayed about generic vertices and represented in a [[ |
One invariant is the array of minimal [[Cycle (graph theory)|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<ref>{{Citation |
||
|last = Eon |
|last = Eon |
||
|first = J. G. |
|first = J. G. |
||
Line 73: | Line 93: | ||
|pages = 7–18 |
|pages = 7–18 |
||
|year = 2004 |
|year = 2004 |
||
|issue = Pt 1 |
|||
|url = http://scripts.iucr.org/cgi-bin/paper?au5001 |
|||
|postscript = . |
|||
|accessdate = August 15, 2010 |
|||
|doi=10.1107/s0108767303022037|pmid = 14691323 |
|||
|postscript = .}}</ref> to another invariant, that of the '''coordination sequence''' (or '''shell map''' in topology <ref>{{Citation |
|||
|bibcode = 2004AcCrA..60....7E |
|||
}}</ref> to another invariant, that of the [[coordination sequence]] (or '''shell map''' in topology<ref>{{Citation |
|||
|first = T. |
|first = T. |
||
|last = Aste |
|last = Aste |
||
Line 88: | Line 110: | ||
|arxiv = cond-mat/9803183 |
|arxiv = cond-mat/9803183 |
||
|editor2-first= N. |
|editor2-first= N. |
||
|bibcode = 1998cond.mat..3183A |
|||
}}</ref>), which is defined as follows. First, a '''distance sequence''' from a vertex ''v'' in a graph is the sequence ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>, ..., where ''n''<sub>''i''</sub> is the number of vertices of distance ''i'' from ''v''. The coordination sequence is the sequence ''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ..., where ''s''<sub>''i''</sub> 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. |
|||
|title = THE SHELL MAP: The structure of froths through a dynamical map |
|||
}}</ref>), which is defined as follows. First, a '''distance sequence''' from a vertex ''v'' in a graph is the sequence ''n''<sub>1</sub>, ''n''<sub>2</sub>, ''n''<sub>3</sub>, ..., where ''n''<sub>''i''</sub> is the number of vertices of distance ''i'' from ''v''. The coordination sequence is the sequence ''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ..., where ''s''<sub>''i''</sub> 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<ref>M. Kotani and [[Toshikazu Sunada|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.</ref> |
|||
<ref>{{Citation |
|||
|last1 = Kotani |
|||
|first1 = M. |
|||
|last2 = Sunada |
|||
|first2 = T. |
|||
|title = Large deviation and the tangent cone at infinity of a crystal lattice |
|||
|journal = Math. Z. |
|||
|volume = 254 |
|||
|issue = 4 |
|||
|pages = 837–870 |
|||
|year = 2006 |
|||
|doi=10.1007/s00209-006-0951-9 |
|||
|s2cid = 122531716 |
|||
}}</ref> 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|CW-complex]] – then the curves and vertices form a Euclidean graph (or [[N-skeleton|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.<ref>{{Citation |
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]] – then the curves and vertices form a Euclidean graph (or [[N-skeleton|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.<ref>{{Citation |
||
| |
|last1 = Blatov |
||
| |
|first1 = V. A. |
||
|last2 = Proserpio |
|last2 = Proserpio |
||
|first2 = D. M. |
|first2 = D. M. |
||
Line 101: | Line 139: | ||
===Generating periodic graphs=== |
===Generating periodic graphs=== |
||
There are several extant periodic graph enumeration algorithms, including modifying extant nets to produce new ones,<ref>{{Citation |
There are several extant periodic graph enumeration algorithms, including modifying extant nets to produce new ones,<ref>{{Citation |
||
| |
|last1 = Earl |
||
| |
|first1 = D. J. |
||
|last2 = Deem |
|last2 = Deem |
||
|first2 = M. W. |
|first2 = M. W. |
||
Line 111: | Line 149: | ||
|doi = 10.1021/ie0510728 |
|doi = 10.1021/ie0510728 |
||
|title = Toward a Database of Hypothetical Zeolite Structures |
|title = Toward a Database of Hypothetical Zeolite Structures |
||
|issue = 16}}</ref> but there appear to be two major classes of enumerators. |
|issue = 16|s2cid = 40620797 |
||
}}</ref> but there appear to be two major classes of enumerators. |
|||
One of the major systematic [[crystal net]] enumeration algorithms extant |
One of the major systematic [[crystal net]] enumeration algorithms extant<ref>{{ Citation |
||
| |
|last1 = Delgado Friedrichs |
||
| |
|first1 = O. |
||
|last2 = Dress |
|last2 = Dress |
||
|first2 = A. W. M. |
|first2 = A. W. M. |
||
Line 128: | Line 167: | ||
|volume = 400 |
|volume = 400 |
||
|pages = 644–647 |
|pages = 644–647 |
||
|date = 12 Aug |
|date = 12 Aug 1999 |
||
|issue=6745 |
|||
|url = http://www.nature.com/nature/journal/v400/n6745/abs/400644a0.html |
|||
|accessdate = August 15, 2010 |
|||
|issue=6745 |
|||
|doi=10.1038/23210 |
|doi=10.1038/23210 |
||
|postscript = .|bibcode = 1999Natur.400..644D |
|||
|postscript = .}}</ref> is based on the representation of tessellations by a generalization of the [[Schläfli symbol]] by [[Delone|Boris Delauney]] and Andreas Dress, by which any tessellation (of any dimension) may be represented by a finite structure,<ref>{{Citation |
|||
| |
|s2cid = 4388277 |
||
}}</ref> is based on the representation of tessellations by a generalization of the [[Schläfli symbol]] by [[Boris Delaunay|Boris Delauney]] and Andreas Dress, by which any tessellation (of any dimension) may be represented by a finite structure,<ref>{{Citation |
|||
|first = A. |
|||
|last1 = Dress |
|||
|first1 = A. |
|||
|last2 = Delgado Friedrichs |
|last2 = Delgado Friedrichs |
||
|first2 = O. |
|first2 = O. |
||
|last3 = Huson |
|last3 = Huson |
||
|first3 = D. |
|first3 = D. |
||
| |
|contribution = An algorithmic approach to tilings |
||
|doi = 10.1007/978-1-4613-3554-2_7 |
|||
|editor1-first = Colbourn |
|editor1-first = Colbourn |
||
|editor1-last = |
|editor1-last = Charles J. | editor1-link = Charles Colbourn |
||
|editor2-first = Mahmoodian |
|editor2-first = Mahmoodian |
||
|editor2-last = |
|editor2-last = Ebadollah S. |
||
|title = Combinatorics Advances: Papers from the Twenty-fifth Annual Iranian Mathematics Conference (AIMC25) held at Sharif University of Technology, Tehran, March 28–31, 1994 |
|||
|series = Combinatorics Advances |
|||
|series = Mathematics and its Applications | volume = 329 |
|||
|pages = 111–119 |
|pages = 111–119 |
||
|publisher = Kluwer |
|publisher = Kluwer |
||
|year = 1995|isbn = 978-1-4613-3556-6 |
|||
|year = 1995}}</ref> 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.<ref>{{Citation |
|||
}}</ref> 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.<ref>{{Citation |
|||
|last = Nouar |
|||
|last1 = Nouar |
|||
|last2 = Eubank |
|last2 = Eubank |
||
|last3 = Bousquet |
|last3 = Bousquet |
||
Line 156: | Line 198: | ||
|last6 = Eddaoudi |
|last6 = Eddaoudi |
||
|title = Supermolecular Building Blocks (SBBs) for the Design and Synthesis of Highly Porous Metal-Organic Frameworks |
|title = Supermolecular Building Blocks (SBBs) for the Design and Synthesis of Highly Porous Metal-Organic Frameworks |
||
|journal = |
|journal = Journal of the American Chemical Society |
||
|volume = 130 |
|volume = 130 |
||
|issue = 6 |
|issue = 6 |
||
Line 162: | Line 204: | ||
|year = 2008 |
|year = 2008 |
||
|doi = 10.1021/ja710123s |
|doi = 10.1021/ja710123s |
||
|pmid = 18205363 |
|||
|first1 = Farid |
|first1 = Farid |
||
|first2 = Jarrod F. |
|first2 = Jarrod F. |
||
Line 167: | Line 210: | ||
|first4 = Lukasz |
|first4 = Lukasz |
||
|first5 = Michael J. |
|first5 = Michael J. |
||
|first6 = Mohamed}}</ref> Meanwhile, a two-dimensional Dress–Delaney enumerator generating reticulations of two |
|first6 = Mohamed}}</ref> Meanwhile, a two-dimensional Dress–Delaney enumerator generating reticulations of two-dimensional [[Hyperbolic geometry|hyperbolic space]] that is surgically dissected and wrapped around a [[Triply periodic minimal surface|triply periodic]] [[minimal surface]] such as the [[Gyroid]], [[Schwarz minimal surface|Diamond or Primitive]], has generated many novel crystal nets.<ref>{{Citation |
||
| |
|last1 = Ramsden |
||
| |
|first1 = S.J. |
||
|last2 = Robins |
|last2 = Robins |
||
|first2 = V. |
|first2 = V. | author2-link = Vanessa Robins |
||
|last3 = Hyde |
|last3 = Hyde |
||
|first3 = S. |
|first3 = S. |
||
Line 182: | Line 225: | ||
|pmid = 19225190 |
|pmid = 19225190 |
||
|issue = Pt 2 |
|issue = Pt 2 |
||
|postscript = . |
|postscript = .|bibcode = 2009AcCrA..65...81R |
||
|doi-access = free |
|||
}}</ref> |
|||
<ref>{{Citation |
<ref>{{Citation |
||
|title = EPINET: Euclidean Patterns in Non-Euclidean Tilings |
|title = EPINET: Euclidean Patterns in Non-Euclidean Tilings |
||
Line 190: | Line 235: | ||
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.<ref>{{Citation |
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.<ref>{{Citation |
||
| |
|last1 = Treacy |
||
| |
|first1 = M.M. J. |
||
|last2 = Rivin |
|last2 = Rivin |
||
|first2 = I. |
|first2 = I. |
||
Line 210: | Line 255: | ||
|doi = 10.1016/j.micromeso.2004.06.013 |
|doi = 10.1016/j.micromeso.2004.06.013 |
||
|postscript = .}}</ref> |
|postscript = .}}</ref> |
||
Other programs have been developed that similarly generate copies of an initial fragment and glue them into a periodic graph |
Other programs have been developed that similarly generate copies of an initial fragment and glue them into a periodic graph<ref>{{Citation |
||
|last = LeBail |
|last = LeBail |
||
|first = A. |
|first = A. |
||
|journal = J. |
|journal = J. Appl. Crystallogr. |
||
|volume = 38 |
|volume = 38 |
||
|pages = |
|pages = 389–395 |
||
|year = 2005 |
|year = 2005 |
||
|doi = 10.1107/S0021889805002384 |
|doi = 10.1107/S0021889805002384 |
||
|title = Inorganic structure prediction with GRINSP |
|title = Inorganic structure prediction with GRINSP |
||
|issue = 2 |
|issue = 2|doi-access = free |
||
}}</ref> |
|||
==See also== |
|||
*[[Periodic Graphs (Crystallography)|Periodic graphs]] as models of crystals for design. |
|||
==References== |
==References== |
||
{{Reflist|colwidth=25em}} |
{{Reflist|colwidth=25em}} |
||
== |
==Further reading== |
||
*[[Periodic Graphs (Crystallography)|Periodic graphs]] as models of crystals for design. |
|||
*{{Citation |
*{{Citation |
||
| |
|last1 = Conway |
||
| |
|first1 = J. H. |
||
|authorlink = John Horton Conway |
|authorlink = John Horton Conway |
||
|last2 = Burgiel |
|last2 = Burgiel |
||
Line 238: | Line 286: | ||
|year = 2008}} |
|year = 2008}} |
||
*{{Citation |
*{{Citation |
||
| |
|last1 = Kotani |
||
| |
|first1 = M. |
||
|last2 = Sunada |
|last2 = Sunada |
||
|first2 = T. |
|first2 = T. |
||
Line 245: | Line 293: | ||
|journal = Comm. Math. Phys. |
|journal = Comm. Math. Phys. |
||
|volume = 209 |
|volume = 209 |
||
|issue = 3 |
|||
|pages = 633–670 |
|pages = 633–670 |
||
|year = 2000 |
|year = 2000 |
||
|doi=10.1007/s002200050033|bibcode = 2000CMaPh.209..633K |
|||
|s2cid = 121065949 |
|||
}} |
|||
*{{Citation |
*{{Citation |
||
| |
|last1 = Kotani |
||
| |
|first1 = M. |
||
|last2 = Sunada |
|last2 = Sunada |
||
|first2 = T. |
|first2 = T. |
||
|title = Heat Kernels and Analysis on Manifolds, Graphs, and Metric Spaces |
|||
|title = Spectral geometry of crystal lattices |
|||
|chapter = Spectral geometry of crystal lattices |
|||
|journal = Contemporary Math. |
|||
|series = Contemporary Mathematics |
|||
|volume = 338 |
|volume = 338 |
||
|pages = 271–305 |
|pages = 271–305 |
||
|year = 2003 |
|year = 2003 |
||
|doi=10.1090/conm/338/06077 |
|||
|isbn = 9780821833834 |
|||
|doi-access = free |
|||
}} |
|||
*{{Citation |
*{{Citation |
||
| |
|last1 = Kazami |
||
| |
|first1 = T. |
||
|last2 = Uchiyama |
|last2 = Uchiyama |
||
|first2 = K. |
|first2 = K. |
||
|title = Random walks on periodic graphs |
|title = Random walks on periodic graphs |
||
|journal = |
|journal = Transactions of the American Mathematical Society |
||
|volume = 360 |
|volume = 360 |
||
|pages = 6065–6087 |
|pages = 6065–6087 |
||
|year = 2008 |
|year = 2008 |
||
|url = http://www.ams.org/journals/tran/2008-360-11/S0002-9947-08-04451-6/home.html |
|||
|accessdate = August 15, 2010 |
|||
|doi = 10.1090/S0002-9947-08-04451-6 |
|doi = 10.1090/S0002-9947-08-04451-6 |
||
|issue = 11 |
|issue = 11 |
||
|postscript = . |
|postscript = .|doi-access = free |
||
}} |
|||
*{{Citation |
|||
|last = Sunada |
|||
|first = T. |
|||
|title = Topological Crystallography, With a View Towards Discrete Geometric Analysis |
|||
|publisher = Springer 2013, ISBN: 978-4-431-54176-9 (Print) 978-4-431-54177-6 (Online) |
|||
}} |
|||
[[Category:Geometric graphs]] |
[[Category:Geometric graphs]] |
Latest revision as of 15:18, 16 December 2024
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
[edit]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
[edit]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
[edit]Much of the theoretical investigation of periodic graphs has focused on the problems of generating and classifying them.
Classification problems
[edit]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 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. 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
[edit]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]
See also
[edit]- Periodic graphs as models of crystals for design.
References
[edit]- ^ 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, ISBN 978-1-4613-3556-6
- ^ 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
Further reading
[edit]- Conway, J. H.; Burgiel, H.; Goodman-Strauss, C. (2008), The Symmetries of Things, A. K. Peters
- Kotani, M.; Sunada, T. (2000), "Albanese maps and an off diagonal long time asymptotic for the heat kernel", Comm. Math. Phys., 209 (3): 633–670, Bibcode:2000CMaPh.209..633K, doi:10.1007/s002200050033, S2CID 121065949
- Kotani, M.; Sunada, T. (2003), "Spectral geometry of crystal lattices", Heat Kernels and Analysis on Manifolds, Graphs, and Metric Spaces, Contemporary Mathematics, vol. 338, pp. 271–305, doi:10.1090/conm/338/06077, ISBN 9780821833834
- Kazami, T.; Uchiyama, K. (2008), "Random walks on periodic graphs", Transactions of the American Mathematical Society, 360 (11): 6065–6087, doi:10.1090/S0002-9947-08-04451-6.