##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 174.04104

**Autor: ** Erdös, Pál; Rényi, Alfréd

**Title: ** On random matrices. II (In English)

**Source: ** Stud. Sci. Math. Hungar. 3, 459-464 (1968).

**Review: ** Let \nu(M_{n}) denote the maximum number of edge-disjoint 1-factors in the bipartite graph corresponding to an n by n matrix M_{n} of 0's and 1's; clearly perm (M_{n}) \geq \nu(M_{n}). Let N = n log n+(r-1)n log log n+n \omega(n) where r is a fixed positive integer and where \omega (n) ––> oo arbitrarily slowly as n ––> oo. The authors show, among other things, that the probability that \nu(M_{n}) \geq r for a random matrix with N 1's and n^{2}-n 0's tends to one as n tends to infinity. This generalizes one of their earlier results [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 455-461 (1963; Zbl 133.26003)].

**Reviewer: ** J.W.Moon

**Classif.: ** * 05C50 Graphs and matrices

**Index Words: ** combinatorics

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag