pith. sign in

arxiv: 2605.21681 · v1 · pith:YCMKA7JXnew · submitted 2026-05-20 · 🧮 math.CO · cs.FL· cs.LO· math.LO· math.RT

The Finite Length Property of the Rado Graph and Friends

Jingjie Yang , Miko{\l}aj Boja\'nczyk , Bartek Klin This is my paper

Pith reviewed 2026-05-22 08:42 UTC · model grok-4.3

classification 🧮 math.CO cs.FLcs.LOmath.LOmath.RT
keywords Rado graphfinite length propertyFraïssé limitsfree amalgamationequivariant subspacesrelational structuresorbit-finite
0
0 comments X

The pith

Any Fraïssé limit with free amalgamation over unary and binary relations has the finite length property, with the Rado graph as a special case.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that certain infinite relational structures satisfy the finite length property. This means that in the free vector space over any finite power of the structure, every chain of subspaces fixed by the automorphism group has bounded length. The result extends earlier cases for the pure countable set and the dense linear order. It holds in two settings: structures approximated by finite substructures with few orbits over characteristic-zero fields, and Fraïssé limits with free amalgamation in finite vocabularies of unary and binary relations, possibly expanded by a generic total order. The Rado graph is shown to satisfy the property by both routes, and the work notes links to function spaces and orbit-finite linear equations.

Core claim

We prove that every Fraïssé limit with free amalgamation in a finite vocabulary consisting of unary and binary relations, possibly expanded with a generic total order, has the finite length property. We also show the property for any structure approximated by finite substructures with few orbits over fields of characteristic zero. In particular, the Rado graph has the finite length property.

What carries the argument

The finite length property, which requires that chains of equivariant subspaces in the free vector space over finite powers of the structure have bounded length.

If this is right

  • The Rado graph has the finite length property under both approximation and amalgamation arguments.
  • Orbit-finite systems of linear equations over these structures admit finite-length solution chains.
  • Weighted register automata over such structures inherit boundedness properties from the vector-space chains.
  • Function spaces built from the structure's powers have correspondingly controlled invariant subspaces.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same boundedness may simplify decision procedures for linear properties in infinite-state systems built from these structures.
  • Similar results could be tested on other homogeneous structures whose ages have free amalgamation, such as the random tournament.
  • The characteristic-zero restriction in the few-orbits case suggests checking whether positive-characteristic fields admit counterexamples with longer chains.

Load-bearing premise

The structure must either be approximated by finite substructures with few orbits or admit free amalgamation in its age.

What would settle it

An explicit infinite ascending chain of equivariant subspaces inside the free vector space over the square of the Rado graph would disprove the claim for that structure.

read the original abstract

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\"iss\'e 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript proves that any Fraïssé limit with free amalgamation in a finite vocabulary of unary and binary relations (possibly expanded by a generic total order) has the finite length property, and that any structure approximated by finite substructures with few orbits has the property over fields of characteristic zero. The Rado graph is recovered as a special case by both methods. Additional connections are drawn to function spaces, weighted register automata, and orbit-finite systems of linear equations.

Significance. If the central claims hold, the work provides a substantial generalization of the finite length property beyond the pure set and dense linear order to a wide class of homogeneous structures arising from Fraïssé theory. The use of two independent methods for the Rado graph and the explicit links to automata and orbit-finite linear algebra strengthen the result and indicate potential applications in model-theoretic combinatorics and theoretical computer science.

major comments (2)
  1. [§4] §4 (free-amalgamation case): the argument that free amalgamation plus finite unary/binary vocabulary yields orbit-finite control over equivariant subspaces is load-bearing for the chain-length bound; the manuscript should supply an explicit reference to the orbit-counting lemma or proposition that converts free amalgamation into the required finite-orbit statement.
  2. [Theorem 5.2] Theorem 5.2 (Rado graph via few-orbit approximation): the reduction to characteristic zero is used to guarantee that the equivariant subspaces form a Noetherian module; if the field has positive characteristic the bound may fail, yet the manuscript does not state whether the result is sharp or merely convenient.
minor comments (3)
  1. [Introduction] The notation for the free vector space V(X) and its equivariant subspaces is introduced without a dedicated preliminary subsection; a short paragraph recalling the action of Aut(M) on the basis would improve readability for readers outside the immediate area.
  2. [Figure 1] Figure 1 (orbit diagram for the Rado graph) uses shading that is difficult to distinguish in black-and-white print; a hatching pattern or explicit labels would help.
  3. [§6.3] The discussion of weighted register automata in §6.3 is only one paragraph long; adding a single concrete example of an orbit-finite linear equation that arises from a register automaton would make the connection more tangible.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, their positive assessment of its significance, and the recommendation of minor revision. We address the two major comments below.

read point-by-point responses

  1. Referee: [§4] §4 (free-amalgamation case): the argument that free amalgamation plus finite unary/binary vocabulary yields orbit-finite control over equivariant subspaces is load-bearing for the chain-length bound; the manuscript should supply an explicit reference to the orbit-counting lemma or proposition that converts free amalgamation into the required finite-orbit statement.

    Authors: We agree that an explicit reference would improve clarity. The finite unary/binary vocabulary together with free amalgamation implies that the automorphism group of the Fraïssé limit has only finitely many orbits on n-tuples for each fixed n; this is a standard fact in the theory of homogeneous relational structures. We will add a direct citation to the relevant orbit-counting statement (from the literature on Fraïssé limits with free amalgamation) at the appropriate point in §4. revision: yes

  2. Referee: [Theorem 5.2] Theorem 5.2 (Rado graph via few-orbit approximation): the reduction to characteristic zero is used to guarantee that the equivariant subspaces form a Noetherian module; if the field has positive characteristic the bound may fail, yet the manuscript does not state whether the result is sharp or merely convenient.

    Authors: The referee correctly identifies that characteristic zero is invoked to obtain the Noetherian property for the module of equivariant subspaces. This hypothesis is used for technical convenience, as it allows application of standard results from commutative algebra that guarantee the ascending chain condition. The manuscript does not claim that the finite-length property necessarily fails in positive characteristic, nor does it assert sharpness of the bound. We will insert a clarifying remark after the statement of Theorem 5.2 noting that the result is proved under the characteristic-zero assumption and that the positive-characteristic case is left open. revision: yes

Circularity Check

0 steps flagged

Derivation self-contained via standard Fraïssé theory and two independent methods

full rationale

The paper generalizes the finite length property from the pure set and dense linear order (prior independent results) to Fraïssé limits with free amalgamation over finite unary/binary vocabularies, possibly with generic order. Part (a) uses orbit-finite approximation with few orbits under char-0 fields; part (b) uses free amalgamation to bound equivariant subspace chains in the free vector space. The Rado graph follows as a special case from both routes, providing cross-check. No step reduces a prediction to a fitted input by construction, no load-bearing self-citation chain, and no ansatz or uniqueness imported circularly; modeling assumptions are explicit and enable the orbit-finite control directly.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Results rest on standard model-theoretic assumptions about Fraïssé limits and orbit counts; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Field of characteristic zero for the few-orbit approximation result
    Explicitly required in part (a) of the abstract
  • domain assumption Free amalgamation property for the Fraïssé-limit result
    Stated as the setting for part (b)

pith-pipeline@v0.9.0 · 5682 in / 1221 out tokens · 32039 ms · 2026-05-22T08:42:20.036644+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages

  1. [1]

    Boja\'nczyk, Miko. Turing. 28th. 2013 , doi =

    work page 2013

  2. [2]

    Boja. An. 2025 , _bib2doi_finished =

    work page 2025

  3. [3]

    Orbit-finite linear programming , author =. J. 2025 , organization =. doi:10.1145/3703909 , timestamp =

    work page doi:10.1145/3703909 2025

  4. [4]

    IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) , pages =

    Imperative programming in sets with atoms , author =. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) , pages =. 2012 , organization =. doi:10.4230/LIPIcs.FSTTCS.2012.4 , timestamp =

    work page doi:10.4230/lipics.fsttcs.2012.4 2012

  5. [5]

    Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages , pages =

    Towards nominal computation , author =. Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages , pages =. 2012 , doi =

    work page 2012

  6. [6]

    2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science , pages =

    Locally finite constraint satisfaction problems , author =. 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science , pages =. 2015 , organization =. doi:10.1109/LICS.2015.51 , timestamp =

    work page doi:10.1109/lics.2015.51 2015

  7. [7]

    Pitts , publisher =

    Andrew M. Pitts , publisher =. Nominal Sets: Names and Symmetry in Computer Science , volume =. 2013 , isbn =

    work page 2013

  8. [8]

    A functional programming language for sets with atoms , year =

    Micha. A functional programming language for sets with atoms , year =

    work page

  9. [9]

    Kopczy. Proceedings of the 14th International Workshop on Satisfiability Modulo Theories affiliated with the International Joint Conference on Automated Reasoning, SMT@IJCAR 2016, Coimbra, Portugal, July 1-2, 2016 , volume =. 2016 , url =

    work page 2016

  10. [10]

    Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata , volume =

    Bojańczyk, Mikołaj and Fijalkow, Joanna and Klin, Bartek and Moerman, Joshua , year =. Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata , volume =. doi:10.46298/theoretics.24.13 , journal =

    work page doi:10.46298/theoretics.24.13

  11. [11]

    Function Spaces for Orbit-Finite Sets , volume =

    Mikołaj Bojańczyk and L. Function Spaces for Orbit-Finite Sets , volume =. ICALP , editor =. 2024 , doi =

    work page 2024

  12. [12]

    Automata Theory in Nominal Sets , volume =

    Boja\'nczyk, Miko. Automata Theory in Nominal Sets , volume =. Logical Methods in Computer Science , number =. 2014 , doi =

    work page 2014

  13. [13]

    Boja\'nczyk, Miko. Nominal. Theory of Computing Systems , number =. 2013 , doi =

    work page 2013

  14. [14]

    Model Theory , year =

    Wilfrid Hodges , publisher =. Model Theory , year =. doi:10.1017/CBO9780511551574 , timestamp =

    work page doi:10.1017/cbo9780511551574

  15. [15]

    Slightly infinite sets , year =

    Boja\'nczyk, Miko. Slightly infinite sets , year =

    work page

  16. [16]

    The Journal of Symbolic Logic , volume =

    Reducts of the random graph , author =. The Journal of Symbolic Logic , volume =. 1991 , publisher =. doi:10.2307/2274912 , timestamp =

    work page doi:10.2307/2274912 1991

  17. [17]

    , title =

    Evans, David M. , title =. 2025 , note =

    work page 2025

  18. [18]

    2026 , _bib2doi_finished =

    Bojańczyk, Mikołaj and Lopez, Aliaume and Stefański, Rafał and Yaghoubi, Omid , title =. 2026 , _bib2doi_finished =

    work page 2026

  19. [19]

    2024 , issue_date =

    Mottet, Antoine and Pinsker, Michael , title =. 2024 , issue_date =. doi:10.1145/3689207 , journal =

    work page doi:10.1145/3689207 2024

  20. [20]

    Kantor, W. M. and Liebeck, Martin W. and Macpherson, H. D. , title =. Proceedings of the London Mathematical Society , volume =. doi:https://doi.org/10.1112/plms/s3-59.3.439 , year =

    work page doi:10.1112/plms/s3-59.3.439

  21. [21]

    Godsil and G

    Algebraic graph theory , author =. 2001 , isbn =. doi:10.1007/978-1-4613-0163-9 , _bib2doi_selected =

    work page doi:10.1007/978-1-4613-0163-9 2001

  22. [22]

    Israel Journal of Mathematics , year =

    Herwig, Bernhard , title =. Israel Journal of Mathematics , year =. doi:10.1007/BF02764005 , issn =

    work page doi:10.1007/bf02764005

  23. [23]

    Coherent extension of partial automorphisms, free amalgamation and automorphism groups , volume =. J. Symb. Log. , author =. 2020 , pages =. doi:10.1017/jsl.2019.32 , number =

    work page doi:10.1017/jsl.2019.32 2020

  24. [24]

    2011 , issn =

    A survey of homogeneous structures , journal =. 2011 , issn =. doi:10.1016/j.disc.2011.01.024 , author =

    work page doi:10.1016/j.disc.2011.01.024 2011

  25. [25]

    The 42 reducts of the random ordered graph , volume =

    Bodirsky, Manuel and Pinsker, Michael and Pongrácz, András , year =. The 42 reducts of the random ordered graph , volume =. Proceedings of the London Mathematical Society , publisher =. doi:10.1112/plms/pdv037 , number =

    work page doi:10.1112/plms/pdv037

  26. [26]

    , year =

    Evans, David M. , year =. Permutation modules for. 2603.29606 , eprinttype=

    work page arXiv

  27. [27]

    2025 , month =

    Some more infinite permutation modules , author =. 2025 , month =

    work page 2025

  28. [28]

    1997 , issn =

    The Structure of Some Permutation Modules for the Symmetric Group of Infinite Degree , journal =. 1997 , issn =. doi:10.1006/jabr.1996.6963 , author =

    work page doi:10.1006/jabr.1996.6963 1997

  29. [29]

    Linear equations for unordered data vectors in [

    Hofman, Piotr and Różycki, Jakub , year =. Linear equations for unordered data vectors in [. doi:10.46298/lmcs-18(4:11)2022 , journal =

    work page doi:10.46298/lmcs-18(4:11)2022 2022

  30. [30]

    Delooping cyclic groups with lens spaces in homotopy type theory

    Ghosh, Arka and Lasota, S. Equivariant ideals of polynomials , year =. doi:10.1145/3661814.3662074 , booktitle =

    work page doi:10.1145/3661814.3662074

  31. [31]

    and Evans, David M

    Camina, Alan R. and Evans, David M. , title =. The Quarterly Journal of Mathematics , volume =. 1991 , month =. doi:10.1093/qmath/42.1.15 , _bib2doi_finished =

    work page doi:10.1093/qmath/42.1.15 1991

  32. [32]

    and Gray, Darren G

    Evans, David M. and Gray, Darren G. D. , editor=. Kernels and cohomology groups for some finite covers , booktitle=. 2017 , pages=

    work page 2017

  33. [33]

    2002 , issn =

    Bounds in the Theory of Finite Covers , journal =. 2002 , issn =. doi:10.1006/jabr.2001.9110 , author =

    work page doi:10.1006/jabr.2001.9110 2002

  34. [34]

    Stability patterns in representation theory , volume =

    Sam, Steven V and Snowden, Andrew , year =. Stability patterns in representation theory , volume =. doi:10.1017/fms.2015.10 , journal =

    work page doi:10.1017/fms.2015.10 2015

  35. [35]

    and Hrushovski, Ehud , address =

    Cherlin, Gregory L. and Hrushovski, Ehud , address =. Finite structures with few types , year =. Finite structures with few types , isbn =

    work page

  36. [36]

    2016 , eprint =

    Stability and periodicity in the modular representation theory of symmetric groups , author =. 2016 , eprint =

    work page 2016

  37. [37]

    2025 , eprint =

    Computability of Equivariant Gr\"obner bases , author =. 2025 , eprint =

    work page 2025

  38. [38]

    Transactions of the American Mathematical Society , number =

    Countable Ultrahomogeneous Undirected Graphs , urldate =. Transactions of the American Mathematical Society , number =. 1980 , _bib2doi_finished =. doi:10.1090/S0002-9947-1980-0583847-2 , author =

    work page doi:10.1090/s0002-9947-1980-0583847-2 1980

  39. [39]

    2016 , author =

    The. 2016 , author =

    work page 2016

  40. [40]

    2025 , eprint =

    Taking model-complete cores , author =. 2025 , eprint =

    work page 2025

  41. [41]

    and Hubička, Jan and Nešetřil, Jaroslav , year =

    Evans, David M. and Hubička, Jan and Nešetřil, Jaroslav , year =. Fundamenta Mathematicae , publisher =. doi:10.4064/fm560-8-2020 , number =

    work page doi:10.4064/fm560-8-2020 2020

  42. [42]

    Przybyłek , year =

    Michał R. Przybyłek , year =. A note on. 2304.09986 , primaryclass =

    work page arXiv

  43. [43]

    Geometric algebra , year =

    Artin, Emil , booktitle =. Geometric algebra , year =

    work page

  44. [44]

    Finite group theory , year =

    Aschbacher, Michael , address =. Finite group theory , year =. Finite group theory , edition =. doi:10.1017/CBO9781139175319 , keywords =

    work page doi:10.1017/cbo9781139175319

  45. [45]

    1976 , issn =

    Homogeneous graphs , journal =. 1976 , issn =. doi:10.1016/0095-8956(76)90072-1 , author =

    work page doi:10.1016/0095-8956(76)90072-1 1976

  46. [46]

    Equivariant subspaces , howpublished =

    Arka Ghosh , year =. Equivariant subspaces , howpublished =

    work page

  47. [47]

    Linear combinations of unordered data vectors , year =

    Piotr Hofman and J. Linear combinations of unordered data vectors , year =. 32nd Annual. doi:10.1109/LICS.2017.8005065 , pages =

    work page doi:10.1109/lics.2017.8005065 2017

  48. [48]

    The pebble-relation comonad in finite model theory

    Ghosh, Arka and Hofman, Piotr and Lasota, Sławomir , title =. 2022 , isbn =. doi:10.1145/3531130.3533333 , booktitle =

    work page doi:10.1145/3531130.3533333 2022

  49. [49]

    2023 , eprint =

    Systems of ideals parametrized by combinatorial structures , author =. 2023 , eprint =

    work page 2023

  50. [50]

    On the automorphism group of the universal homogeneous meet-tree , volume =

    Itay Kaplan and Tomasz Rzepecki and Daoud Siniora , year =. On the automorphism group of the universal homogeneous meet-tree , volume =. J. Symb. Log. , publisher =. doi:10.1017/jsl.2021.9 , number =

    work page doi:10.1017/jsl.2021.9 2021

  51. [51]

    More on the

    Lionel. More on the. 2013 , eprint =

    work page 2013

  52. [52]

    Linear algebra in orbit-finite dimension , year =

    Arka Ghosh , school =. Linear algebra in orbit-finite dimension , year =

    work page

  53. [53]

    1973 , _bib2doi_finished =

    The axiom of choice , author =. 1973 , _bib2doi_finished =

    work page 1973

  54. [54]

    1985 , issn =

    aleph_0 -categorical, aleph_0 -stable structures , journal =. 1985 , issn =. doi:10.1016/0168-0072(85)90023-5 , author =

    work page doi:10.1016/0168-0072(85)90023-5 1985

  55. [55]

    Algebras and Representation Theory , ISBN =

    Erdmann, Karin and Holm, Thorsten , year =. Algebras and Representation Theory , ISBN =. doi:10.1007/978-3-319-91998-0 , series =

    work page doi:10.1007/978-3-319-91998-0

  56. [56]

    Journal of the London Mathematical Society , volume =

    Albert, Michael and Chowdhury, Ambar , title =. Journal of the London Mathematical Society , volume =. doi:https://doi.org/10.1112/S0024610799007140 , year =

    work page doi:10.1112/s0024610799007140

  57. [57]

    Transactions of the American Mathematical Society , number =

    Totally Categorical Structures , volume =. Transactions of the American Mathematical Society , number =. doi:10.2307/2001069 , author =

    work page doi:10.2307/2001069

  58. [58]

    Lachlan, A. H. , year =. Countable homogeneous tournaments , volume =. Transactions of the American Mathematical Society , publisher =. doi:10.1090/s0002-9947-1984-0743728-1 , number =

    work page doi:10.1090/s0002-9947-1984-0743728-1 1984

  59. [59]

    Ward Henson , journal =

    C. Ward Henson , journal =. Countable Homogeneous Relational Structures and _0 -Categorical Theories , urldate =. 1972 , doi=

    work page 1972

  60. [60]

    Ward , year =

    Henson, C. Ward , year =. A family of countable homogeneous graphs , volume =. Pacific Journal of Mathematics , publisher =. doi:10.2140/pjm.1971.38.69 , number =

    work page doi:10.2140/pjm.1971.38.69 1971

  61. [61]

    More on the

    Lionel Nguyen. More on the. 2013 , eprint=

    work page 2013

  62. [62]

    Surveys in Combinatorics 2015 , publisher=

    Bodirsky, Manuel , editor=. Surveys in Combinatorics 2015 , publisher=. 2015 , pages=

    work page 2015