Random graph orders |
| |
Authors: | Michael H Albert Alan M Frieze |
| |
Institution: | (1) Department of Mathematics, Carnegie Mellon University, 15213 Pittsburgh, PA, U.S.A. |
| |
Abstract: | Let P
n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P
n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P
n. |
| |
Keywords: | Primary: 06A10 secondary: 05C80 60C05 |
本文献已被 SpringerLink 等数据库收录! |
|