ASU Electronic Theses and Dissertations
This collection includes most of the ASU Theses and Dissertations from 2011 to present. ASU Theses and Dissertations are available in downloadable PDF format; however, a small percentage of items are under embargo. Information about the dissertations/theses includes degree information, committee members, an abstract, supporting data or media.
In addition to the electronic theses found in the ASU Digital Repository, ASU Theses and Dissertations can be found in the ASU Library Catalog.
Dissertations and Theses granted by Arizona State University are archived and made available through a joint effort of the ASU Graduate College and the ASU Libraries. For more information or questions about this collection contact or visit the Digital Repository ETD Library Guide or contact the ASU Graduate College at gradformat@asu.edu.
Displaying 1 - 4 of 4
Filtering by
- All Subjects: Mathematics
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
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
Description
The main part of this work establishes existence, uniqueness and regularity properties of measure-valued solutions of a nonlinear hyperbolic conservation law with non-local velocities. Major challenges stem from in- and out-fluxes containing nonzero pure-point parts which cause discontinuities of the velocities. This part is preceded, and motivated, by an extended study which proves that an associated optimal control problem has no optimal $L^1$-solutions that are supported on short time intervals.
The hyperbolic conservation law considered here is a well-established model for a highly re-entrant semiconductor manufacturing system. Prior work established well-posedness for $L^1$-controls and states, and existence of optimal solutions for $L^2$-controls, states, and control objectives. The results on measure-valued solutions presented here reduce to the existing literature in the case of initial state and in-flux being absolutely continuous measures. The surprising well-posedness (in the face of measures containing nonzero pure-point part and discontinuous velocities) is directly related to characteristic features of the model that capture the highly re-entrant nature of the semiconductor manufacturing system.
More specifically, the optimal control problem is to minimize an $L^1$-functional that measures the mismatch between actual and desired accumulated out-flux. The focus is on the transition between equilibria with eventually zero backlog. In the case of a step up to a larger equilibrium, the in-flux not only needs to increase to match the higher desired out-flux, but also needs to increase the mass in the factory and to make up for the backlog caused by an inverse response of the system. The optimality results obtained confirm the heuristic inference that the optimal solution should be an impulsive in-flux, but this is no longer in the space of $L^1$-controls.
The need for impulsive controls motivates the change of the setting from $L^1$-controls and states to controls and states that are Borel measures. The key strategy is to temporarily abandon the Eulerian point of view and first construct Lagrangian solutions. The final section proposes a notion of weak measure-valued solutions and proves existence and uniqueness of such.
In the case of the in-flux containing nonzero pure-point part, the weak solution cannot depend continuously on the time with respect to any norm. However, using semi-norms that are related to the flat norm, a weaker form of continuity of solutions with respect to time is proven. It is conjectured that also a similar weak continuous dependence on initial data holds with respect to a variant of the flat norm.
The hyperbolic conservation law considered here is a well-established model for a highly re-entrant semiconductor manufacturing system. Prior work established well-posedness for $L^1$-controls and states, and existence of optimal solutions for $L^2$-controls, states, and control objectives. The results on measure-valued solutions presented here reduce to the existing literature in the case of initial state and in-flux being absolutely continuous measures. The surprising well-posedness (in the face of measures containing nonzero pure-point part and discontinuous velocities) is directly related to characteristic features of the model that capture the highly re-entrant nature of the semiconductor manufacturing system.
More specifically, the optimal control problem is to minimize an $L^1$-functional that measures the mismatch between actual and desired accumulated out-flux. The focus is on the transition between equilibria with eventually zero backlog. In the case of a step up to a larger equilibrium, the in-flux not only needs to increase to match the higher desired out-flux, but also needs to increase the mass in the factory and to make up for the backlog caused by an inverse response of the system. The optimality results obtained confirm the heuristic inference that the optimal solution should be an impulsive in-flux, but this is no longer in the space of $L^1$-controls.
The need for impulsive controls motivates the change of the setting from $L^1$-controls and states to controls and states that are Borel measures. The key strategy is to temporarily abandon the Eulerian point of view and first construct Lagrangian solutions. The final section proposes a notion of weak measure-valued solutions and proves existence and uniqueness of such.
In the case of the in-flux containing nonzero pure-point part, the weak solution cannot depend continuously on the time with respect to any norm. However, using semi-norms that are related to the flat norm, a weaker form of continuity of solutions with respect to time is proven. It is conjectured that also a similar weak continuous dependence on initial data holds with respect to a variant of the flat norm.
ContributorsGong, Xiaoqian, Ph.D (Author) / Kawski, Matthias (Thesis advisor) / Kaliszewski, Steven (Committee member) / Motsch, Sebastien (Committee member) / Smith, Hal (Committee member) / Thieme, Horst (Committee member) / Arizona State University (Publisher)
Created2019
Description
This dissertation consists of three papers about opinion dynamics. The first paper is in collaboration with Prof. Lanchier while the other two papers are individual works.
Two models are introduced and studied analytically: the Deffuant model and the Hegselmann-Krause~(HK) model.
The main difference between the two models is that the Deffuant dynamics consists of pairwise interactions whereas the HK dynamics consists of group interactions.
Translated into graph, each vertex stands for an agent in both models.
In the Deffuant model, two graphs are combined: the social graph and the opinion graph.
The social graph is assumed to be a general finite connected graph where each edge is interpreted as a social link, such as a friendship relationship, between two agents.
At each time step, two social neighbors are randomly selected and interact if and only if their opinion distance does not exceed some confidence threshold, which results in the neighbors' opinions getting closer to each other.
The main result about the Deffuant model is the derivation of a positive lower bound for the probability of consensus that is independent of the size and topology of the social graph but depends on the confidence threshold, the choice of the opinion space and the initial distribution. For the HK model, agent~$i$ updates its opinion~$x_i$ by taking the average opinion of its neighbors, defined as the set of agents with opinion at most~$\epsilon$ apart from~$x_i$. Here,~$\epsilon > 0$ is a confidence threshold.
There are two types of HK models: the synchronous and the asynchronous HK models.
In the former, all the agents update their opinion simultaneously at each time step, whereas in the latter, only one agent is selected uniformly at random to update its opinion at each time step.
The mixed model is a variant of the HK model in which each agent can choose its degree of stubbornness and mix its opinion with the average opinion of its neighbors.
The main results of this dissertation about HK models show conditions under which the asymptotic stability holds or a consensus can be achieved, and give a positive lower bound for the probability of consensus and, in the one-dimensional case, an upper bound for the probability of consensus.
I demonstrate the bounds for the probability of consensus on a unit cube and a unit interval.
ContributorsLi, Hsin-Lun (Author) / Lanchier, Nicolas (Thesis advisor) / Camacho, Erika (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Motsch, Sebastien (Committee member) / Arizona State University (Publisher)
Created2021