abstract: Let T be a tournament with edges colored with any number of colors. A rainbow triangle is a 3-colored 3-cycle. A monochromatic sink of T is a vertex which can be reached along a monochromatic path by every other vertex of T. In 1982, Sands, Sauer, and Woodrow asked if T has no rainbow triangles, then does T have a monochromatic sink? I answer yes in the following five scenarios: when all 4-cycles are monochromatic, all 4-semi-cycles are near-monochromatic, all 5-semi-cycles are near-monochromatic, all back-paths of an ordering of the vertices are vertex disjoint, and for any vertex in an ordering of the vertices, its back edges are all colored the same. I provide conjectures related to these results that ask if the result is also true for larger cycles and semi-cycles. A ruling class is a set of vertices in T so that every other vertex of T can reach a vertex of the ruling class along a monochromatic path. Every tournament contains a ruling class, although the ruling class may have a trivial size of the order of T. Sands, Sauer, and Woodrow asked (again in 1982) about the minimum size of ruling classes in T. In particular, in a 3-colored tournament, must there be a ruling class of size 3? I answer yes when it is required that all 2-colored cycles have an edge xy so that y has a monochromatic path to x. I conjecture that there is a ruling class of size 3 if there are no rainbow triangles in T. Finally, I present the new topic of alpha-step-chromatic sinks along with related results. I show that for certain values of alpha, a tournament is not guaranteed to have an alpha-step-chromatic sink. In fact, similar to the previous results in this thesis, alpha-step-chromatic sinks can only be demonstrated when additional restrictions are put on the coloring of the tournament's edges, such as excluding rainbow triangles. However, when proving the existence of alpha-step-chromatic sinks, it is only necessary to exclude special types of rainbow triangles. / Dissertation/Thesis / Ph.D. Mathematics 2011
| Identifer | oai:union.ndltd.org:asu.edu/item:9361 |
| Date | January 2011 |
| Contributors | Bland, Adam (Author), Kierstead, Henry A (Advisor), Czygrinow, Andrzej M (Committee member), Hurlbert, Glenn H (Committee member), Barcelo, Helene (Committee member), Aen, Arunabha (Committee member), Arizona State University (Publisher) |
| Source Sets | Arizona State University |
| Language | English |
| Detected Language | English |
| Type | Doctoral Dissertation |
| Format | 66 pages |
| Rights | http://rightsstatements.org/vocab/InC/1.0/, All Rights Reserved |
Page generated in 0.0013 seconds