Hallov teorem

master's thesis

• 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
• Created on: 2021-03-01 13:18:00