Current Search: Song, Zixia (x)
View All Items
 Title
 ON SATURATION NUMBERS OF RAMSEYMINIMAL GRAPHS.
 Creator

Davenport, Hunter M, Song, ZiXia, University of Central Florida
 Abstract / Description

Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring of G, we say c is a bad coloring if G contains...
Show moreDating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring of G, we say c is a bad coloring if G contains no red K3or blue K1,t under c. A graph G is (H1,...,Hk)Ramseyminimal if G arrows (H1,...,Hk) but no proper subgraph of G has this property. Given a family F of graphs, we say that a graph G is Fsaturated if no member of F is a subgraph of G, but for any edge xy not in E(G), G + xy contains a member of F as a subgraph. Letting Rmin(K3, K1,t) be the family of (K3,K1,t)Ramsey minimal graphs, we study the saturation number, denoted sat(n,Rmin(K3,K1,t)), which is the minimum number of edges among all Rmin(K3,K1,t)saturated graphs on n vertices. We believe the methods and constructions developed in this thesis will be useful in studying the saturation numbers of (K4,K1,t)saturated graphs.
Show less  Date Issued
 2018
 Identifier
 CFH2000291, ucf:45881
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFH2000291
 Title
 GALLAIRAMSEY NUMBERS FOR C7 WITH MULTIPLE COLORS.
 Creator

Bruce, Dylan, Song, ZiXia, University of Central Florida
 Abstract / Description

The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edgecolorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = ��� = Hk = H, if every kedgecoloring of G contains a monochromatic Hi in color i for some i ? {1,...,k}. The Ramsey number rk(H1, ..., Hk) is the...
Show moreThe core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edgecolorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = ��� = Hk = H, if every kedgecoloring of G contains a monochromatic Hi in color i for some i ? {1,...,k}. The Ramsey number rk(H1, ..., Hk) is the minimum integer n such that Kn ? (H1, ..., Hk), where Kn is the complete graph on n vertices. Computing rk(H1, ..., Hk) is a notoriously difficult problem in combinatorics. A weakening of this problem is to restrict ourselves to Gallai colorings, that is, edgecolorings with no rainbow triangles. From this we define the GallaiRamsey number grk(K3,G) as the minimum integer n such that either Kn contains a rainbow triangle, or Kn ? (G)k . In this thesis, we determine the GallaiRamsey numbers for C7 with multiple colors. We believe the method we developed can be applied to find grk(K3, C2n+1) for any integer n ? 2, where C2n+1 denotes a cycle on 2n + 1 vertices.
Show less  Date Issued
 2017
 Identifier
 CFH2000264, ucf:46025
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFH2000264
 Title
 Weierstrass vertices and divisor theory of graphs.
 Creator

De Vas Gunasekara, Ajani Ruwandhika, Brennan, Joseph, Song, Zixia, Martin, Heath, University of Central Florida
 Abstract / Description

Chipfiring games and divisor theory on finite, connected, undirected and unweighted graphs have been studied as analogs of divisor theory on Riemann Surfaces. As part of this theory, a version of the onedimensional RiemannRoch theorem was introduced for graphs by Matt Baker in 2007. Properties of algebraic curves that have been studied can be applied to study graphs by means of the divisor theory of graphs.In this research, we investigate the property of a vertex of a graph having the...
Show moreChipfiring games and divisor theory on finite, connected, undirected and unweighted graphs have been studied as analogs of divisor theory on Riemann Surfaces. As part of this theory, a version of the onedimensional RiemannRoch theorem was introduced for graphs by Matt Baker in 2007. Properties of algebraic curves that have been studied can be applied to study graphs by means of the divisor theory of graphs.In this research, we investigate the property of a vertex of a graph having the Weierstrass property in analogy to the theory of Weierstrass points on algebraic curves. The weight of the Weierstrass vertices is then calculated in a manner analogous to the algebraic curve case. Although there are many graphs for which all vertices are Weierstrass vertices, there are bounds on the total weight of the Weierstrass vertices as a function of the arithmetic genus.For complete graphs, all of the vertices are Weierstrass when the number of vertices (n) is greater than or equals to $4$ and no vertex is Weierstrass for $n$ strictly less than 4. We study the complete graphs on 4, 5 and 6 vertices and reveal a pattern in the gap sequence for higher cases of n.Furthermore, we introduce a formula to calculate the Weierstrass weight of a vertex of the complete graph on n vertices. Additionally, we prove that Weierstrass semigroup of complete graphs is 2  generated. Moreover, we show that there are no graphs of genus 2 and 6 vertices with all the vertices being normal Weierstrass vertices and generalize this result to any graph with genus g.
Show less  Date Issued
 2018
 Identifier
 CFE0007397, ucf:52072
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0007397
 Title
 Two Ramseyrelated Problems.
 Creator

Zhang, Jingmei, Song, Zixia, Zhao, Yue, Martin, Heath, Turgut, Damla, University of Central Florida
 Abstract / Description

Extremal combinatorics is one of the central branches of discrete mathematics and has experienced an impressive growth during the last few decades. It deals with the problem of determining or estimating the maximum or minimum possible size of a combinatorial structure which satisfies certain requirements. In this dissertation, we focus on studying the minimum number of edges of certain cocritical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, ....
Show moreExtremal combinatorics is one of the central branches of discrete mathematics and has experienced an impressive growth during the last few decades. It deals with the problem of determining or estimating the maximum or minimum possible size of a combinatorial structure which satisfies certain requirements. In this dissertation, we focus on studying the minimum number of edges of certain cocritical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, . . . , H_r) if every rcoloring of the edges of G contains a monochromatic copy of H_i in color i for some i \in {1, . . . , r}. A graph G is (H_1, . . . , H_r)cocritical if G \nrightarrow (H_1, . . . , H_r), but G+uv \rightarrow (H_1, . . . , H_r) for every pair of nonadjacent vertices u, v in G. Motivated in part by Hanson and Toft's conjecture from 1987, we study the minimum number of edges over all (K_t,\mathcal{T}_k)cocritical graphs on n vertices, where \mathcal{T}_k denotes the family of all trees on k vertices. We apply graph bootstrap percolation on a not necessarily K_tsaturated graph to prove that for all t \geq 4 and k \geq max{6, t}, there exists a constant c(t,k) such that, for all n \geq (t1)(k1)+1, if G is a (K_t,\mathcal{T}_k)cocritical graph on n vertices, then e(G) \geq ((4t9)/2+\lceil k/2 \rceil /2)nc(t,k). We then show that this is asymptotically best possible for all sufficiently large n when t \in {4, 5} and k \geq 6. The method we developed may shed some light on solving Hanson and Toft's conjecture, which is wide open.We also study Ramsey numbers of even cycles and paths under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai kcoloring is a Gallai coloring that uses at most k colors. Given an integer k \geq 1 and graphs H_1, . . . , H_k, the GallaiRamsey number GR(H_1, . . . , H_k) is the least integer n such that every Gallai kcoloring of the complete graph K_n contains a monochromatic copy of H_i in color i for some i \in {1, . . . , k}. We completely determine the exact values of GR(H_1, . . . , H_k) for all k \geq 2 when each H_i is a path or an even cycle on at most 13 vertices.
Show less  Date Issued
 2019
 Identifier
 CFE0007745, ucf:52404
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0007745
 Title
 H(&)#252;ckel Energy of a Graph: Its Evolution From Quantum Chemistry to Mathematics.
 Creator

Zimmerman, Steven, Mohapatra, Ram, Song, Zixia, Brigham, Robert, University of Central Florida
 Abstract / Description

The energy of a graph began with German physicist, Erich H(&)#252;ckel's 1931 paper, QuantenttheoretischeBeitr(&)#228;ge zum Benzolproblem. His work developed a method for computing thebinding energy of the ?electrons for a certain class of organic molecules. The vertices of thegraph represented the carbon atoms while the single edge between each pair of distinct verticesrepresented the hydrogen bonds between the carbon atoms. In turn, the chemical graphswere represented by an n (&)#215; n...
Show moreThe energy of a graph began with German physicist, Erich H(&)#252;ckel's 1931 paper, QuantenttheoretischeBeitr(&)#228;ge zum Benzolproblem. His work developed a method for computing thebinding energy of the ?electrons for a certain class of organic molecules. The vertices of thegraph represented the carbon atoms while the single edge between each pair of distinct verticesrepresented the hydrogen bonds between the carbon atoms. In turn, the chemical graphswere represented by an n (&)#215; n matrix used in solving Schr(&)#246;dinger's eigenvalue/eigenvectorequation. The sum of the absolute values of these graph eigenvalues represented the total?electron energy. The criteria for constructing these chemical graphs and the chemical interpretationsof all the quantities involved made up the H(&)#252;ckel Molecular Orbital theoryor HMO theory. In this paper, we will show how the chemical interpretation of H(&)#252;ckel'sgraph energy evolved to a mathematical interpretation of graph energy that Ivan Gutmanprovided for us in his famous 1978 definition of the energy of a graph. Next, we will presentCharles Coulson's 1940 theorem that expresses the energy of a graph as a contour integraland prove some of its corollaries. These corollaries allow us to order the energies of acyclicand bipartite graphs by the coefficients of their characteristic polynomial. Following Coulson'stheorem and its corollaries we will look at McClelland's first theorem on the boundsfor the energy of a graph. In the corollaries that follow McClelland's 1971 theorem, we willprove the corollaries that show a direct variation between the energy of a graph and thenumber of its vertices and edges. Finally, we will see how this relationship led to Gutman'sconjecture that the complete graph on n vertices has maximal energy. Although this wasdisproved by Chris Godsil in 1981, we will provide an independent counterexample with thehelp of the software, Maple 13.
Show less  Date Issued
 2011
 Identifier
 CFE0004184, ucf:49027
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0004184
 Title
 Interval EdgeColorings of Graphs.
 Creator

Foster, Austin, Song, Zixia, Reid, Michael, Brennan, Joseph, University of Central Florida
 Abstract / Description

A proper edgecoloring of a graph G by positive integers is called an interval edgecoloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edgecolorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edgecolorings to schedule parentteacher conferences so...
Show moreA proper edgecoloring of a graph G by positive integers is called an interval edgecoloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edgecolorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edgecolorings to schedule parentteacher conferences so that every person's conferences occur in consecutive slots. A solution exists if and only if the bipartite graph with vertices for parents and teachers, and edges for the required meetings, has an interval edgecoloring.A wellknown result of Vizing states that for any simple graph $G$, $\chi'(G) \leq \Delta(G) + 1$, where $\chi'(G)$ and $\Delta(G)$ denote the edgechromatic number and maximum degree of $G$, respectively. A graph $G$ is called class 1 if $\chi'(G) = \Delta(G)$, and class 2 if $\chi'(G) = \Delta(G) + 1$. One can see that any graph admitting an interval edgecoloring must be of class 1, and thus every graph of class 2 does not have such a coloring.Finding an interval edgecoloring of a given graph is hard. In fact, it has been shown that determining whether a bipartite graph has an interval edgecoloring is NPcomplete. In this thesis, we survey known results on interval edgecolorings of graphs, with a focus on the progress of $(a, b)$biregular bipartite graphs. Discussion of related topics and future work is included at the end. We also give a new proof of Theorem 3.15 on the existence of proper path factors of $(3, 4)$biregular graphs. Finally, we obtain a new result, Theorem 3.18, which states that if a proper path factor of any $(3, 4)$biregular graph has no path of length 8, then it contains paths of length 6 only. The new result we obtained and the method we developed in the proof of Theorem 3.15 might be helpful in attacking the open problems mentioned in the Future Work section of Chapter 5.
Show less  Date Issued
 2016
 Identifier
 CFE0006301, ucf:51609
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006301
 Title
 On Randic Energy of Graphs.
 Creator

Burns, Brittany, Mohapatra, Ram, Song, Zixia, Brennan, Joseph, University of Central Florida
 Abstract / Description

In this research, we explore the subject of graph energy. We first discuss the connections between linear algebra and graph theory and review some important definitions and facts of these two fields. We introduce graph energy and provide some historical perspectives on the subject. Known results of graph energy are also mentioned and some relevant results are proven. We discuss some applications of graph energy in the physical sciences. Then, Randic energy is defined and results are given and...
Show moreIn this research, we explore the subject of graph energy. We first discuss the connections between linear algebra and graph theory and review some important definitions and facts of these two fields. We introduce graph energy and provide some historical perspectives on the subject. Known results of graph energy are also mentioned and some relevant results are proven. We discuss some applications of graph energy in the physical sciences. Then, Randic energy is defined and results are given and proved for specific families of graphs. We focus on simple, connected graphs that are commonly studied in graph theory. Also, the Laplacian energy of a graph is defined. We then examine the connections between the different types of energies for graphs, beginning with graph energy and Randic energy, followed by Laplacian energy and Randic energy. In our results chapter, we introduce the Petersen graph and calculate the Randic energy of this graph. We also define StackedBook graphs and perform some calculations on these graphs. From these calculations, we form a conjecture and discuss some details on how to proceed with the proof of this conjecture. Finally, we summarize our work and details are provided on how this research can be continued.
Show less  Date Issued
 2016
 Identifier
 CFE0006273, ucf:51043
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006273
 Title
 Cascaded Digital Refinement for Intrinsic Evolvable Hardware.
 Creator

Thangavel, Vignesh, DeMara, Ronald, Sundaram, Kalpathy, Song, Zixia, University of Central Florida
 Abstract / Description

Intrinsic evolution of reconfigurable hardware is sought to solve computational problems using the intrinsic processing behavior of SystemonChip (SoC) platforms. SoC devices combine capabilities of analog and digital embedded components within a reconfigurable fabric under software control. A new technique is developed for these fabrics that leverages the digital resources' enhanced accuracy and signal refinement capability to improve circuit performance of the analog resources' which are...
Show moreIntrinsic evolution of reconfigurable hardware is sought to solve computational problems using the intrinsic processing behavior of SystemonChip (SoC) platforms. SoC devices combine capabilities of analog and digital embedded components within a reconfigurable fabric under software control. A new technique is developed for these fabrics that leverages the digital resources' enhanced accuracy and signal refinement capability to improve circuit performance of the analog resources' which are providing low power processing and high computation rates. In particular, Differential Digital Correction (DDC) is developed utilizing an error metric computed from the evolved analog circuit to reconfigure the digital fabric thereby enhancing precision of analog computations. The approach developed herein, Cascaded Digital Refinement (CaDR), explores a multilevel strategy of utilizing DDC for refining intrinsic evolution of analog computational circuits to construct building blocks, known as Constituent Functional Blocks (CFBs). The CFBs are developed in a cascaded sequence followed by digital evolution of higherlevel control of these CFBs to build the final solution for the larger circuit athand. One such platform, Cypress PSoC5LP was utilized to realize solutions to ordinary differential equations by first evolving various powers of the independent variable followed by that of their combinations to emulate mathematical seriesbased solutions for the desired range of values. This is shown to enhance accuracy and precision while incurring lower computational energy and time overheads. The fitness function for each CFB being evolved is different from the fitness function that is defined for the overall problem.
Show less  Date Issued
 2015
 Identifier
 CFE0005723, ucf:50123
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0005723
 Title
 SoftError Resilience Framework For Reliable and EnergyEfficient CMOS Logic and Spintronic Memory Architectures.
 Creator

Alghareb, Faris, DeMara, Ronald, Lin, Mingjie, Zou, Changchun, Jha, Sumit Kumar, Song, Zixia, University of Central Florida
 Abstract / Description

The revolution in chip manufacturing processes spanning five decades has proliferated high performance and energyefficient nanoelectronic devices across all aspects of daily life. In recent years, CMOS technology scaling has realized billions of transistors within largescale VLSI chips to elevate performance. However, these advancements have also continually augmented the impact of SingleEvent Transient (SET) and SingleEvent Upset (SEU) occurrences which precipitate a range of SoftError...
Show moreThe revolution in chip manufacturing processes spanning five decades has proliferated high performance and energyefficient nanoelectronic devices across all aspects of daily life. In recent years, CMOS technology scaling has realized billions of transistors within largescale VLSI chips to elevate performance. However, these advancements have also continually augmented the impact of SingleEvent Transient (SET) and SingleEvent Upset (SEU) occurrences which precipitate a range of SoftError (SE) dependability issues. Consequently, softerror mitigation techniques have become essential to improve systems' reliability. Herein, first, we proposed optimized softerror resilience designs to improve robustness of submicron computing systems. The proposed approaches were developed to deliver energyefficiency and tolerate double/multiple errors simultaneously while incurring acceptable speed performance degradation compared to the prior work. Secondly, the impact of Process Variation (PV) at the NearThreshold Voltage (NTV) region on redundancybased SEmitigation approaches for HighPerformance Computing (HPC) systems was investigated to highlight the approach that can realize favorable attributes, such as reduced critical datapath delay variation and low speed degradation. Finally, recently, spinbased devices have been widely used to design NonVolatile (NV) elements such as NV latches and flipflops, which can be leveraged in normallyoff computing architectures for InternetofThings (IoT) and energyharvestingpowered applications. Thus, in the last portion of this dissertation, we design and evaluate for softerror resilience NVlatching circuits that can achieve intriguing features, such as low energy consumption, high computing performance, and superior soft errors tolerance, i.e., concurrently able to tolerate Multiple Node Upset (MNU), to potentially become a mainstream solution for the aerospace and avionic nanoelectronics. Together, these objectives cooperate to increase energyefficiency and soft errors mitigation resiliency of largerscale emerging NV latching circuits within isoenergy constraints. In summary, addressing these reliability concerns is paramount to successful deployment of future reliable and energyefficient CMOS logic and spintronic memory architectures with deeplyscaled devices operating at lowvoltages.
Show less  Date Issued
 2019
 Identifier
 CFE0007884, ucf:52765
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0007884
 Title
 Methods to Calculate Cut Volumes for Fault Trees with Dependencies Induced by Spatial Locations.
 Creator

Hanes, Phillip, Wiegand, Rudolf, Wu, Annie, DeMara, Ronald, Song, Zixia, University of Central Florida
 Abstract / Description

Fault tree analysis (FTA) is used to find and mitigate vulnerabilities in systems based on their constituent components. Methods exist to efficiently find minimal cut sets (MCS), which are combinations of components whose failure causes the overall system to fail. However, traditional FTA ignores the physical location of the components. Components in close proximity to each other could be defeated by a single event with a radius of effect, such as an explosion or fire. Events such as the...
Show moreFault tree analysis (FTA) is used to find and mitigate vulnerabilities in systems based on their constituent components. Methods exist to efficiently find minimal cut sets (MCS), which are combinations of components whose failure causes the overall system to fail. However, traditional FTA ignores the physical location of the components. Components in close proximity to each other could be defeated by a single event with a radius of effect, such as an explosion or fire. Events such as the Deepwater Horizon explosion and subsequent oil spill demonstrate the potentially devastating risk posed by such spatial dependencies. This motivates the search for techniques to identify this type of vulnerability. Adding physical locations to the fault tree structure can help identify possible points of failure in the overall system caused by localized disasters. Since existing FTA methods cannot address these concerns, using this information requires extending existing solution methods or developing entirely new ones.A problem complicating research in FTA is the lack of benchmark problems for evaluating methods, especially for fault trees over one hundred components. This research presents a method of using Lindenmeyer systems (Lsystems) to generate fault trees that are reproducible, capable of producing fault trees with similar properties to realworld designs, and scalable while maintaining predictable structural properties. This approach will be useful for testing and analyzing different methodologies for FTA tasks at different scales and under different conditions.Using a set of benchmark fault trees derived from Lsystems, three approaches to finding these vulnerabilities were explored in this research. These approaches were compared by defining a metric called (")minimal cut volumes(") (MCV) for describing volumes of effect that defeat the system. Since no existing methods are known for solving this problem, the methods are compared to each other to evaluate performance.1) The control method executes traditional FTA software to find minimal cut sets (MCS), then extends this approach by searching for clusters in the resulting MCS to find MCV.2) The next method starts by searching for clusters of components in the three dimensional space, then evaluates combinations of clusters to find MCV that defeat the system.3) The last method uses an evolutionary algorithm to search the space directly by selecting center points, then using the radius of the smallest sphere(s) as the fitness value for identifying MCV.Results generated using each method are presented. The performance of the methods are compared to the control method and their utilities evaluated accordingly.
Show less  Date Issued
 2018
 Identifier
 CFE0007403, ucf:52075
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0007403
 Title
 Hilbert Series of Graphs, Hypergraphs, and Monomial Ideals.
 Creator

Trainor, Kyle, Brennan, Joseph, Song, Zixia, Martin, Heath, Morey, Susan, Wocjan, Pawel, University of Central Florida
 Abstract / Description

In this dissertation, identities for Hilbert series of quotients of polynomial rings by monomial ideals are explored, beginning in the contexts of graph and hypergraph rings and later generalizing to general monomial ideals. These identities are modeled after constructive identities from graph theory, and can thus be used to construct Hilbert series iteratively from those of smaller algebraic structures.
 Date Issued
 2018
 Identifier
 CFE0007258, ucf:52176
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0007258
 Title
 Spatial Models with Specific Error Structures.
 Creator

Adu, Nathaniel, Richardson, Gary, Mohapatra, Ram, Song, Zixia, Lang, SheauDong, University of Central Florida
 Abstract / Description

The purpose of this dissertation is to study the first order autoregressive model in the spatial context with specific error structures. We begin by supposing that the error structure has a long memory in both the i and the j components. Whenever the model parameters alpha and beta equal one, the limiting distribution of the sequence of normalized Fourier coefficients of the spatial process is shown to be a function of a two parameter fractional Brownian sheet. This result is used to find the...
Show moreThe purpose of this dissertation is to study the first order autoregressive model in the spatial context with specific error structures. We begin by supposing that the error structure has a long memory in both the i and the j components. Whenever the model parameters alpha and beta equal one, the limiting distribution of the sequence of normalized Fourier coefficients of the spatial process is shown to be a function of a two parameter fractional Brownian sheet. This result is used to find the limiting distribution of the periodogram ordinate of the spatial process under the null hypothesis that alpha equals one and beta equals one. We then give the limiting distribution of the normalized Fourier coefficients of the spatial process for both a moving average and autoregressive error structure. Two cases of autoregressive errors are considered. The first error model is autoregressive in one component and the second is autoregressive in both components. We show that the normalizing factor needed to ensure convergence in distribution of the sequence of Fourier coefficients is different in the moving average case, and the two autoregressive cases. In other words, the normalizing factor differs in each of these three cases.Finally, a specific case of the functional central limit theorem in the spatial setting is stated and proved. The assumptions made here are placed on the autocovariance functions. We then discuss some specific examples and provide a test statistics based on the periodogram ordinate.
Show less  Date Issued
 2019
 Identifier
 CFE0007772, ucf:52385
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0007772
 Title
 Mathematical Investigation of the Spatial Spread of an Infectious Disease in a Heterogeneous Environment.
 Creator

Gaudiello, Arielle, Shuai, Zhisheng, Nevai, A, Song, Zixia, Mohapatra, Ram, QuintanaAscencio, Pedro, University of Central Florida
 Abstract / Description

Outbreaks of infectious diseases can devastate a population. Researchers thus study the spread of an infection in a habitat to learn methods of control. In mathematical epidemiology, disease transmission is often assumed to adhere to the law of mass action, yet there are numerous other incidence terms existing in the literature. With recent global outbreaks and epidemics, spatial heterogeneity has been at the forefront of these epidemiological models.We formulate and analyze a model for...
Show moreOutbreaks of infectious diseases can devastate a population. Researchers thus study the spread of an infection in a habitat to learn methods of control. In mathematical epidemiology, disease transmission is often assumed to adhere to the law of mass action, yet there are numerous other incidence terms existing in the literature. With recent global outbreaks and epidemics, spatial heterogeneity has been at the forefront of these epidemiological models.We formulate and analyze a model for humans in a homogeneous population with a nonlinear incidence function and demographics of birth and death. We allow for the combination of host immunity after recovery from infection or host susceptibility once the infection has run its course in the individual. We compute the basic reproduction number, R0, for the system and determine the global stability of the equilibrium states. If R0(<)= 1, the population tends towards a diseasefree state. If R0 (>)1, an endemic equilibrium exists, and the disease is persistent in the population. This work provides the framework needed for a spatially heterogeneous model. The model is then expanded to include a set of cities (or patches), each of which is structured from the homogeneous model. Movement is introduced, allowing travel between the cities at different rates. We assume there always exists a potentially nondirect route between two cities, and the movement need not be symmetric between two patches. Further, each city has its own nonlinear incidence function, demographics, and recovery rates, allowing for realistic interpretations of countrywide network structures. New global stability results are established for the diseasefree equilibrium and endemic equilibrium, the latter utilizing a graph theoretic approach and Lyapunov functions. Asymptotic profiles are determined for both the diseasefree equilibrium and basic reproduction number as the diffusion of human individuals is faster than the disease dynamics. A numerical investigation is performed on a star network, emulating a ruralurban society with a center city and surrounding suburbs. Numerical simulations give rise to similar and contrasting behavior for symmetric movement to the proposed asymmetric movement. Conjectures are made for the monotonicty of the basic reproduction number in terms of the diffusion of susceptible and infectious individuals. The limiting behavior of the system as the diffusion of susceptibles halts is shown to experience varying behavior based on the location of hot spots and biased movement.
Show less  Date Issued
 2019
 Identifier
 CFE0007637, ucf:52463
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0007637
 Title
 Hadwiger Numbers and GallaiRamsey Numbers of Special Graphs.
 Creator

Bosse, Christian, Song, Zixia, Brennan, Joseph, Zhao, Yue, DeMara, Ronald, University of Central Florida
 Abstract / Description

This dissertation explores two separate topics on graphs.We first study a farreaching generalization of the Four Color Theorem. Given a graph G, we use chi(G) to denote the chromatic number; alpha(G) the independence number; and h(G) the Hadwiger number, which is the largest integer t such that the complete graph K_t can be obtained from a subgraph of G by contracting edges. Hadwiger's conjecture from 1943 states that for every graph G, h(G) is greater than or equal to chi(G). This is...
Show moreThis dissertation explores two separate topics on graphs.We first study a farreaching generalization of the Four Color Theorem. Given a graph G, we use chi(G) to denote the chromatic number; alpha(G) the independence number; and h(G) the Hadwiger number, which is the largest integer t such that the complete graph K_t can be obtained from a subgraph of G by contracting edges. Hadwiger's conjecture from 1943 states that for every graph G, h(G) is greater than or equal to chi(G). This is perhaps the most famous conjecture in Graph Theory and remains open even for graphs G with alpha(G) less than or equal to 2. Let W_5 denote the wheel on six vertices. We establish more evidence for Hadwiger's conjecture by proving that h(G) is greater than or equal to chi(G) for all graphs G such that alpha(G) is less than or equal to 2 and G does not contain W_5 as an induced subgraph.Our second topic is related to Ramsey theory, a field that has intrigued those who study combinatorics for many decades. Computing the classical Ramsey numbers is a notoriously difficult problem, leaving many basic questions unanswered even after more than 80 years. We study Ramsey numbers under Gallaicolorings. A Gallaicoloring of a complete graph is an edgecoloring such that no triangle is colored with three distinct colors. Given a graph H and an integer k at least 1, the GallaiRamsey number, denoted GR_k(H), is the least positive integer n such that every Gallaicoloring of K_n with at most k colors contains a monochromatic copy of H. It turns out that GR_k(H) is more wellbehaved than the classical Ramsey number R_k(H), though finding exact values of GR_k(H) is far from trivial. We show that for all k at least 3, GR_k(C_{2n+1}) = n2^k+1 where n is 4, 5, 6 or 7, and GR_k(C_{2n+1}) is at most (n ln n)2^k(k+1)n+1 for all n at least 8, where C_{2n+1} denotes a cycle on 2n+1 vertices.
Show less  Date Issued
 2019
 Identifier
 CFE0007603, ucf:52532
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0007603
 Title
 Coloring graphs with forbidden minors.
 Creator

Rolek, Martin, Song, Zixia, Brennan, Joseph, Reid, Michael, Zhao, Yue, DeMara, Ronald, University of Central Florida
 Abstract / Description

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Ktminor is (t  1)colorable. This conjecture has been proved true for t ? 6, but remains open for all t ? 7. For t = 7, it is not even yet known if a graph with no K7minor is 7colorable. We begin by showing that every graph with no K_tminor is (2t  6)colorable for t = 7, 8, 9, in...
Show moreA graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Ktminor is (t  1)colorable. This conjecture has been proved true for t ? 6, but remains open for all t ? 7. For t = 7, it is not even yet known if a graph with no K7minor is 7colorable. We begin by showing that every graph with no K_tminor is (2t  6)colorable for t = 7, 8, 9, in the process giving a shorter and computerfree proof of the known results for t = 7, 8. We also show that this result extends to larger values of t if Mader's bound for the extremal function for Ktminors is true. Additionally, we show that any graph with no K8?minor is 9colorable, and any graph with no K8?minor is 8colorable. The Kempechain method developed for our proofs of the above results may be of independent interest. We also use Mader's HWege theorem to establish some sufficient conditions for a graph to contain a K8minor.Another motivation for my research is a wellknown conjecture of Erd?s and Lov(&)#225;sz from 1968, the DoubleCritical Graph Conjecture. A connected graph G is doublecritical if for all edges xy ? E(G), ?(G  x  y) = ?(G)  2. Erd?s and Lov(&)#225;sz conjectured that the only doublecritical tchromatic graph is the complete graph Kt. This conjecture has been show to be true for t ? 5 and remains open for t ? 6. It has further been shown that any noncomplete, doublecritical, tchromatic graph contains Kt as a minor for t ? 8. We give a shorter proof of this result for t = 7, a computerfree proof for t = 8, and extend the result to show that G contains a K9minor for all t ? 9. Finally, we show that the DoubleCritical Graph Conjecture is true for doublecritical graphs with chromatic number t ? 8 if such graphs are clawfree.
Show less  Date Issued
 2017
 Identifier
 CFE0006649, ucf:51227
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006649
 Title
 Reactive Rejuvenation of CMOS Logic Paths using Selfactivating Voltage Domains.
 Creator

Khoshavi Najafabadi, Navid, DeMara, Ronald, Yuan, JiannShiun, Song, Zixia, University of Central Florida
 Abstract / Description

Aggressive CMOS technology scaling trends exacerbate the agingrelated degradation of propagation delay and energy efficiency in nanoscale designs. Recently, powergating has been utilized as an effective lowpower design technique which has also been shown to alleviate some aging impacts. However, the use of MOSFETs to realize powergated designs will also encounter aginginduced degradations in the sleep transistors themselves which necessitates the exploration of design strategies to...
Show moreAggressive CMOS technology scaling trends exacerbate the agingrelated degradation of propagation delay and energy efficiency in nanoscale designs. Recently, powergating has been utilized as an effective lowpower design technique which has also been shown to alleviate some aging impacts. However, the use of MOSFETs to realize powergated designs will also encounter aginginduced degradations in the sleep transistors themselves which necessitates the exploration of design strategies to utilize powergating effectively to mitigate aging. In particular, Bias Temperature Instability (BTI) which occurs during activation of powergated voltage islands is investigated with respect to the placement of the sleep transistor in the header or footer as well as the impact of ungated input transitions on interfacial trapping. Results indicate the effectiveness of powergating on NBTI/PBTI phenomena and propose a preferred sleep transistor configuration for maximizing higher recovery. Furthermore, the aging effect can manifest itself as timing error on critical speedpaths of the circuit, if a large design guardband is not reserved. To mitigate circuit from BTIinduced aging, the Reactive Rejuvenation (RR) architectural approach is proposed which entails detection and recovery phases. The BTI impact on the critical and near critical paths performance is continuously examined through a lightweight logic circuit which asserts an error signal in the case of any timing violation in those paths. By observing the timing violation occurrence in the system, the timingsensitive portion of the circuit is recovered from BTI through switching computations to redundant agingcritical voltage domain. The proposed technique achieves aging mitigation and reduced energy consumption as compared to a baseline circuit. Thus, signi?cant voltage guardbands to meet the desired timing speci?cation are avoided result in energy savings during circuit operation.
Show less  Date Issued
 2016
 Identifier
 CFE0006339, ucf:51561
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006339
 Title
 Analysis of Employment and Earnings Using Varying Coefficient Models to Assess Success of Minorities and Women.
 Creator

Goedeker, Amanda, Pensky, Marianna, Song, Zixia, Swanson, Jason, Huang, HsinHsiung, University of Central Florida
 Abstract / Description

The objective of this thesis is to examine the success of minorities (black, and Hispanic/Latino employees) and women in the United States workforce, defining success by employment percentage and earnings. The goal of this thesis is to study the impact gender, race, passage of time, and national economic status reflected in gross domestic product have on the success of minorities and women. In particular, this thesis considers the impact of these factors in Science, Technology, Engineering...
Show moreThe objective of this thesis is to examine the success of minorities (black, and Hispanic/Latino employees) and women in the United States workforce, defining success by employment percentage and earnings. The goal of this thesis is to study the impact gender, race, passage of time, and national economic status reflected in gross domestic product have on the success of minorities and women. In particular, this thesis considers the impact of these factors in Science, Technology, Engineering and Math (STEM) industries. Varying coefficient models are utilized in the analysis of data sets for national employment percentages and earnings.
Show less  Date Issued
 2016
 Identifier
 CFE0006458, ucf:51425
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006458
 Title
 EnergyAware Data Movement In NonVolatile Memory Hierarchies.
 Creator

Khoshavi Najafabadi, Navid, DeMara, Ronald, Yuan, JiannShiun, Song, Zixia, University of Central Florida
 Abstract / Description

While technology scaling enables increased density for memory cells, the intrinsic high leakagepower of conventional CMOS technology and the demand for reduced energy consumption inspiresthe use of emerging technology alternatives such as eDRAM and NonVolatile Memory (NVM) including STTMRAM, PCM, and RRAM. The utilization of emerging technology in Last Level Cache (LLC) designs which occupies a signi?cant fraction of total die area in Chip Multi Processors (CMPs) introduces new dimensions...
Show moreWhile technology scaling enables increased density for memory cells, the intrinsic high leakagepower of conventional CMOS technology and the demand for reduced energy consumption inspiresthe use of emerging technology alternatives such as eDRAM and NonVolatile Memory (NVM) including STTMRAM, PCM, and RRAM. The utilization of emerging technology in Last Level Cache (LLC) designs which occupies a signi?cant fraction of total die area in Chip Multi Processors (CMPs) introduces new dimensions of vulnerability, energy consumption, and performance delivery. To be speci?c, a part of this research focuses on eDRAM Bit Upset Vulnerability Factor (BUVF) to assess vulnerable portion of the eDRAM refresh cycle where the critical charge varies depending on the write voltage, storage and bitline capacitance. This dissertation broaden the study on vulnerability assessment of LLC through investigating the impact of Process Variations (PV) on narrow resistive sensing margins in highdensity NVM arrays, including onchip cache and primary memory. Largelatency and powerhungry Sense Ampli?ers (SAs) have been adapted to combat PV in the past. Herein, a novel approach is proposed to leverage the PV in NVM arrays using SelfOrganized Subbank (SOS) design. SOS engages the preferred SA alternative based on the intrinsic asbuilt behavior of the resistive sensing timing margin to reduce the latency and power consumption while maintaining acceptable access time.On the other hand, this dissertation investigates a novel technique to prioritize the service to 1)Extensive Read Reused Accessed blocks of the LLC that are silently dropped from higher levelsof cache, and 2) the portion of the working set that may exhibit distant rereference interval in L2. In particular, we develop a lightweight Multilevel Access History Pro?ler to ef?ciently identifyERRA blocks through aggregating the LLC block addresses tagged with identical Most Signi?cantBits into a single entry. Experimental results indicate that the proposed technique can reduce theL2 read miss ratio by 51.7% on average across PARSEC and SPEC2006 workloads.In addition, this dissertation will broaden and apply advancements in theories of subspace recoveryto pioneer computationallyaware insitu operand reconstruction via the novel Logic In Interconnect (LI2) scheme. LI2 will be developed, validated, and re?ned both theoretically and experimentally to realize a radically different approach to postMoore's Law computing by leveraginglowrank matrices features offering data reconstruction instead of fetching data from main memory to reduce energy/latency cost per data movement. We propose LI2 enhancement to attain highperformance delivery in the postMoore's Law era through equipping the contemporary microarchitecture design with a customized memory controller which orchestrates the memory requestfor fetching lowrank matrices to customized Fine Grain Recon?gurable Accelerator (FGRA) forreconstruction while the other memory requests are serviced as before. The goal of LI2 is to conquer the high latency/energy required to traverse main memory arrays in the case of LLC miss, by using insitu construction of the requested data dealing with lowrank matrices. Thus, LI2 exchanges a high volume of data transfers with a novel lightweight reconstruction method under speci?c conditions using a crosslayer hardware/algorithm approach.
Show less  Date Issued
 2017
 Identifier
 CFE0006754, ucf:51859
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0006754
 Title
 Information Propagation Algorithms for Consensus Formation in Decentralized MultiAgent Systems.
 Creator

Hollander, Christopher, Wu, Annie, Shumaker, Randall, Wiegand, Rudolf, Turgut, Damla, Song, Zixia, University of Central Florida
 Abstract / Description

Consensus occurs within a multiagent system when every agent is in agreement about the value of some particular state. For example, the color of an LED, the position or magnitude of a vector, a rendezvous location, the most recent state of data within a database, or the identity of a leader are all states that agents might need to agree on in order to execute their tasking.The task of the decentralized consensus problem for multiagent systems is to design an algorithm that enables agents to...
Show moreConsensus occurs within a multiagent system when every agent is in agreement about the value of some particular state. For example, the color of an LED, the position or magnitude of a vector, a rendezvous location, the most recent state of data within a database, or the identity of a leader are all states that agents might need to agree on in order to execute their tasking.The task of the decentralized consensus problem for multiagent systems is to design an algorithm that enables agents to communicate and exchange information such that, in finite time, agents are able to form a consensus without the use of a centralized control mechanism. The primary goal of this research is to introduce and provide supporting evidence for Stochastic Local Observation/Gossip (SLOG) algorithms as a new class of solutions to the decentralized consensus problem for multiagent systems that lack a centralized controller, with the additional constraints that agents act asynchronously, information is discrete, and all consensus options are equally preferable to all agents. Examples of where these constraints might apply include the spread of social norms and conventions in artificial populations, rendezvous among a set of specific locations, and task assignment.This goal is achieved through a combination of theory and experimentation. Information propagation process and an information propagation algorithm are derived by unifying the general structure of multiple existing solutions to the decentralized consensus problem. They are then used to define two classes of algorithms that spread information across a network and solve the decentralized consensus problem: buffered gossip algorithms and local observation algorithms. Buffered gossip algorithms generalize the behavior of many pushbased solutions to the decentralized consensus problem. Local observation algorithms generalize the behavior of many pullbased solutions to the decentralized consensus problem. In the language of object oriented design, buffered gossip algorithms and local observation algorithms are abstract classes; information propagation processes are interfaces. SLOG algorithms combine the transmission mechanisms of buffered gossip algorithms and local observation algorithms into a single "hybrid" algorithm that is able to push and pull information within the local neighborhood. A common mathematical framework is constructed and used to determine the conditions under which each of these algorithms are guaranteed to produce a consensus, and thus solve the decentralized consensus problem. Finally, a series of simulation experiments are conducted to study the performance of SLOG algorithms. These experiments compare the average speed of consensus formation between buffered gossip algorithms, local observation algorithms, and SLOG algorithms over four distinct network topologies.Beyond the introduction of the SLOG algorithm, this research also contributes to the existing literature on the decentralized consensus problem by: specifying a theoretical framework that can be used to explore the consensus behavior of pushbased and pullbased information propagation algorithms; using this framework to define buffered gossip algorithms and local observation algorithms as generalizations for existing solutions to the decentralized consensus problem; highlighting the similarities between consensus algorithms within control theory and opinion dynamics within computational sociology, and showing how these research areas can be successfully combined to create new and powerful algorithms; and providing an empirical comparison between multiple information propagation algorithms.
Show less  Date Issued
 2015
 Identifier
 CFE0005629, ucf:50229
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0005629