View source for Laves graph

{{Short description|Periodic spatial graph}}
{{Use list-defined references|date=August 2022}}
[[File:K 4 crystal.JPG|thumb|300px|The Laves graph]]
In [[Geometry|geometry]] and [[Physics:Crystallography|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 (geometry)|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|fundamental domain]]. One arrangement of the Laves graph uses one out of every eight of the points in the [[Integer lattice|integer lattice]] as its points, and connects all pairs of these points that are nearest neighbors, at distance <math>\sqrt2</math>. It can also be defined, divorced from its geometry, as an abstract undirected graph, a [[Covering graph|covering graph]] of the [[Complete graph|complete graph]] on four vertices.

{{harvs|first=H. S. M.|last=Coxeter|year=1955|txt}} named this graph after Fritz Laves, who first wrote about it as a [[Chemistry:Crystal structure|crystal structure]] in 1932.{{r|coxeter|laves}} It has also been called the '''''K''<sub>4</sub> crystal''',{{r|prl09}} '''(10,3)-a network''',{{r|wells}} '''diamond twin''',{{r|tlnkk}} '''triamond''',{{r|lanier|sequin}} and the '''srs net'''.{{r|doy}} 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|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|minimal surface]], the [[Gyroid|gyroid]], which appears physically in certain soap film structures and in the wings of butterflies.

==Constructions==

===From the integer grid===
[[File:Petrie-1.gif|thumb|240px|The [[Regular skew polyhedron|regular skew polyhedron]] onto which the Laves graph can be inscribed. The edges of the Laves graph are diagonals of some of the squares of this polyhedral surface.]]
As {{harvtxt|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|integer lattice]], and forming their [[Nearest neighbor graph|nearest neighbor graph]]. Specifically, one chooses the points
<math display=block>
\begin{align}(0,0,0),\quad (1,2,3),\quad (2,3,1),\quad (3,1,2),\\
(2,2,2),\quad (3,0,1),\quad (0,1,3),\quad (1,3,0),\\
\end{align}</math>
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, <math>\sqrt{2}</math>, 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 <math>\sqrt{6}</math> from each other. The edges of the resulting geometric graph are [[Diagonal|diagonal]]s of a subset of the faces of the [[Regular skew polyhedron|regular skew polyhedron]] with six square faces per vertex, so the Laves graph is [[Graph embedding|embedded]] in this skew polyhedron.{{r|coxeter}}

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-<math>\sqrt{2}</math> 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 <math>\sqrt{2}</math> apart.{{r|elusive}}

===As a covering graph===
As an abstract graph, the Laves graph can be constructed as the maximal [[Abelian group|abelian]] [[Covering graph|covering graph]] of the [[Complete graph|complete graph]] <math>K_4</math>. Being an abelian covering graph of <math>K_4</math> 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 [[Translation (geometry)|translation]]s 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|abelian group]]. The translation vectors of this group form a three-dimensional [[Lattice (group)|lattice]]. Finally, being a maximal abelian covering graph means that there is no other covering graph of <math>K_4</math> involving a higher-dimensional lattice. This construction justifies an alternative name of the Laves graph, the <math>K_4</math> crystal.{{r|sunada}}

A maximal abelian covering graph can be constructed from any finite graph <math>G</math>; applied to <math>K_4</math>, the construction produces the (abstract) Laves graph, but does not give it the same geometric layout. Choose a [[Spanning tree|spanning tree]] of <math>G</math>, let <math>d</math> 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|unit vector]] in <math>\mathbb{Z}^d</math> for each of these non-tree edges. Then, fix the set of vertices of the covering graph to be the ordered pairs <math>(v,w)</math> where <math>v</math> is a vertex of <math>G</math> and <math>w</math> is a vector in <math>\mathbb{Z}^d</math>. For each such pair, and each edge <math>uv</math> adjacent to <math>v</math> in <math>G</math>, make an edge from <math>(v, w)</math> to <math>(u,w\plusmn\epsilon)</math> where <math>\epsilon</math> is the zero vector if <math>uv</math> belongs to the spanning tree, and is otherwise the basis vector associated with <math>uv</math>, 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 (mathematics)|homology]].{{r|biggs}}

Using the same construction, the [[Hexagonal tiling|hexagonal tiling]] of the plane is the maximal abelian covering graph of the three-edge [[Dipole graph|dipole graph]], and the [[Diamond cubic|diamond cubic]] is the maximal abelian covering graph of the four-edge dipole. The <math>d</math>-dimensional integer lattice (as a graph with unit-length edges) is the maximal abelian covering graph of a graph with one vertex and <math>d</math> self-loops.{{r|sunada}}

===As a unit distance graph===
The [[Unit distance graph|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|induced subgraph]] of these points has no cycles shorter than ten edges. There are four ways to do this, one of which is [[Graph isomorphism|isomorphic]] as an abstract graph to the Laves graph. However, its vertices are in different positions than the more-symmetric, conventional geometric construction.{{r|haugland}}

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.{{r|kuzmin}}

==Properties==
The Laves graph is a [[Cubic graph|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|symmetric graph]]. More strongly, for every two vertices <math>u</math> and <math>v</math>, every one-to-one correspondence between the three edges incident to <math>u</math> and the three edges incident to <math>v</math> can be realized by a symmetry. However, the overall structure is [[Chirality|chiral]]: no sequence of translations and rotations can make it coincide with its mirror image.{{r|sunada}} The symmetry group of the Laves graph is the [[Space group|space group]] <math>I4_132</math>.{{r|kuzmin}}

The [[Girth (graph theory)|girth]] of this structure is 10—the shortest cycles in the graph have 10 vertices—and 15 of these cycles pass through each vertex.{{r|sunada|coxeter|elusive}} The numbers of vertices at distance 0, 1, 2, ... from any vertex (forming the [[Coordination sequence|coordination sequence]] of the Laves graph) are:{{r|oeis}}
{{bi|left=1.6|1, 3, 6, 12, 24, 35, 48, 69, 86, 108, 138, 161, 192, 231, ... {{OEIS|A038620}}.|right=}}

{{multiple image|image1=12-3 plesiohedron.png|width1=240|image2=12-3 plesioh-ani.gif|width2=190|footer=Cells of the [[Voronoi diagram]] of the Laves graph}}
If the surrounding space is partitioned into the regions nearest each vertex—the cells of the [[Voronoi diagram]] of this structure—these form [[Heptadecahedron|heptadecahedra]] with 17 faces each. They are [[Plesiohedron|plesiohedra]], polyhedra that tile space isohedrally. Experimenting with the structures formed by these polyhedra led physicist [[Biography:Alan Schoen|Alan Schoen]] to discover the [[Gyroid|gyroid]] [[Minimal surface|minimal surface]],{{r|schoen}} which is topologically equivalent to the surface obtained by thickening the edges of the Laves graph to cylinders and taking the [[Boundary (topology)|boundary]] of their union.{{r|baez}}

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|fundamental domain]] is any shape that can [[Honeycomb (geometry)|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 [[Physics:Volume|volume]] <math>V</math>. One can also measure the length of the edges of the network within a single copy of the fundamental domain; call this number <math>L</math>. Similarly to <math>V</math>, <math>L</math> 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 <math>6\sqrt2</math>. The volume of its fundamental domain is 32. From these two numbers, the ratio <math>L^3/V</math> (a [[Physics:Dimensionless quantity|dimensionless quantity]]) is therefore <math>27/\sqrt2</math>. This is in fact the minimum possible value: All triply-periodic networks have <math display=block>\frac{L^3}{V}\ge \frac{27}{\sqrt2},</math> with equality only in the case of the Laves graph.{{r|shortest}}

==Physical examples==
[[File:Laves graph STL.stl|thumb|3D model of part of the Laves graph]]

===Art===
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 [[Organization:Eindhoven University of Technology|Eindhoven University of Technology]].{{r|bamboozle}} 

===Molecular crystals===
The Laves graph has been suggested as an allotrope of carbon, analogous to the more common [[Physics:Graphene|graphene]] and [[Chemistry:Graphite|graphite]] carbon structure which also have three bonds per atom at 120° angles.{{r|prl09|tlnkk}} 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.{{r|lzc}}

The Laves graph may also give a [[Chemistry:Allotropes of boron|crystal structure for boron]], one which computations predict should be stable.{{r|boron}} Other chemicals that may form this structure include SrSi<sub>2</sub> (from which the "srs net" name derives){{r|doy}} and elemental [[Chemistry:Nitrogen|nitrogen]],{{r|elusive|boron}} as well as certain metal–organic frameworks{{r|metorg}} and [[Physics:Cyclic compound|cyclic]] [[Chemistry:Hydrocarbon|hydrocarbon]]s.{{r|mincage}}

The [[Physics:Electronic band structure|electronic band structure]] for the tight-binding model of the Laves graph has been studied, showing the existence of [[Physics:Dirac cone|Dirac and Weyl points]] in this structure.{{r|kkwk|tsuchiizu}}

===Other===
The structure of the Laves graph, and of [[Gyroid|gyroid]] surfaces derived from it, has also been observed experimentally in soap-water systems, and in the [[Chemistry:Chitin|chitin]] networks of [[Biology:Butterfly|butterfly]] wing scales.{{r|elusive}}

==References==
{{reflist|refs=

<ref name=baez>{{citation|url=http://blogs.ams.org/visualinsight/2016/10/15/laves-graph/|title=Laves Graph|work=Visual Insight|publisher=American Mathematical Society|first=John|last=Baez|date=October 14, 2016}}</ref>

<ref name=bamboozle>{{citation
 | last1 = Verhoeff | first1 = Tom
 | editor2-last = Sarhangi | editor2-first = Reza
 | contribution = Folded strips of rhombuses and a plea for the <math>\sqrt{2}:1</math> rhombus
 | contribution-url = https://archive.bridgesmathart.org/2013/bridges2013-71.html
 | isbn = 978-1-938664-06-9
 | location = Phoenix, Arizona
 | pages = 71–78
 | publisher = Tessellations Publishing
 | title = Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture
 | year = 2013}}; see also {{citation|url=https://www.win.tue.nl/bamboozle/|title=Bamboozle: A Mathematical Artwork in MetaForum|publisher=Foundation MathArt Koos Verhoeff|access-date=2022-08-20}}</ref>

<ref name=biggs>{{citation
 | doi = 10.1112/jlms/s2-30.1.1
 | issue = 1
 | journal = Journal of the London Mathematical Society
 | mr = 760867
 | pages = 1–14
 | series = Second Series
 | title = Homological coverings of graphs
 | volume = 30
 | year = 1984}}</ref>

<ref name=boron>{{citation
 | last1 = Dai | first1 = Jun
 | last2 = Li | first2 = Zhenyu
 | last3 = Yang | first3 = Jinlong
 | doi = 10.1039/C0CP00735H
 | pmid = 20820588
 | journal = Physical Chemistry Chemical Physics
 | pages = 12420–12422
 | title = Boron ''K''<sub>4</sub> crystal: a stable chiral three-dimensional sp<sup>2</sup> network
 | volume = 12
 | issue = 39
 | year = 2010| bibcode = 2010PCCP...1212420D
 }}</ref>

<ref name=coxeter>{{citation
 | doi = 10.4153/CJM-1955-003-7
 | journal = [[Canadian Journal of Mathematics]]
 | mr = 0067508
 | pages = 18–23
 | title = On Laves' graph of girth ten
 | volume = 7
 | year = 1955| s2cid = 124804911 | doi-access = free
 }}</ref>

<ref name=doy>{{citation
 | last1 = Delgado Friedrichs | first1 = Olaf
 | last2 = O'Keeffe | first2 = Michael
 | last3 = Yaghi | first3 = Omar M.
 | date = December 2002
 | doi = 10.1107/s0108767302018494
 | issue = 1
 | journal = Acta Crystallographica Section A: Foundations of Crystallography
 | pages = 22–27
 | title = Three-periodic nets and tilings: regular and quasiregular nets
 | url = https://www.chem.ucla.edu/dept/Faculty/yaghi/pubs/2003-2004/actacrystA03-pg22.pdf
 | volume = 59| pmid = 12496458
 | hdl = 2027.42/115935
 }}</ref>

<ref name=elusive>{{citation
 | last2 = O'Keeffe | first2 = Michael
 | last3 = Proserpio | first3 = Davide M.
 | doi = 10.1002/anie.200801519
 | issue = 42
 | journal = Angewandte Chemie International Edition
 | pages = 7996–8000
 | title = A short history of an elusive yet ubiquitous structure in chemistry, materials, and mathematics
 | url = http://people.physics.anu.edu.au/~sth110/Angew_Chem_Int_Ed_srs.pdf
 | volume = 47
 | year = 2008 | pmid=18767088}}</ref>

<ref name=haugland>{{citation
 | last1 = Haugland | first1 = Jan Kristian
 | journal = Journal of Graph Theory
 | doi = 10.1002/jgt.10071
 | mr = 1943105 
 | pages = 34–60
 | title = Classification of certain subgraphs of the 3-dimensional grid
 | volume = 42
 | year = 2003| s2cid = 247671824
 }}</ref>

<ref name=kkwk>{{citation |last1=Kaufmann |first1=Ralph M. |last2=Khlebnikov |first2=Sergei |last3=Wehefritz-Kaufmann |first3=Birgit |title=Singularities, swallowtails and Dirac points: an analysis for families of Hamiltonians and applications to wire networks, especially the gyroid |journal=[[Physics:Annals of Physics|Annals of Physics]] |date=2012 |volume=327 |issue=11 |pages=2865–2884 |doi=10.1016/j.aop.2012.08.001|arxiv=1208.3262 |bibcode=2012AnPhy.327.2865K |s2cid=14972547 }}</ref>

<ref name=kuzmin>{{citation
 | last1 = Kuz’min | first1 = M. D.
 | last2 = Kuzian | first2 = R. O.
 | last3 = Richter | first3 = J.
 | journal = The European Physical Journal Plus
 | title = Ferromagnetism of the semi-simple cubic lattice
 | year = 2020| volume = 135 | page = 750 | doi = 10.1140/epjp/s13360-020-00722-z }}.</ref>

<ref name=lanier>{{citation
 | journal = American Scientist
 | title = From planar patterns to polytopes
 | url = http://www.americanscientist.org/bookshelf/pub/from-planar-patterns-to-polytopes
 | year = 2009| volume = 97 | page = 73 | doi = 10.1511/2009.76.73 }}.</ref>

<ref name=laves>{{citation
 | doi = 10.1524/zkri.1932.82.1.1
 | issue = 1
 | journal = Zeitschrift für Kristallographie
 | pages = 1–14
 | title = Zur Klassifikation der Silikate. Geometrische Untersuchungen möglicher Silicium-Sauerstoff-Verbände als Verknüpfungsmöglichkeiten regulärer Tetraeder
 | volume = 82
 | year = 1932| s2cid = 101605313 }}</ref>

<ref name=lzc>{{citation |last1=Liang |first1=Y. |last2=Zhang |first2=W. |last3=Chen |first3=L. |title=Phase stabilities and mechanical properties of two new carbon crystals |journal=EPL |date=2009 |volume=87 |issue=5 |pages=56003 |doi=10.1209/0295-5075/87/56003|bibcode=2009EL.....8756003L |s2cid=119424557 }}</ref>

<ref name=metorg>{{citation
 | last1 = Yang | first1 = Hui
 | last2 = Li | first2 = Tie-hu
 | last3 = Wang | first3 = Fei
 | last4 = Zhang | first4 = Jian
 | date = February 2012
 | doi = 10.1016/j.inoche.2011.11.039
 | journal = Inorganic Chemistry Communications
 | pages = 86–88
 | title = Unusual heterometallic ZnMg(COO)<sub>3</sub> building blocks for the construction of a homochiral srs-type metal-organic framework
 | volume = 16}}</ref>

<ref name=mincage>{{citation
 | last1 = Fukunaga | first1 = Toshiya M.
 | last2 = Kato | first2 = Takahide
 | last3 = Ikemoto | first3 = Koki
 | last4 = Isobe | first4 = Hiroyuki
 | date = February 2022
 | doi = 10.1073/pnas.2120160119
 | issue = 7
 | journal = Proceedings of the National Academy of Sciences
 | title = A minimal cage of a diamond twin with chirality
 | volume = 119| pmid = 35131931
 | pmc = 8851511
 | bibcode = 2022PNAS..11920160F
 }}</ref>

<ref name=oeis>{{cite OEIS|mode=cs2|A038620|Growth function (or coordination sequence) of the infinite cubic graph corresponding to the srs net}}</ref>

<ref name=prl09>{{citation
 | last1 = Itoh | first1 = Masahiro
 | last3 = Naito | first3 = Hisashi
 | last5 = Kawazoe | first5 = Yoshiyuki
 | last6 = Adschiri | first6 = Tadafumi
 | doi = 10.1103/PhysRevLett.102.055703
 | pmid = 19257523
 | journal = [[Physics:Physical Review Letters|Physical Review Letters]]
 | page = 055703
 | title = New metallic carbon crystal
 | volume = 102
 | issue = 5
 | year = 2009| bibcode = 2009PhRvL.102e5703I
 }}</ref>

<ref name=schoen>{{citation
 | date = June–July 2008
 | issue = 6
 | journal = [[Organization:Notices of the American Mathematical Society|Notices of the American Mathematical Society]]
 | page = 663
 | title = On the graph (10,3)-a
 | url = https://www.ams.org/notices/200806/tx080600663p.pdf
 | volume = 55}}</ref>

<ref name=sequin>{{citation
 | editor1-last = Sarhangi | editor1-first = Reza
 | editor2-last = Séquin | editor2-first = Carlo H.
 | contribution = Intricate Isohedral Tilings of 3D Euclidean Space
 | isbn = 9780966520194
 | location = London
 | pages = 139–148
 | publisher = Tarquin Publications
 | title = Bridges Leeuwarden: Mathematics, Music, Art, Architecture, Culture
 | contribution-url = http://archive.bridgesmathart.org/2008/bridges2008-139.html
 | year = 2008}}</ref>

<ref name=shortest>{{citation
 | last1 = Alex | first1 = Jerome
 | last2 = Große-Brauckmann | first2 = Karsten
 | arxiv = 1705.02471
 | title = Periodic Steiner networks minimizing length
 | year = 2017}}; {{citation
 | last = Alex | first = Jerome
 | publisher = Technische Universität Darmstadt
 | title = The Periodic Steiner Problem
 | type = Doctoral dissertation
 | url = https://tuprints.ulb.tu-darmstadt.de/8538/
 | year = 2019}}</ref>

<ref name=sunada>{{citation
 | issue = 2
 | journal = [[Organization:Notices of the American Mathematical Society|Notices of the American Mathematical Society]]
 | mr = 2375022
 | pages = 208–215
 | title = Crystals that nature might miss creating
 | url = https://www.ams.org/notices/200802/tx080200208p.pdf
 | volume = 55
 | year = 2008}}; {{citation
 | last = Sunada | first = Toshikazu
 | issue = 3
 | journal = Notices of the American Mathematical Society
 | mr = 
 | pages = 343
 | title = Correction: Crystals that nature might miss creating
 | url = https://www.ams.org/journals/notices/200803/tx080300342p.pdf
 | volume = 55
 | year = 2008}}</ref>

<ref name=tlnkk>{{citation
 | last1 = Tagami | first1 = Makoto
 | last2 = Liang | first2 = Yunye
 | last3 = Naito | first3 = Hisashi
 | last4 = Kawazoe | first4 = Yoshiyuki
 | doi = 10.1016/j.carbon.2014.04.077
 | journal = Carbon
 | pages = 266–274
 | title = Negatively curved cubic carbon crystals with octahedral symmetry
 | volume = 76
 | year = 2014| doi-access = free
 }}</ref>

<ref name=tsuchiizu>{{citation |last=Tsuchiizu |first=Masahisa |title=Three-dimensional higher-spin Dirac and Weyl dispersions in the strongly isotropic {{math|''K''<sub>4</sub>}} crystal |journal=[[Physics:Physical Review B|Physical Review B]] |date=2016 |volume=94 |issue=19 |pages=195426 |doi=10.1103/PhysRevB.94.195426|arxiv=1609.09762 |bibcode=2016PhRvB..94s5426T |s2cid=119098343 }}</ref>

<ref name=wells>{{citation
 | doi = 10.1080/14786444008520702
 | issue = 199
 | pages = 103–134
 | journal = The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science
 | series=Series 7
 | title = X. Finite complexes in crystals: a classification and review
 | volume = 30
 | year = 1940}}</ref>

}}

==External links==
*{{citation
 | title = The (10, 3)-a Network
 | url = http://www.georgehart.com/rp/10-3.html}}.
*{{cite OEIS|mode=cs2|A046944|Number of self-avoiding walks of length n on the Laves graph}}
*{{cite OEIS|mode=cs2|A290705|Theta series of triamond}}

[[Category:Crystallography]]
[[Category:Infinite graphs]]
[[Category:Regular graphs]]

{{Sourceattribution|Laves graph}}