A Caltech Library Service

Definable Combinatorics of Graphs and Equivalence Relations


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


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: XX 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 xX to a fixed point of some Fj, there exists an increasing filtration X = ⋃m < ω Xm such that χB(DF0, …, Fn-1Xm) ≤ 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)(ij → ¬(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 YX 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 YX 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 CnX, there is some Borel AX so that EB EA and [A]nEC. 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.

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):
  • Kechris, Alexander S.
Thesis Committee:
  • Kechris, Alexander S. (chair)
  • Tamuz, Omer
  • Graber, Thomas B.
  • Lupini, Martino
Defense Date:22 May 2018
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC)Postgraduate Scholarship-Doctoral Program (PGS D)
Record Number:CaltechTHESIS:06012018-160828760
Persistent URL:
Related URLs:
URLURL TypeDescription adapted for Chapter 3
Meehan, Connor George Walmsley0000-0002-7596-2437
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11006
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.


Repository Staff Only: item control page