Martin-Lf Randomness, Invariant Measures and Countable Homogeneous Structures
We use ideas from topological dynamics (amenability), combinatorics (structural Ramsey theory) and model theory (Frass limits) to study closed amenable subgroups G of the symmetric group S ? of a countable set, where S ? has the topology of pointwise convergence. We construct G-invariant measures on the universal minimal flows associated with these groups G in, moreover, an algorithmic manner. This leads to an identification of the generic elements, in the sense of being Martin-Lf random, of these flows with respect to the constructed invariant measures. Along these lines we study the random elements of S ?, which are permutations that transform recursively presented universal structures into such structures which are Martin-Lf random.
martin-lf randomness topological dynamics ramsey theory frass limits amenable groups