The AMS website will be down for maintenance on May 23 between 6:00am - 8:00am EDT. For questions please contact AMS Customer Service at or (800) 321-4267 (U.S. & Canada), (401) 455-4000 (Worldwide).


Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Hall's theorem revisited

Author: Zhi-Wei Sun
Journal: Proc. Amer. Math. Soc. 129 (2001), 3129-3131
MSC (2000): Primary 05A05; Secondary 05C20
Published electronically: May 6, 2001
MathSciNet review: 1840120
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $A_{1},\cdots ,A_{n} (n>1)$ be sets. By a simple graph-theoretic argument we show that any set of distinct representatives of $\{A_{i}\}_{i=1}^{n-1}$can be extended to a set of distinct representatives of $\{A_{i}\}_{i=1}^{n}$in more than $\min _{n\in I\subseteq \{1,\cdots ,n\}} (\vert\bigcup _{i\in I}A_{i}\vert-\vert I\vert)$ ways. This yields a natural induction proof of the well-known theorem of P. Hall.

References [Enhancements On Off] (What's this?)

  • [A] M. Aigner, Combinatorial Theory, Springer, New York, 1979. MR 80h:05002
  • [CS] Hui-Qin Cao and Zhi-Wei Sun, On sums of distinct representatives, Acta Arith. 87 (1998), 159-169. MR 99k:11021
  • [H] M. Hall, Distinct representatives of subsets, Bull. Amer. Math. Soc. 54 (1948), 922-926. MR 10:238g
  • [Ha] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 26-30.
  • [HV] P. R. Halmos and H. E. Vaughan, The marriage problem, Amer. J. Math. 72 (1950), 214-215. MR 11:423h

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05A05, 05C20

Retrieve articles in all journals with MSC (2000): 05A05, 05C20

Additional Information

Zhi-Wei Sun
Affiliation: Department of Mathematics, Nanjing University, Nanjing 210093, People’s Republic of China

Received by editor(s): March 31, 2000
Received by editor(s) in revised form: October 30, 2000
Published electronically: May 6, 2001
Additional Notes: This research was supported by the Teaching and Research Award Fund for Outstanding Young Teachers in Higher Education Institutions of MOE, and the National Natural Science Foundation of P. R. China.
Communicated by: John R. Stembridge
Article copyright: © Copyright 2001 American Mathematical Society

American Mathematical Society