Seminars archive

This dissertation is about arithmetic information encoded by analytic characteristics (such as Fourier coefficients) of classical modular forms and a real-analytic generalization of modular forms called harmonic Maass forms. For example, I use the theory of harmonic Maass forms to extend and refine a theorem of Wiles on class number divisibility. I also prove asymptotic bounds for Rankin-Selberg shifted convolution L-functions in shift aspect. In partition theory, I use the circle method to describe the expected distribution of parts of integer partitions over residue classes, and I use effective estimates for partition functions to obtain simple formulas for functions arising in group theory.

Both results of this dissertation involve finding unexpected connections between the classical theory of monstrous moonshine and the newer umbral moonshine. In our first result, we use generalized Borcherds products to associate to each pure A-type Niemeier lattice a conjugacy class g of the monster group and give rise to identities relating dimensions of representations from umbral moonshine to values of McKay-Thompson series. Our second result focuses on the Mathieu group M23. While it inherits a moonshine from being a subgroup of M24, we find a new and simpler moonshine for M23 such that the graded traces are, up to constant terms, identical to the monstrous moonshine Hauptmoduln.

The next generation of computational science applications will require numerical solvers that are both reliable and capable of high performance on projected exascale platforms. In order to meet these goals, solvers must be resilient to soft and hard system failures, provide high concurrency on heterogeneous hardware configurations, and retain numerical accuracy and efficiency. This work focuses on the solution of large sparse systems of linear equations, for example of the kind arising from the discretization of partial differential equations (PDEs). Specifically, the goal is to investigate alternative approaches to existing solvers (such as preconditioned Krylov subspace or multigrid methods). To do so, we consider stochastic and deterministic accelerations of relaxation schemes. On the one hand, starting from a convergent splitting of the coefficient matrix, we analyze various types of Monte Carlo acceleration schemes applied to the original preconditioned Richardson (stationary) iteration. These methods are expected to have considerable potential for resiliency to faults when implemented on massively parallel machines. In this framework, we have identified classes of problems and preconditioners that guarantee convergence. On the other hand, we consider Anderson-type accelerations to increase efficiency and improve the convergence rate with respect to one level fixed point schemes. In particular, we focus on a recently introduced method called Alternating Anderson-Richardson (AAR). We provide theoretical results to explain the advantages of AAR over other similar schemes presented in literature and we show numerical results where AAR is competitive against restarted versions of the generalized minimum residual method (GMRES) for problems of different nature and different preconditioning techniques.

The McKay Correspondence classifies finite subgroups of the rotation group of 3-space via graphs. In this talk we explore a quantum version of this correspondence. Specifically, we will cover the needed background on category theory, vertex operator algebras, and quantum groups to explain a powerful technique used by Kirillov and Ostrik to develop a quantum analog to the McKay correspondence.

Let $E$ be an elliptic curve defined over a finite field $\mathbb{F}_q$. Hasse’s theorem says that $\#E(\mathbb{F}_q) = q + 1 - t_E$ where $|t_E| \le 2\sqrt{q}$. Deuring uses the theory of complex multiplication to express the number of isomorphism classes of curves with a fixed value of $t_E$ in terms of sums of ideal class numbers of orders in quadratic imaginary fields. Birch shows that as $q$ goes to infinity the normalized values of these point counts converge to the Sato-Tate distribution by applying the Selberg Trace Formula. \\ In this talk we discuss finer counting questions for elliptic curves over $\mathbb{F}_q$. For example, what is the probability that the number of rational points is divisible by $5$? What is the probability that the group of rational points is cyclic? If we choose a curve at random, and then pick a random point on that curve, what is the probability that the order of the point is odd? We study the distribution of rational point counts for elliptic curves containing a specified subgroup, giving exact formulas for moments in terms of traces of Hecke operators. We will also discuss some open problems. This is joint with work Ian Petrow (ETH Zurich).

A long-standing conjecture of Erd\H{o}s states that any n-vertex triangle-free graph can be made bipartite by deleting at most $n^2/25$ edges. In this talk, we study how many edges need to be removed from an H-free graph for a general graph H. By generalizing a result of Sudakov for 4-colorable graphs H, we show that if H is 6-colorable then G can be made bipartite by deleting at most $4n^2/25+O(n)$ edges. In the case of $H=K_6$, we actually prove the exact bound $4n^2/25$ and show that this amount is needed only in the case G is a complete 5-partite graph with balanced parts. As one of the steps in the proof, we use a strengthening of a result of $F\ddot{u}redi$ on stable version of $Tur\acute{a}n's$ theorem. This is a joint work with P. Hu, B. $Lidick\acute{y}$, T. Martins-Lopez and S. Norin.

A spectrum of applications arising from Statistics, Machine Learning, Network Analysis require computation of bilinear forms $x^Tf(A)y$, where $A$ is a diagonalizable matrix and $x$, $y$ are given vectors. In this work we are interested in efficiently computing bilinear forms primarily due to their importance in several contexts. For large scale computation problems it is preferable to achieve approximations of bilinear forms without exploiting the whole matrix function. For this purpose an extrapolation procedure has been developed, attaining the approximation of bilinear forms with one, two or three term estimates in a complexity of square order. The extrapolation procedure gives us the flexibility to define the moments of a matrix $A$ either directly or through the polarization identity. The presented approach is characterized by easy applicable formulae of low complexity that can be implemented in vectorized form.

Hamiltonian paths, which are a special kind of spanning tree, have long been of interest in graph theory and are notoriously hard to compute. One notable feature of a Hamiltonian path is that all its vertices have degree two in the path. In a tree, we call vertices of degree at least three \emph{branch vertices}. If a connected graph has no Hamiltonian path, we can still look for spanning trees that come "close," in particular by having few branch vertices (since a Hamiltonian path would have none). \bigskip A conjecture of Matsuda, Ozeki, and Yamashita posits that, for any positive integer $k$, a connected claw-free $n$-vertex graph $G$ must contain either a spanning tree with at most $k$ branch vertices or an independent set of $2k+3$ vertices whose degrees add up to at most $n-3$. In other words, $G$ has this spanning tree whenever $\sigma_{2k+3}(G)\geq n-2$. We prove this conjecture, which was known to be sharp.

Graphs are a natural representation for modeling relationships between entities across many different fields of research. In real-world networks today, new data is constantly being produced, leading to the notion of dynamic graphs. An important query when analyzing graphs is to identify the most important vertices in a graph. Vertex importance is termed as centrality, and centrality scores can be used to provide rankings on the vertices of a graph. Specifically, I focus on Katz Centrality, a linear algebra based metric that measures the affinity between vertices in a graph as a weighted sum of the number of walks between them. Calculating Katz scores involves approximating the solution to a linear system using iterative solvers. Currently, we do not have a sense of how the numerical error from the iterative method in the approximation to the centrality vector affects the identification of the highly ranked vertices. In the first part of the talk, I bridge the two research areas of numerical analysis and network analysis by providing insight into how bounding the error between the approximate and exact solution in the numerical problem affects the correct relative ranking of vertices in the data mining problem. Typically, Katz scores are calculated through linear algebra. In the second section of the talk, I present an new alternative, agglomerative method of calculating personalized Katz scores. The algorithm presented is several orders of magnitude faster than the typical linear algebra approach and is able to return good quality scores of vertices. Finally, updating centrality scores of the vertices in a dynamic graph quickly becomes expensive to recompute from scratch every time the underlying graph is changed, as is the case in evolving networks. I conclude the talk by presenting a new algorithm for updating the Katz scores of vertices in a dynamic graph that is faster than static recomputation while maintaining good quality of the scores returned.

Sufficient conditions to imply the existence of certain substructures in a graph are of considerable interest in extremal graph theory, and conditions that guarantee a large set of cycles or chorded cycles are a recurring theme. This dissertation explores different degree sum conditions that are sufficient for finding a large set of vertex-disjoint cycles or a large set of vertex-disjoint chorded cycles in a graph. \vskip.1in For an integer $t\ge 1$, let $\sigma_t (G)$ be the smallest sum of degrees of $t$ independent vertices of $G$. We first prove that if a graph $G$ has order at least $7k+1$ and degree sum condition $\sigma_4(G)\ge 8k-3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint cycles. Then, we consider an equivalent condition for chorded cycles, proving that if $G$ has order at least $11k+7$ and $\sigma_4(G)\ge 12k-3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint chorded cycles. We prove that the degree sum condition in each result is sharp. Finally, we conjecture generalized degree sum conditions on $\sigma_t(G)$ for $t\ge 2$ sufficient to imply that $G$ contains $k$ vertex-disjoint cycles for $k \ge 2$ and $k$ vertex-disjoint chorded cycles for $k \ge 2$. This is joint work with Ronald J. Gould and Kazuhide Hirohata.