Department of Mathematics Colloquium

University of Idaho

Spring 2012

Thursday,  March 1, 3:30-4:20 pm, room TLC 032

Refreshments in Brink 305 at 3:00 pm

Turán Number, Ramsey Number and
The Regularity Lemma

 

Hong Wang


Department of Mathematics

University of Idaho



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.