caa a22 4500 38638620X CHVBK 20180307112059.0 cr unu---uuuuu 161130e198911 xx s 000 0 eng 10.1017/S0305004100068195 doi S0305004100068195 pii (NATIONALLICENCE)cambridge-10.1017/S0305004100068195 Mckay Brendan D. Computer Science Department, Australian National University, GPO Box 4, ACT 2601, Australia On the shape of a random acyclic digraph [Elektronische Daten] [Brendan D. Mckay] 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. Copyright © Cambridge Philosophical Society 1989 Mathematical Proceedings of the Cambridge Philosophical Society Cambridge University Press 106/3(1989-11), 459-465 0305-0041 106:3<459 1989 106 PSP https://doi.org/10.1017/S0305004100068195 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1017/S0305004100068195 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Mckay Brendan D. Computer Science Department, Australian National University, GPO Box 4, ACT 2601, Australia NATIONALLICENCE 773 0- Mathematical Proceedings of the Cambridge Philosophical Society Cambridge University Press 106/3(1989-11), 459-465 0305-0041 106:3<459 1989 106 PSP CC0 http://creativecommons.org/publicdomain/zero/1.0 nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-cambridge