Dept. of Mathematics
http://hdl.handle.net/2142/16339
Tue, 21 Nov 2017 10:18:33 GMT2017-11-21T10:18:33ZSome problems in polynomial interpolation and topological complexity
http://hdl.handle.net/2142/97758
Some problems in polynomial interpolation and topological complexity
Fieldsteel, Nathan Mulvey
This thesis is comprised of two projects in applied computational mathematics. In Chapter 1, we discuss the geometry and combinatorics of geometrically characterized sets. These are finite sets of n+d choose n points in R^d which impose independent conditions on polynomials of degree n, and which have Lagrange polynomials of a special form. These sets were introduced by Chung and Yao in a 1977 paper in the SIAM Journal of Numerical Analysis in the context of polynomial interpolation. There are several conjectures on the nature and geometric structure of these sets. We investigate the geometry and combinatorics of GC sets for d at least 2, and prove they are closely related to simplicial complexes which are Cohen-Macaulay and have a Cohen-Macaulay dual.
In Chapter 2, we will discuss the motion planning problem in complex hyperplane arrangement complements. The difficulty of constructing a minimally discontinuous motion planning algorithm for a topological space X is measured by an integer invariant of X called topological complexity or TC(X). Yuzvinsky developed a combinatorial criterion for hyperplane arrangement complements which guarantees that their topological complexity is as large as possible. Applying this criterion in the special case when the arrangement is graphic, we simplify the criterion to an inequality on the edge density of the graph which is closely related to the inequality in the arboricity theorem of Nash-Williams.
Approximation theory; Polynomial interpolation; Motion planning
Fri, 21 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/977582017-04-21T00:00:00ZFieldsteel, Nathan MulveyViewing 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, TayyabExtremal problems on counting combinatorial structures
http://hdl.handle.net/2142/97401
Extremal problems on counting combinatorial structures
Petrickova, Sarka
The fast developing field of extremal combinatorics provides a diverse spectrum of powerful tools with many applications to economics, computer science, and optimization theory. In this thesis, we focus on counting and coloring problems in this field.
The complete balanced bipartite graph on $n$ vertices has $\floor{n^2/4}$ edges. Since all of its subgraphs are triangle-free, the number of (labeled) triangle-free graphs on $n$ vertices is at least $2^{\floor{n^2/4}}$. This was shown to be the correct order of magnitude in a celebrated paper Erd\H{o}s, Kleitman, and Rothschild from 1976, where the authors furthermore proved that almost all triangle-free graphs are bipartite. In Chapters 2 and 3 we study analogous problems for triangle-free graphs that are maximal with respect to inclusion.
In Chapter 2, we solve the following problem of Paul Erd\H{o}s: Determine or estimate the number of maximal triangle-free graphs on $n$ vertices. We show that the number of maximal triangle-free graphs is at most $2^{n^2/8+o(n^2)}$, which matches the previously known lower bound. Our proof uses among other tools the Ruzsa-Szemer\'{e}di Triangle Removal Lemma and recent results on characterizing of the structure of independent sets in hypergraphs. This is a joint work with J\'{o}zsef Balogh.
In Chapter 3, we investigate the structure of maximal triangle-free graphs. We prove that almost all maximal triangle-free graphs admit a vertex partition $(X, Y)$ such that $G[X]$ is a perfect matching and $Y$ is an independent set. Our proof uses the Ruzsa-Szemer\'{e}di Removal Lemma, the Erd\H{o}s-Simonovits stability theorem, and recent results of Balogh-Morris-Samotij and Saxton-Thomason on the characterization of the structure of independent sets in hypergraphs. The proof also relies on a new bound on the number of maximal independent sets in triangle-free graphs with many vertex-disjoint $P_3$'s, which is of independent interest. This is a joint work with J\'{o}zsef Balogh, Hong Liu, and Maryam Sharifzadeh.
In Chapte 4, we seek families in posets with the smallest number of comparable pairs. Given a poset $P$, a family $\F\subseteq P$ is \emph{centered} if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the \emph{centeredness property} if for any $M$, among all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\{0,1\}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\{0,1,\ldots,k\}^n$ also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\geq 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of $\mathbb{F}_q^n$ has the centeredness property. Several open problems are also given. This is a joint result with J\'{o}zsef Balogh and Adam Zsolt Wagner.
In Chapter 5, we consider a graph coloring problem. Kim and Park have found an infinite family of graphs whose squares are not chromatic-choosable. Xuding Zhu asked whether there is some $k$ such that all $k$-th power graphs are chromatic-choosable. We answer this question in the negative: we show that there is a positive constant $c$ such that for any $k$ there is a family of graphs $G$ with $\chi(G^k)$ unbounded and $\chi_{\ell}(G^k)\geq c \chi(G^k) \log \chi(G^k)$. We also provide an upper bound, $\chi_{\ell}(G^k)<\chi(G^k)^3$ for $k>1$. This is a joint work with Nicholas Kosar, Benjamin Reiniger, and Elyse Yeager.
Extremal; Counting; Triangle-free; Maximal; Structure; Poset; Comparable pair; Chromatic number; Choosability
Wed, 19 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/974012017-04-19T00:00:00ZPetrickova, SarkaGromov boundaries of complexes associated to surfaces
http://hdl.handle.net/2142/97398
Gromov boundaries of complexes associated to surfaces
Pho-on, Witsarut
In 1996, Masur and Minsky showed that the curve graph is hyperbolic. Recently, Hensel, Przytycki, and Webb proved a stronger result which was the uniform hyperbolicity of the curve graph, and they also gave the first proof of the uniform hyperbolicity of the arc graph using unicorn arcs. For closed surfaces, their proof is indirect, but Przytycki and Sisto gave a more direct proof of hyperbolicity in that case using bicorn curves.
In this dissertation, we extend the notion of unicorn arcs and bicorn curves between two arcs or curves to the case where we replace one arc or curve with a geodesic asymptotic to a lamination or a leaf of the lamination. Using these paths, we give new proofs of the results of Klarreich and Schleimer identifying the Gromov boundaries of the curve graph and the arc graph, respectively, as spaces of laminations.
Gromov boundary; Curve complex; Arc complex; Lamination; Surface; Unicorn curve; Bicorn curve
Wed, 19 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/973982017-04-19T00:00:00ZPho-on, WitsarutStability thresholds for signed Laplacians on locally-connected networks
http://hdl.handle.net/2142/97363
Stability thresholds for signed Laplacians on locally-connected networks
Cong, Lin
In this work we are interested in the stability bifurcations of the dynamical systems defined on graphs, and we use signed graph Laplacians as our tool. In chapter 1, we give the formal definition of the Laplacian matrix for a graph, and point out several references on it. In chapter 2, we give the main result from one of the references, along with other preliminaries we need for our results. In chapter 3, we give our first main result -- finding the stable point for the Laplacians of one family of graphs, namely $\mathcal{C}_n^2$. In chapter 4, we extend the previous definition and question to $\mathcal{C}_n^{(k)}$, and we give the exact result for $k=3$, along with a procedure to find the answer for general $k>3$. We then give several conjectures about this topic, which are supported by numerical experiments.
Graph Laplacian; Dynamics on graphs
Wed, 19 Apr 2017 00:00:00 GMThttp://hdl.handle.net/2142/973632017-04-19T00:00:00ZCong, LinSmoothing 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 Nicholas