Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  194.25401
Autor:  Elliott, P.D.; Erdös, Pál
Title:  Some matching theorems (In English)
Source:  J. Indian Math. Soc., n. Ser. 32, 215-219 (1968).
Review:  The authors give the following improvements of an earlier result of the first author [Mathematika, London 13, 23-25 (1966; Zbl 144.00504)].
Theorem 1. Let G be an even (i.e. bipartite) graph of type (n,n) and suppose that G has at least (½+c)n2 edges, and has at least one matching. Then G has at least (1) 2\mu\mu! distinct matchings, where (2) \mu = [1/2m], m \geq \alpha n, \alpha = 1-(1-2c) ½, and m is an integer. In particular, if c is fixed and n large, the number of distinct matchings exceeds (n!)c1 where c1 > 0 depends only upon c.
Theorem 2. Let G satisfy the hypotheses of Theorem 1 with 2c > \sqrt 3-1. Then G has at least m! distinct matchings where m is an integer satisfying m+1 \geq n(2c-(2-4c) ½).
Reviewer:  R.L.Hemminger
Classif.:  * 05C70 Factorization, etc.
Index Words:  topology

© 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