Department of Mathematics Colloquium


Abstract 

One of the powerful tools in combinatorics is
the regularity lemma of Szemerédi. This talk is to introduce
this powerful regularity lemma and its related blowup methods.
We will begin with some basic definitions and then introduce
Turán numbers and Ramsey numbers in graphs. These serve as some
background for our introduction of the Regularity Lemma and Blowup
Lemma. I will outline the ideas in these two lemmas and demonstrate
their application in the proof of a 1975 ErdősBurr conjecture. The
conjecture deals with the 2color Ramsey number of a graph H, namely, the smallest integer r such that if the edges of the
complete graph K_{t} (t≥r) are colored by two colors, a
monochromatic copy of H must
occur. The conjecture states that for every positive integer Δ, there
exists a constant c, depending only on Δ, such that for every graph H on n vertices with maximum
degree at most Δ, the Ramsey number of H does not exceed cn. In other words, for every graph
G of order at least cn, either G contains H or the complement of G contains H. This conjecture has been
confirmed in 1983 by Chvátal, Rödl, Szemerédi and
Troter. Recently, in 2009 it has been determined by Conlon that c is
an exponential function of Δ. The talk is intended for general
math audience as well as mathematically specialists.
