Matching Items (28)
Description
A tiling is a collection of vertex disjoint subgraphs called tiles. If the tiles are all isomorphic to a graph $H$ then the tiling is an $H$-tiling. If a graph $G$ has an $H$-tiling which covers all of the vertices of $G$ then the $H$-tiling is a perfect $H$-tiling or an $H$-factor. A goal of this study is to extend theorems on sufficient minimum degree conditions for perfect tilings in graphs to directed graphs. Corrádi and Hajnal proved that every graph $G$ on $3k$ vertices with minimum degree $delta(G)ge2k$ has a $K_3$-factor, where $K_s$ is the complete graph on $s$ vertices. The following theorem extends this result to directed graphs: If $D$ is a directed graph on $3k$ vertices with minimum total degree $delta(D)ge4k-1$ then $D$ can be partitioned into $k$ parts each of size $3$ so that all of parts contain a transitive triangle and $k-1$ of the parts also contain a cyclic triangle. The total degree of a vertex $v$ is the sum of $d^-(v)$ the in-degree and $d^+(v)$ the out-degree of $v$. Note that both orientations of $C_3$ are considered: the transitive triangle and the cyclic triangle. The theorem is best possible in that there are digraphs that meet the minimum degree requirement but have no cyclic triangle factor. The possibility of added a connectivity requirement to ensure a cycle triangle factor is also explored. Hajnal and Szemerédi proved that if $G$ is a graph on $sk$ vertices and $delta(G)ge(s-1)k$ then $G$ contains a $K_s$-factor. As a possible extension of this celebrated theorem to directed graphs it is proved that if $D$ is a directed graph on $sk$ vertices with $delta(D)ge2(s-1)k-1$ then $D$ contains $k$ disjoint transitive tournaments on $s$ vertices. We also discuss tiling directed graph with other tournaments. This study also explores minimum total degree conditions for perfect directed cycle tilings and sufficient semi-degree conditions for a directed graph to contain an anti-directed Hamilton cycle. The semi-degree of a vertex $v$ is $min{d^+(v), d^-(v)}$ and an anti-directed Hamilton cycle is a spanning cycle in which no pair of consecutive edges form a directed path.
ContributorsMolla, Theodore (Author) / Kierstead, Henry A (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Hurlbert, Glenn (Committee member) / Spielberg, Jack (Committee member) / Arizona State University (Publisher)
Created2013
Description
Communication networks, both wired and wireless, are expected to have a certain level of fault-tolerance capability.These networks are also expected to ensure a graceful degradation in performance when some of the network components fail. Traditional studies on fault tolerance in communication networks, for the most part, make no assumptions regarding the location of node/link faults, i.e., the faulty nodes and links may be close to each other or far from each other. However, in many real life scenarios, there exists a strong spatial correlation among the faulty nodes and links. Such failures are often encountered in disaster situations, e.g., natural calamities or enemy attacks. In presence of such region-based faults, many of traditional network analysis and fault-tolerant metrics, that are valid under non-spatially correlated faults, are no longer applicable. To this effect, the main thrust of this research is design and analysis of robust networks in presence of such region-based faults. One important finding of this research is that if some prior knowledge is available on the maximum size of the region that might be affected due to a region-based fault, this piece of knowledge can be effectively utilized for resource efficient design of networks. It has been shown in this dissertation that in some scenarios, effective utilization of this knowledge may result in substantial saving is transmission power in wireless networks. In this dissertation, the impact of region-based faults on the connectivity of wireless networks has been studied and a new metric, region-based connectivity, is proposed to measure the fault-tolerance capability of a network. In addition, novel metrics, such as the region-based component decomposition number(RBCDN) and region-based largest component size(RBLCS) have been proposed to capture the network state, when a region-based fault disconnects the network. Finally, this dissertation presents efficient resource allocation techniques that ensure tolerance against region-based faults, in distributed file storage networks and data center networks.
ContributorsBanerjee, Sujogya (Author) / Sen, Arunabha (Thesis advisor) / Xue, Guoliang (Committee member) / Richa, Andrea (Committee member) / Hurlbert, Glenn (Committee member) / Arizona State University (Publisher)
Created2013
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
Rabies disease remains enzootic among raccoons, skunks, foxes and bats in the United States. It is of primary concern for public-health agencies to control spatial spread of rabies in wildlife and its potential spillover infection of domestic animals and humans. Rabies is invariably fatal in wildlife if untreated, with a non-negligible incubation period. Understanding how this latency affects spatial spread of rabies in wildlife is the concern of chapter 2 and 3. Chapter 1 deals with the background of mathematical models for rabies and lists main objectives. In chapter 2, a reaction-diffusion susceptible-exposed-infected (SEI) model and a delayed diffusive susceptible-infected (SI) model are constructed to describe the same epidemic process -- rabies spread in foxes. For the delayed diffusive model a non-local infection term with delay is resulted from modeling the dispersal during incubation stage. Comparison is made regarding minimum traveling wave speeds of the two models, which are verified using numerical experiments. In chapter 3, starting with two Kermack and McKendrick's models where infectivity, death rate and diffusion rate of infected individuals can depend on the age of infection, the asymptotic speed of spread $c^\ast$ for the cumulated force of infection can be analyzed. For the special case of fixed incubation period, the asymptotic speed of spread is governed by the same integral equation for both models. Although explicit solutions for $c^\ast$ are difficult to obtain, assuming that diffusion coefficient of incubating animals is small, $c^\ast$ can be estimated in terms of model parameter values. Chapter 4 considers the implementation of realistic landscape in simulation of rabies spread in skunks and bats in northeast Texas. The Finite Element Method (FEM) is adopted because the irregular shapes of realistic landscape naturally lead to unstructured grids in the spatial domain. This implementation leads to a more accurate description of skunk rabies cases distributions.
ContributorsLiu, Hao (Author) / Kuang, Yang (Thesis advisor) / Jackiewicz, Zdzislaw (Committee member) / Lanchier, Nicolas (Committee member) / Smith, Hal (Committee member) / Thieme, Horst (Committee member) / Arizona State University (Publisher)
Created2013
Description
This thesis focuses on sequencing questions in a way that provides students with manageable steps to understand some of the fundamental concepts in discrete mathematics. The questions are aimed at younger students (middle and high school aged) with the goal of helping young students, who have likely never seen discrete mathematics, to learn through guided discovery. Chapter 2 is the bulk of this thesis as it provides questions, hints, solutions, as well as a brief discussion of each question. In the discussions following the questions, I have attempted to illustrate some relationships between the current question and previous questions, explain the learning goals of that question, as well as point out possible flaws in students' thinking or point out ways to explore this topic further. Chapter 3 provides additional questions with hints and solutions, but no discussion. Many of the questions in Chapter 3 contain ideas similar to questions in Chapter 2, but also illustrate how versatile discrete mathematics topics are. Chapter 4 focuses on possible future directions. The overall framework for the questions is that a student is hosting a birthday party, and all of the questions are ones that might actually come up in party planning. The purpose of putting it in this setting is to make the questions seem more coherent and less arbitrary or forced.
ContributorsBell, Stephanie (Author) / Fishel, Susana (Thesis advisor) / Hurlbert, Glenn (Committee member) / Quigg, John (Committee member) / Arizona State University (Publisher)
Created2014
Description
In a 2004 paper, John Nagy raised the possibility of the existence of a hypertumor \emph{i.e.}, a focus of aggressively reproducing parenchyma cells that invade part or all of a tumor. His model used a system of nonlinear ordinary differential equations to find a suitable set of conditions for which these hypertumors exist. Here that model is expanded by transforming it into a system of nonlinear partial differential equations with diffusion, advection, and a free boundary condition to represent a radially symmetric tumor growth. Two strains of parenchymal cells are incorporated; one forming almost the entirety of the tumor while the much more aggressive strain
appears in a smaller region inside of the tumor. Simulations show that if the aggressive strain focuses its efforts on proliferating and does not contribute to angiogenesis signaling when in a hypoxic state, a hypertumor will form. More importantly, this resultant aggressive tumor is paradoxically prone to extinction and hypothesize is the cause of necrosis in many vascularized tumors.
appears in a smaller region inside of the tumor. Simulations show that if the aggressive strain focuses its efforts on proliferating and does not contribute to angiogenesis signaling when in a hypoxic state, a hypertumor will form. More importantly, this resultant aggressive tumor is paradoxically prone to extinction and hypothesize is the cause of necrosis in many vascularized tumors.
ContributorsAlvarez, Roberto L (Author) / Milner, Fabio A (Thesis advisor) / Nagy, John D. (Committee member) / Kuang, Yang (Committee member) / Thieme, Horst (Committee member) / Mahalov, Alex (Committee member) / Smith, Hal (Committee member) / Arizona State University (Publisher)
Created2014
Description
Persistence theory provides a mathematically rigorous answer to the question of population survival by establishing an initial-condition- independent positive lower bound for the long-term value of the population size. This study focuses on the persistence of discrete semiflows in infinite-dimensional state spaces that model the year-to-year dynamics of structured populations. The map which encapsulates the population development from one year to the next is approximated at the origin (the extinction state) by a linear or homogeneous map. The (cone) spectral radius of this approximating map is the threshold between extinction and persistence. General persistence results are applied to three particular models: a size-structured plant population model, a diffusion model (with both Neumann and Dirichlet boundary conditions) for a dispersing population of males and females that only mate and reproduce once during a very short season, and a rank-structured model for a population of males and females.
ContributorsJin, Wen (Author) / Thieme, Horst (Thesis advisor) / Milner, Fabio (Committee member) / Quigg, John (Committee member) / Smith, Hal (Committee member) / Spielberg, John (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
In a large network (graph) it would be desirable to guarantee the existence of some local property based only on global knowledge of the network. Consider the following classical example: how many connections are necessary to guarantee that the network contains three nodes which are pairwise adjacent? It turns out that more than n^2/4 connections are needed, and no smaller number will suffice in general. Problems of this type fall into the category of ``extremal graph theory.'' Generally speaking, extremal graph theory is the study of how global parameters of a graph are related to local properties. This dissertation deals with the relationship between minimum degree conditions of a host graph G and the property that G contains a specified spanning subgraph (or class of subgraphs). The goal is to find the optimal minimum degree which guarantees the existence of a desired spanning subgraph. This goal is achieved in four different settings, with the main tools being Szemeredi's Regularity Lemma; the Blow-up Lemma of Komlos, Sarkozy, and Szemeredi; and some basic probabilistic techniques.
ContributorsDeBiasio, Louis (Author) / Kierstead, Henry A (Thesis advisor) / Czygrinow, Andrzej (Thesis advisor) / Hurlbert, Glenn (Committee member) / Kadell, Kevin (Committee member) / Fishel, Susanna (Committee member) / Arizona State University (Publisher)
Created2011
Description
In complex consumer-resource type systems, where diverse individuals are interconnected and interdependent, one can often anticipate what has become known as the tragedy of the commons, i.e., a situation, when overly efficient consumers exhaust the common resource, causing collapse of the entire population. In this dissertation I use mathematical modeling to explore different variations on the consumer-resource type systems, identifying some possible transitional regimes that can precede the tragedy of the commons. I then reformulate it as a game of a multi-player prisoner's dilemma and study two possible approaches for preventing it, namely direct modification of players' payoffs through punishment/reward and modification of the environment in which the interactions occur. I also investigate the questions of whether the strategy of resource allocation for reproduction or competition would yield higher fitness in an evolving consumer-resource type system and demonstrate that the direction in which the system will evolve will depend not only on the state of the environment but largely on the initial composition of the population. I then apply the developed framework to modeling cancer as an evolving ecological system and draw conclusions about some alternative approaches to cancer treatment.
ContributorsKareva, Irina (Author) / Castillo-Chavez, Carlos (Thesis advisor) / Collins, James (Committee member) / Nagy, John (Committee member) / Smith, Hal (Committee member) / Arizona State University (Publisher)
Created2012