Definable Combinatorics of Graphs and Equivalence Relations

Citation

Meehan, Connor George Walmsley (2018) Definable Combinatorics of Graphs and Equivalence Relations. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/45E4-MC27. https://resolver.caltech.edu/CaltechTHESIS:06012018-160828760

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₀, …, F_n-1: X → X are Borel functions, let D_{F0, …, Fn-1} be the directed graph that they generate. It is an open problem if χ_B(D_{F0, …, Fn-1}) ∈ {1, …, 2n + 1, ℵ₀}. 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, …, Fn-1}↾ 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]ⁿ_E = {(x₀, ..., x_{n - 1}) ∈ ⁿX: (∀i,j)(i ≠ j → ¬(x_i E x_j))}. For n ∈ ω, a set X has the n-Jónsson property if and only if for every function f: [X]ⁿ₌ → X, there exists some Y ⊆ X with X and Y in bijection so that f[[Y]ⁿ₌] ≠ X. A set X has the Jónsson property if and only for every function f : (⋃_{n ∈ ω} [X]ⁿ₌) → X, there exists some Y ⊆ X with X and Y in bijection so that f[⋃_{n ∈ ω} [Y]ⁿ₌] ≠ X. Let n ∈ ω, X be a Polish space, and E be an equivalence relation on X. E has the n-Mycielski property if and only if for all comeager C ⊆ ⁿX, there is some Borel A ⊆ X so that E ≤_B E ↾ A and [A]ⁿ_E ⊆ C. The following equivalence relations will be considered: E₀ is defined on ^ω2 by x E₀ y if and only if (∃n)(∀k > n)(x(k) = y(k)). E₁ is defined on ^ω(^ω2) by x E₁ y if and only if (∃n)(∀k > n)(x(k) = y(k)). E₂ is defined on ^ω2 by x E₂ y if and only if ∑{¹⁄_{(n + 1)}: x(n) ≠ y(n)} < ∞. E₃ is defined on ^ω(^ω2) by x E₃ y if and only if (∀n)(x(n) E₀ y(n)). Holshouser and Jackson have shown that ℝ is Jónsson under AD. The present research will show that E₀ does not have the 3-Mycielski property and that E₁, E₂, and E₃ do not have the 2-Mycielski property. Under ZF + AD, ^ω2/E₀ does not have the 3-Jónsson property.

Let G = (X, G) be a graph and define for b ≥ 1 its b-fold chromatic number χ^(b)(G) as the minimum size of Y such that there is a function c from X into b-sets 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.

Thesis Files