Matching Items (3)
Description
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.
ContributorsBland, Adam K (Author) / Kierstead, Henry A (Thesis advisor) / Czygrinow, Andrzej M (Committee member) / Hurlbert, Glenn H. (Committee member) / Barcelo, Helene (Committee member) / Aen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2011
Description
Gray codes are perhaps the best known structures for listing sequences of combinatorial objects, such as binary strings. Simply defined as a minimal change listing, Gray codes vary greatly both in structure and in the types of objects that they list. More specific types of Gray codes are universal cycles and overlap sequences. Universal cycles are Gray codes on a set of strings of length n in which the first n-1 letters of one object are the same as the last n-1 letters of its predecessor in the listing. Overlap sequences allow this overlap to vary between 1 and n-1. Some of our main contributions to the areas of Gray codes and universal cycles include a new Gray code algorithm for fixed weight m-ary words, and results on the existence of universal cycles for weak orders on [n]. Overlap cycles are a relatively new structure with very few published results. We prove the existence of s-overlap cycles for k-permutations of [n], which has been an open research problem for several years, as well as constructing 1- overlap cycles for Steiner triple and quadruple systems of every order. Also included are various other results of a similar nature covering other structures such as binary strings, m-ary strings, subsets, permutations, weak orders, partitions, and designs. These listing structures lend themselves readily to some classes of combinatorial objects, such as binary n-tuples and m-ary n-tuples. Others require more work to find an appropriate structure, such as k-subsets of an n-set, weak orders, and designs. Still more require a modification in the representation of the objects to fit these structures, such as partitions. Determining when and how we can fit these sets of objects into our three listing structures is the focus of this dissertation.
ContributorsHoran, Victoria E (Author) / Hurlbert, Glenn H. (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Colbourn, Charles (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2012
Description
Graph coloring is about allocating resources that can be shared except where there are certain pairwise conflicts between recipients. The simplest coloring algorithm that attempts to conserve resources is called first fit. Interval graphs are used in models for scheduling (in computer science and operations research) and in biochemistry for one-dimensional molecules such as genetic material. It is not known precisely how much waste in the worst case is due to the first-fit algorithm for coloring interval graphs. However, after decades of research the range is narrow. Kierstead proved that the performance ratio R is at most 40. Pemmaraju, Raman, and Varadarajan proved that R is at most 10. This can be improved to 8. Witsenhausen, and independently Chrobak and Slusarek, proved that R is at least 4. Slusarek improved this to 4.45. Kierstead and Trotter extended the method of Chrobak and Slusarek to one good for a lower bound of 4.99999 or so. The method relies on number sequences with a certain property of order. It is shown here that each sequence considered in the construction satisfies a linear recurrence; that R is at least 5; that the Fibonacci sequence is in some sense minimally useless for the construction; and that the Fibonacci sequence is a point of accumulation in some space for the useful sequences of the construction. Limitations of all earlier constructions are revealed.
ContributorsSmith, David A. (Author) / Kierstead, Henry A. (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Gelb, Anne (Committee member) / Hurlbert, Glenn H. (Committee member) / Kadell, Kevin W. J. (Committee member) / Arizona State University (Publisher)
Created2010