A counterexample in the theory of random orders
type: Item
instance of: scholarly article
title: A counterexample in the theory of random orders
zbMATH Open document ID: 0674.06004
DOI: 10.1007/BF00353655
published in: Order
publication date: 1989-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 60F20
zbMATH DE Number: 4103139
zbMATH Keywords: 0-1 law
zbMATH Keywords: random orders
zbMATH Keywords: first-order sentence
author: Peter Winkler
reviewed by: Dimitru Buşneag
MaRDI profile type: Publication
Wikidata QID: Q124802645
cites work: The computational complexity of asymptotic problems. I: Partial orders
cites work: Partially Ordered Sets
cites work: Random orders
cites work: Connectedness and diameter for random orders of fixed dimension
full work available at URL: https://doi.org/10.1007/bf00353655
OpenAlex ID: W2011929149
description: scientific article; zbMATH DE number 4103139