Bilge, Onur
Descriptive graph combinatorics studies graph-theoretic concepts under definable constraints. The systematic study of the field was started by Kechris, Solecki and Todorčević and the field has been mainly focused on Borel chromatic numbers and Borel matchings. One of the major investigations in the field has been about finding conditions for a definable graph to have a specific Borel chromatic number. The G₀ dichotomy theorem is one such theorem for graphs with uncountable Borel chromatic numbers. After the first proof of this dichotomy theorem, a classical proof was found by Ben Miller. Later, Carroy, Miller, Schrittesser and Vidnyánszky used this technique to prove the L₀ dichotomy theorem, an analogue of the G₀ dichotomy theorem for Borel chromatic number at least three. In the first part of this thesis, we provide a survey of these results. In the second part, we will be concerned with definable automorphism groups of definable graphs. In classical graph theory, one of the most prominent theorems in the study of automorphism groups of graphs is Frucht theorem that states that any group can be realized as the automorphism group of a graph. We will prove that Frucht theorem generalizes to both topological and Borel measurable setting. More specifically, we shall show that every standard Borel group (respectively, Polish group) can be realized as the Borel (respectively, homeomorphic) automorphism group of a Borel graph on a standard Borel (respectively, Polish) space.
Citation Formats
O. Bilge, “DICHOTOMY THEOREMS AND FRUCHT THEOREM IN DESCRIPTIVE GRAPH COMBINATORICS,” M.S. - Master of Science, Middle East Technical University, 2023.