Spelling suggestions: "subject:"rearrangeable"" "subject:"arrangeable""
1 |
An Extension of Ramsey's Theorem to Multipartite GraphsCook, Brian Michael 04 May 2007 (has links)
Ramsey Theorem, in the most simple form, states that if we are given a positive integer l, there exists a minimal integer r(l), called the Ramsey number, such any partition of the edges of K_r(l) into two sets, i.e. a 2-coloring, yields a copy of K_l contained entirely in one of the partitioned sets, i.e. a monochromatic copy of Kl. We prove an extension of Ramsey's Theorem, in the more general form, by replacing complete graphs by multipartite graphs in both senses, as the partitioned set and as the desired monochromatic graph. More formally, given integers l and k, there exists an integer p(m) such that any 2-coloring of the edges of the complete multipartite graph K_p(m);r(k) yields a monochromatic copy of K_m;k . The tools that are used to prove this result are the Szemeredi Regularity Lemma and the Blow Up Lemma. A full proof of the Regularity Lemma is given. The Blow-Up Lemma is merely stated, but other graph embedding results are given. It is also shown that certain embedding conditions on classes of graphs, namely (f , ?) -embeddability, provides a method to bound the order of the multipartite Ramsey numbers on the graphs. This provides a method to prove that a large class of graphs, including trees, graphs of bounded degree, and planar graphs, has a linear bound, in terms of the number of vertices, on the multipartite Ramsey number.
|
Page generated in 0.0441 seconds