On random relational structures (Q1395812)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On random relational structures |
scientific article |
Statements
On random relational structures (English)
0 references
1 July 2003
0 references
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.
0 references
random poset
0 references
universal structure
0 references
homogeneous structure
0 references
random graph
0 references
relational systems
0 references
categories
0 references
0 references