|
|
Colorings of Infinite Graphs
Uhrik, Dávid ; Chodounský, David (advisor) ; Rinot, Assaf (referee) ; Raghavan, Dilip (referee)
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...
|
|
| |
|
| |
|
|
Definable graphs
Grebík, Jan ; Chodounský, David (advisor) ; Kurka, Ondřej (referee) ; Zapletal, Jindřich (referee)
In this thesis we consider various questions and problems about graphs that appear in the framework of descriptive set theory. The main object of study are graphons, graphings and variations of the graph G0. We establish an approach to the compactness of the graphon space via the weak* topology and introduce the notion of a fractional isomorphism for graphons. We use a variant of the G0-dichotomy in the context of the classification problem. Finally, we show a measurable version of the Vizing's theorem for graphings. 1
|
|
|
Products of Fréchet spaces
Olšák, Miroslav ; Simon, Petr (advisor) ; Chodounský, David (referee)
The article gives a constructions of k-tuples of topological spaces such that the product of the k-tuple is not Frchet-Urysohn but all smaller subproducts are. The construction uses almost disjoint systems. The article repeats the construction by Petr Simon of two such compact spaces. To achieve more dimensional example there are generalized terms of AD systems. The example is constructed under the assumption of existence of a strong completely separable MAD system. It is then constructed under the assumption s ≤ b where s is the splitting number and b is the bounding number.
|
|
|
On the Katowice Problem
Chodounský, David
N;izev piace: On the Kiitinvk-t* Problem Autor: Da\d t'liodounsky Kaieilra: Kaiedra teoieticke inlbrmaliky ;i inaiemaiickd logiky Vedinici dizenaCni prate: 1'iof. RNDr. Petr Simon, DrSc. e-mail \vJouviho: petr.Miiion(«nis.mfl cunt.c/ Ahstrakt Price po|ednava tak/vaiiem Katovickem pioblcmu, ledy olazce zda jc isomniliMiius mc/i P(uf)/ Kin a T(WI )/ l-'in kiin/isleiiini s1 aiioniy 7.FC. Hlavnmi obsaheni je vy\oj no\ych michigovych technik produkazy kon/.istenci souvisejicich s Katovickym problemem. Prvtii kapilola ohsahuje pfehled /namych vy^ledku. kiere se ivkaji icto prohlematiky Diuh.i kapnola i.c uvod do filler games, melody vyvimue I:. Galvinein a C. Laflammcm. Je /dc lovne? delinovana nova tower game a di>ka/;iim, /e prvtif tirat nonia v (eto life vyliravajiVi' Mialeiiii, pnkuil prisliiMia lira LienL-iUjo non-nie,igi.'i liln Ti'nuo je /esilen i?a piedpokhuiu CH) klasieky vvsledek pro p-liliei ganii-'s. Tenio v\'slfdek |e klieovy pro diika-c propeiness Ibiviiigii v nasledujieieli kapitolaeh. ITetf kapilola oKsahuje č|C(lniKJuscn<ui pruseniiici vysledku S Shckiha o knn/islentni' i'\islenci pou/e jodinohu p-hodu. Ctvrta kajiilola pojednavaosliong-Q-posloiipiiosteeh v P(^'}/ Fin . Jejiodam pfehled vysledku J. Steprause /.telo ohlaMi a je vyhudovan *'u; hounding forcing pfidavajiVi stiong-Q-posloiipnost. To...
|
|
|
Definable graphs
Grebík, Jan ; Chodounský, David (advisor) ; Kurka, Ondřej (referee) ; Zapletal, Jindřich (referee)
In this thesis we consider various questions and problems about graphs that appear in the framework of descriptive set theory. The main object of study are graphons, graphings and variations of the graph G0. We establish an approach to the compactness of the graphon space via the weak* topology and introduce the notion of a fractional isomorphism for graphons. We use a variant of the G0-dichotomy in the context of the classification problem. Finally, we show a measurable version of the Vizing's theorem for graphings. 1
|
|
|
Diamond principles and GCH
Fuková, Kateřina ; Šaroch, Jan (advisor) ; Chodounský, David (referee)
Diamond principles and the generalized continuum hypothesis are assertions related to infinite combinatorics. This thesis studies various connections between these assertions. From numerous formulations of diamond principles, it explicitly mentions exactly two of them: ♢S and ♢∗ S. Apart from an overview of the basic notions involved in this study, the thesis also contains a concise proof of Shelah's theorem published in the paper "Diamonds" in 2010. 1
|
|
|
Products of Fréchet spaces
Olšák, Miroslav ; Simon, Petr (advisor) ; Chodounský, David (referee)
The article gives a constructions of k-tuples of topological spaces such that the product of the k-tuple is not Frchet-Urysohn but all smaller subproducts are. The construction uses almost disjoint systems. The article repeats the construction by Petr Simon of two such compact spaces. To achieve more dimensional example there are generalized terms of AD systems. The example is constructed under the assumption of existence of a strong completely separable MAD system. It is then constructed under the assumption s ≤ b where s is the splitting number and b is the bounding number.
|
|
|
Logical background of forcing
Glivická, Jana ; Honzík, Radek (advisor) ; Chodounský, David (referee)
This thesis examines the method of forcing in set theory and focuses on aspects that are set aside in the usual presentations or applications of forcing. It is shown that forcing can be formalized in Peano arithmetic (PA) and that consis- tency results obtained by forcing are provable in PA. Two ways are presented of overcoming the assumption of the existence of a countable transitive model. The thesis also studies forcing as a method giving rise to interpretations between theories. A notion of bi-interpretability is defined and a method of forcing over a non-standard model of ZFC is developed in order to argue that ZFC and ZF are not bi-interpretable. 1
|
guest ::
