Colorings of Infinite Graphs

Abstract

COLORINGS OF INFINITE GRAPHS DÁVID UHRIK Abstract: This thesis focuses on the study of uncountable graphs in relation to Ramsey theory, the chromatic number, and the uncountable Hadwiger conjec- ture. A large part of this text deals with constructions of uncountable graphs in Cohen forcing extensions. We show that adding ω2 Cohen reals forces the partition relation ω2 → (ω2, ω : ω)2 but it also forces that ω2 ̸→ (ω2, ω : ω1)2 . An unpublished result of Stevo Todorčević is proved-adding a single Cohen real forces that ω1 ̸→ (ω1, ω : 2)2 . From a single Cohen real, we also construct a triangle-free Hajnal-Máté graph, answering a question of Dániel Soukup. Using the same method, we construct a T-Hajnal-Máté graph with the same properties in ZFC, extending a result of Péter Komjáth and Saharon Shelah. Section 2.4.1 concentrates on a different generalization of HM graphs, the so-called δ-Hajnal- Máté graphs. We show that they do not exist under MA(ω1). In the same section, we also deduce a weak partition relation: ω2 → (ω1, δ : 2)2 , where δ is any count- able ordinal, which holds in ZFC and is related to an old result of Fred Galvin. In Chapter 3, we focus on the uncountable Hadwiger conjecture. We introduce the cardinal invariant hc, the least size of a counterexample to the uncountable Hadwiger conjecture. We...

BARVENÍ NEKONEČNÝCH GRAFŮ DÁVID UHRIK Abstrakt: Táto práca sa sústreďuje na analýzu nespočitateľných grafov v súvis- losti s rozkladovými šípkami, chromatickým číslom a nespočitateľnou Hadwi- gerovou domnienkou. Značná časť textu sa zaoberá konštrukciou nespočitateľ- ných grafov v generických rozšíreniach po pridaní Cohen reálnych čísel. Ukážeme, že ak sa pridá ω2 Cohen čísel, tak v rozšírení platí, že ω2 → (ω2, ω : ω)2 , zároveň ale platí ω2 ̸→ (ω2, ω : ω1)2 . Dokážeme aj nepublikovaný výsledok Steva Todor- čevića, že po pridaní jedného Cohen čísla máme ω1 ̸→ (ω1, ω : 2)2 . Z jedného Cohen čísla skonštruujeme aj Hajnal-Máté graf bez trojuholníkov, čím dávame pozitívnu odpoveď na otázku Dániela Soukupa. Rovnakou metódou zostrojíme aj príklad T-Hajnal-Máté grafu v ZFC s rovnakými vlastnosťami, čím rozšírime výsledok Pétera Komjátha a Saharona Shelaha. V sekcií 2.4.1 sa sústredíme na iné zovšeobecnenie HM grafov, takzvané δ-Hajnal-Máté grafy. Ukážeme, že za predpokladu MA(ω1) žiadne neexistujú. V tej istej sekcií odvodíme aj slabú rozkladovú šípku: ω2 → (ω1, δ : 2)2 , kde δ je spočitateľný ordinál, ktorá súvisí so starým výsledkom Freda Galvina. V kapitole 3 sa sústredíme na nespoči- tateľnú Hadwigerovu domnienku, zavedieme kardinálny invariant hc, určujúci najmenšiu veľkosť grafu, ktorý je protipríkladom na...