Date: Thursday, March 10, 2016
Location: 2866 East Hall (4:00 PM to 5:30 PM)
Title: Rado's Path Decomposition
Abstract: 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 Erdos, 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.
Files:
Speaker: Peter Cholak
Institution: Notre Dame University
Event Organizer: Andreas Blass ablass@umich.edu
|