Restricted Ramsey theorems and Combinatorial Games

Combinatorics Seminar
Friday, October 14, 2011 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Charles University, Prague
Ramsey theory studies the internal homogenity of mathematical structures (i.e. graphs, number sets), parts of which (subgraphs, number subsets) are arbitrarily coloured. Often, the sufficient object size implies the existence of a monochromatic sub-object. Combinatorial games are 2-player games of skill with perfect information. The theory of combinatorial games studies mostly the questions of existence of winning or drawing strategies. Let us consider an object that is studied by a particular Ramsey-type theorem. Assume two players alternately colour parts of this object by two colours and their goal is to create certain monochromatic sub-object. Then this is a combinatorial game. We focus on the minimum object size such that the appropriate Ramsey-type theorem holds, called "Ramsey number", and on the minimum object size such that the first player has a winning strategy in the corresponding combinatorial game, called "game number". In this talk, we investigate the "restricted Ramsey-type theorems". This means, we show the existence of first player's winning strategies, and we show that game numbers are surprisingly small, compared to Ramsey numbers. (This is joint work with Jarek Nesetril.)