Hall’s theorem revisited
HTML articles powered by AMS MathViewer
- by Zhi-Wei Sun PDF
- Proc. Amer. Math. Soc. 129 (2001), 3129-3131 Request permission
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\}} (|\bigcup _{i\in I}A_{i}|-|I|)$ ways. This yields a natural induction proof of the well-known theorem of P. Hall.References
- Martin Aigner, Combinatorial theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 234, Springer-Verlag, Berlin-New York, 1979. MR 542445
- Hui-Qin Cao and Zhi-Wei Sun, On sums of distinct representatives, Acta Arith. 87 (1998), no. 2, 159–169. MR 1665203, DOI 10.4064/aa-87-2-159-169
- Morgan Ward, Ring homomorphisms which are also lattice homomorphisms, Amer. J. Math. 61 (1939), 783–787. MR 10, DOI 10.2307/2371336
- P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935), 26–30.
- Morgan Ward and R. P. Dilworth, The lattice theory of ova, Ann. of Math. (2) 40 (1939), 600–608. MR 11, DOI 10.2307/1968944
Additional Information
- Zhi-Wei Sun
- Affiliation: Department of Mathematics, Nanjing University, Nanjing 210093, People’s Republic of China
- MR Author ID: 254588
- Email: zwsun@nju.edu.cn
- 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
- © Copyright 2001 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 129 (2001), 3129-3131
- MSC (2000): Primary 05A05; Secondary 05C20
- DOI: https://doi.org/10.1090/S0002-9939-01-06215-3
- MathSciNet review: 1840120