|
Ramsey theory and combinatorial games
Valla, Tomáš ; Nešetřil, Jaroslav (advisor)
Ramsey theory studies the internal homogenity of mathematical structures (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 rst player has a winning strategy in the corresponding combinatorial game, called game number. In this thesis, we describe such Ramsey-type theorems where the Ramsey number is substantially greater than the game number. This means, we show the existence of rst player's winning strategies, together with Ramsey and game numbers upper bounds, and we compare both numbers.
|
guest ::
