Peter Cholak: Rado’s Path Decomposition

Thursday, March 10, 4:00-5:30 PM in 2866 East Hall

Let X be a countably infinite set, let r be a positive integer, and let c be a coloring of the two-element subsets of X with r colors.  By a path of color j, I mean a (finite or infinite, possibly empty) sequence (a_0, a_1, …) of distinct elements of X in which each pair of consecutive elements {a_i, a_(i+1)} has color j.  (The empty sequence and one-term sequences count as paths of color j for all j; for longer sequences, the color is unique.)  In 1978, improving an earlier result of Erdös, Rado proved that, in this situation, there are r paths, one of each color, which, as sets, partition X.  We will provide some results and proofs that allow us to analyze the effective content of this theorem.  These results and proofs are joint work with Greg Igusa, Ludovic Patey, Mariya Soskova, and Dan Turetsky.


Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.