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 blow-up 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 Blow-up
Lemma. I will outline the ideas in these two lemmas and demonstrate
their application in the proof of a 1975 Erdős-Burr conjecture. The
conjecture deals with the 2-color Ramsey number of a graph H, namely, the smallest integer r such that if the edges of the
complete graph Kt (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.
|