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.