Coloring number and on-line Ramsey theory for graphs and hypergraphs

摘要

Let c,s,t be positive integers. The (c,s,t)-Ramsey game is played by Builder and Painter. Play begins with an s-uniform hypergraph G ₀=(V,E ₀), where E ₀=Ø 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 =(V,E _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 s-uniform hypergraph on t vertices; otherwise Painter wins when she has colored all possible edges. We extend the definition of coloring number to hypergraphs so that χ(G)≤col(G) for any hypergraph G and then show that Builder can win (c,s,t)-Ramsey game while building a hypergraph with coloring number at most col(K _s t ). An important step in the proof is the analysis of an auxiliary survival game played by Presenter and Chooser. The (p,s,t)-survival game begins with an s-uniform hypergraph H ₀ = (V,Ø) with an arbitrary finite number of vertices and no edges. Let H _i−1=(V _i−1,E _i−1) be the hypergraph constructed in the first i − 1 rounds. On the i-th round Presenter plays by presenting a p-subset P _i ⊆V _i−1 and Chooser responds by choosing an s-subset 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 p,s,t with s≤p, Presenter has a winning strategy.