Matching Items (603)
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
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
This research compares shifts in a SuperSpec titanium nitride (TiN) kinetic inductance detector's (KID's) resonant frequency with accepted models for other KIDs. SuperSpec, which is being developed at the University of Colorado Boulder, is an on-chip spectrometer designed with a multiplexed readout with multiple KIDs that is set up for a broadband transmission of these measurements. It is useful for detecting radiation in the mm and sub mm wavelengths which is significant since absorption and reemission of photons by dust causes radiation from distant objects to reach us in infrared and far-infrared bands. In preparation for testing, our team installed stages designed previously by Paul Abers and his group into our cryostat and designed and installed other parts necessary for the cryostat to be able to test devices on the 250 mK stage. This work included the design and construction of additional parts, a new setup for the wiring in the cryostat, the assembly, testing, and installation of several stainless steel coaxial cables for the measurements through the devices, and other cryogenic and low pressure considerations. The SuperSpec KID was successfully tested on this 250 mK stage thus confirming that the new setup is functional. Our results are in agreement with existing models which suggest that the breaking of cooper pairs in the detector's superconductor which occurs in response to temperature, optical load, and readout power will decrease the resonant frequencies. A negative linear relationship in our results appears, as expected, since the parameters are varied only slightly so that a linear approximation is appropriate. We compared the rate at which the resonant frequency responded to temperature and found it to be close to the expected value.
ContributorsDiaz, Heriberto Chacon (Author) / Mauskopf, Philip (Thesis director) / McCartney, Martha (Committee member) / Department of Physics (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Barrett, The Honors College (Contributor)
Created2018-05
Description
This paper considers what factors influence student interest, motivation, and continued engagement. Studies show anticipated extrinsic rewards for activity participation have been shown to reduce intrinsic value for that activity. This might suggest that grade point average (GPA) has a similar effect on academic interests. Further, when incentives such as scholarships, internships, and careers are GPA-oriented, students must adopt performance goals in courses to guarantee success. However, performance goals have not been shown to correlated with continued interest in a topic. Current literature proposes that student involvement in extracurricular activities, focused study groups, and mentored research are crucial to student success. Further, students may express either a fixed or growth mindset, which influences their approach to challenges and opportunities for growth. The purpose of this study was to collect individual cases of students' experiences in college. The interview method was chosen to collect complex information that could not be gathered from standard surveys. To accomplish this, questions were developed based on content areas related to education and motivation theory. The content areas included activities and meaning, motivation, vision, and personal development. The developed interview method relied on broad questions that would be followed by specific "probing" questions. We hypothesize that this would result in participant-led discussions and unique narratives from the participant. Initial findings suggest that some of the questions were effective in eliciting detailed responses, though results were dependent on the interviewer. From the interviews we find that students value their group involvements, leadership opportunities, and relationships with mentors, which parallels results found in other studies.
ContributorsAbrams, Sara (Author) / Hartwell, Lee (Thesis director) / Correa, Kevin (Committee member) / Department of Psychology (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Barrett, The Honors College (Contributor)
Created2018-05
Description
This study estimates the capitalization effect of golf courses in Maricopa County using the hedonic pricing method. It draws upon a dataset of 574,989 residential transactions from 2000 to 2006 to examine how the aesthetic, non-golf benefits of golf courses capitalize across a gradient of proximity measures. The measures for amenity value extend beyond home adjacency and include considerations for homes within a range of discrete walkability buffers of golf courses. The models also distinguish between public and private golf courses as a proxy for the level of golf course access perceived by non-golfers. Unobserved spatial characteristics of the neighborhoods around golf courses are controlled for by increasing the extent of spatial fixed effects from city, to census tract, and finally to 2000 meter golf course ‘neighborhoods.’ The estimation results support two primary conclusions. First, golf course proximity is found to be highly valued for adjacent homes and homes up to 50 meters way from a course, still evident but minimal between 50 and 150 meters, and insignificant at all other distance ranges. Second, private golf courses do not command a higher proximity premia compared to public courses with the exception of homes within 25 to 50 meters of a course, indicating that the non-golf benefits of courses capitalize similarly, regardless of course type. The results of this study motivate further investigation into golf course features that signal access or add value to homes in the range of capitalization, particularly for near-adjacent homes between 50 and 150 meters thought previously not to capitalize.
ContributorsJoiner, Emily (Author) / Abbott, Joshua (Thesis director) / Smith, Kerry (Committee member) / Economics Program in CLAS (Contributor) / School of Sustainability (Contributor) / School of Mathematical and Statistical Sciences (Contributor) / Barrett, The Honors College (Contributor)
Created2018-05
Description
The objective of this paper is to provide an educational diagnostic into the technology of blockchain and its application for the supply chain. Education on the topic is important to prevent misinformation on the capabilities of blockchain. Blockchain as a new technology can be confusing to grasp given the wide possibilities it can provide. This can convolute the topic by being too broad when defined. Instead, the focus will be maintained on explaining the technical details about how and why this technology works in improving the supply chain. The scope of explanation will not be limited to the solutions, but will also detail current problems. Both public and private blockchain networks will be explained and solutions they provide in supply chains. In addition, other non-blockchain systems will be described that provide important pieces in supply chain operations that blockchain cannot provide. Blockchain when applied to the supply chain provides improved consumer transparency, management of resources, logistics, trade finance, and liquidity.
ContributorsKrukar, Joel Michael (Author) / Oke, Adegoke (Thesis director) / Duarte, Brett (Committee member) / Hahn, Richard (Committee member) / School of Mathematical and Statistical Sciences (Contributor) / Department of Economics (Contributor) / Barrett, The Honors College (Contributor)
Created2018-05
Description
The Super Catalan numbers are a known set of numbers which have so far eluded a combinatorial interpretation. Several weighted interpretations have appeared since their discovery, one of which was discovered by William Kuszmaul in 2017. In this paper, we connect the weighted Super Catalan structure created previously by Kuszmaul and a natural $q$-analogue of the Super Catalan numbers. We do this by creating a statistic $\sigma$ for which the $q$ Super Catalan numbers, $S_q(m,n)=\sum_X (-1)^{\mu(X)} q^{\sigma(X)}$. In doing so, we take a step towards finding a strict combinatorial interpretation for the Super Catalan numbers.
ContributorsHouse, John Douglas (Author) / Fishel, Susanna (Thesis director) / Childress, Nancy (Committee member) / School of Mathematical and Statistical Sciences (Contributor) / Barrett, The Honors College (Contributor)
Created2018-05