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