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.
H. S. M.Coxeter ( 1955 ) named this graph after Fritz Laves, who first wrote about it as a crystal structure in 1932. [1] [2] It has also been called the K4 crystal, [3] (10,3)-a network, [4] diamond twin, [5] triamond, [6] [7] and the srs net. [8] The regions of space nearest each vertex of the graph are congruent 17-sided polyhedra that tile space. Its edges lie on diagonals of the regular skew polyhedron, a surface with six squares meeting at each integer point of space.
Several crystalline chemicals have known or predicted structures in the form of the Laves graph. Thickening the edges of the Laves graph to cylinders produces a related minimal surface, the gyroid, which appears physically in certain soap film structures and in the wings of butterflies.
As Coxeter (1955) describes, the vertices of the Laves graph can be defined by selecting one out of every eight points in the three-dimensional integer lattice, and forming their nearest neighbor graph. Specifically, one chooses the points
and all the other points formed by adding multiples of four to these coordinates. The edges of the Laves graph connect pairs of points whose Euclidean distance from each other is the square root of two, , as the points of each pair differ by one unit in two coordinates, and are the same in the third coordinate. The edges meet at 120° angles at each vertex, in a flat plane. All pairs of vertices that are non-adjacent are farther apart, at a distance of at least from each other. The edges of the resulting geometric graph are diagonals of a subset of the faces of the regular skew polyhedron with six square faces per vertex, so the Laves graph is embedded in this skew polyhedron. [1]
It is possible to choose a larger set of one out of every four points of the integer lattice, so that the graph of distance- pairs of this larger set forms two mirror-image copies of the Laves graph, disconnected from each other, with all other pairs of points farther than apart. [9]
As an abstract graph, the Laves graph can be constructed as the maximal abelian covering graph of the complete graph . Being an abelian covering graph of means that the vertices of the Laves graph can be four-colored such that each vertex has neighbors of the other three colors and so that there are color-preserving symmetries taking any vertex to any other vertex with the same color. For the Laves graph in its geometric form with integer coordinates, these symmetries are translations that add even numbers to each coordinate (additionally, the offsets of all three coordinates must be congruent modulo four). When applying two such translations in succession, the net translation is irrespective of their order: they commute with each other, forming an abelian group. The translation vectors of this group form a three-dimensional lattice. Finally, being a maximal abelian covering graph means that there is no other covering graph of involving a higher-dimensional lattice. This construction justifies an alternative name of the Laves graph, the crystal. [10]
A maximal abelian covering graph can be constructed from any finite graph ; applied to , the construction produces the (abstract) Laves graph, but does not give it the same geometric layout. Choose a spanning tree of , let be the number of edges that are not in the spanning tree (in this case, three non-tree edges), and choose a distinct unit vector in for each of these non-tree edges. Then, fix the set of vertices of the covering graph to be the ordered pairs where is a vertex of and is a vector in . For each such pair, and each edge adjacent to in , make an edge from to where is the zero vector if belongs to the spanning tree, and is otherwise the basis vector associated with , and where the plus or minus sign is chosen according to the direction the edge is traversed. The resulting graph is independent of the chosen spanning tree, and the same construction can also be interpreted more abstractly using homology. [11]
Using the same construction, the hexagonal tiling of the plane is the maximal abelian covering graph of the three-edge dipole graph, and the diamond cubic is the maximal abelian covering graph of the four-edge dipole. The -dimensional integer lattice (as a graph with unit-length edges) is the maximal abelian covering graph of a graph with one vertex and self-loops. [10]
The unit distance graph on the three-dimensional integer lattice has a vertex for each lattice point; each vertex has exactly six neighbors. It is possible to remove some of the points from the lattice, so that each remaining point has exactly three remaining neighbors, and so that the induced subgraph of these points has no cycles shorter than ten edges. There are four ways to do this, one of which is isomorphic as an abstract graph to the Laves graph. However, its vertices are in different positions than the more-symmetric, conventional geometric construction. [12]
Another subgraph of the simple cubic net isomorphic to the Laves graph is obtained by removing half of the edges in a certain way. The resulting structure, called semi-simple cubic lattice, also has lower symmetry than the Laves graph itself. [13]
The Laves graph is a cubic graph, meaning that there are exactly three edges at each vertex. Every pair of a vertex and adjacent edge can be transformed into every other such pair by a symmetry of the graph, so it is a symmetric graph. More strongly, for every two vertices and , every one-to-one correspondence between the three edges incident to and the three edges incident to can be realized by a symmetry. However, the overall structure is chiral: no sequence of translations and rotations can make it coincide with its mirror image. [10] The symmetry group of the Laves graph is the space group . [13]
The girth of this structure is 10—the shortest cycles in the graph have 10 vertices—and 15 of these cycles pass through each vertex. [10] [1] [9] The numbers of vertices at distance 0, 1, 2, ... from any vertex (forming the coordination sequence of the Laves graph) are: [14]
If the surrounding space is partitioned into the regions nearest each vertex—the cells of the Voronoi diagram of this structure—these form heptadecahedra with 17 faces each. They are plesiohedra, polyhedra that tile space isohedrally. Experimenting with the structures formed by these polyhedra led physicist Alan Schoen to discover the gyroid minimal surface, [15] which is topologically equivalent to the surface obtained by thickening the edges of the Laves graph to cylinders and taking the boundary of their union. [16]
The Laves graph is the unique shortest triply-periodic network, in the following sense. Triply-periodic means repeating infinitely in all three dimensions of space, so a triply-periodic network is a connected geometric graph with a three-dimensional lattice of translational symmetries. A fundamental domain is any shape that can tile space with its translated copies under these symmetries. Any lattice has infinitely many choices of fundamental domain, of varying shapes, but they all have the same volume . One can also measure the length of the edges of the network within a single copy of the fundamental domain; call this number . Similarly to , does not depend on the choice of fundamental domain, as long as the domain boundary only crosses the edges, rather than containing parts of their length. The Laves graph has four symmetry classes of vertices (orbits), because the symmetries considered here are only translations, not the rotations needed to map these four classes into each other. Each symmetry class has one vertex in any fundamental domain, so the fundamental domain contains twelve half-edges, with total length . The volume of its fundamental domain is 32. From these two numbers, the ratio (a dimensionless quantity) is therefore . This is in fact the minimum possible value: All triply-periodic networks have
with equality only in the case of the Laves graph. [17]
A sculpture titled Bamboozle, by Jacobus Verhoeff and his son Tom Verhoeff, is in the form of a fragment of the Laves graph, with its vertices represented by multicolored interlocking acrylic triangles. It was installed in 2013 at the Eindhoven University of Technology. [18]
The Laves graph has been suggested as an allotrope of carbon, analogous to the more common graphene and graphite carbon structure which also have three bonds per atom at 120° angles. [3] [5] In graphene, adjacent atoms have the same bonding planes as each other, whereas in the Laves graph structure the bonding planes of adjacent atoms are twisted by an angle of approximately 70.5° around the line of the bond. However, this hypothetical carbon allotrope turns out to be unstable. [19]
The Laves graph may also give a crystal structure for boron, one which computations predict should be stable. [20] Other chemicals that may form this structure include SrSi2 (from which the "srs net" name derives) [8] and elemental nitrogen, [9] [20] as well as certain metal–organic frameworks [21] and cyclic hydrocarbons. [22]
The electronic band structure for the tight-binding model of the Laves graph has been studied, showing the existence of Dirac and Weyl points in this structure. [23] [24]
The structure of the Laves graph, and of gyroid surfaces derived from it, has also been observed experimentally in soap-water systems, and in the chitin networks of butterfly wing scales. [9]
A cuboctahedron is a polyhedron with 8 triangular faces and 6 square faces. A cuboctahedron has 12 identical vertices, with 2 triangles and 2 squares meeting at each, and 24 identical edges, each separating a triangle from a square. As such, it is a quasiregular polyhedron, i.e. an Archimedean solid that is not only vertex-transitive but also edge-transitive. It is radially equilateral.
In geometry, a regular icosahedron is a convex polyhedron with 20 faces, 30 edges and 12 vertices. It is one of the five Platonic solids, and the one with the most faces.
In geometry, the rhombicuboctahedron, or small rhombicuboctahedron, is a polyhedron with eight triangular, six square, and twelve rectangular faces. There are 24 identical vertices, with one triangle, one square, and two rectangles meeting at each one. If all the rectangles are themselves square, it is an Archimedean solid. The polyhedron has octahedral symmetry, like the cube and octahedron. Its dual is called the deltoidal icositetrahedron or trapezoidal icositetrahedron, although its faces are not really true trapezoids.
In geometry, a tesseract is the four-dimensional analogue of the cube; the tesseract is to the cube as the cube is to the square. Just as the surface of the cube consists of six square faces, the hypersurface of the tesseract consists of eight cubical cells. The tesseract is one of the six convex regular 4-polytopes.
In mathematics, a root system is a configuration of vectors in a Euclidean space satisfying certain geometrical properties. The concept is fundamental in the theory of Lie groups and Lie algebras, especially the classification and representation theory of semisimple Lie algebras. Since Lie groups and Lie algebras have become important in many parts of mathematics during the twentieth century, the apparently special nature of root systems belies the number of areas in which they are applied. Further, the classification scheme for root systems, by Dynkin diagrams, occurs in parts of mathematics with no overt connection to Lie theory. Finally, root systems are important for their own sake, as in spectral graph theory.
In geometry, the truncated tetrahedron is an Archimedean solid. It has 4 regular hexagonal faces, 4 equilateral triangle faces, 12 vertices and 18 edges. It can be constructed by truncating all 4 vertices of a regular tetrahedron at one third of the original edge length.
In geometry, the truncated octahedron is the Archimedean solid that arises from a regular octahedron by removing six pyramids, one at each of the octahedron's vertices. The truncated octahedron has 14 faces, 36 edges, and 24 vertices. Since each of its faces has point symmetry the truncated octahedron is a 6-zonohedron. It is also the Goldberg polyhedron GIV(1,1), containing square and hexagonal faces. Like the cube, it can tessellate 3-dimensional space, as a permutohedron.
In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.
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 crystallographic restriction theorem in its basic form was based on the observation that the rotational symmetries of a crystal are usually limited to 2-fold, 3-fold, 4-fold, and 6-fold. However, quasicrystals can occur with other diffraction pattern symmetries, such as 5-fold; these were not discovered until 1982 by Dan Shechtman.
In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.
In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen graph G(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.
In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G. A covering map f is a surjection and a local isomorphism: the neighbourhood of a vertex v in C is mapped bijectively onto the neighbourhood of in G.
In geometry, a parallelohedron is a polyhedron that can be translated without rotations in 3-dimensional Euclidean space to fill space with a honeycomb in which all copies of the polyhedron meet face-to-face. There are five types of parallelohedron, first identified by Evgraf Fedorov in 1885 in his studies of crystallographic systems: the cube, hexagonal prism, rhombic dodecahedron, elongated dodecahedron, and truncated octahedron.
In mathematics, a Bratteli diagram is a combinatorial structure: a graph composed of vertices labelled by positive integers ("level") and unoriented edges between vertices having levels differing by one. The notion was introduced by Ola Bratteli in 1972 in the theory of operator algebras to describe directed sequences of finite-dimensional algebras: it played an important role in Elliott's classification of AF-algebras and the theory of subfactors. Subsequently Anatoly Vershik associated dynamical systems with infinite paths in such graphs.
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.
A Euclidean graph is periodic if there exists a basis of that Euclidean space whose corresponding translations induce symmetries of that graph. Equivalently, a periodic Euclidean graph is a periodic realization of an abelian covering graph over a finite graph. 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 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.
In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.
In geometry, Keller's conjecture is the conjecture that in any tiling of n-dimensional Euclidean space by identical hypercubes, there are two hypercubes that share an entire (n − 1)-dimensional face with each other. For instance, in any tiling of the plane by identical squares, some two squares must share an entire edge, as they do in the illustration.
In crystallography and the theory of infinite vertex-transitive graphs, the coordination sequence of a vertex is an integer sequence that counts how many vertices are at each possible distance from . That is, it is a sequence