The Finite Length Property of the Rado Graph and Friends
For researchers in infinite combinatorics and automata theory, this work significantly extends the known classes of structures with the finite length property, which has implications for orbit-finite systems and weighted register automata.
The paper establishes the finite length property for a broad class of infinite structures, including the Rado graph, by generalizing prior results from pure sets and dense linear orders. It provides two methods: one for structures approximated by finite substructures with few orbits over characteristic zero, and another for Fraïssé limits with free amalgamation in a finite binary vocabulary.
An infinite structure has the finite length property (over a given field) if, for each of its finite powers, chains of equivariant subspaces in the corresponding free vector space are bounded in length. Prior work showed that the countable pure set and the countable dense linear order without endpoints have this property. We generalise these results to (a) any structure approximated by finite substructures with few orbits, provided the field is of characteristic zero, and (b) any Fraïssé limit with free amalgamation in a finite vocabulary consisting of unary and binary relations, possibly expanded with a generic total order. As a special case, we deduce the finite length property of the Rado graph using both methods. We also describe some connections with function spaces, weighted register automata, and orbit-finite systems of linear equations.