Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-29T19:06:14.925Z Has data issue: false hasContentIssue false
  • English
  • Français

On the shape of a random acyclic digraph

Published online by Cambridge University Press:  24 October 2008

Brendan D. Mckay
Brendan D. Mckay
Affiliation:
Computer Science Department, Australian National University, GPO Box 4, ACT 2601, Australia
Get access Rights & Permissions [Opens in a new window]

Abstract

If D is an acyclic digraph, define the height h = h(D) to be the length of the longest directed path in D. We prove that the values of h(D) over all labelled acyclic digraphs D on n vertices are asymptotically normally distributed with mean Cn and variance C′n, where C ≈ 0·764334 and C′ ≈ 0·145210. Furthermore, define V0(D) to be the set of sinks (vertices of out-degree 0) and, for r ≥ 1, define Vr(D) to be the set of vertices ν such that the longest directed path from ν to V0(D) has length r. For each k ≥ 1, let nk(D) be the number of sets Vt(D) which have size k. We prove that, for fixed k, the values of nk(D) over all labelled acyclic digraphs D on n vertices are asymptotically normally distributed with mean Ckn and variance C′kn, for positive constants Ck and C′k. Results of Bender and Robinson imply that our claim holds also for unlabelled acyclic digraphs.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 106 , Issue 3 , November 1989 , pp. 459 - 465
Copyright
Copyright © Cambridge Philosophical Society 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bender, E. A.. Central and local limit theorems applied to asymptotic enumeration. J. Combin. Theory Ser. A 15 (1973), 91–111.CrossRefGoogle Scholar
[2]Bender, E. A., Richmond, L. B., Robinson, R. W. and Wormald, N. C.. The asymptotic number of acyclic digraphs. I. Combinatorial 6 (1986), 15–22.CrossRefGoogle Scholar
[3]Bender, E. A. and Robinson, R. W.. The asymptotic number of acyclic digraphs. II. J. Combin. Theory Ser. B 44 (1988), 363–369.CrossRefGoogle Scholar
[4]Eichinger, B. E., Jackson, D. M. and McKay, B. D.. Generating function methods for macromolecules at surfaces. I. One molecule at a plane surface. J. Chem. Phys. 85 (1986), 5299–5305.CrossRefGoogle Scholar
[5]Liskovec, V. A.. The number of maximal vertices of a random acyclic digraph. Teor. Veroyatnost. i Primenen. 20 (1975), 412–421Google Scholar
Liskovec, V. A.. The number of maximal vertices of a random acyclic digraph. Theory Probab. Appl. 20 (1975), 401–409.CrossRefGoogle Scholar
[6]Robinson, R. W.. Counting labelled acyclic digraphs. In New Directions in Graph Theory (Academic Press, 1973), pp. 239–273.Google Scholar
[7]Stanley, R. P.. Acyclic orientations of graphs. Discrete Math. 5 (1973), 171–178.CrossRefGoogle Scholar