Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 24, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Elias Vicari
In this talk we will present a deterministic proof of Spencer's lower bound for the off-diagonal Ramsey numbers. The basic tool will be the Erdős-Selfridge theorem (biased version), a well-known result from the field of positional games. We will interpret the Ramsey problem as a positional game, where two players alternately color edges of a complete graph Km. The goal of both is to color monochromatically the edge set of a copy of a target complete graph Ks and Kn, respectively (for s fix and n growing). If the board size m=m(n) is not too big, we will be able to provide both players a deterministic drawing strategy, which would imply that R(s,n)>m.
Automatic MiSe System Software Version 1.4803M | admin login