DICHOTOMY THEOREMS AND FRUCHT THEOREM IN DESCRIPTIVE GRAPH COMBINATORICS

Date

2023-8-18

Author

Bilge, Onur

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

125
views

144
downloads

Cite This

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.

Subject Keywords

Borel chromatic number, Dichotomy, Borel graph automorphism, Frucht’s theorem

URI

https://hdl.handle.net/11511/105203

Collections

Graduate School of Natural and Applied Sciences, Thesis