Matching Items (23)
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
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
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 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 this thesis, I investigate the C*-algebras and related constructions that arise from combinatorial structures such as directed graphs and their generalizations. I give a complete characterization of the C*-correspondences associated to directed graphs as well as results about obstructions to a similar characterization of these objects for generalizations of directed graphs. Viewing the higher-dimensional analogues of directed graphs through the lens of product systems, I give a rigorous proof that topological k-graphs are essentially product systems over N^k of topological graphs. I introduce a "compactly aligned" condition for such product systems of graphs and show that this coincides with the similarly-named conditions for topological k-graphs and for the associated product systems over N^k of C*-correspondences. Finally I consider the constructions arising from topological dynamical systems consisting of a locally compact Hausdorff space and k commuting local homeomorphisms. I show that in this case, the associated topological k-graph correspondence is isomorphic to the product system over N^k of C*-correspondences arising from a related Exel-Larsen system. Moreover, I show that the topological k-graph C*-algebra has a crossed product structure in the sense of Larsen.
ContributorsPatani, Nura (Author) / Kaliszewski, Steven (Thesis advisor) / Quigg, John (Thesis advisor) / Bremner, Andrew (Committee member) / Kawski, Matthias (Committee member) / Spielberg, John (Committee member) / Arizona State University (Publisher)
Created2011
Description
The theory of geometric quantum mechanics describes a quantum system as a Hamiltonian dynamical system, with a projective Hilbert space regarded as the phase space. This thesis extends the theory by including some aspects of the symplectic topology of the quantum phase space. It is shown that the quantum mechanical uncertainty principle is a special case of an inequality from J-holomorphic map theory, that is, J-holomorphic curves minimize the difference between the quantum covariance matrix determinant and a symplectic area. An immediate consequence is that a minimal determinant is a topological invariant, within a fixed homology class of the curve. Various choices of quantum operators are studied with reference to the implications of the J-holomorphic condition. The mean curvature vector field and Maslov class are calculated for a lagrangian torus of an integrable quantum system. The mean curvature one-form is simply related to the canonical connection which determines the geometric phases and polarization linear response. Adiabatic deformations of a quantum system are analyzed in terms of vector bundle classifying maps and related to the mean curvature flow of quantum states. The dielectric response function for a periodic solid is calculated to be the curvature of a connection on a vector bundle.
ContributorsSanborn, Barbara (Author) / Suslov, Sergei K (Thesis advisor) / Suslov, Sergei (Committee member) / Spielberg, John (Committee member) / Quigg, John (Committee member) / Menéndez, Jose (Committee member) / Jones, Donald (Committee member) / Arizona State University (Publisher)
Created2011
Description
Diophantine arithmetic is one of the oldest branches of mathematics, the search
for integer or rational solutions of algebraic equations. Pythagorean triangles are
an early instance. Diophantus of Alexandria wrote the first related treatise in the
fourth century; it was an area extensively studied by the great mathematicians of the seventeenth century, including Euler and Fermat.
The modern approach is to treat the equations as defining geometric objects, curves, surfaces, etc. The theory of elliptic curves (or curves of genus 1, which are much used in modern cryptography) was developed extensively in the twentieth century, and has had great application to Diophantine equations. This theory is used in application to the problems studied in this thesis. This thesis studies some curves of high genus, and possible solutions in both rationals and in algebraic number fields, generalizes some old results and gives answers to some open problems in the literature. The methods involve known techniques together with some ingenious tricks. For example, the equations $y^2=x^6+k$, $k=-39,\,-47$, the two previously unsolved cases for $|k|<50$, are solved using algebraic number theory and the ‘elliptic Chabauty’ method. The thesis also studies the genus three quartic curves $F(x^2,y^2,z^2)=0$ where F is a homogeneous quadratic form, and extend old results of Cassels, and Bremner. It is a very delicate matter to find such curves that have no rational points, yet which do have points in odd-degree extension fields of the rationals.
The principal results of the thesis are related to surfaces where the theory is much less well known. In particular, the thesis studies some specific families of surfaces, and give a negative answer to a question in the literature regarding representation of integers n in the form $n=(x+y+z+w)(1/x+1/y+1/z+1/w).$ Further, an example, the first such known, of a quartic surface $x^4+7y^4=14z^4+18w^4$ is given with remarkable properties: it is everywhere locally solvable, yet has no non-zero rational point, despite having a point in (non-trivial) odd-degree extension fields of the rationals. The ideas here involve manipulation of the Hilbert symbol, together with the theory of elliptic curves.
for integer or rational solutions of algebraic equations. Pythagorean triangles are
an early instance. Diophantus of Alexandria wrote the first related treatise in the
fourth century; it was an area extensively studied by the great mathematicians of the seventeenth century, including Euler and Fermat.
The modern approach is to treat the equations as defining geometric objects, curves, surfaces, etc. The theory of elliptic curves (or curves of genus 1, which are much used in modern cryptography) was developed extensively in the twentieth century, and has had great application to Diophantine equations. This theory is used in application to the problems studied in this thesis. This thesis studies some curves of high genus, and possible solutions in both rationals and in algebraic number fields, generalizes some old results and gives answers to some open problems in the literature. The methods involve known techniques together with some ingenious tricks. For example, the equations $y^2=x^6+k$, $k=-39,\,-47$, the two previously unsolved cases for $|k|<50$, are solved using algebraic number theory and the ‘elliptic Chabauty’ method. The thesis also studies the genus three quartic curves $F(x^2,y^2,z^2)=0$ where F is a homogeneous quadratic form, and extend old results of Cassels, and Bremner. It is a very delicate matter to find such curves that have no rational points, yet which do have points in odd-degree extension fields of the rationals.
The principal results of the thesis are related to surfaces where the theory is much less well known. In particular, the thesis studies some specific families of surfaces, and give a negative answer to a question in the literature regarding representation of integers n in the form $n=(x+y+z+w)(1/x+1/y+1/z+1/w).$ Further, an example, the first such known, of a quartic surface $x^4+7y^4=14z^4+18w^4$ is given with remarkable properties: it is everywhere locally solvable, yet has no non-zero rational point, despite having a point in (non-trivial) odd-degree extension fields of the rationals. The ideas here involve manipulation of the Hilbert symbol, together with the theory of elliptic curves.
ContributorsNguyen, Xuan Tho (Author) / Bremner, Andrew (Thesis advisor) / Childress, Nancy (Committee member) / Jones, John (Committee member) / Quigg, John (Committee member) / Fishel, Susanna (Committee member) / Arizona State University (Publisher)
Created2019
Description
Almost commuting matrices, i.e. matrices with a sufficiently small commutator, may be nearly commuting, i.e. there may exist matrices close by which do commute. By referencing current literature, this condition is studied for fixed dimension, unitary, self-adjoint, and orthogonal matrices. These proofs are made more accessible and compared to each other, providing insight to possible future progress in the field.
ContributorsMolloy, Riley Phillip (Author) / Spielberg, Jack (Thesis director) / Quigg, John (Committee member) / Barrett, The Honors College (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Department of Physics (Contributor)
Created2015-05