home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11461 < prev    next >
Encoding:
Text File  |  1992-09-14  |  1.1 KB  |  25 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!west
  3. From: west@symcom.math.uiuc.edu (Douglas West)
  4. Subject: Re: Graph Problem
  5. References: <1992Sep7.084511.3401@alf.uib.no>
  6. Message-ID: <BuLsIw.n0q@news.cso.uiuc.edu>
  7. Sender: usenet@news.cso.uiuc.edu (Net Noise owner)
  8. Organization: University of Illinois at Urbana
  9. Date: Tue, 15 Sep 1992 04:59:18 GMT
  10. Keywords: Combinatorial problem, bipartite graphs.
  11. Lines: 12
  12.  
  13. The original poster asked for bounds on the number of complete matchings in a
  14. bipartite graph with partite sets V,U, where |V|<=|U| and each vertex in V has
  15. degree l<=|V|, and where the graph satisfies Philip Hall's marriage condition
  16. and therefore has a complete matching (saturating |V|, that is).
  17.  
  18. The best possible upper bound is l^l.
  19. The best possible lower bound is l!, which is a special case
  20. of a 1948 theorem of Marshall Hall.
  21.  
  22. In general, if d is the minimum degree of vertices in V, M. Hall's theorem
  23. states that there are at least d(d-1)...(d-k+1) matchings,
  24. where k is the minimum of d and |V|.  This is proved by induction on |V|.
  25.