Dissertations and Theses - Mathematics
http://hdl.handle.net/2142/16340
Tue, 24 Oct 2017 03:56:49 GMT2017-10-24T03:56:49ZViewing extremal and structural problems through a probabilistic lens
http://hdl.handle.net/2142/97669
Viewing extremal and structural problems through a probabilistic lens
Delcourt, Michelle Jeannette
This thesis focuses on using techniques from probability to solve problems from extremal and structural combinatorics. The main problem in Chapter 2 is determining the typical structure of $t$-intersecting families in various settings and enumerating such systems. The analogous sparse random versions of our extremal results are also obtained. The proofs follow the same general framework, in each case using a version of the Bollobás Set-Pairs Inequality to bound the number of maximal intersecting families, which then can be combined with known stability theorems. Following this framework from joint work with Balogh, Das, Liu, and Sharifzadeh, similar results for permutations, uniform hypergraphs, and vector spaces are obtained.
In 2006, Barát and Thomassen conjectured that the edges of every planar 4-edge-connected 4-regular graph can be decomposed into disjoint copies of $S_3$, the star with three leaves. Shortly afterward, Lai constructed a counterexample to this conjecture. Following joint work with Postle, in Chapter 3 using the Small Subgraph Conditioning Method of Robinson and Wormald, we find that a random 4-regular graph has an $S_3$-decomposition asymptotically almost surely, provided we have the obvious necessary divisibility conditions.
In 1988, Thomassen showed that if $G$ is at least $(2k-1)$-edge-connected then $G$ has a spanning, bipartite $k$-connected subgraph. In 1989, Thomassen asked whether a similar phenomenon holds for vertex-connectivity; more precisely: is there an integer-valued function $f(k)$ such that every $f(k)$-connected graph admits a spanning, bipartite $k$-connected subgraph? In Chapter 4, as in joint work with Ferber, we show that every $10^{10}k^3 \log n$-connected graph admits a spanning, bipartite $k$-connected subgraph.
Small subgraph conditioning method; Random regular graph; Intersecting families; Star decomposition; Structural graph theory; Extremal combinatorcs
Mon, 27 Mar 2017 00:00:00 GMThttp://hdl.handle.net/2142/976692017-03-27T00:00:00ZDelcourt, Michelle JeannetteApplications of Stein's method and large deviations principle's in mean-field O(N) models
http://hdl.handle.net/2142/97544
Applications of Stein's method and large deviations principle's in mean-field O(N) models
Nawaz, Tayyab
In the first part of this thesis, we will discuss the classical XY model on complete graph in the mean-field (infinite-vertex) limit. Using theory of large deviations and Stein's method, in particular, Cramér and Sanov-type results, we present a number of results coming from the limit theorems with rates of convergence, and phase transition behavior for classical XY model.
In the second part, we will generalize our results to mean-field classical $N$-vector models, for integers $N \ge 2$. We will use the theory of large deviations and Stein's method to study the total spin and its typical behavior, specifically obtaining non-normal limit theorems at the critical temperatures and central limit theorems away from criticality. Some of the important special cases of these models are the XY ($N=2$) model of superconductors, the Heisenberg ($N=3$) model (previously studied in [KM13] but with a correction to the critical distribution here), and the Toy ($N=4$) model of the Higgs sector in particle physics.
Mean-field; Rate function; Total spin; Limit theorem; Phase transition
Fri, 07 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/975442017-04-07T00:00:00ZNawaz, TayyabSmoothing properties of certain dispersive nonlinear partial differential equations
http://hdl.handle.net/2142/97315
Smoothing properties of certain dispersive nonlinear partial differential equations
Compaan, Erin Leigh
This thesis is primarily concerned with the smoothing properties of dispersive equations and systems. Smoothing in this context means that the nonlinear part of the solution flow is of higher regularity than the initial data. We establish this property, and some of its consequences, for several equations.
The first part of the thesis studies a periodic coupled Korteweg-de Vries (KdV) system. This system, known as the Majda-Biello system, displays an interesting dependancy on the coupling coefficient α linking the two KdV equations. Our main result is that the nonlinear part of the evolution resides in a smoother space for almost every choice of α. The smoothing index depends on number-theoretic properties of α, which control the behavior of the resonant sets. We then consider the forced and damped version of the system and obtain similar smoothing estimates. These estimates are used to show the existence of a global attractor in the energy space. We also use a modified energy functional to show that when the damping is large, the attractor is trivial.
The next chapter studies the Zakharov and related Klein-Gordon-Schrödinger (KGS) systems on Euclidean spaces. Again, the main result is that the nonlinear part of the solution is smoother than the initial data. The proof relies on a new bilinear Bourgain-space estimate, which is proved using delicate dyadic and angular decompositions of the frequency domain. As an application, we give a simplified proof of the existence of global attractors for the KGS flow in the energy space for dimensions two and three. We also use smoothing in conjunction with a high-low decomposition to show global well-posedness of the KGS evolution on R4 below the energy space for sufficiently small initial data.
In the final portion of the thesis we consider well-posedness and regularity properties of the “good” Boussinesq equation on the half line. We obtain local existence, uniqueness and continuous dependence on initial data in low-regularity spaces. We also establish a smoothing result, obtaining up to half derivative smoothing of the nonlinear term. The results are sharp within the framework of the restricted norm method that we use and match known results on the full line.
Dispersive partial differential equations; Well-posedness; Smoothing; Zakharov; Klein-Gordon Schrödinger; Majda-Biello; Boussinesq equation
Wed, 12 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/973152017-04-12T00:00:00ZCompaan, Erin LeighCluster algebras and discrete integrable systems
http://hdl.handle.net/2142/97314
Cluster algebras and discrete integrable systems
Vichitkunakorn, Panupong
This dissertation presents connections between cluster algebras and discrete integrable systems, especially T-systems and their specializations/generalizations.
We give connections between the T-system or the octahedron relation, and the pentagram map and its various generalizations. A solution to the T-system with quasi-periodic boundary conditions gives rise to a solution to a higher pentagram map. In order to obtain all the solutions of higher pentagram map, we define T-systems with principal coefficients from cluster algebra aspect. Combinatorial solutions of the T-systems with principal coefficients with respect to any valid initial condition are shown to be partition functions of perfect matchings, non-intersecting paths and networks. This also provides a solution to other systems with various choices of coefficients on T-systems including Speyer's octahedron recurrence (Speyer 2007), generalized lambda-determinants (Di Francesco 2013) and (higher) pentagram maps (Schwartz 1992, Ovsienko et al. 2010, Glick 2011, Gekhtman et al. 2016).
We study a discrete dynamic on weighted bipartite graphs on a torus, analogous to dimer integrable systems of Goncharov and Kenyon 2013. We show that all Hamiltonians, partition functions of all weighted perfect matchings with a common homology class, are invariant under a move on the weighted graph. This move coincides with a cluster mutation, analog to Y-seed mutation in dimer integrable systems. Q-systems are reductions of T-systems by forgetting one of the parameters. We construct graphs for Q-systems of type A and B and show that the Hamiltonians are conserved quantities of the systems. The conserved quantities can be written as partition functions of hard particles on a certain graph. For type A, they Poisson commute under a nondegenerate Poisson bracket.
Cluster algebras; Discrete integrable systems
Thu, 13 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/973142017-04-13T00:00:00ZVichitkunakorn, PanupongApproximating rotation algebras and inclusions of C*-algebras
http://hdl.handle.net/2142/97307
Approximating rotation algebras and inclusions of C*-algebras
Rezvani, Sepideh
In the first part of this thesis, we will follow Kirchberg’s categorical perspective to establish new notions of WEP and QWEP relative to a C∗-algebra, and develop similar properties as in the classical WEP and QWEP. Also we will show some examples of relative WEP and QWEP to illustrate the relations with the classical cases.
The focus of the second part of this thesis is the approximation of rotation algebras in the quantum Gromov–Hausdorff distance. We introduce the completely bounded quantum Gromov–Hausdorff distance and show that for even dimensions, the higher dimensional rotation algebras can be approximated by matrix algebras in this sense. Finally, we show that for even dimensions, matrix algebras converge to the rotation algebras in the strongest form of Gromov–Hausdorff distance, namely in the sense of Latrémolière’s Gromov–Hausdorff propinquity.
C*-algebras; Weak expectation property (WEP); Quotient weak expectation property (QWEP); A-WEP; A-QWEP; Relatively weak injectivity; Order-unit space; Noncommutative tori; Compact quantum metric space; Conditionally negative length function; Heat semigroup; Poisson semigroup; Rotation algebra; Continuous field of compact quantum metric spaces; Gromov–Hausdorff distance; Completely bounded quantum Gromov–Hausdorff distance; Gromov–Hausdorff propinquity
Thu, 06 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/973072017-04-06T00:00:00ZRezvani, SepidehApplications of dynamical systems to Farey sequences and continued fractions
http://hdl.handle.net/2142/97300
Applications of dynamical systems to Farey sequences and continued fractions
Heersink, Byron Nicholas
This thesis explores three main topics in the application of ergodic theory and dynamical systems to equidistribution and spacing statistics in number theory. The first is concerned with utilizing the ergodic properties of the horocycle flow in SL(2,R) to study the spacing statistics of Farey fractions. For a given finite index subgroup H ⊆ SL(2,Z), we use a process developed by Fisher and Schmidt to lift a cross section of the horocycle flow on SL(2,R)/SL(2,Z) found by Athreya and Cheung to the finite cover SL(2,R)/H of SL(2,R)/SL(2,Z). We then use the properties of this section to prove the existence of the limiting gap distribution of various subsets of Farey fractions. Additionally, to each of these subsets of fractions, we extend solutions by Xiong and Zaharescu, and independently Boca, to a Diophantine approximation problem of Erdős, Szüsz, and Turán.
The latter two topics of this thesis establish properties of the Farey map F by analyzing the transfer operators of F and the Gauss map G, well known maps of the unit interval relating to continued fractions. We first prove an equidistribution result for the periodic points of the Farey map using a connection between continued fractions and the geodesic flow in SL(2,Z)\SL(2,R) illuminated by Series. Specifically, we expand a cross section of the geodesic flow given by Series to produce another section whose first return map under the geodesic flow is a double cover of the natural extension of the Farey map. We then use this cross section to extend the correspondence between the closed geodesics on the modular surface and the periodic points of G to include the periodic points of F. Then, analogous to the work of Pollicott, we find the limiting distribution of the periodic points of F when they are ordered according to the length of their corresponding closed geodesics through the analysis of the transfer operator of G.
Lastly, we provide effective asymptotic results for the equidistribution of sets of the form F⁻ⁿ([α,β]), where [α,β] ⊆ (0,1], and, as a corollary, certain weighted subsets of the Stern-Brocot sequence. To do so, we employ mostly basic properties of the transfer operator of the Farey map and an application of Freud's effective version of Karamata's Tauberian theorem. This strengthens previous work of Kesseböhmer and Stratmann, who first established the equidistribution results utilizing infinite ergodic theory.
Equidistribution; Gap distribution; Farey fractions; Horocycle flow; Geodesic flow; Farey map; Continued fractions; Transfer operator
Wed, 05 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/973002017-04-05T00:00:00ZHeersink, Byron NicholasSufficient conditions for the existence of specified subgraphs in graphs
http://hdl.handle.net/2142/97294
Sufficient conditions for the existence of specified subgraphs in graphs
McConvey, Andrew Ross
A classical problem in combinatorics is, given graphs G and H, to determine if H is a subgraph of G. It is usually computationally complex to determine if H is a subgraph of G. Therefore, we often prove conditions that are sufficient to guarantee that a graph G contains H as a subgraph.
In Chapter 2, we consider a theorem of Dirac and Erdős from 1963 that considers when a graph contains many disjoint cycles. Generalizing the seminal result of Corrádi and Hajnal, they prove that if a graph G contains many more vertices of degree at least 2k than vertices of degree at most 2k-2, then G contains k vertex-disjoint cycles. We strengthen their result, proving that if G contains 3k more vertices of high degree than vertices of low degree, then G contains k disjoint cycles and that this bound is sharp. Moreover, when G has many vertices, G is planar, or G contains few triangles, this value can be improved to 2k. The value 2k is the best possible, as shown by examples of Dirac and Erdős.
In Chapter 3, we rephrase the problem of subgraphs in the language of graph packing. Two graphs G and G' pack if G is a subgraph of the complement of G' or, equivalently, if G' is a subgraph of the complement of G. Graph packing is a restatement of the subgraph problem that does not require one graph to be specified as the underlying graph and the other as the subgraph. Theorems of Sauer and Spencer and, independently, Bollobás and Eldridge prove that if G and G' together have few edges or if the maximum degree of G and the maximum degree of G' are small, then G and G' pack. We explore two results that combine bounds on the maximum degrees and number of edges in G and G'.
Recently, Alon and Yuster proved that if G and G' are graphs on n vertices such that G has a bounded number of edges and G' has bounded degree, then G and G' pack. We characterize the pairs of graphs for which their theorem is sharp. In particular, we show that for sufficiently large n, if the vertex of maximum degree in G can be appropriately placed, then G can contain more edges and still pack with G'.
We also consider a conjecture of Żak that states if the sum of the number of edges in G, the number of edges in G', and the degree of the largest vertex in G or G' is bounded above by 3n - 7, then G and G' pack. We prove that, up to an additive constant, this conjecture is correct. Using the notion of list packing, we prove that there is a constant C such that if the same sum is bounded above by 3n - C, then G and G' pack. This improves a theorem of Żak from 2014.
Finally, we consider a generalization of finding a matching in a graph. The stable marriage problem was introduced by Gale and Shapley in 1962 and the generalization to multiple dimensions was first mentioned by Knuth in 1976. We consider a generalization of the Stable Marriage problem with s-dimensions and purely cyclic preferences (cyclic s-DSM). In 2004, Boros et al. showed that if there are at most s agents of each gender, then every instance of cyclic s-DSM admits a stable matching. In 2006, Eriksson et al. showed this is also true when s = 3 and there are 4 agents of each gender. We extend their result, proving that when there are s+1 agents of each gender, each instance of s-DSM admits a stable matching. We also provide a minimal example of an instance of s-DSM which admits no strongly stable matching.
Combinatorics; Graph theory; Extremal graph theory; Cycles; Disjoint cycles; Graph packing; Turán number; List packing; Matching; Stable matching; Stable marriage
Wed, 05 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/972942017-04-05T00:00:00ZMcConvey, Andrew RossSyzygies and implicitization of tensor product surfaces
http://hdl.handle.net/2142/97285
Syzygies and implicitization of tensor product surfaces
Duarte Gelvez, Eliana Maria
A tensor product surface is the closure of the image of a rational map λ : P1 ×P1-->P3. These surfaces arise in geometric modeling and in this context it is useful to know the implicit equation of λ in P3. Currently, syzygies and Rees algebras provide the fastest and most versatile method to find implicit equations of parameterized surfaces. Knowing the structure of the syzygies of the polynomials that define the map λ allows us to formulate faster algorithms for implicitization of these surfaces and also to understand their singularities. We show that for tensor product surfaces without basepoints, the existence of a linear syzygy imposes strong conditions on the structure of the syzygies that determine the implicit equation. For tensor product surfaces with basepoints we show that the syzygies that determine the implicit equation of λ are closely related to the geometry of the set of points at which λ is undefined.
Implicitization; Syzygy; Rees algebras; Basepoints; Tensor product surface; Smooth quadric
Mon, 10 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/972852017-04-10T00:00:00ZDuarte Gelvez, Eliana MariaQuasi-elliptic cohomology
http://hdl.handle.net/2142/97268
Quasi-elliptic cohomology
Huan, Zhen
We introduce and study quasi-elliptic cohomology, a theory related to Tate K-theory but built over the ring $\mathbb{Z}[q^{\pm}]$. In Chapter 2 we build an orbifold version of the theory, inspired by Devoto's equivariant Tate K-theory. In Chapter 3 we construct power operation in the orbifold theory, and prove a version of Strickland's theorem on symmetric equivariant cohomology modulo transfer ideals. In Chapter 4 we construct representing spectra but show that they cannot assemble into a global spectrum in the usual sense. In Chapter 6 we construct a new global homotopy theory containing the classical theory. In Chapter 7 we show quasi-elliptic cohomology is a global theory in the new category.
Quasi-elliptic cohomology; Tate K-theory; Power operation; Spectra; Global homotopy theory
Fri, 21 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/972682017-04-21T00:00:00ZHuan, ZhenCompactness of the space of marked groups and examples of L2-Betti numbers of simple groups
http://hdl.handle.net/2142/97234
Compactness of the space of marked groups and examples of L2-Betti numbers of simple groups
Zhu, Kejia
This paper contains two parts. The first part will introduce Gn space and will show its compact. I will give two proofs for the compactness, the first one is due to Rostislav Grigorchuk [1], which refers to geometrical group theory and after the first proof I will give a more topological proof. In the second part, our goal is to prove a theorem by Denis Osin and Andreas Thom [2]: for every integer n ≥ 2 and every ε ≥ 0 there exists an infinite simple group Q generated by n elements such that β(2)(Q) ≥ n − 1 − ε. As a corollary, we can prove that for every positive integer n 1 there exists a simple group Q with d(Q) = n. In the proof of this theorem, I added the details to the original proof. Moreover, I found and fixed an error of the original proof in [2], although it doesn’t affect the final result.
Geometric group theory; Topology
Tue, 28 Mar 2017 00:00:00 GMThttp://hdl.handle.net/2142/972342017-03-28T00:00:00ZZhu, Kejia