Current Search: Song, Zixia (x)
View All Items
(1 - 19 of 19)
- Title
- ON SATURATION NUMBERS OF RAMSEY-MINIMAL GRAPHS.
- Creator
-
Davenport, Hunter M, Song, Zi-Xia, 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 edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every k-edge-coloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring 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 edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every k-edge-coloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring 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)-Ramsey-minimal 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 F-saturated 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
- GALLAI-RAMSEY NUMBERS FOR C7 WITH MULTIPLE COLORS.
- Creator
-
Bruce, Dylan, Song, Zi-Xia, 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 edge-colorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = ��� = Hk = H, if every k-edge-coloring 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 edge-colorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = ��� = Hk = H, if every k-edge-coloring 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, edge-colorings with no rainbow triangles. From this we define the Gallai-Ramsey 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 Gallai-Ramsey 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
-
Chip-firing 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 one-dimensional Riemann-Roch 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 moreChip-firing 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 one-dimensional Riemann-Roch 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 Ramsey-related 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 co-critical 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 co-critical graphs. Given an integer r \geq 1 and graphs G, H_1, . . . , H_r, we write G \rightarrow (H_1, . . . , H_r) if every r-coloring 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)-co-critical if G \nrightarrow (H_1, . . . , H_r), but G+uv \rightarrow (H_1, . . . , H_r) for every pair of non-adjacent 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)-co-critical 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_t-saturated 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 (t-1)(k-1)+1, if G is a (K_t,\mathcal{T}_k)-co-critical graph on n vertices, then e(G) \geq ((4t-9)/2+\lceil k/2 \rceil /2)n-c(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 k-coloring is a Gallai coloring that uses at most k colors. Given an integer k \geq 1 and graphs H_1, . . . , H_k, the Gallai-Ramsey number GR(H_1, . . . , H_k) is the least integer n such that every Gallai k-coloring 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 Edge-Colorings of Graphs.
- Creator
-
Foster, Austin, Song, Zixia, Reid, Michael, Brennan, Joseph, University of Central Florida
- Abstract / Description
-
A proper edge-coloring of a graph G by positive integers is called an interval edge-coloring 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 edge-colorings 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 edge-colorings to schedule parent-teacher conferences so...
Show moreA proper edge-coloring of a graph G by positive integers is called an interval edge-coloring 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 edge-colorings 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 edge-colorings to schedule parent-teacher 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 edge-coloring.A well-known result of Vizing states that for any simple graph $G$, $\chi'(G) \leq \Delta(G) + 1$, where $\chi'(G)$ and $\Delta(G)$ denote the edge-chromatic 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 edge-coloring must be of class 1, and thus every graph of class 2 does not have such a coloring.Finding an interval edge-coloring of a given graph is hard. In fact, it has been shown that determining whether a bipartite graph has an interval edge-coloring is NP-complete. In this thesis, we survey known results on interval edge-colorings 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 Stacked-Book 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 System-on-Chip (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 System-on-Chip (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 multi-level 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 higher-level control of these CFBs to build the final solution for the larger circuit at-hand. One such platform, Cypress PSoC-5LP 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 series-based 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
- Soft-Error Resilience Framework For Reliable and Energy-Efficient 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 energy-efficient nano-electronic devices across all aspects of daily life. In recent years, CMOS technology scaling has realized billions of transistors within large-scale VLSI chips to elevate performance. However, these advancements have also continually augmented the impact of Single-Event Transient (SET) and Single-Event Upset (SEU) occurrences which precipitate a range of Soft-Error...
Show moreThe revolution in chip manufacturing processes spanning five decades has proliferated high performance and energy-efficient nano-electronic devices across all aspects of daily life. In recent years, CMOS technology scaling has realized billions of transistors within large-scale VLSI chips to elevate performance. However, these advancements have also continually augmented the impact of Single-Event Transient (SET) and Single-Event Upset (SEU) occurrences which precipitate a range of Soft-Error (SE) dependability issues. Consequently, soft-error mitigation techniques have become essential to improve systems' reliability. Herein, first, we proposed optimized soft-error resilience designs to improve robustness of sub-micron computing systems. The proposed approaches were developed to deliver energy-efficiency 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 Near-Threshold Voltage (NTV) region on redundancy-based SE-mitigation approaches for High-Performance 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, spin-based devices have been widely used to design Non-Volatile (NV) elements such as NV latches and flip-flops, which can be leveraged in normally-off computing architectures for Internet-of-Things (IoT) and energy-harvesting-powered applications. Thus, in the last portion of this dissertation, we design and evaluate for soft-error resilience NV-latching 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 energy-efficiency and soft errors mitigation resiliency of larger-scale emerging NV latching circuits within iso-energy constraints. In summary, addressing these reliability concerns is paramount to successful deployment of future reliable and energy-efficient CMOS logic and spintronic memory architectures with deeply-scaled devices operating at low-voltages.
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 (L-systems) to generate fault trees that are reproducible, capable of producing fault trees with similar properties to real-world 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 L-systems, 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, Sheau-Dong, 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, Quintana-Ascencio, 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 disease-free 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 non-direct 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 country-wide network structures. New global stability results are established for the disease-free equilibrium and endemic equilibrium, the latter utilizing a graph theoretic approach and Lyapunov functions. Asymptotic profiles are determined for both the disease-free 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 rural-urban 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 Gallai-Ramsey 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 far-reaching 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 far-reaching 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 Gallai-colorings. A Gallai-coloring of a complete graph is an edge-coloring such that no triangle is colored with three distinct colors. Given a graph H and an integer k at least 1, the Gallai-Ramsey number, denoted GR_k(H), is the least positive integer n such that every Gallai-coloring of K_n with at most k colors contains a monochromatic copy of H. It turns out that GR_k(H) is more well-behaved 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 Kt-minor 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 K7-minor is 7-colorable. We begin by showing that every graph with no K_t-minor 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 Kt-minor 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 K7-minor is 7-colorable. We begin by showing that every graph with no K_t-minor is (2t - 6)-colorable for t = 7, 8, 9, in the process giving a shorter and computer-free 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 Kt-minors is true. Additionally, we show that any graph with no K8?-minor is 9-colorable, and any graph with no K8?-minor is 8-colorable. The Kempe-chain method developed for our proofs of the above results may be of independent interest. We also use Mader's H-Wege theorem to establish some sufficient conditions for a graph to contain a K8-minor.Another motivation for my research is a well-known conjecture of Erd?s and Lov(&)#225;sz from 1968, the Double-Critical Graph Conjecture. A connected graph G is double-critical if for all edges xy ? E(G), ?(G - x - y) = ?(G) - 2. Erd?s and Lov(&)#225;sz conjectured that the only double-critical t-chromatic 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 non-complete, double-critical, t-chromatic graph contains Kt as a minor for t ? 8. We give a shorter proof of this result for t = 7, a computer-free proof for t = 8, and extend the result to show that G contains a K9-minor for all t ? 9. Finally, we show that the Double-Critical Graph Conjecture is true for double-critical graphs with chromatic number t ? 8 if such graphs are claw-free.
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 Self-activating Voltage Domains.
- Creator
-
Khoshavi Najafabadi, Navid, DeMara, Ronald, Yuan, Jiann-Shiun, Song, Zixia, University of Central Florida
- Abstract / Description
-
Aggressive CMOS technology scaling trends exacerbate the aging-related degradation of propagation delay and energy efficiency in nanoscale designs. Recently, power-gating has been utilized as an effective low-power design technique which has also been shown to alleviate some aging impacts. However, the use of MOSFETs to realize power-gated designs will also encounter aging-induced degradations in the sleep transistors themselves which necessitates the exploration of design strategies to...
Show moreAggressive CMOS technology scaling trends exacerbate the aging-related degradation of propagation delay and energy efficiency in nanoscale designs. Recently, power-gating has been utilized as an effective low-power design technique which has also been shown to alleviate some aging impacts. However, the use of MOSFETs to realize power-gated designs will also encounter aging-induced degradations in the sleep transistors themselves which necessitates the exploration of design strategies to utilize power-gating effectively to mitigate aging. In particular, Bias Temperature Instability (BTI) which occurs during activation of power-gated 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 power-gating 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 speed-paths of the circuit, if a large design guardband is not reserved. To mitigate circuit from BTI-induced 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 timing-sensitive portion of the circuit is recovered from BTI through switching computations to redundant aging-critical 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, Hsin-Hsiung, 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
- Energy-Aware Data Movement In Non-Volatile Memory Hierarchies.
- Creator
-
Khoshavi Najafabadi, Navid, DeMara, Ronald, Yuan, Jiann-Shiun, 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 Non-Volatile Memory (NVM) including STT-MRAM, 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 Non-Volatile Memory (NVM) including STT-MRAM, 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 bit-line 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 high-density NVM arrays, including on-chip cache and primary memory. Large-latency and power-hungry 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 Self-Organized Sub-bank (SOS) design. SOS engages the preferred SA alternative based on the intrinsic as-built 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 re-reference interval in L2. In particular, we develop a lightweight Multi-level 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 computationally-aware in-situ operand reconstruction via the novel Logic In Intercon-nect (LI2) scheme. LI2 will be developed, validated, and re?ned both theoretically and experimentally to realize a radically different approach to post-Moore's Law computing by leveraginglow-rank 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 post-Moore's Law era through equipping the contemporary micro-architecture design with a customized memory controller which orchestrates the memory requestfor fetching low-rank 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 in-situ construction of the requested data dealing with low-rank matrices. Thus, LI2 exchanges a high volume of data transfers with a novel lightweight reconstruction method under speci?c conditions using a cross-layer 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 Multi-Agent Systems.
- Creator
-
Hollander, Christopher, Wu, Annie, Shumaker, Randall, Wiegand, Rudolf, Turgut, Damla, Song, Zixia, University of Central Florida
- Abstract / Description
-
Consensus occurs within a multi-agent 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 multi-agent systems is to design an algorithm that enables agents to...
Show moreConsensus occurs within a multi-agent 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 multi-agent 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 multi-agent 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 push-based solutions to the decentralized consensus problem. Local observation algorithms generalize the behavior of many pull-based 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 push-based and pull-based 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
