Mathematics Colloquium: Hong Wang
Thursday, March 1 2012 at 3:30 PM
Location: TLC 032
Mathematics Colloquium: Hong Wang (University of Idaho) titled "Turán Number, Ramsey Number and The Regularity Lemma" will
occur March 1 at 3:30 p.m. in TLC 032.
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 Erdos-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.