Definable Combinatorics of Graphs and Equivalence Relations

Author: Meehan, Connor George Walmsley

Year: 2018

Degree: Dissertation (Ph.D.)

Advisor: Kechris, Alexander S.

Committee Members: Kechris, Alexander S.; Tamuz, Omer; Graber, Thomas B.; Lupini, Martino

Option: Mathematics

DOI: 10.7907/45E4-MC27

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 F0, …, Fn-1: X → X are Borel functions, let DF0, …, Fn-1 be the directed graph that they generate. It is an open problem if χB(DF0, …, Fn-1) ∈ {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 Fj, there exists an increasing filtration X = ⋃m < ω Xm such that χB(DF0, …, Fn-1↾ Xm) ≤ 2n for each m. We also prove that if n = 2 in the previous case, then χB(DF0, F1) ≤ 4. It follows that the approximate measure chromatic number χapM(D) ≤ 2n + 1 when the functions commute.

If X is a set, E is an equivalence relation on X, and n ∈ ω, then define [X]nE = {(x0, ..., xn - 1) ∈ nX: (∀i,j)(i ≠ j → ¬(xi E xj))}. For n ∈ ω, a set X has the n-Jó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 n-Mycielski property if and only if for all comeager C ⊆ nX, there is some Borel A ⊆ X so that E ≤B E ↾ A and [A]nE ⊆ C. The following equivalence relations will be considered: E0 is defined on ω2 by x E0 y if and only if (∃n)(∀k > n)(x(k) = y(k)). E1 is defined on ω(ω2) by x E1 y if and only if (∃n)(∀k > n)(x(k) = y(k)). E2 is defined on ω2 by x E2 y if and only if ∑{1⁄(n + 1): x(n) ≠ y(n)} < ∞. E3 is defined on ω(ω2) by x E3 y if and only if (∀n)(x(n) E0 y(n)). Holshouser and Jackson have shown that ℝ is Jónsson under AD. The present research will show that E0 does not have the 3-Mycielski property and that E1, E2, and E3 do not have the 2-Mycielski property. Under ZF + AD, ω2/E0 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) = infb χ(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 χfB(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 χfBM(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.

Files