Hales-Jewettov teorem i njegove posljedice

master's thesis

• Title (english): The Hales-Jewett theorem and its consequences
• Author: Bojan Štetić
• Mentor: Nina Kamčev (mentor)
• Committee member: Nina Kamčev (predsjednik povjerenstva)
• Committee member: Vedran Čačić (član povjerenstva)
• Committee member: Rudi Mrazović (član povjerenstva)
• Committee member: Mea Bombardelli (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2024-11-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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... More 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. Less

Abstract (english)

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... More 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. Less

• Keywords: 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
• Keywords (english): 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
• Language: croatian
• URN:NBN: urn:nbn:hr:217:732117
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar računarstva i matematike (sveučilišni magistar računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-11-13 10:42:31