tailieunhanh - Báo cáo toán học: "On-line Ramsey Theory for Bounded Degree Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On-line Ramsey Theory for Bounded Degree Graphs. | On-line Ramsey Theory for Bounded Degree Graphs Jane Butterfield Tracy Grauman William B. Kinnersley Kevin G. Milans Christopher Stocker Douglas B. West University of Illinois Urbana IL . Submitted Nov 9 2010 Accepted Jun 15 2011 Published Jul 1 2011 Mathematics Subject Classification 05C55 05C57 Abstract When graph Ramsey theory is viewed as a game Painter 2-colors the edges of a graph presented by Builder . Builder wins if every coloring has a monochromatic copy of a fixed graph G. In the on-line version iteratively Builder presents one edge and Painter must color it. Builder must keep the presented graph in a class H. Builder wins the game G H if a monochromatic copy of G can be forced. The on-line degree Ramsey number Ra G is the least k such that Builder wins G H when H is the class of graphs with maximum degree at most k. Our results include 1 ra G 3 if and only if G is a linear forest or each component lies inside K1 3. 2 ra G A G 1 1 where t maxuveE G min d u d v . 3 Ra G d1 d2 1 for a tree G where d1 and d2 are two largest vertex degrees. 4 4 RA Cn 5 with RA Cn 4 except for finitely many odd values of n. 5 Ra G 6 when A G 2. The lower bounds come from strategies for Painter that color edges red whenever the red graph remains in a specified class. The upper bounds use a result showing that Builder may assume that Painter plays consistently . 1 Introduction The classical problem of graph Ramsey theory specifies a target graph G and seeks a graph H such that every 2-coloring of E H produces a monochromatic copy of G. For such H we write H G and say that H arrows G. More generally when every s-coloring of E H produces a monochromatic G we write H A G. Ramsey s Theorem guarantees for every G that such a graph H exists. The Ramsey number R G s or R G when s 2 is the minimum number of vertices in such a graph H. Email addresses jbutter2@ grauman2@ wkinner2@ milans@ stocker2@ west@. Research of . .