On random relational structures
type: Item
instance of: scholarly article
title: On random relational structures
zbMATH Open document ID: 1026.03020
DOI: 10.1016/S0097-3165(03)00004-9
author: Manfred Droste
author: Dietrich Kuske
published in: Journal of Combinatorial Theory. Series A
publication date: 2003-07-01T00:00:00Z
review text: Using universal algebra convention, the authors consider relational systems as sets \(S\) and a subset-sequence \(R_i\subseteq S^i= S\times S^{i-1}\), subject to certain laws specified by equations\break \(W_i(X_1,\dots,X_i)= V_i(X_1,\dots,X_i)\) for \((X_1,\dots,X_i)\in R_i\), \(i\in \mathbb{N}\). The categories of such relational systems \(C\) (e.g., graphs, posets, groups etc.) equipped with morphisms are the objects of inquiry in this paper. In particular, the question addressed is the following: is it possible to use a variant of the Erdős-Rényi construction to produce a generalization to \(C\) of their method of producing a countable universal homogeneous graph. Given that this construction can (and has been) generalized itself to many classes (categories) \(C\), it is noted in this interesting paper that if \(C\) contains an infinite \(\omega\)-categorical universal homogeneous structure \(U\) (\(U\) contains a copy of every finite element of \(C\) and isomorphisms of (copies of) finite elements can be extended to automorphisms of \(U\) while \(C\) contains for each \(n\) only a finite number of isomorphism classes of objects generated by \(n\) elements), then the probabilistic master construction produces \(U\). Importantly, in applications, this means that, via the construction, \(U\) can be approximated to any degree of ``accuracy'' in a controlled fashion.
reviewed by: J. Neggers
Mathematics Subject Classification ID: 03C50
Mathematics Subject Classification ID: 08A02
Mathematics Subject Classification ID: 08C05
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 1944994
zbMATH Keywords: random poset
zbMATH Keywords: universal structure
zbMATH Keywords: homogeneous structure
zbMATH Keywords: random graph
zbMATH Keywords: relational systems
zbMATH Keywords: categories
MaRDI profile type: Publication
cites work: Finite axiomatizations for existentially closed posets and semilattices
cites work: Notions of relative ubiquity for invariant sets of relational structures
cites work: Q3995219
cites work: Q4026893
cites work: Universal domains and the amalgamation property
cites work: Asymmetric graphs
cites work: Sur l'extension aux relations de quelques propriétés des ordres
cites work: Theory of relations. Transl. from the French by P. Clote. With an appendix by Norbert Sauer.
cites work: Q4003410
cites work: Q4305611
cites work: The Random Graph and Automorphisms of the Rational World
cites work: Universal graphs and universal functions
cites work: The group of the countable universal graph
cites work: The group of almost automorphisms of the countable universal graph
description: scientific article; zbMATH DE number 1944994