Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Summary:
Hallova věta a její varianty patří k základním pilířům kombinatoriky. V textu představíme některé její klasické i méně známé aplikace. Popíšeme též ranou historii věty a příbuzných tvrzení, která je spojena nejen se jménem Philipa Halla, ale i řady dalších předních matematiků první poloviny 20. století.
References:
[1] Aigner, M., Ziegler, G. M.: Proofs from THE BOOK. 6th edition, Springer, 2018. MR 3823190
[2] Ardila, F., Stanley, R. P.: Tilings. Math. Intelligencer 32 (2010), 32–43. DOI 10.1007/s00283-010-9160-9 | MR 2747701
[3] Bachelis, G. F.: A short proof of Hall’s theorem on SDRs. Amer. Math. Monthly 109 (2002), 473–474. DOI 10.1080/00029890.2002.11919877 | MR 1901502
[4] Bryant, V.: Aspects of combinatorics. A wide-ranging introduction. Cambridge University Press, 1993. MR 1213683
[5] Easterfield, T. E.: A combinatorial algorithm. J. Lond. Math. Soc. 21 (1946), 219–226. DOI 10.1112/jlms/s1-21.3.219 | MR 0019575
[6] Egerváry, J.: Matrixok kombinatórius tulajdonságairól. Mat. Fiz. Lapok 38 (1931), 16–28.
[7] Ehrenhorg, R: An unbiased marriage theorem. Amer. Math. Monthly 122 (2015), 59. DOI 10.4169/amer.math.monthly.122.01.59 | MR 3324955
[8] Everett, C. J., Whaples, G.: Representations of sequences of sets. Amer. J. Math. 71 (1949), 287–293. DOI 10.2307/2372244 | MR 0028914
[9] Frobenius, G.: Über zerlegbare Determinanten. Sitzber. König. Preuss. Akad. Wiss. 18 (1917), 274–277.
[10] Hall, M.: An existence theorem for Latin squares. Bull. Amer. Math. Soc. 51 (1945), 387–388. DOI 10.1090/S0002-9904-1945-08361-X | MR 0013111
[11] Hall, M.: Distinct representatives of subsets. Bull. Amer. Math. Soc. 54 (1948), 922–926. DOI 10.1090/S0002-9904-1948-09098-X | MR 0027033
[12] Hall, M.: Combinatorial theory. 2nd ed., John Wiley, 1986. MR 0840216
[13] Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 10 (1935), 26–30. DOI 10.1112/jlms/s1-10.37.26 | Zbl 0010.34503
[14] Halmos, P. R., Vaughan, H. E.: The marriage problem. Amer. J. Math. 72 (1950), 214–215. DOI 10.2307/2372148 | MR 0033330
[15] König, D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77 (1916), 453–465. DOI 10.1007/BF01456961 | MR 1511872
[16] König, D.: Graphok és alkalmazásuk a determinánsok és a halmazok elméletére. Math. és Termész. Ért. 34 (1916), 104–119.
[17] König, D.: Graphok és matrixok. Mat. Fiz. Lapok 38 (1931), 116–119.
[18] Landau, H. G.: On dominance relations and the structure of animal societies III. The condition for a score structure. Bull. Math. Biophys. 15 (1953), 143–148. DOI 10.1007/BF02476378 | MR 0054933
[19] Leep, D. B., Myerson, G.: Marriage, magic, and solitaire. Amer. Math. Monthly 106 (1999), 419–429. DOI 10.1080/00029890.1999.12005064 | MR 1699260
[20] Maak, W.: Eine neue Definition der fastperiodischen Funktionen. Abh. Math. Semin. Univ. Hambg. 11 (1935), 240–244. DOI 10.1007/BF02940727 | MR 3069657
[21] Mareš, M., Valla, T.: Průvodce labyrintem algoritmů. CZ.NIC, 2017.
[22] Martello, S.: Jenö Egerváry: from the origins of the Hungarian algorithm to satellite communication. Cent. Eur. J. Oper. Res. 18 (2010), 47–58. DOI 10.1007/s10100-009-0125-z | MR 2593123
[23] Miller, G. A.: On a method due to Galois. Quart. J. Math. 41 (1910), 382–384.
[24] O’Connor, J. J., Robertson, E. F.: MacTutor History of Mathematics archive. [online]. Dostupné z: http://www-history.mcs.st-and.ac.uk/
[25] Pach, J., Morić, F.: Graph theory (Spring 2013). [online]. Dostupné z: http://sma.epfl.ch/~moric/gt2013/
[26] Shamir, E., Sudakov, B.: Two-sided, unbiased version of Hall’s marriage theorem. Amer. Math. Monthly 124 (2017), 79–80. DOI 10.4169/amer.math.monthly.124.1.79 | MR 3608689
[27] Schneider, H.: The concepts of irreducibility and full indecomposability of a matrix in the works of Frobenius, König and Markov. Linear Algebra Appl. 18 (1977), 139–162. DOI 10.1016/0024-3795(77)90070-2 | MR 0446850
[28] Smetaniuk, B.: A new construction on Latin squares. A proof of the Evans conjecture. Ars Combin. 11 (1981), 155–172. MR 0629869
[29] Sperner, E.: Note zu der Arbeit von Herrn B. L. van der Waerden: Ein Satz über Klasseneinteilungen von endlichen Mengen. Abh. Math. Semin. Univ. Hambg. 5 (1927), 232. DOI 10.1007/BF02952523 | MR 3069478
[30] Strang, G.: Introduction to applied mathematics. Wellesley-Cambridge Press, 1986. MR 0870634
[31] van der Waerden, B. L.: Ein Satz über Klasseneinteilungen von endlichen Mengen. Abh. Math. Semin. Univ. Hambg. 5 (1927), 185–187. DOI 10.1007/BF02952519 | MR 3069474
[32] Weyl, H.: Almost periodic invariant vector sets in a metric vector space. Amer. J. Math. 71 (1949), 178–205. DOI 10.2307/2372104 | MR 0028530
[33] Wikipedia, The Free Encyclopedia: Hopcroft–Karp algorithm. [online]. Dostupné z: https://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm
[34] Zhan, X.: Matrix theory. American Mathematical Society, 2013. MR 3076701
Search
Partner of
