Matching Items (58)
Filtering by
- Genre: Doctoral Dissertation
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
In 1959, Iwasawa proved that the size of the $p$-part of the class groups of a $\mathbb{Z}_p$-extension grows as a power of $p$ with exponent ${\mu}p^m+{\lambda}\,m+\nu$ for $m$ sufficiently large. Broadly, I construct conditions to verify if a given $m$ is indeed sufficiently large. More precisely, let $CG_m^i$ (class group) be the $\epsilon_i$-eigenspace component of the $p$-Sylow subgroup of the class group of the field at the $m$-th level in a $\mathbb{Z}_p$-extension; and let $IACG^i_m$ (Iwasawa analytic class group) be ${\mathbb{Z}_p[[T]]/((1+T)^{p^m}-1,f(T,\omega^{1-i}))}$, where $f$ is the associated Iwasawa power series. It is expected that $CG_m^i$ and $IACG^i_m$ be isomorphic, providing us with a powerful connection between algebraic and analytic techniques; however, as of yet, this isomorphism is unestablished in general. I consider the existence and the properties of an exact sequence $$0\longrightarrow\ker{\longrightarrow}CG_m^i{\longrightarrow}IACG_m^i{\longrightarrow}\textrm{coker}\longrightarrow0.$$ In the case of a $\mathbb{Z}_p$-extension where the Main Conjecture is established, there exists a pseudo-isomorphism between the respective inverse limits of $CG_m^i$ and $IACG_m^i$. I consider conditions for when such a pseudo-isomorphism immediately gives the existence of the desired exact sequence, and I also consider work-around methods that preserve cardinality for otherwise. However, I primarily focus on constructing conditions to verify if a given $m$ is sufficiently large that the kernel and cokernel of the above exact sequence have become well-behaved, providing similarity of growth both in the size and in the structure of $CG_m^i$ and $IACG_m^i$; as well as conditions to determine if any such $m$ exists. The primary motivating idea is that if $IACG_m^i$ is relatively easy to work with, and if the relationship between $CG_m^i$ and $IACG_m^i$ is understood; then $CG_m^i$ becomes easier to work with. Moreover, while the motivating framework is stated concretely in terms of the cyclotomic $\mathbb{Z}_p$-extension of $p$-power roots of unity, all results are generally applicable to arbitrary $\mathbb{Z}_p$-extensions as they are developed in terms of Iwasawa-Theory-inspired, yet abstracted, algebraic results on maps between inverse limits.
ContributorsElledge, Shawn Michael (Author) / Childress, Nancy (Thesis advisor) / Bremner, Andrew (Committee member) / Fishel, Susanna (Committee member) / Jones, John (Committee member) / Paupert, Julien (Committee member) / Arizona State University (Publisher)
Created2013
Description
Research on combinatorics education is sparse when compared with other fields in mathematics education. This research attempted to contribute to the dearth of literature by examining students' reasoning about enumerative combinatorics problems and how students conceptualize the set of elements being counted in such problems, called the solution set. In particular, the focus was on the stable patterns of reasoning, known as ways of thinking, which students applied in a variety of combinatorial situations and tasks. This study catalogued students' ways of thinking about solution sets as they progressed through an instructional sequence. In addition, the relationships between the catalogued ways of thinking were explored. Further, the study investigated the challenges students experienced as they interacted with the tasks and instructional interventions, and how students' ways of thinking evolved as these challenges were overcome. Finally, it examined the role of instruction in guiding students to develop and extend their ways of thinking. Two pairs of undergraduate students with no formal experience with combinatorics participated in one of the two consecutive teaching experiments conducted in Spring 2012. Many ways of thinking emerged through the grounded theory analysis of the data, but only eight were identified as robust. These robust ways of thinking were classified into three categories: Subsets, Odometer, and Problem Posing. The Subsets category encompasses two ways of thinking, both of which ultimately involve envisioning the solution set as the union of subsets. The three ways of thinking in Odometer category involve holding an item or a set of items constant and systematically varying the other items involved in the counting process. The ways of thinking belonging to Problem Posing category involve spontaneously posing new, related combinatorics problems and finding relationships between the solution sets of the original and the new problem. The evolution of students' ways of thinking in the Problem Posing category was analyzed. This entailed examining the perturbation experienced by students and the resulting accommodation of their thinking. It was found that such perturbation and its resolution was often the result of an instructional intervention. Implications for teaching practice are discussed.
ContributorsHalani, Aviva (Author) / Roh, Kyeong Hah (Thesis advisor) / Fishel, Susanna (Committee member) / Saldanha, Luis (Committee member) / Thompson, Patrick (Committee member) / Zandieh, Michelle (Committee member) / Arizona State University (Publisher)
Created2013
Description
The pay-as-you-go economic model of cloud computing increases the visibility, traceability, and verifiability of software costs. Application developers must understand how their software uses resources when running in the cloud in order to stay within budgeted costs and/or produce expected profits. Cloud computing's unique economic model also leads naturally to an earn-as-you-go profit model for many cloud based applications. These applications can benefit from low level analyses for cost optimization and verification. Testing cloud applications to ensure they meet monetary cost objectives has not been well explored in the current literature. When considering revenues and costs for cloud applications, the resource economic model can be scaled down to the transaction level in order to associate source code with costs incurred while running in the cloud. Both static and dynamic analysis techniques can be developed and applied to understand how and where cloud applications incur costs. Such analyses can help optimize (i.e. minimize) costs and verify that they stay within expected tolerances. An adaptation of Worst Case Execution Time (WCET) analysis is presented here to statically determine worst case monetary costs of cloud applications. This analysis is used to produce an algorithm for determining control flow paths within an application that can exceed a given cost threshold. The corresponding results are used to identify path sections that contribute most to cost excess. A hybrid approach for determining cost excesses is also presented that is comprised mostly of dynamic measurements but that also incorporates calculations that are based on the static analysis approach. This approach uses operational profiles to increase the precision and usefulness of the calculations.
ContributorsBuell, Kevin, Ph.D (Author) / Collofello, James (Thesis advisor) / Davulcu, Hasan (Committee member) / Lindquist, Timothy (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2012
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
As networks are playing an increasingly prominent role in different aspects of our lives, there is a growing awareness that improving their performance is of significant importance. In order to enhance performance of networks, it is essential that scarce networking resources be allocated smartly to match the continuously changing network environment. This dissertation focuses on two different kinds of networks - communication and social, and studies resource allocation problems in these networks. The study on communication networks is further divided into different networking technologies - wired and wireless, optical and mobile, airborne and terrestrial. Since nodes in an airborne network (AN) are heterogeneous and mobile, the design of a reliable and robust AN is highly complex. The dissertation studies connectivity and fault-tolerance issues in ANs and proposes algorithms to compute the critical transmission range in fault free, faulty and delay tolerant scenarios. Just as in the case of ANs, power optimization and fault tolerance are important issues in wireless sensor networks (WSN). In a WSN, a tree structure is often used to deliver sensor data to a sink node. In a tree, failure of a node may disconnect the tree. The dissertation investigates the problem of enhancing the fault tolerance capability of data gathering trees in WSN. The advent of OFDM technology provides an opportunity for efficient resource utilization in optical networks and also introduces a set of novel problems, such as routing and spectrum allocation (RSA) problem. This dissertation proves that RSA problem is NP-complete even when the network topology is a chain, and proposes approximation algorithms. In the domain of social networks, the focus of this dissertation is study of influence propagation in presence of active adversaries. In a social network multiple vendors may attempt to influence the nodes in a competitive fashion. This dissertation investigates the scenario where the first vendor has already chosen a set of nodes and the second vendor, with the knowledge of the choice of the first, attempts to identify a smallest set of nodes so that after the influence propagation, the second vendor's market share is larger than the first.
ContributorsShirazipourazad, Shahrzad (Author) / Sen, Arunabha (Committee member) / Xue, Guoliang (Committee member) / Richa, Andrea (Committee member) / Saripalli, Srikanth (Committee member) / Arizona State University (Publisher)
Created2014
Description
In 1984, Sinnott used $p$-adic measures on $\mathbb{Z}_p$ to give a new proof of the Ferrero-Washington Theorem for abelian number fields by realizing $p$-adic $L$-functions as (essentially) the $Gamma$-transform of certain $p$-adic rational function measures. Shortly afterward, Gillard and Schneps independently adapted Sinnott's techniques to the case of $p$-adic $L$-functions associated to elliptic curves with complex multiplication (CM) by realizing these $p$-adic $L$-functions as $Gamma$-transforms of certain $p$-adic rational function measures. The results in the CM case give the vanishing of the Iwasawa $mu$-invariant for certain $mathbb{Z}_p$-extensions of imaginary quadratic fields constructed from torsion points of CM elliptic curves.
In this thesis, I develop the theory of $p$-adic measures on $mathbb{Z}_p^d$, with particular interest given to the case of $d>1$. Although I introduce these measures within the context of $p$-adic integration, this study includes a strong emphasis on the interpretation of $p$-adic measures as $p$-adic power series. With this dual perspective, I describe $p$-adic analytic operations as maps on power series; the most important of these operations is the multivariate $Gamma$-transform on $p$-adic measures.
This thesis gives new significance to product measures, and in particular to the use of product measures to construct measures on $mathbb{Z}_p^2$ from measures on $mathbb{Z}_p$. I introduce a subring of pseudo-polynomial measures on $mathbb{Z}_p^2$ which is closed under the standard operations on measures, including the $Gamma$-transform. I obtain results on the Iwasawa-invariants of such pseudo-polynomial measures, and use these results to deduce certain continuity results for the $Gamma$-transform. As an application, I establish the vanishing of the Iwasawa $mu$-invariant of Yager's two-variable $p$-adic $L$-function from measure theoretic considerations.
In this thesis, I develop the theory of $p$-adic measures on $mathbb{Z}_p^d$, with particular interest given to the case of $d>1$. Although I introduce these measures within the context of $p$-adic integration, this study includes a strong emphasis on the interpretation of $p$-adic measures as $p$-adic power series. With this dual perspective, I describe $p$-adic analytic operations as maps on power series; the most important of these operations is the multivariate $Gamma$-transform on $p$-adic measures.
This thesis gives new significance to product measures, and in particular to the use of product measures to construct measures on $mathbb{Z}_p^2$ from measures on $mathbb{Z}_p$. I introduce a subring of pseudo-polynomial measures on $mathbb{Z}_p^2$ which is closed under the standard operations on measures, including the $Gamma$-transform. I obtain results on the Iwasawa-invariants of such pseudo-polynomial measures, and use these results to deduce certain continuity results for the $Gamma$-transform. As an application, I establish the vanishing of the Iwasawa $mu$-invariant of Yager's two-variable $p$-adic $L$-function from measure theoretic considerations.
ContributorsZinzer, Scott Michael (Author) / Childress, Nancy (Thesis advisor) / Bremner, Andrew (Committee member) / Fishel, Susanna (Committee member) / Jones, John (Committee member) / Spielberg, John (Committee member) / Arizona State University (Publisher)
Created2015
Description
Resource allocation is one of the most challenging issues policy decision makers must address. The objective of this thesis is to explore the resource allocation from an economical perspective, i.e., how to purchase resources in order to satisfy customers' requests. In this thesis, we attend to answer the question: when and how to buy resources to fulfill customers' demands with minimum costs?
The first topic studied in this thesis is resource allocation in cloud networks. Cloud computing heralded an era where resources (such as computation and storage) can be scaled up and down elastically and on demand. This flexibility is attractive for its cost effectiveness: the cloud resource price depends on the actual utilization over time. This thesis studies two critical problems in cloud networks, focusing on the economical aspects of the resource allocation in the cloud/virtual networks, and proposes six algorithms to address the resource allocation problems for different discount models. The first problem attends a scenario where the virtual network provider offers different contracts to the service provider. Four algorithms for resource contract migration are proposed under two pricing models: Pay-as-You-Come and Pay-as-You-Go. The second problem explores a scenario where a cloud provider offers k contracts each with a duration and a rate respectively and a customer buys these contracts in order to satisfy its resource demand. This work shows that this problem can be seen as a 2-dimensional generalization of the classic online parking permit problem, and present a k-competitive online algorithm and an optimal online algorithm.
The second topic studied in this thesis is to explore how resource allocation and purchasing strategies work in our daily life. For example, is it worth buying a Yoga pass which costs USD 100 for ten entries, although it will expire at the end of this year? Decisions like these are part of our daily life, yet, not much is known today about good online strategies to buy discount vouchers with expiration dates. This work hence introduces a Discount Voucher Purchase Problem (DVPP). It aims to optimize the strategies for buying discount vouchers, i.e., coupons, vouchers, groupons which are valid only during a certain time period. The DVPP comes in three flavors: (1) Once Expire Lose Everything (OELE): Vouchers lose their entire value after expiration. (2) Once Expire Lose Discount (OELD): Vouchers lose their discount value after expiration. (3) Limited Purchasing Window (LPW): Vouchers have the property of OELE and can only be bought during a certain time window.
This work explores online algorithms with a provable competitive ratio against a clairvoyant offline algorithm, even in the worst case. In particular, this work makes the following contributions: we present a 4-competitive algorithm for OELE, an 8-competitive algorithm for OELD, and a lower bound for LPW. We also present an optimal offline algorithm for OELE and LPW, and show it is a 2-approximation solution for OELD.
The first topic studied in this thesis is resource allocation in cloud networks. Cloud computing heralded an era where resources (such as computation and storage) can be scaled up and down elastically and on demand. This flexibility is attractive for its cost effectiveness: the cloud resource price depends on the actual utilization over time. This thesis studies two critical problems in cloud networks, focusing on the economical aspects of the resource allocation in the cloud/virtual networks, and proposes six algorithms to address the resource allocation problems for different discount models. The first problem attends a scenario where the virtual network provider offers different contracts to the service provider. Four algorithms for resource contract migration are proposed under two pricing models: Pay-as-You-Come and Pay-as-You-Go. The second problem explores a scenario where a cloud provider offers k contracts each with a duration and a rate respectively and a customer buys these contracts in order to satisfy its resource demand. This work shows that this problem can be seen as a 2-dimensional generalization of the classic online parking permit problem, and present a k-competitive online algorithm and an optimal online algorithm.
The second topic studied in this thesis is to explore how resource allocation and purchasing strategies work in our daily life. For example, is it worth buying a Yoga pass which costs USD 100 for ten entries, although it will expire at the end of this year? Decisions like these are part of our daily life, yet, not much is known today about good online strategies to buy discount vouchers with expiration dates. This work hence introduces a Discount Voucher Purchase Problem (DVPP). It aims to optimize the strategies for buying discount vouchers, i.e., coupons, vouchers, groupons which are valid only during a certain time period. The DVPP comes in three flavors: (1) Once Expire Lose Everything (OELE): Vouchers lose their entire value after expiration. (2) Once Expire Lose Discount (OELD): Vouchers lose their discount value after expiration. (3) Limited Purchasing Window (LPW): Vouchers have the property of OELE and can only be bought during a certain time window.
This work explores online algorithms with a provable competitive ratio against a clairvoyant offline algorithm, even in the worst case. In particular, this work makes the following contributions: we present a 4-competitive algorithm for OELE, an 8-competitive algorithm for OELD, and a lower bound for LPW. We also present an optimal offline algorithm for OELE and LPW, and show it is a 2-approximation solution for OELD.
ContributorsHu, Xinhui (Author) / Richa, Andrea (Thesis advisor) / Schmid, Stefan (Committee member) / Sen, Arunabha (Committee member) / Xue, Guoliang (Committee member) / Arizona State University (Publisher)
Created2015
Description
US Senate is the venue of political debates where the federal bills are formed and voted. Senators show their support/opposition along the bills with their votes. This information makes it possible to extract the polarity of the senators. Similarly, blogosphere plays an increasingly important role as a forum for public debate. Authors display sentiment toward issues, organizations or people using a natural language.
In this research, given a mixed set of senators/blogs debating on a set of political issues from opposing camps, I use signed bipartite graphs for modeling debates, and I propose an algorithm for partitioning both the opinion holders (senators or blogs) and the issues (bills or topics) comprising the debate into binary opposing camps. Simultaneously, my algorithm scales the entities on a univariate scale. Using this scale, a researcher can identify moderate and extreme senators/blogs within each camp, and polarizing versus unifying issues. Through performance evaluations I show that my proposed algorithm provides an effective solution to the problem, and performs much better than existing baseline algorithms adapted to solve this new problem. In my experiments, I used both real data from political blogosphere and US Congress records, as well as synthetic data which were obtained by varying polarization and degree distribution of the vertices of the graph to show the robustness of my algorithm.
I also applied my algorithm on all the terms of the US Senate to the date for longitudinal analysis and developed a web based interactive user interface www.PartisanScale.com to visualize the analysis.
US politics is most often polarized with respect to the left/right alignment of the entities. However, certain issues do not reflect the polarization due to political parties, but observe a split correlating to the demographics of the senators, or simply receive consensus. I propose a hierarchical clustering algorithm that identifies groups of bills that share the same polarization characteristics. I developed a web based interactive user interface www.ControversyAnalysis.com to visualize the clusters while providing a synopsis through distribution charts, word clouds, and heat maps.
In this research, given a mixed set of senators/blogs debating on a set of political issues from opposing camps, I use signed bipartite graphs for modeling debates, and I propose an algorithm for partitioning both the opinion holders (senators or blogs) and the issues (bills or topics) comprising the debate into binary opposing camps. Simultaneously, my algorithm scales the entities on a univariate scale. Using this scale, a researcher can identify moderate and extreme senators/blogs within each camp, and polarizing versus unifying issues. Through performance evaluations I show that my proposed algorithm provides an effective solution to the problem, and performs much better than existing baseline algorithms adapted to solve this new problem. In my experiments, I used both real data from political blogosphere and US Congress records, as well as synthetic data which were obtained by varying polarization and degree distribution of the vertices of the graph to show the robustness of my algorithm.
I also applied my algorithm on all the terms of the US Senate to the date for longitudinal analysis and developed a web based interactive user interface www.PartisanScale.com to visualize the analysis.
US politics is most often polarized with respect to the left/right alignment of the entities. However, certain issues do not reflect the polarization due to political parties, but observe a split correlating to the demographics of the senators, or simply receive consensus. I propose a hierarchical clustering algorithm that identifies groups of bills that share the same polarization characteristics. I developed a web based interactive user interface www.ControversyAnalysis.com to visualize the clusters while providing a synopsis through distribution charts, word clouds, and heat maps.
ContributorsGokalp, Sedat (Author) / Davulcu, Hasan (Thesis advisor) / Sen, Arunabha (Committee member) / Liu, Huan (Committee member) / Woodward, Mark (Committee member) / Arizona State University (Publisher)
Created2015