## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  558.05026
Autor:  Barak, Amnon B.; Erdös, Paul
Title:  On the maximal number of strongly independent vertices in a random acyclic directed graph. (In English)
Source:  SIAM J. Algebraic Discrete Methods 5, 508-514 (1984).
Review:  In a random digraph on {1,...,n} the arcs from i to j occur independently for 1 \leq j < i \leq n with a common probability p. Two vertices are strongly independent if there is no directed path between them. It is shown that the size Sn of the largest strongly independent subset of { 1,...,n} satisfies Sn/\sqrt{log n} ––> \sqrt{2}/\sqrt{log 1/(1-p)} with probability tending to 1 as n ––> oo.
Reviewer:  O.Frank
Classif.:  * 05C20 Directed graphs (digraphs)
05C80 Random graphs
60C05 Combinatorial probability
60F20 Zero-one laws
Keywords:  independent vertices; random digraph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag