LINEAR EXTENSIONS OF A RANDOM PARTIAL ORDER

被引：27

作者：

Alon, Noga ^{[1
]}

Bollobas, Bela ^{[2
]}

Brightwell, Grajham ^{[3
]}

Janson, Svante ^{[4
]}

机构：

[1] Tel Aviv Univ, Dept Math, IL-69978 Tel Aviv, Israel

[2] Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB2 1SB, England

[3] London Sch Econ, Dept Stat & Math Sci, London WC 2AE, England

[4] Uppsala Univ, Dept Math, S-75106 Uppsala, Sweden

来源：

ANNALS OF APPLIED PROBABILITY | 1994年 / 4卷 / 01期

关键词：

Random partial order; linear extension;

D O I：

10.1214/aoap/1177005202

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We study asymptotics of the number of linear extensions of the random G(n, p) partial order, where p is fixed and n -> infinity. In particular, it is shown that the distribution is asymptotically log-normal.

引用

页码：108 / 123

页数：16

共 11 条

[1] RANDOM GRAPH ORDERS [J].

ALBERT, MH ;

FRIEZE, AM .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1989, 6 (01) :19-30

[2]

Azuma K, 1967, TOHOKU MATH J, V19, P357, DOI DOI 10.2748/TMJ/1178243286

[3] ON THE MAXIMAL NUMBER OF STRONGLY INDEPENDENT VERTICES IN A RANDOM ACYCLIC DIRECTED GRAPH [J].

BARAK, AB ;

ERDOS, P .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (04) :508-514

[4]

BOLLOBAS B., 1991, RAND GRAPHS 87, P1

[5]

BOLLOBAS B., 1988, C MATH SCI J BOLYAI, V52

[6]

BRIGHTWELL G, 1993, SURVEYS COMBINATORIC, P53

[7]

BRIGHTWELL G., 1991, DISCRETE MA IN PRESS

[8]

GUT A, 1988, STOPPED RANDOM WALKS

[9] PROBABILITY-INEQUALITIES FOR SUMS OF BOUNDED RANDOM-VARIABLES [J].

HOEFFDING, W .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1963, 58 (301) :13-+

[10]

KINGMAN JFC, 1968, J ROY STAT SOC B, V30, P499

← 1 2 →