Some problems in Graph Ramsey Theory

A graph G is r-Ramsey minimal with respect to a graph H if every r-coloring of the edges of G yields a monochromatic copy of H, but the same is not true for any proper subgraph of G. The study of the properties of graphs that are Ramsey minimal with respect to some H and similar problems is known as graph Ramsey theory; we study several problems in this area. Burr, Erdös, and Lovász introduced s(H), the minimum over all G that are 2- Ramsey minimal for H of [delta](G), the minimum degree of G. We find the values of s(H) for several classes of graphs H, most notably for all 3-connected bipartite graphs which proves many cases of a conjecture due to Szabó, Zumstein, and Zürcher. One natural question when studying graph Ramsey theory is what happens when, rather than considering all 2-colorings of a graph G, we restrict to a subset of the possible 2-colorings. Erdös and Hajnal conjectured that, for any fixed color pattern C, there is some [epsilon] > 0 so that every 2-coloring of the edges of a Kn, the complete graph on n vertices, which doesn't contain a copy of C contains a monochromatic clique on n[epsilon] vertices. Hajnal generalized this conjecture to more than 2 colors and asked in particular about the case when the number of colors is 3 and C is a rainbow triangle (a K3 where each edge is a different color); we prove Hajnal's conjecture for rainbow triangles. One may also wonder what would happen if we wish to cover all of the vertices with monochromatic copies of graphs. Let F = {F₁, F₂, . . .} be a sequence of graphs such that Fn is a graph on n vertices with maximum degree at most [delta]. If each Fn is bipartite, then the vertices of any 2-edge-colored complete graph can be partitioned into at most 2C[delta] vertex disjoint monochromatic copies of graphs from F, where C is an absolute constant. This result is best possible, up to the constant C.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Grinshpun, Andrey Vadim

Advisor dc:contributor.advisor

• Jacob Fox.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/97767

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/97767