×

Metrically homogeneous graphs of diameter \(3\). (English) Zbl 1490.03020

The main result of this article is a classification of all countable, possibly finite, metrically homogeneous (undirected) graphs of diameter 3 where the metric under consideration is the graph metric. It is shown that each such graph belongs to one of 10 classes of graphs defined by certain parameters. It follows that there are only countably many metrically homogeneous graphs of diameter 3, up to isomorphism. A metrically homogeneous graph of diameter 2 is a connected (ultra)homogeneous graph and all such graphs have been classified by A. H. Lachlan and R. E. Woodrow [Trans. Am. Math. Soc. 262, 51–94 (1980; Zbl 0471.03025)]. The main result of this 106 pages article requires a long proof involving a detailed case analysis, but the introductory sections give a thorough discussion about the methodology, the structure of the proof, and previous and related work, in particular about (ultra)homogeneous structures, amalgamation classes and Ramsey theory.

MSC:

03C15 Model theory of denumerable and separable structures
03C10 Quantifier elimination, model completeness, and related topics
03C13 Model theory of finite structures
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05D10 Ramsey theory
05C12 Distance in graphs
20B22 Multiply transitive infinite groups
20B27 Infinite automorphism groups
03C65 Models of other mathematical theories

Citations:

Zbl 0471.03025

Software:

kepler98; Flyspeck
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Aranda, D. Bradley-Williams, J. Hubička, M. Karamanlis, M. Kompatscher, M. Konečný and M. Pawliuk, Ramsey expansions of metrically homogeneous graphs, preprint (2017), arXiv:1707.02612. · Zbl 1378.05122
[2] Atiyah, M., An interview with Michael Atiyah, Math. Intelligencer6 (1984) 9-19.
[3] Avigad, J., The mechanization of mathematics, Not. Amer. Math. Soc.65(6) (2018) 681-690. · Zbl 1398.68478
[4] Bannai, E. and Bannai, E., How many \(P\)-polynomial structures can an association scheme have?Eur. J. Combin.1 (1980) 289-298. · Zbl 0458.94047
[5] Bousquet, N., Lagoutte, A. and Thomassé, S., The Erdős-Hajnal conjecture for paths and antipaths, J. Combin. Theory Ser. B113 (2015) 261-264. · Zbl 1315.05077
[6] Braunfeld, S., The undecidability of joint embedding and joint homomorphism for hereditary graph classes, Disc. Math. Theore. Comput. Sci.21(2) (2019) 17.
[7] S. Braunfeld and P. Simon, The classification of homogeneous finite-dimensional permutation structures, preprint (2018), arXiv:1807.07110 [math.LO]. · Zbl 07165607
[8] A. Bundy (ed.), Discussion meeting issue “The nature of mathematical proof” organized by A. Bundy, M. Atiyah, A. Macintyre and D. Mackenzie, Philos. Trans. Roy. Soc. A: Math. Phys. Eng. Sci.363(1835) (2005) 2331-2461. Essays by D. MacKenzie, H. Barendregt, F. Wiedijk, A. Bundy, M. Aschbacher, P. J. Cohen, A. Macintyre, P. Swinnerton-Dyer and E. B. Davies. · Zbl 1152.03303
[9] Cameron, P., 6-transitive graphs, J. Combin. Theory Ser. B28 (1980) 68-179. · Zbl 0451.05038
[10] Cameron, P. J., Finite permutation groups and finite simple groups, Bull. London Math. Soc.13(1) (1981) 1-22. · Zbl 0463.20003
[11] Cameron, P., A census of infinite distance transitive graphs, Discrete Math.192 (1998) 11-26. · Zbl 0957.05114
[12] Cherlin, G., The classification of countable homogeneous directed graphs and countable homogeneous \(n\)-tournaments, Mem. Amer. Math. Soc.131(621) (1998) xiv+161 pp. · Zbl 0978.03029
[13] Cherlin, G., Infinite imprimitive homogeneous \(3\)-edge-colored complete graphs, J. Symbolic Logic64 (1999) 159-179. · Zbl 0932.03044
[14] Cherlin, G., Sporadic homogeneous structures, in The Gelfand Mathematical Seminars, 1996-1999, (Birkhäuser Boston, Boston, MA, 2000), pp. 15-48. · Zbl 0955.03040
[15] Cherlin, G., Two problems on homogeneous structures, revisited, in Model Theoretic Methods in Finite Combinatorics, Grohe, M. and Makowsky, J. A. (eds.), , Vol. 558 (American Mathematical Society, Providence, RI, 2011). · Zbl 1261.03115
[16] Cherlin, G., Forbidden substructures and combinatorial dichotomies: WQO and universality, Discrete Math.311(15) (2011) 1543-1584. · Zbl 1223.05131
[17] G. Cherlin, Homogeneous ordered graphs and metrically homogeneous graphs, preprint (2018).
[18] Cherlin, G. and Hrushovski, E., Finite Structures with Few Types, , Vol. 152 (Princeton University Press, Princeton, NJ, 2003), vi+193 pp. · Zbl 1024.03001
[19] Chudnovsky, M., The Erdős-Hajnal Conjecture — A Survey, J. Graph Theory75(2) (2014) 178-190. · Zbl 1280.05086
[20] Chudnovsky, M., Robertson, N., Seymour, P. and Thomas, R., Progress on perfect graphs, Math. Program. Ser. B97(1-2) (2003) 405-422. · Zbl 1028.05035
[21] Chudnovsky, M., Robertson, N., Seymour, P. and Thomas, R., The strong perfect graph theorem, Ann. Math. (2)164(1) (2006) 51-229. · Zbl 1112.05042
[22] Chudnovsky, M. and Safra, S., The Erdős-Hajnal conjecture for bull-free graphs, J. Combin. Theory Ser. B98(6) (2008) 1301-1310. · Zbl 1168.05317
[23] Cohn, H., Kumar, A., Miller, S. D., Radchenko, D. and Viazovska, M., The sphere packing problem in dimension 24, Ann. Math. (2)185(3) (2017) 1017-1033. · Zbl 1370.52037
[24] R. Coulson, Twists and twistability, preprint (2018), arXiv:1802.00467 [math.LO].
[25] D. M. Evans, J. Hubicka, M. Konecný and Y. Li, Simplicity of the automorphism groups of generalised metric spaces, preprint (2019), arXiv:1907.13204 [math.GR].
[26] Fraïssé, R., Sur l’extension aux relations de quelques propriétés des ordres, Ann. Ecole Normale Sup.7 (1954) 361-388. · Zbl 0057.04206
[27] A. Gardiner, Redrawing distance-regular graphs, unpublished manuscript (1980).
[28] Goldstern, M., Grossberg, R. and Kojman, M., Infinite homogeneous bipartite graphs with unequal sides, Discrete Math.149 (1996) 69-82. · Zbl 0843.05050
[29] Gorenstein, D., Classifying the finite simple groups, Bull. Amer. Math. Soc. \((\) N.S.\()14(1) (1986) 1-98\). · Zbl 0585.20003
[30] Hales, T. C., A proof of the Kepler conjecture, Ann. Math. (2)162(3) (2005) 1065-1185. · Zbl 1096.52010
[31] Hales, T. C., Dense Sphere Packings. A Blueprint for Formal Proofs, , Vol. 400 (Cambridge University Press, Cambridge, 2012), xiv+271 pp. · Zbl 1263.52001
[32] T. Hales, Big Conjecture, talk given July 10, 2017 at the Newton Institute, Cambridge University, http://www.newton.ac.uk/seminar/20170710100011001.
[33] Hales, T., Adams, M., Bauer, G., Dang, T. D., Harrison, J., Le Truong, H., Kaliszyk, C., Magron, V., McLauglin, S., Nguyen, T. T., Nguyen, Q. T., Nipkow, T., Obua, S., Pleso, J., Rute, J., Solovyev, A., Ta, T. H. A., Tran, N. T., Trieu, T. D., Vu, J. U. K. and Zumkeller, R., A formal proof of the Kepler conjecture, Forum Math. Pi5 (2017) e2, 29 pp.
[34] T. Hales and S. Ferguson, The Kepler Conjecture. The Hales-Ferguson Proof. Including Papers Reprinted from Discrete Comput. Geom.36(1) (2006), ed. J. C. Lagarias (Springer, New York, 2011), xiv \(+456\) pp.
[35] Henson, C. W., A family of countable homogeneous graphs, Pacific J. Math.38 (1971) 69-83. · Zbl 0204.24103
[36] Herwig, B. and Lascar, D., Extending partial automorphisms and the profinite topology on free groups, Trans. Amer. Math. Soc.352(5) (2000) 1985-2021. · Zbl 0947.20018
[37] Higman, G., Ordering by divisibility in abstract algebras, Proc. London Math. Soc.2 (1952) 326-336. https://doi.org/10.1112/plms/s3-2.1.326 · Zbl 0047.03402
[38] W.-Y. Hsiang, A rejoinder to T. C. Hales’s article: “The status of the Kepler conjecture” [Math. Intelligencer16(3) (1994) 47-58; MR1281754 (95g:52033)], Math. Intelligencer17(1) (1995) 35-42.
[39] J. Hubička, M. Kompatscher and M. Konečný, Forbidden cycles in metrically homogeneous graphs, preprint (2018), arXiv:1808.05177.
[40] J. Hubička, M. Konečný and J. Nešetřil, Semigroup-valued metric spaces: Ramsey expansions and EPPA, in preparation. · Zbl 1435.05238
[41] Hubička, J. and Nešetřil, J., Homomorphism and embedding universal structures for restricted classes, J. Mult.-Valued Logic Soft Comput.27 (2016) 229-253. · Zbl 1394.03058
[42] J. Hubička and J. Nešetřil, All those Ramsey classes, preprint (2016), arXiv:1606.07979 [math.CO] (v1:2016; v3:2019). · Zbl 1421.05091
[43] Hubička, J. and Nešetřil, J., All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms), Advances in Mathematics356 (2019) 106791. · Zbl 1421.05091
[44] Hušek, M., Urysohn universal space, its development and Hausdorff’s approach, Topol. Appl.155 (2008) 1493-1501. · Zbl 1159.54006
[45] Kechris, A. S., Pestov, V. G. and Todorcevic, S., Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups, Geom. Funct. Anal.15(1) (2005) 106-189. · Zbl 1084.54014
[46] Kechris, A. S. and Rosendal, C., Turbulence, amalgamation and generic automorphisms of homogeneous structures, Proc. London Math. Soc.94(2) (2007) 302-350. · Zbl 1118.03042
[47] Krantz, S. G., The Proof is in the Pudding. The Changing Nature of Mathematical Proof (Springer, New York, 2011), xviii+264 pp. · Zbl 1318.00005
[48] Lachlan, A. H., Countable homogeneous tournaments, Trans. Amer. Math. Soc.284(2) (1984) 431-461. · Zbl 0562.05025
[49] Lachlan, A. H., Homogeneous structures, in Proc. Int. Congr. Mathematicians, Vols. 1 and 2, Berkeley, CA, , 1986 (American Mathematical Society, Providence, RI, 1987), pp. 314-321.
[50] Lachlan, A. H., Stable finitely homogeneous structures: A survey, in Algebraic Model Theory, , Vol. 496 (Kluwer Academic Publishers, Dordrecht, 1997), pp. 145-159. · Zbl 0878.03024
[51] Lachlan, A. and Woodrow, R., Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc.262 (1980) 51-94. · Zbl 0471.03025
[52] Lovász, L., Graph minor theory, Bull. Amer. Math. Soc. (N.S.)43(1) (2006) 75-86. · Zbl 1082.05082
[53] Macpherson, H. D., Infinite distance transitive graphs of finite valency, Combinatorica2 (1982) 63-69. · Zbl 0492.05036
[54] Moss, L., Distanced graphs, Discrete Math.102 (1992) 287-305. · Zbl 0754.03028
[55] P. Simon, NIP \(\omega \)-categorical structures: The rank 1 case, preprint (2018), arXiv:1807.07102 [math.LO].
[56] Solecki, S., Extending partial isometries, Israel J. Math.150 (2005) 315-331. · Zbl 1124.54012
[57] Tits, J., Sur certaines classes d’espaces homogènes de groupes de Lie, Acad. Roy. Belg. Cl. Sci. Mém.29(3) (1955) 268 pp. · Zbl 0067.12301
[58] Urysohn, P., Sur un espace métrique universel (Note de Paul Urysohn), C. R. Hebd. Acad. Sci.180 (1925) 803-806. · JFM 51.0452.03
[59] Viazovska, M. S., The sphere packing problem in dimension 8, Ann. Math. (2)185(3) (2017) 991-1015. · Zbl 1373.52025
[60] Wang, Hs.-Ch., Two-point homogeneous spaces, Ann. Math.55 (1952) 177-191. · Zbl 0048.40503
[61] Wilson, R. A., Graphs, Colourings and the Four-Colour Theorem (Oxford University Press, Oxford, 2002), viii+141 pp. · Zbl 1007.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.