2021-10-23T15:31:47Zhttps://keep.lib.asu.edu/oai/requestoai:keep.lib.asu.edu:node-1500652021-08-30T18:51:44Zoai_pmh:alloai_pmh:repo_items150065
https://hdl.handle.net/2286/R.I.9361
http://rightsstatements.org/vocab/InC/1.0/
All Rights Reserved
2011
v, 61 p. : ill
Doctoral Dissertation
Academic theses
Text
eng
Bland, Adam K
Kierstead, Henry A
Czygrinow, Andrzej M
Hurlbert, Glenn H.
Barcelo, Helene
Aen, Arunabha
Arizona State University
Partial requirement for: Ph.D., Arizona State University, 2011
Includes bibliographical references (p
Field of study: Mathematics
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.
Mathematics
Tournaments
Tournaments (Graph theory)
Reachability in K-colored tournaments