L6

The study of random matrix moments of moments has connections to number theory, combinatorics, and log-correlated fields. Our results give the leading order of these functions for integer moment parameters by exploiting connections with Gelfand-Tsetlin patterns and counts of lattice points in convex sets. This is joint work with Jon Keating and Theo Assiotis.

The genus of a knot in a 3-manifold is defined to be the minimum genus of a compact, orientable surface bounding that knot, if such a surface exists. We consider the computational complexity of determining knot genus. Such problems have been studied by several mathematicians; among them are the works of Hass--Lagarias--Pippenger, Agol--Hass--Thurston, Agol and Lackenby. For a fixed 3-manifold the knot genus problem asks, given a knot K and an integer g, whether the genus of K is equal to g. In joint work with Lackenby, we prove that for any fixed, compact, orientable 3-manifold, the knot genus problem lies inNP, answering a question of Agol--Hass--Thurston from 2002. Previously this was known for rational homology 3-spheres by the work of Lackenby.

Modularity is a function on graphs which is used in algorithms for community detection. For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in $G$. The (max) modularity $q^\ast(G)$ of the graph $G$ is defined to be the maximum over all vertex partitions of the modularity score, and satisfies $0 \leq q^\ast(G) \leq 1$.

We analyse when community structure of an underlying graph can be determined from an observed subset of the graph. In a natural model where we suppose edges in an underlying graph $G$ appear with some probability in our observed graph $G'$ we describe how high a sampling probability we need to infer the community structure of the underlying graph.

Joint work with Colin McDiarmid.

In this talk, we consider the random version of some classical extremal problems in the context of long cycles. This type of problems can also be seen as random analogues of the Turán number of long cycles, established by Woodall in 1972.

For a graph $G$ on $n$ vertices and a graph $H$, denote by $\text{ex}(G,H)$ the maximal number of edges in an $H$-free subgraph of $G$. We consider a random graph $G\sim G(n,p)$ where $p>C/n$, and determine the asymptotic value of $\text{ex}(G,C_t)$, for every $A\log(n)< t< (1- \varepsilon)n$. The behaviour of $\text{ex}(G,C_t)$ can depend substantially on the parity of $t$. In particular, our results match the classical result of Woodall, and demonstrate the transference principle in the context of long cycles.

Using similar techniques, we also prove a robustness-type result, showing the likely existence of cycles of prescribed lengths in a random subgraph of a graph with a nearly optimal density (a nearly ''Woodall graph"). If time permits, we will present some connections to size-Ramsey numbers of long cycles.

Based on joint works with Michael Krivelevich and Adva Mond.

A broad challenge in the theory of finitely generated groups is to understand their subgroups. A group is commensurably coHopfian if its finite index subgroups are distinct from its infinite index subgroups (that is to say not abstractly isomorphic). We will focus primarily on hyperbolic groups, and give the first examples of one-ended hyperbolic groups that are not commensurably coHopfian.
This is joint work with Emily Stark.
 

In this talk we will survey a novel domain of computational group theory: computing with linear groups over infinite fields.  We will provide an introduction to the area, and will discuss available methods and algorithms. Special consideration is given to algorithms for Zariski dense subgroups. This includes a computer realization of the strong approximation theorem, and algorithms for arithmetic groups. We illustrate applications of our methods to the solution of problems further afield by computer experimentation.

The rows of a Young diagram chosen at random with respect to the Plancherel measure are known to share some features with the eigenvalues of the Gaussian Unitary Ensemble. We shall discuss several ideas, going back to the work of Kerov and developed by Biane and by Okounkov, which to some extent clarify this similarity. Partially based on joint work with Jeong and on joint works in progress with Feldheim and Jeong and with Täufer.

This presentation introduces a rigorous framework for the study of commonly used machine learning techniques (kernel methods, random feature maps, etc.) in the regime of large dimensional and numerous data. Exploiting the fact that very realistic data can be modeled by generative models (such as GANs), which are theoretically concentrated random vectors, we introduce a joint random matrix and concentration of measure theory for data processing. Specifically, we present fundamental random matrix results for concentrated random vectors, which we apply to the performance estimation of spectral clustering on real image datasets.

The talk will describe how ideas from random matrix theory can be leveraged to effectively, accurately, and reliably solve important problems that arise in data analytics and large scale matrix computations. We will focus in particular on accelerated techniques for computing low rank approximations to matrices. These techniques rely on randomised embeddings that reduce the effective dimensionality of intermediate steps in the computation. The resulting algorithms are particularly well suited for processing very large data sets.

The algorithms described are supported by rigorous analysis that depends on probabilistic bounds on the singular values of rectangular Gaussian matrices. The talk will briefly review some representative results.

Note: There is a related talk in the Computational Mathematics and Applications seminar on Thursday Feb 27, at 14:00 in L4. There, the ideas introduced in this talk will be extended to the problem of solving large systems of linear equations.