TAILIEUCHUNG - Báo cáo toán học: "Trees with an On-Line Degree Ramsey Number of Fou"

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: Trees with an On-Line Degree Ramsey Number of Four. | Trees with an On-Line Degree Ramsey Number of Four David Rolnick Massachusetts Institute of Technology Cambridge MA USA drolnick@ Submitted Dec 17 2010 Accepted Aug 11 2011 Published Sep 2 2011 Mathematics Subject Classification 05C55 05C57 05C05 Abstract On-line Ramsey theory studies a graph-building game between two players. The player called Builder builds edges one at a time and the player called Painter paints each new edge red or blue after it is built. The graph constructed is called the background graph. Builder s goal is to cause the background graph to contain a monochromatic copy of a given goal graph and Painter s goal is to prevent this. In the Sk-game variant of the typical game the background graph is constrained to have maximum degree no greater than k. The on-line degree Ramsey number Ra G of a graph G is the minimum k such that Builder wins an Sk-game in which G is the goal graph. Butterfield et al. previously determined all graphs G satisfying Ra G 3. We provide a complete classification of trees T satisfying Ra T 4. 1 Introduction The quintessential problem of Ramsey theory involves finding a monochromatic copy of a graph G within a larger graph whose edges are colored with some s colors. Given G and s we say that a graph H arrows G if every s-coloring of H contains a monochromatic G as a subgraph. Two basic parameters of Ramsey theory are The Ramsey number R G is the minimum number of vertices among graphs H that arrow G. The size Ramsey number R G is the minimum number of edges among graphs that arrow G. The numbers called on-line Ramsey numbers are based upon the following game which we consider in the 2-color case though an s-color generalization is possible Two THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P173 1 players called Builder and Painter generate a 2-colored graph H. Builder builds edges one at a time using some combination of existing vertices and new vertices. As each edge is built Painter paints it either red or blue.

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học