| Title:
|
Hallova věta, její aplikace a historie (Czech) |
| Title:
|
Hall's Marriage Theorem, Its Applications and History (English) |
| Author:
|
Slavík, Antonín |
| Language:
|
Czech |
| Journal:
|
Pokroky matematiky, fyziky a astronomie |
| ISSN:
|
0032-2423 |
| Volume:
|
63 |
| Issue:
|
3 |
| Year:
|
2018 |
| Pages:
|
175-195 |
| Summary lang:
|
Czech |
| . |
| Category:
|
math |
| . |
| 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í. (Czech) |
| MSC:
|
01A60 |
| MSC:
|
05-01 |
| MSC:
|
05-03 |
| . |
| Date available:
|
2018-11-02T16:32:34Z |
| Last updated:
|
2020-01-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147443 |
| . |
| Reference:
|
[1] Aigner, M., Ziegler, G. M.: Proofs from THE BOOK.. 6th edition, Springer, 2018. MR 3823190 |
| Reference:
|
[2] Ardila, F., Stanley, R. P.: Tilings.. Math. Intelligencer 32 (2010), 32–43. MR 2747701, 10.1007/s00283-010-9160-9 |
| Reference:
|
[3] Bachelis, G. F.: A short proof of Hall’s theorem on SDRs.. Amer. Math. Monthly 109 (2002), 473–474. MR 1901502, 10.1080/00029890.2002.11919877 |
| Reference:
|
[4] Bryant, V.: Aspects of combinatorics. A wide-ranging introduction.. Cambridge University Press, 1993. MR 1213683 |
| Reference:
|
[5] Easterfield, T. E.: A combinatorial algorithm.. J. Lond. Math. Soc. 21 (1946), 219–226. MR 0019575, 10.1112/jlms/s1-21.3.219 |
| Reference:
|
[6] Egerváry, J.: Matrixok kombinatórius tulajdonságairól.. Mat. Fiz. Lapok 38 (1931), 16–28. |
| Reference:
|
[7] Ehrenhorg, R: An unbiased marriage theorem.. Amer. Math. Monthly 122 (2015), 59. MR 3324955, 10.4169/amer.math.monthly.122.01.59 |
| Reference:
|
[8] Everett, C. J., Whaples, G.: Representations of sequences of sets.. Amer. J. Math. 71 (1949), 287–293. MR 0028914, 10.2307/2372244 |
| Reference:
|
[9] Frobenius, G.: Über zerlegbare Determinanten.. Sitzber. König. Preuss. Akad. Wiss. 18 (1917), 274–277. |
| Reference:
|
[10] Hall, M.: An existence theorem for Latin squares.. Bull. Amer. Math. Soc. 51 (1945), 387–388. MR 0013111, 10.1090/S0002-9904-1945-08361-X |
| Reference:
|
[11] Hall, M.: Distinct representatives of subsets.. Bull. Amer. Math. Soc. 54 (1948), 922–926. MR 0027033, 10.1090/S0002-9904-1948-09098-X |
| Reference:
|
[12] Hall, M.: Combinatorial theory.. 2nd ed., John Wiley, 1986. MR 0840216 |
| Reference:
|
[13] Hall, P.: On representatives of subsets.. J. Lond. Math. Soc. 10 (1935), 26–30. Zbl 0010.34503, 10.1112/jlms/s1-10.37.26 |
| Reference:
|
[14] Halmos, P. R., Vaughan, H. E.: The marriage problem.. Amer. J. Math. 72 (1950), 214–215. MR 0033330, 10.2307/2372148 |
| Reference:
|
[15] König, D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.. Math. Ann. 77 (1916), 453–465. MR 1511872, 10.1007/BF01456961 |
| Reference:
|
[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. |
| Reference:
|
[17] König, D.: Graphok és matrixok.. Mat. Fiz. Lapok 38 (1931), 116–119. |
| Reference:
|
[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. MR 0054933, 10.1007/BF02476378 |
| Reference:
|
[19] Leep, D. B., Myerson, G.: Marriage, magic, and solitaire.. Amer. Math. Monthly 106 (1999), 419–429. MR 1699260, 10.1080/00029890.1999.12005064 |
| Reference:
|
[20] Maak, W.: Eine neue Definition der fastperiodischen Funktionen.. Abh. Math. Semin. Univ. Hambg. 11 (1935), 240–244. MR 3069657, 10.1007/BF02940727 |
| Reference:
|
[21] Mareš, M., Valla, T.: Průvodce labyrintem algoritmů.. CZ.NIC, 2017. |
| Reference:
|
[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. MR 2593123, 10.1007/s10100-009-0125-z |
| Reference:
|
[23] Miller, G. A.: On a method due to Galois.. Quart. J. Math. 41 (1910), 382–384. |
| Reference:
|
[24] O’Connor, J. J., Robertson, E. F.: MacTutor History of Mathematics archive. [online]. Dostupné z: http://www-history.mcs.st-and.ac.uk/ |
| Reference:
|
[25] Pach, J., Morić, F.: Graph theory (Spring 2013). [online]. Dostupné z: http://sma.epfl.ch/~moric/gt2013/ |
| Reference:
|
[26] Shamir, E., Sudakov, B.: Two-sided, unbiased version of Hall’s marriage theorem.. Amer. Math. Monthly 124 (2017), 79–80. MR 3608689, 10.4169/amer.math.monthly.124.1.79 |
| Reference:
|
[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. MR 0446850, 10.1016/0024-3795(77)90070-2 |
| Reference:
|
[28] Smetaniuk, B.: A new construction on Latin squares. A proof of the Evans conjecture.. Ars Combin. 11 (1981), 155–172. MR 0629869 |
| Reference:
|
[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. MR 3069478, 10.1007/BF02952523 |
| Reference:
|
[30] Strang, G.: Introduction to applied mathematics.. Wellesley-Cambridge Press, 1986. MR 0870634 |
| Reference:
|
[31] van der Waerden, B. L.: Ein Satz über Klasseneinteilungen von endlichen Mengen.. Abh. Math. Semin. Univ. Hambg. 5 (1927), 185–187. MR 3069474, 10.1007/BF02952519 |
| Reference:
|
[32] Weyl, H.: Almost periodic invariant vector sets in a metric vector space.. Amer. J. Math. 71 (1949), 178–205. MR 0028530, 10.2307/2372104 |
| Reference:
|
[33] Wikipedia, The Free Encyclopedia: Hopcroft–Karp algorithm. [online]. Dostupné z: https://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm |
| Reference:
|
[34] Zhan, X.: Matrix theory.. American Mathematical Society, 2013. MR 3076701 |
| . |
