Geodesic
Hallova věta, její aplikace a historie
Pokroky matematiky, fyziky a astronomie, Tome 63 (2018) no. 3, pp. 175-195 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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í.
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í.
Classification : 01A60, 05-01, 05-03 
@article{PMFA_2018_63_3_a1,
     author = {Slav{\'\i}k, Anton{\'\i}n},
     title = {Hallova v\v{e}ta, jej{\'\i} aplikace a historie},
     journal = {Pokroky matematiky, fyziky a astronomie},
     pages = {175--195},
     year = {2018},
     volume = {63},
     number = {3},
     language = {cs},
     url = {http://geodesic.mathdoc.fr/item/PMFA_2018_63_3_a1/}
}
TY  - JOUR
AU  - Slavík, Antonín
TI  - Hallova věta, její aplikace a historie
JO  - Pokroky matematiky, fyziky a astronomie
PY  - 2018
SP  - 175
EP  - 195
VL  - 63
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/PMFA_2018_63_3_a1/
LA  - cs
ID  - PMFA_2018_63_3_a1
ER  - 
%0 Journal Article
%A Slavík, Antonín
%T Hallova věta, její aplikace a historie
%J Pokroky matematiky, fyziky a astronomie
%D 2018
%P 175-195
%V 63
%N 3
%U http://geodesic.mathdoc.fr/item/PMFA_2018_63_3_a1/
%G cs
%F PMFA_2018_63_3_a1
Slavík, Antonín. Hallova věta, její aplikace a historie. Pokroky matematiky, fyziky a astronomie, Tome 63 (2018) no. 3, pp. 175-195. http://geodesic.mathdoc.fr/item/PMFA_2018_63_3_a1/

[1] Aigner, M., Ziegler, G. M.: Proofs from THE BOOK. 6th edition, Springer, 2018. | MR

[2] Ardila, F., Stanley, R. P.: Tilings. Math. Intelligencer 32 (2010), 32–43. | DOI | MR

[3] Bachelis, G. F.: A short proof of Hall’s theorem on SDRs. Amer. Math. Monthly 109 (2002), 473–474. | DOI | MR

[4] Bryant, V.: Aspects of combinatorics. A wide-ranging introduction. Cambridge University Press, 1993. | MR

[5] Easterfield, T. E.: A combinatorial algorithm. J. Lond. Math. Soc. 21 (1946), 219–226. | DOI | MR

[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 | MR

[8] Everett, C. J., Whaples, G.: Representations of sequences of sets. Amer. J. Math. 71 (1949), 287–293. | DOI | MR

[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 | MR

[11] Hall, M.: Distinct representatives of subsets. Bull. Amer. Math. Soc. 54 (1948), 922–926. | DOI | MR

[12] Hall, M.: Combinatorial theory. 2nd ed., John Wiley, 1986. | MR

[13] Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 10 (1935), 26–30. | DOI | Zbl

[14] Halmos, P. R., Vaughan, H. E.: The marriage problem. Amer. J. Math. 72 (1950), 214–215. | DOI | MR

[15] König, D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77 (1916), 453–465. | DOI | MR

[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 | MR

[19] Leep, D. B., Myerson, G.: Marriage, magic, and solitaire. Amer. Math. Monthly 106 (1999), 419–429. | DOI | MR

[20] Maak, W.: Eine neue Definition der fastperiodischen Funktionen. Abh. Math. Semin. Univ. Hambg. 11 (1935), 240–244. | DOI | MR

[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 | MR

[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 | MR

[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 | MR

[28] Smetaniuk, B.: A new construction on Latin squares. A proof of the Evans conjecture. Ars Combin. 11 (1981), 155–172. | MR

[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 | MR

[30] Strang, G.: Introduction to applied mathematics. Wellesley-Cambridge Press, 1986. | MR

[31] van der Waerden, B. L.: Ein Satz über Klasseneinteilungen von endlichen Mengen. Abh. Math. Semin. Univ. Hambg. 5 (1927), 185–187. | DOI | MR

[32] Weyl, H.: Almost periodic invariant vector sets in a metric vector space. Amer. J. Math. 71 (1949), 178–205. | DOI | MR

[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