Random Matchings in Regular Graphs |
| |
| Authors: | Jeff Kahn Jeong Han Kim |
| |
| Affiliation: | (1) Department of Mathematics and RUTCOR, Rutgers University; New Brunswick, NJ 08903, USA; E-mail: jkahn@math.rutgers.edu, US;(2) AT&T Bell Laboratories; Murray Hill, NJ 07974, USA. Current address: Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA; , US |
| |
| Abstract: | d -regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for let be the probability that M does not cover x. We show that for large d, the 's and the mean μ and variance of are determined to within small tolerances just by d and (in the case of μ and ) : Theorem. For any d-regular graph G, (a) , so that , (b) , where the rates of convergence depend only on d. Received: April 12, 1996 |
| |
| Keywords: | AMS Subject Classification (1991) Classes: 05C65, 05C70, 05C80, 60C05, 60F05, 60G42 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
