We show that the only random orderings of finite graphs that are invariant under isomorphism and induced subgraph are the uniform random orderings. We show how this implies the unique ergodicity of the automorphism group of the random graph. We give similar theorems for other structures, including, for example, metric spaces. These give the first examples of uniquely ergodic groups, other than compact groups and extremely amenable groups, after Glasner andWeiss’s example of the group of all permutations...

Let 𝒦 be a class of finite relational structures. We define ℰ𝒦 to be the class of finite relational structures A such that A/E ∈ 𝒦, where E is an equivalence relation defined on the structure A. Adding arbitrary linear orderings to structures from ℰ𝒦, we get the class 𝒪ℰ𝒦. If we add linear orderings to structures from ℰ𝒦 such that each E-equivalence class is an interval then we get the class 𝒞ℰ[𝒦*]. We provide a list of Fraïssé classes among ℰ𝒦, 𝒪ℰ𝒦 and 𝒞ℰ[𝒦*]. In addition, we classify...