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(Mn) denote the maximum number of edge-disjoint 1-factors in the bipartite graph corresponding to an n by n matrix Mn of 0's and 1's; clearly perm (Mn) \geq \nu(Mn). 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(Mn) \geq r for a random matrix with N 1's and n2-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