The Finite Length Property of the Rado Graph and Friends
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913151080988672 |
|---|---|
| author | Yang, Jingjie Bojańczyk, Mikołaj Klin, Bartek |
| author_facet | Yang, Jingjie Bojańczyk, Mikołaj Klin, Bartek |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_21681 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Finite Length Property of the Rado Graph and Friends Yang, Jingjie Bojańczyk, Mikołaj Klin, Bartek Combinatorics Formal Languages and Automata Theory Logic in Computer Science Logic Representation Theory 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. |
| title | The Finite Length Property of the Rado Graph and Friends |
| topic | Combinatorics Formal Languages and Automata Theory Logic in Computer Science Logic Representation Theory |
| url | https://arxiv.org/abs/2605.21681 |