# Spring 2022

January 27th: Quentin Dubroff (Rutgers)

Title: Linear cover time is exponentially unlikely
Abstract: Proving a 2009 conjecture of Itai Benjamini, we show: For any C, there is a > 0 such that for any simple random walk on an n-vertex graph G, the probability that the first Cn steps of the walk hit every vertex of G is at most exp[-an]. A first ingredient of the proof is a similar statement for Markov chains in which all transition probabilities are less than a suitable function of C.
Joint with Jeff Kahn.

February 3rd: Kasun Fernando (University of Toronto and Scuola Normale Superiore di Pisa)

Title: The bootstrap for dynamical systems

Abstract: Despite their deterministic nature, dynamical systems often exhibit seemingly random behaviour. Consequently, a dynamical system is usually represented by a probabilistic model

of which the unknown parameters must be estimated using statistical methods. When measuring the uncertainty of such parameter estimation, the bootstrap stands out as a simple but powerful technique. In this talk, I will introduce the bootstrap for dynamical systems and discuss its consistency and second-order efficiency using a novel continuous Edgeworth expansions for dynamical systems. This is a joint work with Nan Zou (Macquarie University).

February 10th, Pratik Misra (KTH Royal Institute of Technology)

Title: “Gaussian graphical models with toric vanishing ideal”

Abstract: Gaussian graphical models are semi-algebraic subsets of the cone of positive definite covariance matrices. They are widely used throughout  natural sciences, computational biology and many other fields. Computing the vanishing ideal gives us an implicit description of the model. In this talk, I will mainly focus on proving a conjecture given by Sturmfels and Uhler. In particular, we characterize those graphs for which the vanishing ideal of the Gaussian graphical model is generated in degree 1 and 2. These turn out to be the Gaussian graphical models whose ideals are toric, and the resulting graphs are 1-clique sums of complete graphs.

February 17th: Hunter Novak Spink (Stanford)

Title: Anti-concentration of random walks on model-theoretic definable sets.

Abstract:  Classical anti-concentration results show “random walks in R^d with BIG independent steps can’t concentrate in balls much better than they can concentrate on individual points”.

Model-theoretic definable sets include boolean combinations of subsets of R^d defined using equalities and inequalities of arbitrary compositions of polynomials, e^x, ln(x) and analytic functions restricted to compact boxes. For example, the intersection of
e^{sin(1/(1+(xyz)^2))+x^2y}+zy >=0 and xyz=5 in R^3.
In this talk, I will discuss recent results which show “random walks in R^d with ARBITRARY independent steps can’t concentrate in definable sets not containing line segments much better than they can concentrate on individual points”.

Time permitting, I will discuss how these results extend to other groups like GL_d(R).

(Joint with Jacob Fox, Matthew Kwan)

February 24th: Ashwin Sah (MIT)

Title: Singularity of the k-core of a random graph

Abstract: Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of “low-degree dependencies” such as isolated vertices and pairs of degree-1 vertices with the same neighbourhood. We prove that these kinds of dependencies are in some sense the only causes of singularity: for constants $k\ge 3$ and $\lambda > 0$, an Erd\H{o}s–R\’enyi random graph $n$ vertices and edge probability $\lambda/n$ typically has the property that its $k$-core (largest subgraph with min-degree at least $k$) is nonsingular. This resolves a conjecture of Vu from the 2014 International Congress of Mathematicians, and adds to a short list of known nonsingularity theorems for “extremely sparse” random matrices with density $O(1/n)$. A key aspect of our proof is a technique to extract high-degree vertices and use them to “boost” the rank, starting from approximate rank bounds obtainable from (non-quantitative) spectral convergence machinery due to Bordenave, Lelarge, and Salez.​

(Joint with Asaf Ferber, Matthew Kwan, and Mehtaab Sawhney)

Marth 3rd: Jorge Garza-Vargas (UC Berkeley)

Title: Finite Free Cumulants: Multiplicative Convolutions, Genus Expansion and Infinitesimal DistributionsAbstract: Since the seminal work of Voiculescu in the early 90’s, the connection between the asymptotic behavior of random matrices and free probability has been extensively studied. More recently, in relation to the solution of the Kadison-Singer problem, Marcus, Spielman, and Srivastava discovered a deep connection between certain classical polynomial convolutions and free probability, and this connection was further understood by Marcus, who introduced the notion of finite free probability.

In this talk I will present recent results on finite free probability with applications to the asymptotic analysis of real-rooted polynomials. Our approach is based on a careful combinatorial analysis of the finite free cumulants, from where we derive a topological expansion. In turn, we use this expansion to study the root distribution dynamics of polynomials after repeated differentiation, as well as the root distribution fluctuations for certain families of polynomials. This is joint work with Octavio Arizmendi and Daniel Perales: arXiv:2108.08489.

March 10th:

March 17th: Spring break, no seminar.

March 24th: Erika Roldán (TU Munich & EPFL Switzerland)

Title: Parity Property of Hexagonal Sliding Puzzles

Abstract: We study the puzzle graphs of hexagonal sliding puzzles of various shapes and with various numbers of holes. The puzzle graph is a combinatorial model which captures the solvability and the complexity of sequential mechanical puzzles. Questions relating to the puzzle graph have been previously studied and resolved for the 15 Puzzle which is the most famous, and unsolvable, square sliding puzzle of all times. The puzzle graph is also a discrete model for the configuration space of hard tiles (hexagons or squares) moving on different tessellation-based domains. Understanding the combinatorics of the puzzle graph leads to understanding some aspects of the topology of these configuration spaces.This is join work with Ray Karpman.

March 31st: Stefan Steinerberger  (University of Washington)

Title: Boundary and Curvature on Graphs
Abstract:  I will discuss new definitions of boundary and curvature on combinatorial graphs. The boundary will include an earlier definition of Chartrand-Erwin-Johns-Zhang and satisfy an isoperimetric principle: graphs with many vertices have a large boundary (or gigantic diameter: the path graph only has 2 boundary vertices independently of length).  There are multiple definitions of curvature on graphs (combinatorial, via the behavior of the Laplacian, via Optimal Transport). We propose a new one based on potential theory: this curvature can be computed by solving a linear system and has a large number of desirable properties: it satisfies a Bonnet-Myers theorem (graphs with curvature bounded from below have diameter bounded from above) as well as an inverse Bonnet-Myers and a Lichnerowicz theorem. The von Neumann Minimax Theorem from Game Theory plays a crucial role in the proofs. There will be many pictures and many open problems.

April 14th: Nhan Nguyen (UVA)

Title: Cumulants of the number of real zeros of random polynomials

Abstract: If we consider a polynomial with random coefficients, then the number of its real zeros becomes a random variable. A key problem in the theory of random polynomial is to understand the behavior and the limiting law of this random variable when the degree of the polynomial approaches infinity. To this end, we need to investigate some of its statistical invariants such as expectation, variance, and so on. This talk deals with the cumulants of the number of real zeros of some classes of random polynomials. As a consequence, some convergence theorems for the number of real zeros are also considered.

April 21th: Brett Kolesnik (UCSD)

Title: Graph bootstrap percolation

Abstract: Bootstrap percolation is a classical model for a dynamical network, in which sites (e.g., people) in a network update their status (e.g., become infected) depending on the status of their local network (e.g., depending on how many of their close contacts are infected). Béla Bollobás introduced a variant of this model, called graph bootstrap percolation, wherein the rule by which sites change status is significantly more complex. In this talk, we will discuss our recent work with Zsolt Bartha, which locates the critical percolation threshold, at which point it becomes likely that all sites are eventually infected. This solves an open problem of József Balogh, Béla Bollobás and Robert Morris.

April 28th: final exams