##
**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 S_{n} of the largest strongly independent subset of **{** 1,...,n**}** satisfies S_{n}/\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