printable pdf
比利时vs摩洛哥足彩 ,
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

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