Coloring problems in combinatorics and descriptive set theory.
Degree: PhD, Mathematics, 2018, University of Illinois – Urbana-Champaign
In this dissertation we study problems related to colorings of combinatorial structures both in the “classical” finite context and in the framework of descriptive set theory, with applications to topological dynamics and ergodic theory. This work consists of two parts, each of which is in turn split into a number of chapters. Although the individual chapters are largely independent from each other (with the exception of Chapters 4 and 6, which partially rely on some of the results obtained in Chapter 3), certain common themes feature throughout—most prominently, the use of probabilistic techniques.
In Chapter 1, we establish a generalization of the Lovász Local Lemma (a powerful tool in probabilistic combinatorics), which we call the Local Cut Lemma, and apply it to a variety of problems in graph coloring.
In Chapter 2, we study DP-coloring (also known as correspondence coloring)—an extension of list
coloring that was recently introduced by Dvorák and Postle. The goal of that chapter is to gain some
understanding of the similarities and the differences between DP-coloring and list coloring, and we find many instances of both.
In Chapter 3, we adapt the Lovász Local Lemma for the needs of descriptive set theory and use it to
establish new bounds on measurable chromatic numbers of graphs induced by group actions.
In Chapter 4, we study shift actions of countable groups on spaces of the form A, where A is a finite set, and apply the Lovász Local Lemma to find “large” closed shift-invariant subsets X A on which the induced action of is free.
In Chapter 5, we establish precise connections between certain problems in graph theory and in descriptive set theory. As a corollary of our general result, we obtain new upper bounds on Baire measurable chromatic numbers from known results in finite combinatorics.
Finally, in Chapter 6, we consider the notions of weak containment and weak equivalence of probability measure-preserving actions of a countable group—relations introduced by Kechris that are combinatorial in spirit and involve the way the action interacts with finite colorings of the underlying probability space.
This work is based on the following papers and preprints: [Ber16a; Ber16b; Ber16c; Ber17a; Ber17b;
Ber17c; Ber18a; Ber18b], [BK16; BK17a] (with Alexandr Kostochka), [BKP17] (with Alexandr Kostochka and Sergei Pron), and [BKZ17; BKZ18] (with Alexandr Kostochka and Xuding Zhu).
Advisors/Committee Members: Kostochka, Alexandr (advisor), Tserunyan, Anush (advisor), Balogh, Jozsef (Committee Chair), Solecki, Slawomir (committee member).
Subjects/Keywords: coloring; probabilistic method; Lovasz Local Lemma; graphs; hypergraphs; list coloring; DP-coloring; descriptive combinatorics; measurable dynamics; generic dynamics; symbolic dynamics; weak containment
to Zotero / EndNote / Reference
APA (6th Edition):
Bernshteyn, A. (2018). Coloring problems in combinatorics and descriptive set theory. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/101454
Chicago Manual of Style (16th Edition):
Bernshteyn, Anton. “Coloring problems in combinatorics and descriptive set theory.” 2018. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed April 02, 2020.
MLA Handbook (7th Edition):
Bernshteyn, Anton. “Coloring problems in combinatorics and descriptive set theory.” 2018. Web. 02 Apr 2020.
Bernshteyn A. Coloring problems in combinatorics and descriptive set theory. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2018. [cited 2020 Apr 02].
Available from: http://hdl.handle.net/2142/101454.
Council of Science Editors:
Bernshteyn A. Coloring problems in combinatorics and descriptive set theory. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2018. Available from: http://hdl.handle.net/2142/101454