EPPA for two-graphs and antipodal metric spaces

Evans, David; Hubička, Jan; Konečný, Matěj; Nešetřil, Jaroslav

doi:10.1090/proc/14872

EPPA for two-graphs and antipodal metric spaces
HTML articles powered by AMS MathViewer

by David M. Evans, Jan Hubička, Matěj Konečný and Jaroslav Nešetřil PDF

Proc. Amer. Math. Soc. 148 (2020), 1901-1915 Request permission

Abstract:

We prove that the class of finite two-graphs has the extension property for partial automorphisms (EPPA, or Hrushovski property), thereby answering a question of Macpherson. In other words, we show that the class of graphs has the extension property for switching automorphisms. We present a short, self-contained, purely combinatorial proof which also proves EPPA for the class of integer-valued antipodal metric spaces of diameter 3, answering a question of Aranda et al.

The class of two-graphs is an important new example which behaves differently from all the other known classes with EPPA: Two-graphs do not have the amalgamation property with automorphisms (APA), their Ramsey expansion has to add a graph, it is not known if they have coherent EPPA, and even EPPA itself cannot be proved using the Herwig–Lascar theorem.

References

Daniela Amato, Gregory Cherlin, and Dugald Macpherson, Metrically homogeneous graphs of diameter three, preprint, 2016.
Andres Aranda, David Bradley-Williams, Jan Hubička, Miltiadis Karamanlis, Michael Kompatscher, Matěj Konečný, and Micheal Pawliuk, Ramsey expansions of metrically homogeneous graphs, Submitted, arXiv:1707.02612, 2017.
Peter J. Cameron, Permutation groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999. MR 1721031, DOI 10.1017/CBO9780511623677
Gregory Cherlin, Homogeneous ordered graphs and metrically homogeneous graphs, In preparation, December 2017.
Gabriel Conant, Extending partial isometries of generalized metric spaces, Fund. Math. 244 (2019), no. 1, 1–16. MR 3874663, DOI 10.4064/fm484-9-2018
David M. Evans, Jan Hubička, and Jaroslav Nešetřil, Ramsey properties and extending partial automorphisms for classes of finite structures, To appear in Fundamenta Mathematicae, arXiv:1705.02379, 2017.
Jon Folkman, Graphs with monochromatic complete subgraphs in every edge coloring, SIAM J. Appl. Math. 18 (1970), 19–24. MR 268080, DOI 10.1137/0118004
Bernhard Herwig, Extending partial isomorphisms on finite structures, Combinatorica 15 (1995), no. 3, 365–371. MR 1357282, DOI 10.1007/BF01299742
Bernhard Herwig, Extending partial isomorphisms for the small index property of many $\omega$-categorical structures, Israel J. Math. 107 (1998), 93–123. MR 1658539, DOI 10.1007/BF02764005
Bernhard Herwig and Daniel Lascar, Extending partial automorphisms and the profinite topology on free groups, Trans. Amer. Math. Soc. 352 (2000), no. 5, 1985–2021. MR 1621745, DOI 10.1090/S0002-9947-99-02374-0
Wilfrid Hodges, Ian Hodkinson, Daniel Lascar, and Saharon Shelah, The small index property for $\omega$-stable $\omega$-categorical structures and for the random graph, J. London Math. Soc. (2) 48 (1993), no. 2, 204–218. MR 1231710, DOI 10.1112/jlms/s2-48.2.204
Ian Hodkinson, Finite model property for guarded fragments, slides available at http://www.cllc.vuw.ac.nz/LandCtalks/imhslides.pdf, 2002.
Ian Hodkinson and Martin Otto, Finite conformal hypergraph covers and Gaifman cliques in finite structures, Bull. Symbolic Logic 9 (2003), no. 3, 387–405. MR 2005955, DOI 10.2178/bsl/1058448678
Ehud Hrushovski, Extending partial isomorphisms of graphs, Combinatorica 12 (1992), no. 4, 411–416. MR 1194731, DOI 10.1007/BF01305233
Jan Hubička, Matěj Konečný, and Jaroslav Ne et il, A combinatorial proof of the extension property for partial isometries, Comment. Math. Univ. Carolin. 60 (2019), no. 1, 39–47. MR 3946663, DOI 10.14712/1213-7243.2015.275
Jan Hubička, Matěj Konečný, and Jaroslav Nešetřil, Semigroup-valued metric spaces: Ramsey expansions and EPPA, In preparation, 2018.
Jan Hubička and Jaroslav Nešetřil, All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms), Advances in Mathematics 356C (2019), 106791.
A. S. Kechris, V. G. Pestov, and S. Todorcevic, Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups, Geom. Funct. Anal. 15 (2005), no. 1, 106–189. MR 2140630, DOI 10.1007/s00039-005-0503-1
Matěj Konečný, Semigroup-valued metric spaces, Master’s thesis, Charles University, 2019, arXiv:1810.08963.
Matěj Konečný, Extending partial isometries of antipodal graphs, Discrete Mathematics (2019), 111633, https://doi.org/10.1016/j.disc.2019.111633.
Jaroslav Ne et il, For graphs there are only four types of hereditary Ramsey classes, J. Combin. Theory Ser. B 46 (1989), no. 2, 127–132. MR 992986, DOI 10.1016/0095-8956(89)90038-5
Jaroslav Ne et il, Ramsey classes and homogeneous structures, Combin. Probab. Comput. 14 (2005), no. 1-2, 171–189. MR 2128088, DOI 10.1017/S0963548304006716
Jaroslav Ne et il and Vojtěch Rödl, Partitions of vertices, Comment. Math. Univ. Carolinae 17 (1976), no. 1, 85–95. MR 412044
Jaroslav Ne et il and Vojtěch Rödl, A structural generalization of the Ramsey theorem, Bull. Amer. Math. Soc. 83 (1977), no. 1, 127–128. MR 422035, DOI 10.1090/S0002-9904-1977-14212-2
Jaroslav Ne et il and Vojtěch Rödl, Partitions of finite relational and set systems, J. Combinatorial Theory Ser. A 22 (1977), no. 3, 289–312. MR 437351, DOI 10.1016/0097-3165(77)90004-8
Lionel Nguyen Van Thé, A survey on structural Ramsey theory and topological dynamics with the Kechris-Pestov-Todorcevic correspondence in mind, Zb. Rad. (Beogr.) 17(25) (2015), no. Selected topics in combinatorial analysis, 189–207. MR 3362231
Martin Otto, Amalgamation and symmetry: From local to global consistency in the finite, arXiv:1709.00031 (2017).
J. J. Seidel, A survey of two-graphs, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 481–511 (English, with Italian summary). MR 0550136
Daoud Siniora, Automorphism groups of homogeneous structures, Ph.D. thesis, University of Leeds, March 2017.
Daoud Siniora and Sławomir Solecki, Coherent extension of partial automorphisms, free amalgamation, and automorphism groups, The Journal of Symbolic Logic (2019).
Sławomir Solecki, Extending partial isometries, Israel J. Math. 150 (2005), 315–331. MR 2255813, DOI 10.1007/BF02762385
Sławomir Solecki, Notes on a strengthening of the Herwig–Lascar extension theorem, Unpublished note, 2009.
Simon Thomas, Reducts of the random graph, J. Symbolic Logic 56 (1991), no. 1, 176–181. MR 1131738, DOI 10.2307/2274912
A. M. Vershik, Globalization of the partial isometries of metric spaces and local approximation of the group of isometries of Urysohn space, Topology Appl. 155 (2008), no. 14, 1618–1626. MR 2435153, DOI 10.1016/j.topol.2008.03.007