Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Combinatorics Reading

Jacob Fox

MIT Graduate Student

Ramsey theory on the integers and reals

Abstract:

In this talk, I will present several classical results and remarkable new developments in Ramsey theory on the integers and reals. A system of linear equations is called partition $k$-regular if for every $k$-coloring of the positive integers, there exists a monochromatic solution to the given system of linear equations. Generalizing classical theorems of Schur and van der Waerden, Richard Rado classified those systems of linear equations that are partition $k$-regular for all positive integers $k$ in his famous 1933 dissertation {\it Studien zur Kombinatorik}. Rado further conjectured in his dissertation that there exists a function $K:N \to N$ such that if a linear equation $a_1x_1+ \cdots +a_nx_n=b$ is partition $K(n)$-regular, then it is partition $k$-regular for all positive integers k. D. Kleitman and I recently settled the first nontrivial case of this conjecture, known as Rado's Boundedness Conjecture. In particular, if $a$, $b$, $c$, and $d$ are integers, and if every $36$-coloring of the positive integers contains a monochromatic solution to $ax+by+cz=d$, then every finite coloring of the positive integers must have a monochromatic solution to $ax+by+cz=d$. The degree of regularity of an equation $a_1x_1+ \cdots +a_nx_n=0$ over $R$ is the largest positive integer $r$ (if it exists) such that every $r$-coloring of $R-{0}$ has a monochromatic solution to $a_1x_1+ \cdots +a_nx_n=0$. In 1943, Rado extended the results of his dissertation by classifying those equations that have finite degree of regularity over $R$. Motivated by recent results of S.\ Shelah and A.\ Soifer, R.\ Radoi\v{c}i\'{c} and I found equations whose degree of regularity over $R$ is dependent on the axioms for set theory. For example, in the Zermelo-Fraenkel-Choice (ZFC) system of axioms, we show there exists a $3$-coloring of the nonzero real numbers without a monochromatic solution to $x+2y=4z$. However, in a consistent system of axioms with limited choice studied by R.\ Solovay in 1970, every $3$-coloring of the nonzero real numbers contains a monochromatic solution to $x+2y=4z$. Time permitting, I will discuss applications to several related problems.

Host: Fan Chung Graham

August 11, 2005

1:00 PM

AP&M 7321

****************************