55 KAM Mathematical Colloquium
Mikl\'os Simonovits
Alfr\'ed R\'enyi Institute of Mathematics, Budapest
TUR\'AN PROBLEMS, RAMSEY PROBLEMS, SIMPLE AND RANDOM-LOOKING EXTREMAL STRUCTURES
February 23, 2005
Lecture room S3, III. floor
10:30 AM
Abstract
Tur\'an and Ramsey type problems were always very closely related to each
other.
For the original questions (i.e., Ramsey numbers and Tur\'an numbers for
complete graphs) the extremal graphs were simple looking for Tur\'an type
problems and very involved for the Ramsey case. When the selected excluded
substructures were extended, the situation changed: Tur\'an type
problems with fuzzy extremal graphs and Ramsey extremal graphs with very
regular, simple structures occurred.
In my talk I will analyse this strong relation through some specific examples.
Among others, I will put emphasis on two basic cases, one of which is the
problem of 3-coloring the edges of a complete graph and looking for
monochromatic odd cycles. Recently Skokan, Kohayakawa and myself improved the corresponding
asymptotic result of \L uczak, proving an old conjecture of Bondy and
Erd\H{o}s, at least for $n$ large:
We have proved that if $n>n_0$ and $K_{4n-3}$ is 3-colored then it contains
a monochromatic $C_n$ (which is sharp for odd values of $n$).
Some related results of Figaj, \L uczak, Gy\'arf\'as, Ruszink\'o,
G. S\'ark\"ozy, and Szemer\'edi will also be discussed.
The proof was obtained using the Regularity Lemma and the stability method.
As I mentioned, the particular results will be embedded into discussing
phenomena from the general setting.
