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
Additional Information
- David M. Evans
- Affiliation: Department of Mathematics, Imperial College London, London SW7 2AZ, United Kingdom
- MR Author ID: 222893
- Email: david.evans@imperial.ac.uk
- Jan Hubička
- Affiliation: Faculty of Mathematics and Physics, Department of Applied Mathematics (KAM), Charles University, Prague, Czech Republic
- Email: hubicka@kam.mff.cuni.cz
- Matěj Konečný
- Affiliation: Faculty of Mathematics and Physics, Department of Applied Mathematics (KAM), Charles University, Prague, Czech Republic
- Email: matej@kam.mff.cuni.cz
- Jaroslav Nešetřil
- Affiliation: Faculty of Mathematics and Physics, Computer Science Institute of Charles University (IUUK), Charles University, Prague, Czech Republic
- Email: nesetril@kam.mff.cuni.cz
- Received by editor(s): February 20, 2019
- Received by editor(s) in revised form: September 11, 2019
- Published electronically: January 15, 2020
- Additional Notes: The last three authors were supported by ERC Synergy grant DYNASNET 810115
The second and third authors were supported by project 18-13685Y of the Czech Science Foundation (GAČR)
The third author was also supported by the Charles University Grant Agency (GA UK), project 378119 - Communicated by: Patricia L. Hersh
- © Copyright 2020 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 148 (2020), 1901-1915
- MSC (2010): Primary 05E18, 20B25, 22F50, 03C15, 03C52
- DOI: https://doi.org/10.1090/proc/14872
- MathSciNet review: 4078076