Coloring number and online Ramsey theory for grap

Authors: H A Kierstead Goran Konjevod

Publish Date: 2009/05/09

Volume: 29, Issue: 1, Pages: 49-64

PDF Link

Abstract

Let cst be positive integers The cstRamsey game is played by Builder and Painter Play begins with an suniform hypergraph G 0=VE 0 where E 0=Ø and V is determined by Builder On the ith round Builder constructs a new edge e i distinct from previous edges and sets G i =VE i where E i =E i−1∪e i Painter responds by coloring e i with one of c colors Builder wins if Painter eventually creates a monochromatic copy of K s t the complete suniform hypergraph on t vertices otherwise Painter wins when she has colored all possible edgesWe extend the definition of coloring number to hypergraphs so that χG≤colG for any hypergraph G and then show that Builder can win cstRamsey game while building a hypergraph with coloring number at most colK s t An important step in the proof is the analysis of an auxiliary survival game played by Presenter and Chooser The pstsurvival game begins with an suniform hypergraph H 0 = VØ with an arbitrary finite number of vertices and no edges Let H i−1=V i−1E i−1 be the hypergraph constructed in the first i − 1 rounds On the ith round Presenter plays by presenting a psubset P i ⊆V i−1 and Chooser responds by choosing an ssubset X i ⊆P i The vertices in P i − X i are discarded and the edge X i added to E i−1 to form E i Presenter wins the survival game if H i contains a copy of K s t for some i We show that for positive integers pst with s≤p Presenter has a winning strategy

Keywords: