Coloring number and on-line Ramsey theory for graphs and hypergraphs |
| |
Authors: | H. A. Kierstead Goran Konjevod |
| |
Affiliation: | (1) Department of Mathematics and Statistics, Arizona State University, Tempe, AZ 85287, USA;(2) Department of Computer Science, Arizona State University, Tempe, AZ 85287, USA |
| |
Abstract: | 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 0=(V,E 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 =(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 0 = (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. |
| |
Keywords: | KeywordHeading" >Mathematics Subject Classification (2000) 05D10 05C55 05C65 03C13 03D99 |
本文献已被 SpringerLink 等数据库收录! |
|