Kolmogorov complexity and symmetric relational structures

Abstract

We study partitions of Fra\"ıssé limits of classes of finite relational structures where the partitions are encoded by infinite binary sequences which are random in the sense of Kolmogorov, Chaitin and Solomonoff. It is shown that partition by a random sequence of a Fra\"ıssé limit preserves the limit property of the object.

arXiv comment11 pages, two diagrams