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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    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