A counterexample in the theory of random orders

DOI10.1007/BF00353655MaRDI QIDQ1121295zbMATH OpenOpenAlexWikidataFDO

Authors Peter Winkler

Publication date 1989

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00353655

zbMATH Keywords

0-1 lawfirst-order sentencerandom orders

Mathematics Subject Classification ID

Partial orders, general (06A06) Zero-one laws (60F20)

Review text

The main result of this paper is that the 0-1 law fails in random orders of fixed dimension k, \(k\geq 3\). In particular, an example of a first- order sentence \(\Phi\) in the language of partial orders is given which cannot have limiting probability 0 or 1 among random orders of dimension 3.

Recommendations

• scientific article; zbMATH DE number 3946188
• Random orders of dimension 2
• The dimension of random ordered sets
• Random graph orders do not satisfy a 0–1 law
• Nonconvergence in the theory of random orders

Cites work

• Connectedness and diameter for random orders of fixed dimension
• Partially Ordered Sets
• Random orders
• The computational complexity of asymptotic problems. I: Partial orders

Cited in

(5)

• Random orders of dimension 2
• Nonconvergence in the theory of random orders
• scientific article; zbMATH DE number 3946188 (Why is no real title available?)
• Random k-dimensional orders: Width and number of linear extensions
• On increasing sequences formed by points from a random finite subset of a hypercube

This page was built for publication: A counterexample in the theory of random orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1121295)