DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.82

The Finite Length Property of the Rado Graph and Friends

Authors: Jingjie Yang, Mikołaj Bojańczyk, and Bartek Klin

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

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ï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.

Cite as

Jingjie Yang, Mikołaj Bojańczyk, and Bartek Klin. The Finite Length Property of the Rado Graph and Friends. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 82:1-82:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{yang_et_al:LIPIcs.LICS.2026.82,
  author =	{Yang, Jingjie and Boja\'{n}czyk, Miko{\l}aj and Klin, Bartek},
  title =	{{The Finite Length Property of the Rado Graph and Friends}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{82:1--82:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.82},
  URN =		{urn:nbn:de:0030-drops-268695},
  doi =		{10.4230/LIPIcs.LICS.2026.82},
  annote =	{Keywords: Rado graph, oligomorphic structure, orbit-finite set, orbit-finitely spanned vector space, equivariant subspace, finite length}
}

Search Results

Documents authored by Yang, Jingjie

The Finite Length Property of the Rado Graph and Friends

Abstract

Cite as

Thanks for your feedback!

Could not send message