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