Ramsey numbers

This thesis is devoted to estimating Ramsey numbers, which is a central problem in combinatorics.The Ramsey number rk(s, n) is the minimum N such that every red-blue coloring of the k-tuples of an N-element set contains a red set of size s or a blue set of size n, where a set is called red (blue) if all k-tuples from this set are red (blue). We prove new upper and lower bounds for rk( s, n) for k &ge 3. Our upper bound is a substantial improvement on the previous upper bound of Erd&odblacs and Rado from 1952, and our lower bound answers a question posed by Erd&odblacs and Hajnal in 1972. We also answer another question of Erd&odblacs and Hajnal from 1989, showing that the maximum almost monochromatic subset that an &ell-coloring of the triples of an N-element set must contain is much larger than the corresponding monochromatic subset.The Ramsey number r(H) of a graph H is the least positive integer N such that every two-coloring of the edges of the complete graph KN contains a monochromatic copy of H. We make progress on the classical problem of estimating Ramsey numbers of graphs and hypergraphs of bounded degree.The induced Ramsey number rind(H ) of a graph H is the least positive integer N for which there exists a graph G on N vertices such that every two-coloring of the edges of G contains an induced monochromatic copy of H. We make progress on an old conjecture of Erd&odblacs by proving a new upper bound on the induced Ramsey number for graphs on n vertices. We also prove a polynomial upper bound on the induced Ramsey number of graphs of bounded degeneracy, which improves an earlier result of Luczak and Rodl which settled a conjecture of Trotter.The triangle removal lemma states that every graph on n vertices with o(n3) triangles can be made triangle-free by removing o(n 2) edges. We give a new proof which avoids Szemeredi's regularity lemma and gives a better bound. This answers questions posed by Alon, Erd&odblacs, Gowers, and Tao.