Matching Items (15)
Filtering by
- All Subjects: Mathematics
- Genre: Academic theses
- Genre: Doctoral Dissertation
- Creators: Colbourn, Charles
- Creators: Kuang, Yang
Description
A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually added to a poset or graph while a chain partition or coloring (respectively) is maintained. %The optima of the static cases cannot be achieved in the on-line setting. Both upper and lower bounds for the optimum of the number of chains needed to partition a width $w$ on-line poset exist. Kierstead's upper bound of $\frac{5^w-1}{4}$ was improved to $w^{14 \lg w}$ by Bosek and Krawczyk. This is improved to $w^{3+6.5 \lg w}$ by employing the First-Fit algorithm on a family of restricted posets (expanding on the work of Bosek and Krawczyk) . Namely, the family of ladder-free posets where the $m$-ladder is the transitive closure of the union of two incomparable chains $x_1\le\dots\le x_m$, $y_1\le\dots\le y_m$ and the set of comparabilities $\{x_1\le y_1,\dots, x_m\le y_m\}$. No upper bound on the number of colors needed to color a general on-line graph exists. To lay this fact plain, the performance of on-line coloring of trees is shown to be particularly problematic. There are trees that require $n$ colors to color on-line for any positive integer $n$. Furthermore, there are trees that usually require many colors to color on-line even if they are presented without any particular strategy. For restricted families of graphs, upper and lower bounds for the optimum number of colors needed to maintain an on-line coloring exist. In particular, circular arc graphs can be colored on-line using less than 8 times the optimum number from the static case. This follows from the work of Pemmaraju, Raman, and Varadarajan in on-line coloring of interval graphs.
ContributorsSmith, Matthew Earl (Author) / Kierstead, Henry A (Thesis advisor) / Colbourn, Charles (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Hurlbert, Glenn (Committee member) / Arizona State University (Publisher)
Created2012
Description
There has been important progress in understanding ecological dynamics through the development of the theory of ecological stoichiometry. This fast growing theory provides new constraints and mechanisms that can be formulated into mathematical models. Stoichiometric models incorporate the effects of both food quantity and food quality into a single framework that produce rich dynamics. While the effects of nutrient deficiency on consumer growth are well understood, recent discoveries in ecological stoichiometry suggest that consumer dynamics are not only affected by insufficient food nutrient content (low phosphorus (P): carbon (C) ratio) but also by excess food nutrient content (high P:C). This phenomenon, known as the stoichiometric knife edge, in which animal growth is reduced not only by food with low P content but also by food with high P content, needs to be incorporated into mathematical models. Here we present Lotka-Volterra type models to investigate the growth response of Daphnia to algae of varying P:C ratios. Using a nonsmooth system of two ordinary differential equations (ODEs), we formulate the first model to incorporate the phenomenon of the stoichiometric knife edge. We then extend this stoichiometric model by mechanistically deriving and tracking free P in the environment. This resulting full knife edge model is a nonsmooth system of three ODEs. Bifurcation analysis and numerical simulations of the full model, that explicitly tracks phosphorus, leads to quantitatively different predictions than previous models that neglect to track free nutrients. The full model shows that the grazer population is sensitive to excess nutrient concentrations as a dynamical free nutrient pool induces extreme grazer population density changes. These modeling efforts provide insight on the effects of excess nutrient content on grazer dynamics and deepen our understanding of the effects of stoichiometry on the mechanisms governing population dynamics and the interactions between trophic levels.
ContributorsPeace, Angela (Author) / Kuang, Yang (Thesis advisor) / Elser, James J (Committee member) / Baer, Steven (Committee member) / Tang, Wenbo (Committee member) / Kang, Yun (Committee member) / Arizona State University (Publisher)
Created2014
Description
In 1968, phycologist M.R. Droop published his famous discovery on the functional relationship between growth rate and internal nutrient status of algae in chemostat culture. The simple notion that growth is directly dependent on intracellular nutrient concentration is useful for understanding the dynamics in many ecological systems. The cell quota in particular lends itself to ecological stoichiometry, which is a powerful framework for mathematical ecology. Three models are developed based on the cell quota principal in order to demonstrate its applications beyond chemostat culture.
First, a data-driven model is derived for neutral lipid synthesis in green microalgae with respect to nitrogen limitation. This model synthesizes several established frameworks in phycology and ecological stoichiometry. The model demonstrates how the cell quota is a useful abstraction for understanding the metabolic shift to neutral lipid production that is observed in certain oleaginous species.
Next a producer-grazer model is developed based on the cell quota model and nutrient recycling. The model incorporates a novel feedback loop to account for animal toxicity due to accumulation of nitrogen waste. The model exhibits rich, complex dynamics which leave several open mathematical questions.
Lastly, disease dynamics in vivo are in many ways analogous to those of an ecosystem, giving natural extensions of the cell quota concept to disease modeling. Prostate cancer can be modeled within this framework, with androgen the limiting nutrient and the prostate and cancer cells as competing species. Here the cell quota model provides a useful abstraction for the dependence of cellular proliferation and apoptosis on androgen and the androgen receptor. Androgen ablation therapy is often used for patients in biochemical recurrence or late-stage disease progression and is in general initially effective. However, for many patients the cancer eventually develops resistance months to years after treatment begins. Understanding how and predicting when hormone therapy facilitates evolution of resistant phenotypes has immediate implications for treatment. Cell quota models for prostate cancer can be useful tools for this purpose and motivate applications to other diseases.
First, a data-driven model is derived for neutral lipid synthesis in green microalgae with respect to nitrogen limitation. This model synthesizes several established frameworks in phycology and ecological stoichiometry. The model demonstrates how the cell quota is a useful abstraction for understanding the metabolic shift to neutral lipid production that is observed in certain oleaginous species.
Next a producer-grazer model is developed based on the cell quota model and nutrient recycling. The model incorporates a novel feedback loop to account for animal toxicity due to accumulation of nitrogen waste. The model exhibits rich, complex dynamics which leave several open mathematical questions.
Lastly, disease dynamics in vivo are in many ways analogous to those of an ecosystem, giving natural extensions of the cell quota concept to disease modeling. Prostate cancer can be modeled within this framework, with androgen the limiting nutrient and the prostate and cancer cells as competing species. Here the cell quota model provides a useful abstraction for the dependence of cellular proliferation and apoptosis on androgen and the androgen receptor. Androgen ablation therapy is often used for patients in biochemical recurrence or late-stage disease progression and is in general initially effective. However, for many patients the cancer eventually develops resistance months to years after treatment begins. Understanding how and predicting when hormone therapy facilitates evolution of resistant phenotypes has immediate implications for treatment. Cell quota models for prostate cancer can be useful tools for this purpose and motivate applications to other diseases.
ContributorsPacker, Aaron (Author) / Kuang, Yang (Thesis advisor) / Nagy, John (Committee member) / Smith, Hal (Committee member) / Kostelich, Eric (Committee member) / Kang, Yun (Committee member) / Arizona State University (Publisher)
Created2014
Description
Different logic-based knowledge representation formalisms have different limitations either with respect to expressivity or with respect to computational efficiency. First-order logic, which is the basis of Description Logics (DLs), is not suitable for defeasible reasoning due to its monotonic nature. The nonmonotonic formalisms that extend first-order logic, such as circumscription and default logic, are expressive but lack efficient implementations. The nonmonotonic formalisms that are based on the declarative logic programming approach, such as Answer Set Programming (ASP), have efficient implementations but are not expressive enough for representing and reasoning with open domains. This dissertation uses the first-order stable model semantics, which extends both first-order logic and ASP, to relate circumscription to ASP, and to integrate DLs and ASP, thereby partially overcoming the limitations of the formalisms. By exploiting the relationship between circumscription and ASP, well-known action formalisms, such as the situation calculus, the event calculus, and Temporal Action Logics, are reformulated in ASP. The advantages of these reformulations are shown with respect to the generality of the reasoning tasks that can be handled and with respect to the computational efficiency. The integration of DLs and ASP presented in this dissertation provides a framework for integrating rules and ontologies for the semantic web. This framework enables us to perform nonmonotonic reasoning with DL knowledge bases. Observing the need to integrate action theories and ontologies, the above results are used to reformulate the problem of integrating action theories and ontologies as a problem of integrating rules and ontologies, thus enabling us to use the computational tools developed in the context of the latter for the former.
ContributorsPalla, Ravi (Author) / Lee, Joohyung (Thesis advisor) / Baral, Chitta (Committee member) / Kambhampati, Subbarao (Committee member) / Lifschitz, Vladimir (Committee member) / Arizona State University (Publisher)
Created2012
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
Bacteriophage (phage) are viruses that infect bacteria. Typical laboratory experiments show that in a chemostat containing phage and susceptible bacteria species, a mutant bacteria species will evolve. This mutant species is usually resistant to the phage infection and less competitive compared to the susceptible bacteria species. In some experiments, both susceptible and resistant bacteria species, as well as phage, can coexist at an equilibrium for hundreds of hours. The current research is inspired by these observations, and the goal is to establish a mathematical model and explore sufficient and necessary conditions for the coexistence. In this dissertation a model with infinite distributed delay terms based on some existing work is established. A rigorous analysis of the well-posedness of this model is provided, and it is proved that the susceptible bacteria persist. To study the persistence of phage species, a "Phage Reproduction Number" (PRN) is defined. The mathematical analysis shows phage persist if PRN > 1 and vanish if PRN < 1. A sufficient condition and a necessary condition for persistence of resistant bacteria are given. The persistence of the phage is essential for the persistence of resistant bacteria. Also, the resistant bacteria persist if its fitness is the same as the susceptible bacteria and if PRN > 1. A special case of the general model leads to a system of ordinary differential equations, for which numerical simulation results are presented.
ContributorsHan, Zhun (Author) / Smith, Hal (Thesis advisor) / Armbruster, Dieter (Committee member) / Kawski, Matthias (Committee member) / Kuang, Yang (Committee member) / Thieme, Horst (Committee member) / Arizona State University (Publisher)
Created2012
Description
Since the seminal work of Tur ́an, the forbidden subgraph problem has been among the central questions in extremal graph theory. Let ex(n;F) be the smallest number m such that any graph on n vertices with m edges contains F as a subgraph. Then the forbidden subgraph problem asks to find ex(n; F ) for various graphs F . The question can be further generalized by asking for the extreme values of other graph parameters like minimum degree, maximum degree, or connectivity. We call this type of question a Tura ́n-type problem. In this thesis, we will study Tura ́n-type problems and their variants for graphs and hypergraphs.
Chapter 2 contains a Tura ́n-type problem for cycles in dense graphs. The main result in this chapter gives a tight bound for the minimum degree of a graph which guarantees existence of disjoint cycles in the case of dense graphs. This, in particular, answers in the affirmative a question of Faudree, Gould, Jacobson and Magnant in the case of dense graphs.
In Chapter 3, similar problems for trees are investigated. Recently, Faudree, Gould, Jacobson and West studied the minimum degree conditions for the existence of certain spanning caterpillars. They proved certain bounds that guarantee existence of spanning caterpillars. The main result in Chapter 3 significantly improves their result and answers one of their questions by proving a tight minimum degree bound for the existence of such structures.
Chapter 4 includes another Tur ́an-type problem for loose paths of length three in a 3-graph. As a corollary, an upper bound for the multi-color Ramsey number for the loose path of length three in a 3-graph is achieved.
Chapter 2 contains a Tura ́n-type problem for cycles in dense graphs. The main result in this chapter gives a tight bound for the minimum degree of a graph which guarantees existence of disjoint cycles in the case of dense graphs. This, in particular, answers in the affirmative a question of Faudree, Gould, Jacobson and Magnant in the case of dense graphs.
In Chapter 3, similar problems for trees are investigated. Recently, Faudree, Gould, Jacobson and West studied the minimum degree conditions for the existence of certain spanning caterpillars. They proved certain bounds that guarantee existence of spanning caterpillars. The main result in Chapter 3 significantly improves their result and answers one of their questions by proving a tight minimum degree bound for the existence of such structures.
Chapter 4 includes another Tur ́an-type problem for loose paths of length three in a 3-graph. As a corollary, an upper bound for the multi-color Ramsey number for the loose path of length three in a 3-graph is achieved.
ContributorsYie, Jangwon (Author) / Czygrinow, Andrzej (Thesis advisor) / Kierstead, Henry (Committee member) / Colbourn, Charles (Committee member) / Fishel, Susanna (Committee member) / Spielberg, John (Committee member) / Arizona State University (Publisher)
Created2018
Description
Rabies is an infectious viral disease. It is usually fatal if a victim reaches the rabid stage, which starts after the appearance of disease symptoms. The disease virus attacks the central nervous system, and then it migrates from peripheral nerves to the spinal cord and brain. At the time when the rabies virus reaches the brain, the incubation period is over and the symptoms of clinical disease appear on the victim. From the brain, the virus travels via nerves to the salivary glands and saliva.
A mathematical model is developed for the spread of rabies in a spatially distributed fox population to model the spread of the rabies epizootic through middle Europe that occurred in the second half of the 20th century. The model considers both territorial and wandering rabid foxes and includes a latent period for the infection. Since the model assumes these two kinds of rabid foxes, it is a system of both partial differential and integral equations (with integration
over space and, occasionally, also over time). To study the spreading speeds of the rabies epidemic, the model is reduced to a scalar Volterra-Hammerstein integral equation, and space-time Laplace transform of the integral equation is used to derive implicit formulas for the spreading speed. The spreading speeds are discussed and implicit formulas are given for latent periods of fixed length, exponentially distributed length, Gamma distributed length, and log-normally distributed length. A number of analytic and numerical results are shown pertaining to the spreading speeds.
Further, a numerical algorithm is described for the simulation
of the spread of rabies in a spatially distributed fox population on a bounded domain with Dirichlet boundary conditions. I propose the following methods for the numerical approximation of solutions. The partial differential and integral equations are discretized in the space variable by central differences of second order and by
the composite trapezoidal rule. Next, the ordinary or delay differential equations that are obtained this way are discretized in time by explicit
continuous Runge-Kutta methods of fourth order for ordinary and delay differential systems. My particular interest
is in how the partition of rabid foxes into
territorial and diffusing rabid foxes influences
the spreading speed, a question that can be answered by purely analytic means only for small basic reproduction numbers. I will restrict the numerical analysis
to latent periods of fixed length and to exponentially
distributed latent periods.
The results of the numerical calculations
are compared for latent periods
of fixed and exponentially distributed length
and for various proportions of territorial
and wandering rabid foxes.
The speeds of spread observed in the
simulations are compared
to spreading speeds obtained by numerically solving the analytic formulas
and to observed speeds of epizootic frontlines
in the European rabies outbreak 1940 to 1980.
A mathematical model is developed for the spread of rabies in a spatially distributed fox population to model the spread of the rabies epizootic through middle Europe that occurred in the second half of the 20th century. The model considers both territorial and wandering rabid foxes and includes a latent period for the infection. Since the model assumes these two kinds of rabid foxes, it is a system of both partial differential and integral equations (with integration
over space and, occasionally, also over time). To study the spreading speeds of the rabies epidemic, the model is reduced to a scalar Volterra-Hammerstein integral equation, and space-time Laplace transform of the integral equation is used to derive implicit formulas for the spreading speed. The spreading speeds are discussed and implicit formulas are given for latent periods of fixed length, exponentially distributed length, Gamma distributed length, and log-normally distributed length. A number of analytic and numerical results are shown pertaining to the spreading speeds.
Further, a numerical algorithm is described for the simulation
of the spread of rabies in a spatially distributed fox population on a bounded domain with Dirichlet boundary conditions. I propose the following methods for the numerical approximation of solutions. The partial differential and integral equations are discretized in the space variable by central differences of second order and by
the composite trapezoidal rule. Next, the ordinary or delay differential equations that are obtained this way are discretized in time by explicit
continuous Runge-Kutta methods of fourth order for ordinary and delay differential systems. My particular interest
is in how the partition of rabid foxes into
territorial and diffusing rabid foxes influences
the spreading speed, a question that can be answered by purely analytic means only for small basic reproduction numbers. I will restrict the numerical analysis
to latent periods of fixed length and to exponentially
distributed latent periods.
The results of the numerical calculations
are compared for latent periods
of fixed and exponentially distributed length
and for various proportions of territorial
and wandering rabid foxes.
The speeds of spread observed in the
simulations are compared
to spreading speeds obtained by numerically solving the analytic formulas
and to observed speeds of epizootic frontlines
in the European rabies outbreak 1940 to 1980.
ContributorsAlanazi, Khalaf Matar (Author) / Thieme, Horst R. (Thesis advisor) / Jackiewicz, Zdzislaw (Committee member) / Baer, Steven (Committee member) / Gardner, Carl (Committee member) / Kuang, Yang (Committee member) / Smith, Hal (Committee member) / Arizona State University (Publisher)
Created2018
Description
Knowledge representation and reasoning is a prominent subject of study within the field of artificial intelligence that is concerned with the symbolic representation of knowledge in such a way to facilitate automated reasoning about this knowledge. Often in real-world domains, it is necessary to perform defeasible reasoning when representing default behaviors of systems. Answer Set Programming is a widely-used knowledge representation framework that is well-suited for such reasoning tasks and has been successfully applied to practical domains due to efficient computation through grounding--a process that replaces variables with variable-free terms--and propositional solvers similar to SAT solvers. However, some domains provide a challenge for grounding-based methods such as domains requiring reasoning about continuous time or resources.
To address these domains, there have been several proposals to achieve efficiency through loose integrations with efficient declarative solvers such as constraint solvers or satisfiability modulo theories solvers. While these approaches successfully avoid substantial grounding, due to the loose integration, they are not suitable for performing defeasible reasoning on functions. As a result, this expressive reasoning on functions must either be performed using predicates to simulate the functions or in a way that is not elaboration tolerant. Neither compromise is reasonable; the former suffers from the grounding bottleneck when domains are large as is often the case in real-world domains while the latter necessitates encodings to be non-trivially modified for elaborations.
This dissertation presents a novel framework called Answer Set Programming Modulo Theories (ASPMT) that is a tight integration of the stable model semantics and satisfiability modulo theories. This framework both supports defeasible reasoning about functions and alleviates the grounding bottleneck. Combining the strengths of Answer Set Programming and satisfiability modulo theories enables efficient continuous reasoning while still supporting rich reasoning features such as reasoning about defaults and reasoning in domains with incomplete knowledge. This framework is realized in two prototype implementations called MVSM and ASPMT2SMT, and the latter was recently incorporated into a non-monotonic spatial reasoning system. To define the semantics of this framework, we extend the first-order stable model semantics by Ferraris, Lee and Lifschitz to allow "intensional functions" and provide analyses of the theoretical properties of this new formalism and on the relationships between this and existing approaches.
To address these domains, there have been several proposals to achieve efficiency through loose integrations with efficient declarative solvers such as constraint solvers or satisfiability modulo theories solvers. While these approaches successfully avoid substantial grounding, due to the loose integration, they are not suitable for performing defeasible reasoning on functions. As a result, this expressive reasoning on functions must either be performed using predicates to simulate the functions or in a way that is not elaboration tolerant. Neither compromise is reasonable; the former suffers from the grounding bottleneck when domains are large as is often the case in real-world domains while the latter necessitates encodings to be non-trivially modified for elaborations.
This dissertation presents a novel framework called Answer Set Programming Modulo Theories (ASPMT) that is a tight integration of the stable model semantics and satisfiability modulo theories. This framework both supports defeasible reasoning about functions and alleviates the grounding bottleneck. Combining the strengths of Answer Set Programming and satisfiability modulo theories enables efficient continuous reasoning while still supporting rich reasoning features such as reasoning about defaults and reasoning in domains with incomplete knowledge. This framework is realized in two prototype implementations called MVSM and ASPMT2SMT, and the latter was recently incorporated into a non-monotonic spatial reasoning system. To define the semantics of this framework, we extend the first-order stable model semantics by Ferraris, Lee and Lifschitz to allow "intensional functions" and provide analyses of the theoretical properties of this new formalism and on the relationships between this and existing approaches.
ContributorsBartholomew, Michael James (Author) / Lee, Joohyung (Thesis advisor) / Bazzi, Rida (Committee member) / Colbourn, Charles (Committee member) / Fainekos, Georgios (Committee member) / Lifschitz, Vladimir (Committee member) / Arizona State University (Publisher)
Created2016
Description
The Tamari lattice T(n) was originally defined on bracketings of a set of n+1 objects, with a cover relation based on the associativity rule in one direction. Since then it has been studied in various areas of mathematics including cluster algebras, discrete geometry, algebraic combinatorics, and Catalan theory. Although in several related lattices the number of maximal chains is known, the enumeration of these chains in Tamari lattices is still an open problem.
This dissertation defines a partially-ordered set on equivalence classes of certain saturated chains of T(n) called the Tamari Block poset, TB(lambda). It further proves TB(lambda) is a graded lattice. It then shows for lambda = (n-1,...,2,1) TB(lambda) is anti-isomorphic to the Higher Stasheff-Tamari orders in dimension 3 on n+2 elements. It also investigates enumeration questions involving TB(lambda), and proves other structural results along the way.
This dissertation defines a partially-ordered set on equivalence classes of certain saturated chains of T(n) called the Tamari Block poset, TB(lambda). It further proves TB(lambda) is a graded lattice. It then shows for lambda = (n-1,...,2,1) TB(lambda) is anti-isomorphic to the Higher Stasheff-Tamari orders in dimension 3 on n+2 elements. It also investigates enumeration questions involving TB(lambda), and proves other structural results along the way.
ContributorsTreat, Kevin (Author) / Fishel, Susanna (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Jones, John (Committee member) / Childress, Nancy (Committee member) / Colbourn, Charles (Committee member) / Arizona State University (Publisher)
Created2016