Submission date: 19 June 2012

Abstract:

Let L be a countable language. Given a countable L-structure M with underlying set the natural numbers N, we determine when there is a probability measure on the space of all such L-structures that is invariant under the action of Sym(N), and that assigns measure one to the isomorphism class of M. In recent work, Petrov and Vershik [PV10] have proven the existence of such invariant measures for Henson's countable universal ultrahomogeneous K_n-free graphs. Here we give a complete characterization of countable infinite structures that admit invariant measures: There is an invariant measure concentrated on the isomorphism class of M if and only if the “group-theoretic” definable closure of every finite tuple of M is trivial, i.e., the pointwise stabilizer in Aut(M) of an arbitrary finite tuple of M fixes no additional points. When M is a Fraisse limit, this amounts to requiring that the age of M have strong amalgamation. The proof makes use of the model theory of infinitary logic to build upon Petrov and Vershik's constructions. In the case when M is a graph, these methods provide a new means of building dense graph limits, in the sense of Lovasz and Szegedy [LS06]. Our result gives rise to new instances of structures admitting invariant measures, such as the countable universal ultrahomogeneous partial order, Henson's family of continuum-many countable ultrahomogeneous directed graphs, certain countable universal graphs forbidding a finite homomorphism-closed set of finite connected graphs, and the rational Urysohn space.

Mathematics Subject Classification: 03C98, 60G09, 37L40, 05C80, 03C75, 62E10, 05C63

Keywords and phrases:

Full text arXiv 1206.4011: pdf, ps.