Seminars archive

In 1946 Erdos asked to determine or estimate the minimum number of distinct distances determined by an n-element planar point set V. He showed that a square integer lattice determines \Theta(n/\sqrt{log n}) distinct distances, and conjectured that any n-element point set determines at least n^{1−o(1)} distinct distances. In 2010-2015, Guth and Katz answered Erdos’s question by proving that any n-element planar point set determines at least \Omega(n/log n) distinct distances. In this talk, we consider a variant of this problem by Erdos and Gyarfas. For integers n, p, q with p \geq q \geq 2, determine the minimum number D(n,p,q) of distinct distances determined by a planar n-element point set V with the property that any p points from V determine at least q distinct distance. In a recent paper, Fox, Pach and Suk prove that when q = {p \choose 2} - p + 6, D(n,p,q) is always at least n^{8/7 - o(1)}. We will discuss a recent improvement of their result and some new bounds for a related (graph theoretic) Ramsey problem of Erdos and Shelah which arise. This is joint work with Adam Sheffer.

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.

The basic objects of algebraic number theory are number fields, and the basic invariant of a number field is its discriminant, which in some sense measures its arithmetic complexity. A basic finiteness result is that there are only finitely many degree-$d$ number fields of discriminant at most $X$; more generally, for any fixed global field $K$, there are only finitely many degree-$d$ extensions $L/K$ whose discriminant has norm at most $X$. (The classical case is where $K = \mathbb{Q}$.) \\ When a set is finite, we greedily ask if we can compute its cardinality. Write $N_d(K,X)$ for the number of degree-$d$ extensions of $K$ with discriminant at most $d$. A folklore conjecture holds that $N_d(K,X)$ is on order $c_d X$. In the case $K = \mathbb{Q}$, this is easy for $d=2$, a theorem of Davenport and Heilbronn for $d=3$, a much harder theorem of Bhargava for $d=4$ and 5, and completely out of reach for $d > 5$. More generally, one can ask about extensions with a specified Galois group $G$; in this case, a conjecture of Malle holds that the asymptotic growth is on order $X^a (\log X)^b$ for specified constants $a,b$. \\ I'll talk about two recent results on this old problem: \\ 1) (joint with TriThang Tran and Craig Westerland) We prove that $N_d(\mathbb{F}_q(t),X)) < c_{\epsilon} X^{1+\epsilon}$ for all $d$, and similarly prove Malle’s conjecture ``up to epsilon" — this is much more than is known in the number field case, and relies on a new upper bound for the cohomology of Hurwitz spaces coming from quantum shuffle algebras: https://arxiv.org/abs/1701.04541 \\ 2) (joint with Matt Satriano and David Zureick-Brown) The form of Malle's conjecture is very reminiscent of the Batyrev-Manin conjecture, which says that the number of rational points of height at most $X$ on a Batyrev-Manin variety also grows like $X^a (\log X)^b$ for specified constants $a,b$. What’s more, an extension of $\mathbb{Q}$ with Galois group $G$ is a rational point on a Deligne--Mumford stack called $BG$, the classifying stack of $G$. A natural reaction is to say “the two conjectures is the same; to count number fields is just to count points on the stack BG with bounded height?” The problem: there is no definition of the height of a rational point on a stack. I'll explain what we think the right definition is, and explain how it suggests a heuristic which has both the Malle conjecture and the Batyrev--Manin conjecture as special cases.

Talks will be at the University of Georgia \\ \textbf{David Harbater} (University of Pennsylvania), 4:00 \\ Local-global principles for zero-cycles over semi-global fields \\ Classical local-global principles are given over global fields. This talk will discuss such principles over semi-global fields, which are function fields of curves defined over a complete discretely valued field. Paralleling a result that Y. Liang proved over number fields, we prove a local-global principle for zero-cycles on varieties over semi-global fields. This builds on earlier work about local-global principles for rational points. (Joint work with J.-L. Colliot-Thélène, J. Hartmann, D. Krashen, R. Parimala, J. Suresh.) \\ \textbf{Jacob Tsimerman} (U. Toronto), 5:15 \\ Cohen-Lenstra heuristics in the Presence of Roots of Unity \\ The class group is a natural abelian group one can associated to a number field, and it is natural to ask how it varies in families. Cohen and Lenstra famously proposed a model for families of quadratic fields based on random matrices of large rank, and this was later generalized by Cohen-Martinet to general number fields. However, their model was observed by Malle to have issues when the base field contains roots of unity. We explain that in this setting there are naturally defined additional invariants on the class group, and based on this we propose a refined model in the number field setting rooted in random matrix theory. Our conjecture is based on keeping track not only of the underlying group structure, but also certain natural pairings one can define in the presence of roots of unity. Specifically, if the base field contains roots of unity, we keep track of the class group G together with a naturally defined homomorphism $G^*[n] \to G$ from the n-torsion of the Pontryagin dual of G to G. Using methods of Ellenberg-Venkatesh-Westerland, we can prove some of our conjecture in the function field setting.

The construction of the Brauer group of a field can be generalized to (commutative) rings, and more generally to schemes, by replacing central simple algebras with Azumaya algebras. As in the case of fields, the Brauer group is an important cohomological invariant of the scheme, featuring, for instance, in the Manin obstruction for rational points. \\ Many of the properties of central simple algebras generalize to Azumaya algebras, but sometimes modifications are needed. For example, Albert characterized the central simple algebras admitting an involution of the first kind as those whose Brauer class is 2-torsion. While this fails for Azumaya algebras over a ring R, Saltman showed that the 2-torsion classes in the Brauer group of R are precisely those containing some representative admitting an involution of the first kind. Knus, Parimala and Srinivas later gave a quantitative version of this statement: If A is an Azumaya algebra of over R such that its Brauer class is 2-torsion, then there is an Azumaya algebra in the Brauer class of A that admits an involution and has degree 2*deg(A). \\ In this talk, we shall recall what are Azumaya algebras and how the Brauer group of a ring (or a scheme) is constructed. Then we will present a recent work with Asher Auel and Ben Williams where we use topological obstruction theory to show that the quantitative result of Knus, Parimala and Srinivas cannot be improved in general. Specifically, there are Azumaya algebras of degree 4 whose Brauer class is 2-torsion, but such that any algebra that is Brauer-equivalent to them and admits an involution has degree divisible by 8 = 2*4.

Sparse linear algebra problems, typically solved using iterative methods, are ubiquitous throughout scientific and data analysis applications and are often the most expensive computations in large-scale codes due to the high cost of data movement. Approaches to improving the performance of iterative methods typically involve modifying or restructuring the algorithm to reduce or hide this cost. Such modifications can, however, result in drastically different behavior in terms of convergence rate and accuracy. A clear, thorough understanding of how inexact computations, due to either finite precision error or intentional approximation, affect numerical behavior is thus imperative in balancing the tradeoffs between accuracy, convergence rate, and performance in practical settings. In this talk, we focus on two general classes of iterative methods for solving linear systems: Krylov subspace methods and iterative refinement. We present bounds on the attainable accuracy and convergence rate in finite precision s-step and pipelined Krylov subspace methods, two popular variants designed for high performance. For s-step methods, we demonstrate that our bounds on attainable accuracy can lead to adaptive approaches that both achieve efficient parallel performance and ensure that a user-specified accuracy is attained. We present two such adaptive approaches, including a residual replacement scheme and a variable s-step technique in which the parameter s is chosen dynamically throughout the iterations. Motivated by the recent trend of multiprecision capabilities in hardware, we present new forward and backward error bounds for a general iterative refinement scheme using three precisions. The analysis suggests that on architectures where half precision is implemented efficiently, it is possible to solve certain linear systems up to twice as fast and to greater accuracy. As we push toward exascale level computing and beyond, designing efficient, accurate algorithms for emerging architectures and applications is of utmost importance. We discuss extensions to machine learning and data analysis applications, the development of numerical autotuning tools, and the broader challenge of understanding what increasingly large problem sizes will mean for finite precision computation both in theory and practice.

Anisotropic mesh adaptation has been proved to be a powerful strategy for improving the quality and the efficiency of numerical modeling. Anisotropic phenomena occur in many applications, ranging from shocks in compressible flows, steep boundary or internal layers in viscous flows around bodies, fronts of different nature to be sharply tracked. These problems typically require advanced methods of scientific computing that rely on a tessellation or “mesh” of the region of interest. The intrinsic directionalities of these dynamics call for an accurate control of the shape, the size and the orientation of mesh elements in contrast to standard isotropic meshes where the only parameter to choose is the element size. Metric-based techniques usually drive anisotropic mesh adaptation, the metric being derived by either heuristic or theoretical approaches. In the former case, the metric is identified by a numerical approximation of the Hessian or of the gradient of the discrete solution, coupled with an a priori error estimator. More rigorous - theoretically based - approaches move from a posteriori error analyses, i.e., from an explicit control of the discretization error or – in more sophisticated cases – of a functional of the error. This control is enhanced by an appropriate inclusion of the main directional features of the problem at hand.\\ \\In this presentation, we focus on both heuristic and rigorous anisotropic error estimators. We present some theoretical aspects and applications to a variety of problems relevant for different fields, (i) propagation of cracks in brittle materials, (ii) topology optimization of structures for aerospace engineering (in collaboration with Thales Alenia Space) and (iii) medical image segmentation.