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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page