๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Linear extensions of random orders

โœ Scribed by Graham Brightwell

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
621 KB
Volume
125
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

A popular model of random orders is obtained by taking two disjoint n-element antichains A, and Al, and putting in each relation in A, x A, with probability l/2, all the choices being made independently.

We estimate the number of linear extensions of such an ordered set, showing that this number is almost always very close to q(n!)', where q is a known constant.

We extend this result to produce estimates for the number of linear extensions of almost every n-element ordered set.

๐Ÿ“œ SIMILAR VOLUMES

A combinatorial bijection between linear
A combinatorial bijection between linear extensions of equivalent orders
โœ Ulrich Faigle; Rainer Schrader ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 404 KB

Let P and Q be (partially) ordered sets with the same comparability graph. A bijection is constructed between the sets of linear extensions of P and Q such that the number of setups is preserved. This yields a common generaliTation of the comparability invariance of order dimension, setup number and

Extension Theorems of Continuous Random
Extension Theorems of Continuous Random Linear Operators on Random Domains
โœ T.X. Guo ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 570 KB

The central purpose of this paper is to prove the following theorem: let \((\Omega, \sigma\), \(u)\) be a complete probability space, \((B,\|\cdot\|)\) a normed linear space over the scalar field \(K, E: \Omega \rightarrow 2^{B}\) a separable random domain with linear subspace values, and \(f: \oper

The number of linear extensions of subse
The number of linear extensions of subset ordering
โœ Jichang Sha; D.J. Kleitman ๐Ÿ“‚ Article ๐Ÿ“… 1987 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 520 KB

We find asymptotic upper and lower bounds on the number of linear extensions of the containment ordering of subsets of a finite set. These agree in their most significant non-trivial terms. A related open question is described. L > 2"((n + 1)log 2 -4 log 2m -5 + o(1 ln)).