Citation
Meehan, Connor George Walmsley (2018) Definable Combinatorics of Graphs and Equivalence Relations. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/45E4MC27. https://resolver.caltech.edu/CaltechTHESIS:06012018160828760
Abstract
Let D = (X, D) be a Borel directed graph on a standard Borel space X and let χ_{B}(D) be its Borel chromatic number. If F_{0}, …, F_{n1}: X → X are Borel functions, let D_{F0, …, Fn1} be the directed graph that they generate. It is an open problem if χ_{B}(D_{F0, …, Fn1}) ∈ {1, …, 2n + 1, ℵ_{0}}. Palamourdas verified the foregoing for commuting functions with no fixed points. We show here that for commuting functions with the property that there is a path from each x ∈ X to a fixed point of some F_{j}, there exists an increasing filtration X = ⋃_{m < ω} X_{m} such that χ_{B}(D_{F0, …, Fn1}↾ X_{m}) ≤ 2n for each m. We also prove that if n = 2 in the previous case, then χ_{B}(D_{F0, F1}) ≤ 4. It follows that the approximate measure chromatic number χ^{ap}_{M}(D) ≤ 2n + 1 when the functions commute.
If X is a set, E is an equivalence relation on X, and n ∈ ω, then define [X]^{n}_{E} = {(x_{0}, ..., x_{n  1}) ∈ ^{n}X: (∀i,j)(i ≠ j → ¬(x_{i} E x_{j}))}. For n ∈ ω, a set X has the nJónsson property if and only if for every function f: [X]^{n}_{=} → X, there exists some Y ⊆ X with X and Y in bijection so that f[[Y]^{n}_{=}] ≠ X. A set X has the Jónsson property if and only for every function f : (⋃_{n ∈ ω} [X]^{n}_{=}) → X, there exists some Y ⊆ X with X and Y in bijection so that f[⋃_{n ∈ ω} [Y]^{n}_{=}] ≠ X. Let n ∈ ω, X be a Polish space, and E be an equivalence relation on X. E has the nMycielski property if and only if for all comeager C ⊆ ^{n}X, there is some Borel A ⊆ X so that E ≤_{B} E ↾ A and [A]^{n}_{E} ⊆ C. The following equivalence relations will be considered: E_{0} is defined on ^{ω}2 by x E_{0} y if and only if (∃n)(∀k > n)(x(k) = y(k)). E_{1} is defined on ^{ω}(^{ω}2) by x E_{1} y if and only if (∃n)(∀k > n)(x(k) = y(k)). E_{2} is defined on ^{ω}2 by x E_{2} y if and only if ∑{^{1}⁄_{(n + 1)}: x(n) ≠ y(n)} < ∞. E_{3} is defined on ^{ω}(^{ω}2) by x E_{3} y if and only if (∀n)(x(n) E_{0} y(n)). Holshouser and Jackson have shown that ℝ is Jónsson under AD. The present research will show that E_{0} does not have the 3Mycielski property and that E_{1}, E_{2}, and E_{3} do not have the 2Mycielski property. Under ZF + AD, ^{ω}2/E_{0} does not have the 3Jónsson property.
Let G = (X, G) be a graph and define for b ≥ 1 its bfold chromatic number χ^{(b)}(G) as the minimum size of Y such that there is a function c from X into bsets of Y with c(x) ∩ c(y) = ∅ if x G y. Then its fractional chromatic number is χ^{f}(G) = inf_{b} ^{χ(b)(G)}⁄_{b} if the quotients are finite. If X is Polish and G is a Borel graph, we can also define its fractional Borel chromatic number χ^{f}_{B}(G) by restricting to only Borel functions. We similarly define this for Baire measurable and μmeasurable functions for a Borel measure μ. We show that for each countable graph G, one may construct an acyclic Borel graph G' on a Polish space such that χ^{f}_{BM}(G') = χ^{f}(G) and χ_{BM}(G') = χ(G), and similarly for χ^{f}_{μ} and χ_{μ}. We also prove that the implication χ^{f}(G) = 2 ⇒ χ(G) = 2 is false in the Borel setting.
Item Type:  Thesis (Dissertation (Ph.D.))  

Subject Keywords:  Descriptive set theory; graph theory; combinatorics; equivalence relations  
Degree Grantor:  California Institute of Technology  
Division:  Physics, Mathematics and Astronomy  
Major Option:  Mathematics  
Awards:  Apostol Award for Excellence in Teaching in Mathematics, 2014.  
Thesis Availability:  Public (worldwide access)  
Research Advisor(s): 
 
Thesis Committee: 
 
Defense Date:  22 May 2018  
Funders: 
 
Record Number:  CaltechTHESIS:06012018160828760  
Persistent URL:  https://resolver.caltech.edu/CaltechTHESIS:06012018160828760  
DOI:  10.7907/45E4MC27  
Related URLs: 
 
ORCID: 
 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  11006  
Collection:  CaltechTHESIS  
Deposited By:  Connor Meehan  
Deposited On:  04 Jun 2018 20:22  
Last Modified:  04 Oct 2019 00:22 
Thesis Files

PDF (Complete thesis)
 Final Version
See Usage Policy. 791kB 
Repository Staff Only: item control page