Random orders of dimension 2 (Q1177705): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Q3950588 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The computational complexity of asymptotic problems. I: Partial orders / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the number of k-realizations of an ordered set / rank
 
Normal rank
Property / cites work
 
Property / cites work: Partially Ordered Sets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Transitiv orientierbare Graphen / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3691784 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Asymptotic Enumeration of Partial Orders on a Finite Set / rank
 
Normal rank
Property / cites work
 
Property / cites work: Random orders / rank
 
Normal rank
Property / cites work
 
Property / cites work: Connectedness and diameter for random orders of fixed dimension / rank
 
Normal rank
Property / cites work
 
Property / cites work: A counterexample in the theory of random orders / rank
 
Normal rank

Revision as of 10:34, 15 May 2024

scientific article
Language Label Description Also known as
English
Random orders of dimension 2
scientific article

    Statements

    Random orders of dimension 2 (English)
    0 references
    0 references
    26 June 1992
    0 references
    Let \(P_ k\) be the random poset of dimension \(k\) on \(n\) elements obtained by intersecting \(k\) randomly and independently chosen linear orders; let \(P_ 2(n)=P(n)\) (also \(P_ 2(n)=\hbox{Ran}(n)\) elsewhere). Then, although in \(P=\bigcup_{k,n}P_ k(n)\), the finite posets, the \(0-1\) law holds, it is not true for \(P_ 2=\bigcup_ n P_ 2(n)\). Indeed, Winkler and Brightwell have observed that there are simple first- order properties with limits \((n\to\infty)\) other than 0 and 1 and Spencer has shown that such limits may even fail to exist. In this paper the author investigates the random poset \(P(n)\) as well as random variables \(Q(n)\) (all 2-dimensional orderings are equiprobable), \(U(n)\) (all isomorphism types, types are equiprobable) and \(I(n)\) (the number of realizations of the isomorphism class \([P(n)])\). Using a sequence of clever counting and structural lemmas the author shows that (Theorem 2.1) the number of elements in the range of \(P_ 2(n)\) is \((1+O(1)n!^ 2/(2\sqrt e)\), while (Theorem 4.5) the number of elements in the range of \(U(n)\) is \((1+O(1)n!/2\) (also proven by El-Zahar and Sauer). Since the random variables described represent distinct methods of obtaining random posets, it is also of interest to compare limiting probabilities as in Corollary 3.2, e.g.: Any statement with limiting probability in (0,1) in \(P(n)\) has limiting probability in (0,1) in \(Q(n)\). Similarly, if the limiting probability is 0 or 1 in \(P\), then it is so in \(Q(n)\). Thus, Spencer's result may also be considered relative to both ranges. The author also shows that for the properties `rigid', `uniquely realizable' and `has a uniquely transitively orientable comparability graph' the limiting probabilities are \(1/e\) in \(P(n)\) and \(1/(2\sqrt e)\) in \(Q(n)\).
    0 references
    realization
    0 references
    orientation
    0 references
    dimension
    0 references
    rigid posets
    0 references
    random poset
    0 references
    limiting probabilities
    0 references
    comparability graph
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references