Title Hallov teorem
Title (english) Hall's theorem
Author Jelena Mišerić
Mentor Slaven Kožić (mentor)
Committee member Slaven Kožić (predsjednik povjerenstva)
Committee member Marko Tadić (član povjerenstva)
Committee member Ozren Perše (član povjerenstva)
Committee member Nela Bosner (član povjerenstva)
Granter University of Zagreb Faculty of Science (Department of Mathematics) Zagreb
Defense date and country 2020-09-28, Croatia
Scientific / art field, discipline and subdiscipline NATURAL SCIENCES Mathematics
Abstract U ovom radu cilj je bio dokazati i vidjeti primjene jednog od važnijih teorema iz područja kombinatorike, Hallovog teorema. U prvom dijelu rada iskazana je njegova kombinatorna formulacija i ekvivalencija u smislu teorije grafova i sparivanja te su dana četiri različita dokaza Hallovog teorema. Prvi iskaz teorema govori o nužnom i dovoljnom uvjetu za postojanje transverzale danih konačnih skupova. Jednostavnom generalizacijom dolazi se do iskaza Hallovog teorema u smislu teorije grafova koji govori o nužnom i dovoljnom uvjetu za postojanje potpunog sparivanja u bipartitnom grafu. Na kraju drugog poglavlja iskazane su i neke posljedice iz područja kombinatorike, teorije skupova, teorije grupa i linearne algebre. Nadalje, u posljednjem poglavlju smo pokazali da je on samo jedan u nizu ekvivalentnih teorema čija primjena se širi na mnoga područja matematike pa je i motivacija koju smo vidjeli na početku rada raznolika. Medu ekvivalentne teoreme pripadaju osim Hallovog još Koenigov, Dilworthov, Mengerov, Birkhoff-Von Neumannov teorem i drugi. U radu su iskazani i dokazani navedeni teoremi i prikazana je njihova primjena. Vidjeli smo da objekti koji se promatraju u tim teoremima sežu od jednostavnih grafova (Mengerov i Koenigov teorem), binarnih matrica (Koenigov teorem) i dvostruko stohastičih matrica (Birkhoff-Von Neumannov teorem) do parcijalno uredenih skupova (Dilworthov teorem). Upoznali smo se i s latinskim pravokutnicima, još jednom specifičnom vrstom matrica, te smo pokazali da je Hallov teorem zaslužan za dokaz jednog od važnijih teorema o latinskim pravokutnicima.
Abstract (english) The aim of this thesis was to prove and present the applications of one of the central theorems in the field of combinatorics, Hall’s theorem. Through the first part of the thesis we have expressed its combinatorial formulation, equivalence in terms of graph theory and matching and provided four different proofs. The first statement of the theorem gives the necessary and suficient condition for the existence of a system of distinct representatives of given sets. A simple generalization leads to the statement of Hall’s theorem in terms of graph theory, which speaks of a necessary and suficient condition for the existence of complete matching in a bipartite graph. At the end of the second chapter, several consequences from the field of combinatorics, set theory, group theory and linear algebra are presented. Furthermore, in the last chapter we have shown that Hall’s theorem is one in a sequence of equivalent theorems whose application extends to many areas of mathematics, so the motivation we saw at the beginning of the paper is diverse. Among the equivalent theorems, in addition to Hall’s theorem, there are Koenig’s, Dilworth’s, Menger’s, Birkhoff-Von Neumann theorem, and others. These theorems are stated and proved in this thesis and their application is presented. We have seen that the objects observed in these theorems vary from simple graphs (Menger’s and Koenig’s theorem), binary matrices (Koenig’s theorem) and doubly stochastic matrices (Birkhoff-Von Neumann theorem) to partially ordered sets (Dilworth’s theorem). We were also introduced to Latin rectangles, another specific type of matrix, and have shown that Hall’s theorem is responsible for proving one of the most important theorems in Latin rectangles.
Keywords
bipartitni graf
kombinatorika
teorija skupova
teorija grupa
linearna algebra
Koenigov teorem
Dilworthov teorem
Mengerov teorem
Birkhoff-Von Neumannov teorem
Keywords (english)
bipartite graph
combinatorics
set theory
group theory
linear algebra
Koenig’s theorem
Dilworth’s theorem
Menger’s theorem
Birkhoff-Von Neumann theorem
Language croatian
URN:NBN urn:nbn:hr:217:952118
Study programme Title: Computer Science and Mathematics Study programme type: university Study level: graduate Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
Type of resource Text
File origin Born digital
Access conditions Open access
Terms of use
Repository Repository of the Faculty of Science
Created on 2021-03-01 13:18:00