Naslov Hales-Jewettov teorem i njegove posljedice
Naslov (engleski) The Hales-Jewett theorem and its consequences
Autor Bojan Štetić
Mentor Nina Kamčev (mentor)
Član povjerenstva Nina Kamčev (predsjednik povjerenstva)
Član povjerenstva Vedran Čačić (član povjerenstva)
Član povjerenstva Rudi Mrazović (član povjerenstva)
Član povjerenstva Mea Bombardelli (član povjerenstva)
Ustanova koja je dodijelila akademski / stručni stupanj Sveučilište u Zagrebu Prirodoslovno-matematički fakultet (Matematički odsjek) Zagreb
Datum i država obrane 2024-11-27, Hrvatska
Znanstveno / umjetničko područje, polje i grana PRIRODNE ZNANOSTI Matematika
Sažetak U ovom radu izlažu se rezultati Ramseyeve teorije, sa fokusom na Hales-Jewettov i Van der Waerdenov teorem te njihove korolare. U prvom poglavlju uvodimo standardne oznake te definiramo pojam bojenja. Dalje uvodimo pojam Ramseyeve funkcije i dokazujemo konačne verzije Ramseyevog teorema te na kraju iznosimo beskonačnu verziju teorema. U drugom poglavlju iznosimo povijesnu pozadinu Van der Waerdenovog teorema te dajemo iskaz i dokaz teorema, koji koristi dvostruku indukciju. Nakon toga
... Više predstavljamo jači rezultat iz kojeg direktno slijedi Van der Waerdenov teorem. Treće poglavlje uvodi definicije n -dimenzionalne kocke na k elemenata te kombinatornog pravca i pomoću njih iskazuje Hales-Jewettov teorem. Nakon toga dajemo izvod Van der Waerdenovog teorema pomoću Hales-Jewettovog teorem. Sljedeće, predstavljamo skicu standardnog dokaza Hales-Jewettovog teorema, dvostrukom indukcijom, te na kraju prikazujemo Shelahov dokaz teorema, bez dvostruke indukcije. U četvrtom poglavlju prvo iznosimo Ackermannovu hijerarhiju funkcija. Pomoću nje iskazujemo ograde za Van der Waerdenove i Hales-Jewettove brojeve, dobivene prateći originalne dokaze tih teorema te prateći Shelahov dokaz. Nakon toga predstavljamo gornju ogradu za Hales-Jewettove brojeve, za kocke na 3 elementa, iz nedavnog reda Davida Conlona. Na kraju dajemo Berlekampovu donju ogradu za Van der Waerdenove brojeve te neformalno predstavljamo rezultate za donju ogradu 2 -bojnih Van der Waerdenovih brojeva iz nedavnih radova Greena i Huntera. U zadnjem poglavlju predstavljamo korolare Hales-Jewettovog teorema, Prošireni Hales-Jewettov teorem te Gallaiev teorem. Sljedeće, dokazujemo rezultat o postojanju uzastopnih kvadratnih ostataka, koji slijedi iz Van der Waerdenovog teorema. Na kraju predstavljamo neke otvorene probleme Ramseyeve teorije vezane uz rezultate ovog rada. Sakrij dio sažetka
Sažetak (engleski) In this thesis, we present the results of Ramsey theory, focusing on the Hales-Jewett and Van der Waerden theorems, along with their corollaries. In the first chapter, we introduce standard notations and give the definition of a coloring. Next, we introduce the Ramsey function and prove the finite versions of Ramsey's theorem, concluding with the infinite version of the theorem. In the second chapter, we provide the historical background of Van der Waerden's theorem and present its
... Više statement and proof, which uses double induction. After that, we introduce a stronger result from which Van der Waerden's theorem directly follows. The third chapter introduces the definitions of an n -dimensional cube over k elements and a combinatorial line, later using them to state the Hales-Jewett theorem. Following this, we derive Van der Waerden's theorem using the Hales-Jewett theorem. Next, we present an outline of the standard proof of the Hales-Jewett theorem, which employs double induction, and finally, we discuss Shelah’s proof of the theorem, which avoids double induction. In the fourth chapter, we first present the Ackermann hierarchy of functions. Using it, we establish bounds for the Van der Waerden and Hales-Jewett numbers, obtained by following the original proofs of these theorems and by following Shelah's proof. After that, we present an upper bound for the Hales-Jewett numbers for cubes over 3 elements, based on a recent paper by David Conlon. Finally, we present Berlekamp's lower bound for the Van der Waerden numbers and informally introduce results on the lower bound of 2 -color Van der Waerden numbers from recent works by Green and Hunter. In the final chapter, we present corollaries of the Hales-Jewett theorem, the Extended Hales-Jewett theorem, and Gallai's theorem. Next, we prove a result on the existence of consecutive quadratic residues, which follows from Van der Waerden's theorem. Finally, we introduce some open problems in Ramsey theory related to the results of this paper. Sakrij dio sažetka
Ključne riječi
Ramseyeva teorija
Ramseyev teorem
Hales-Jewettov teorem
Van der Waerdenov teorem
bojenje
aritmetički niz
n-dimenzionalna kocka na k elemenata
kombinatorni pravac
Shelah
dvostruka indukcija
ograda
Ackermannova hijerarhija
Conlon
Berlekamp
Green
Hunter
Gallaiev teorem
kvadratni ostaci
Ključne riječi (engleski)
Ramsey theory
Ramsey's theorem
Hales-Jewett theorem
Van der Waerden's theorem
coloring
arithmetic sequence
n-dimensional cube over k elements
combinatorial line
Shelah
double induction
bound
Ackermann hierarchy
Conlon
Berlekamp
Green
Hunter
Gallai's theorem
quadratic residues
Jezik hrvatski
URN:NBN urn:nbn:hr:217:732117
Studijski program Naziv: Računarstvo i matematika Vrsta studija: sveučilišni Stupanj studija: diplomski Akademski / stručni naziv: sveučilišni magistar računarstva i matematike (univ. mag. inf. et math.)
Vrsta resursa Tekst
Način izrade datoteke Izvorno digitalna
Prava pristupa Otvoreni pristup
Uvjeti korištenja
Datum i vrijeme pohrane 2024-11-13 10:42:31