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:

1. It is uniformly discrete in that there exists e > 0 such that for any two distinct vertices, their distance apart is |u – v| > e.
2. 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.
3. Each vertex is of finite degree or valency.
4. 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]

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]