Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-26T13:08:29.201Z Has data issue: false hasContentIssue false
  • English
  • Français

Amenability and unique ergodicity of automorphism groups of countable homogeneous directed graphs

Part of: Connections with other structures, applications Graph theory Abstract harmonic analysis

Published online by Cambridge University Press:  17 October 2018

MICHEAL PAWLIUK  and
MIODRAG SOKIĆ
MICHEAL PAWLIUK
Affiliation:
University of CalgaryMathematics & Statistics, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4 email [email protected]
MIODRAG SOKIĆ
Affiliation:
University of CalgaryMathematics & Statistics, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4 email [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the automorphism groups of countable homogeneous directed graphs (and some additional homogeneous structures) from the point of view of topological dynamics. We determine precisely which of these automorphism groups are amenable (in their natural topologies). For those which are amenable, we determine whether they are uniquely ergodic, leaving unsettled precisely one case (the ‘semi-generic’ complete multipartite directed graph). We also consider the Hrushovski property. For most of our results we use the various techniques of Angel et al [Random orderings and unique ergodicity of automorphism groups. J. Eur. Math. Soc., 16 (2014), 2059–2095], suitably generalized to a context in which the universal minimal flow is not necessarily the space of all orders. Negative results concerning amenability rely on constructions of the type considered in Zucker [Amenability and unique ergodicity of automorphism groups of Fraïssé structures. Fund. Math., 226 (2014), 41–61]. An additional class of structures (compositions) may be handled directly on the basis of very general principles. The starting point in all cases is the determination of the universal minimal flow for the automorphism group, which in the context of countable homogeneous directed graphs is given in Jasiński et al [Ramsey precompact expansions of homogeneous directed graphs. Electron. J. Combin., 21(4), (2014), 31] and the papers cited therein.

Keywords

infinite dimensional dynamicstopological dynamicsamenabilitydirected graphs (digraphs)tournaments

MSC classification

Primary: 43A07: Means on groups, semigroups, etc.; amenable groups
Secondary: 05C55: Generalized Ramsey theory 54H20: Topological dynamics 05C20: Directed graphs (digraphs), tournaments
Type
Original Article
Information
Ergodic Theory and Dynamical Systems , Volume 40 , Issue 5 , May 2020 , pp. 1351 - 1401
Copyright
© Cambridge University Press, 2018

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramson, F. G. and Harrington, L. A.. Models without indiscernibles. J. Symbolic Logic 43 (1978), 572–600.Google Scholar
Adeleke, S. A. and Neumann, P. M.. Relations related to betweenness: their structure and automorphisms. Mem. Amer. Math. Soc. 131(623) (1998), 125pp.Google Scholar
Angel, O., Kechris, A. S. and Lyons, R.. Random orderings and unique ergodicity of automorphism groups. J. Eur. Math. Soc. 16 (2014), 2059–2095.Google Scholar
Becker, H. and Kechris, A. S.. The Descriptive Set Theory of Polish Group Actions (London Mathematical Society Lecture Note Series, 232). Cambridge University Press, Cambridge, 1996.Google Scholar
Bodirsky, M.. New Ramsey classes from old. Electron. J. Combin. 21(2) (2014), 2–22.Google Scholar
Cherlin, G. L.. The classification of countable homogeneous directed graphs and countable homogeneous n-tournaments. Mem. Amer. Math. Soc. 621(634) (1998), 161pp.Google Scholar
Glasner, E. and Weiss, B.. Minimal actions of the group 𝕊(ℤ) of permutations of the integers. Geom. Funct. Anal. GAFA 12(5) (2002), 964–988.Google Scholar
Hodges, W.. Model Theory (Encyclopedia of Mathematics and its Applications, 42). Cambridge University Press, Cambridge, 1993.Google Scholar
Hrushovski, E.. Extending partial isomorphisms of graphs. Combinatorica 12(4) (1992), 411–416.Google Scholar
Jasiński, J., Laflamme, C., Nguyen Van Thé, L. and Woodrow, R.. Ramsey precompact expansions of homogeneous directed graphs. Electron. J. Combin. 21(4) (2014), 31.Google Scholar
Kechris, A. S.. Dynamics of non-Archimedian Polish groups. Proc. European Congress of Mathematics. European Mathematical Society, Zurich, 2013, pp. 375–397.Google Scholar
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.Google Scholar
Kechris, A. S. and Sokić, M.. Dynamical properties of the automorphism groups of the random poset and random distributive lattice. Fundam. Math. 218(1) (2012), 69–94.Google Scholar
Laflamme, C., Nguyen Van Thé, L. and Sauer, N. W.. Partition properties of the dense local order and a colored version of Milliken’s theorem. Combinatorica 30(1) (2010), 83–104.Google Scholar
McDiarmid, C.. On the method of bounded differences. Surveys Combin. 141(1) (1989), 148–188.Google Scholar
Milliken, K. R.. A Ramsey theorem for trees. J. Combin. Theory, Ser. A 26(3) (1979), 215–237.Google Scholar
Nešetřil, J. and Rödl, V.. Partitions of finite relational and set systems. J. Combin. Theory Ser. A 22(3) (1977), 289–312.Google Scholar
Nešetřil, J. and Rödl, V.. Ramsey classes of set systems. J. Combin. Theory Ser. A 34(2) (1983), 183–201.Google Scholar
Nešetřil, J. and Rödl, V.. The partite construction and Ramsey set systems. Discrete Math. 75(1) (1989), 327–334.Google Scholar
Nguyen Van Thé, L.. More on the Kechris–Pestov–Todorcevic correspondence: precompact expansions. Fundam. Math. 222 (2013), 19–47.Google Scholar
Pestov, V.. On free actions, minimal flows, and a problem by Ellis. Trans. Amer. Math. Soc. 350(10) (1998), 4149–4165.Google Scholar
Pestov, V.. Dynamics of Infinite-dimensional Groups: The Ramsey–Dvoretzky–Milman Phenomenon (University Lecture Series, 40). American Mathematical Society, Providence, RI, 2006.Google Scholar
Sokić, M.. Relational quotients. Fundam. Math. 221(3) (2013), 189–220.Google Scholar
Sokić, M.. Directed graphs and boron trees. J. Combin. Theory Ser. A 132 (2015), 142–171.Google Scholar
Uspenskij, V.. On universal minimal compact g-spaces. Proceedings of the 2000 Topology and Dynamics Conference (San Antonio, TX). Topology Proc. 25 (2000), 301–308.Google Scholar
Zucker, A.. Amenability and unique ergodicity of automorphism groups of Fraïssé structures. Fundam. Math. 226 (2014), 41–61.Google Scholar