Coordination sequence

In crystallography and the theory of infinite vertex-transitive graphs, the coordination sequence of a vertex ${\displaystyle v}$ is an integer sequence that counts how many vertices are at each possible distance from ${\displaystyle v}$. That is, it is a sequence $${\displaystyle n_{0},n_{1},n_{2},\dots }$$ where each ${\displaystyle n_{i}}$ is the number of vertices that are ${\displaystyle i}$ steps away from ${\displaystyle v}$. If the graph is vertex-transitive, then the sequence is an invariant of the graph that does not depend on the specific choice of ${\displaystyle v}$. Coordination sequences can also be defined for sphere packings, by using either the contact graph of the spheres or the Delaunay triangulation of their centers, but these two choices may give rise to different sequences.[1][2]

A square grid, shaded by distance from the central blue point. The number of grid points at distance exactly ${\displaystyle i>0}$ is ${\displaystyle 4i}$, so the coordination sequence of the grid is the sequence of multiples of four, modified to start with one instead of zero.

As an example, in a square grid, for each positive integer ${\displaystyle i}$, there are ${\displaystyle 4i}$ grid points that are ${\displaystyle i}$ steps away from the origin. Therefore, the coordination sequence of the square grid is the sequence $${\displaystyle 1,4,8,12,16,20,\dots \ .}$$ in which, except for the initial value of one, each number is a multiple of four.[3]

The concept was proposed by Georg O. Brunner and Fritz Laves and later developed by Michael O'Keefe. The coordination sequences of many low-dimensional lattices[2][4] and uniform tilings are known.[5][6]

The coordination sequences of periodic structures are known to be quasi-polynomial.[7][8]

References

1. Brunner, G. O. (July 1979), "The properties of coordination sequences and conclusions regarding the lowest possible density of zeolites", Journal of Solid State Chemistry, 29 (1): 41–45, Bibcode:1979JSSCh..29...41B, doi:10.1016/0022-4596(79)90207-x
2. Conway, J. H.; Sloane, N. J. A. (November 1997), "Low-dimensional lattices. VII. Coordination sequences", Proceedings of the Royal Society A, 453 (1966): 2369–2389, Bibcode:1997RSPSA.453.2369C, doi:10.1098/rspa.1997.0126, MR 1480120, S2CID 120323174
3. Sloane, N. J. A. (ed.), "Sequence A008574", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
4. O'Keeffe, M. (January 1995), "Coordination sequences for lattices", Zeitschrift für Kristallographie – Crystalline Materials, 210 (12): 905–908, Bibcode:1995ZK....210..905O, doi:10.1524/zkri.1995.210.12.905
5. Goodman-Strauss, C.; Sloane, N. J. A. (January 2019), "A coloring-book approach to finding coordination sequences" (PDF), Acta Crystallographica Section A, 75 (1): 121–134, arXiv:1803.08530, doi:10.1107/s2053273318014481, MR 3896412, PMID 30575590, S2CID 4553572, archived from the original (PDF) on 2022-02-17, retrieved 2021-06-18
6. Shutov, Anton; Maleev, Andrey (2020), "Coordination sequences for lattices", Zeitschrift für Kristallographie – Crystalline Materials, 235: 157–166, doi:10.1515/zkri-2020-0002
7. Nakamura, Y.; Sakamoto, R.; Mase, T.; Nakagawa, J. (2021), "Coordination sequences of crystals are of quasi-polynomial type", Acta Crystallogr., A77 (2): 138–148, Bibcode:2021AcCry..77..138N, doi:10.1107/S2053273320016769, PMC 7941273, PMID 33646200
8. Kopczyński, Eryk (2022), "Coordination sequences of periodic structures are rational via automata theory", Acta Crystallogr., A78 (2): 155–157, arXiv:2307.15803, doi:10.1107/S2053273322000262, PMID 35230271