Autumn 2018 | Combinatorics and Probability Seminar

September 13: Hoi Nguyen (OSU)

Title: A universality aspect of integral matrices

Abstract: For a random matrix of entries sampled independently from a fairly general distribution in $\mathbb{Z}$ we discuss the probability that the cokernel is isomorphic to a given finite abelian group, or when it is cyclic. We will show that these statistics are asymptotically universal.

Partly joint with E. Paquette and with M. M. Wood.

September 20: Elliot Paquette

Title: Random matrix point processes via stochastic processes

Abstract:

In 2007, Virág and Válko introduced the Brownian carousel, a dynamical system that describes the eigenvalues of a canonical class of random matrices. This dynamical system can be reduced to a diffusion, the stochastic sine equation, a beautiful probabilistic object requiring no random matrix theory to understand. This talk will show how this dynamical system arises and describe the stochastic sine equation in a non–technical way.

Many features of the eigenvalues of the random matrix can then be studied via this stochastic process. We will sketch how this stochastic process is connected to eigenvalues of a random matrix and how problems relating to the eigenvalues of this process can be tackled using this stochastic process.

Based on joint works with Diane Holcomb, Gaultier Lambert, Bálint Vető, and Bálint Virág.

September 27: David Sivakoff

Title: Bootstrap percolation on the Cartesian product of a lattice with a Hamming square.

Abstract: Spread of signals on graphs with community structure has attracted interest in the mathematical literature recently. The idea is that any single community is densely connected, while the connections between communities are much more sparse. This naturally leads to multiscale phenomena, as the spread of the signal within a community is much faster then between different communities. The focus of this talk will be on the graph $\mathbb{Z}^2 \times K_n^2$ , the Cartesian product of the two-dimensional lattice with two copies of the complete graph. Thus, each “community” consists of individuals determined by two characteristics, and two individuals within a community only communicate if they have one of the characteristics in common. Between communities, communication is between like individuals that are also neighbors in the lattice. For comparison, we also address the case where each community is a clique, that is, the graph $\mathbb{Z}^2 \times K_n$ .

We model the spread of signals using the bootstrap percolation dynamics with integer threshold r>1. In this simple, deterministic process, one starts with an initial configuration of empty and occupied vertices of the graph. At each step, occupied vertices remain occupied, and empty vertices become occupied if they have at least r occupied neighbors. For an initial density p of occupied vertices, we are interested in the density of eventually occupied vertices. We identify distinct behavior for odd and even values of the threshold parameter, r, and for the clique community graph. Our analyses rely on couplings with a class of dynamical systems on $\mathbb{Z}^2$ that we call heterogeneous bootstrap percolation, which is of independent interest. Based on joint work with Janko Gravner.

October 4: Sebastian Cioaba (Delaware)

Title:The smallest eigenvalues of Hamming, Johnson and other graphs

Abstract: The smallest eigenvalue of graphs is closely related to other graph parameters such as the independence number, the chromatic number or the max-cut. In this talk, I will describe some of these results as well as the connections between the smallest eigenvalue and the max-cut of a graph that have motivated various researchers such as Karloff, Alon, Sudakov, Van Dam, Sotirov to investigate the smallest eigenvalue of Hamming and Johnson graphs. I will describe our proofs of a conjecture by Van Dam and Sotirov on the smallest eigenvalue of (distance-j) Hamming graphs and a conjecture by Karloff on the smallest eigenvalue of (distance-j) Johnson graphs and mention some open problems. This is joint work with Andries Brouwer, Ferdinand Ihringer and Matt McGinnis.

October 11: Fall Break

October 18: Thomas Leblé (NYU/Courant)

Title: The Sine-beta process: DLR equations and applications

Abstract: One-dimensional log-gases, or Beta-ensembles, are statistical physics models finding an incarnation in random matrix theory. Their limit behavior at microscopic scale is known as the Sine-beta process, its original description involves systems of coupled SDE’s. We give a new description of Sine-beta as an “infinite volume Gibbs measure”, using the Dobrushin-Lanford-Ruelle (DLR) formalism, and we use it to prove the rigidity of the process, in the sense of Ghosh-Peres. If time permits, I will mention another application to the fluctuations of linear statistics. Joint work with David Dereudre, Adrien Hardy, and Mylène Maïda.

October 25: Tomasz Tkocz (Carnegie Melon University)

Title: On the cover time of the emerging giant

Abstract: Using the notion of a Gaussian Free Field, we shall determine (asymptotically) the cover time of an emerging unique giant component of the Erdos-Renyi random graph G(n,p). Based on joint work with A. Frieze and W. Pegden.

November 1: Shirshendu Chatterjee (CUNY, City College)

Title: TBA

Abstract: TBA

November 8: Georgios Petridis (Georgia)

Title: Counting isosceles trapezoids

Abstract: Given n points on the plane (we think of n as a large integer) we aim to bound the number of isosceles trapezoids with all four vertices in the point set. One is interested in this question because it is related to the pinned variant of Erdos’ distinct distances question. One can verify that if the point are the vertices of a regular n-gon or n equally spaced points on a line, then there are a constant multiple of n^3 ordered isosceles trapezoids (n^3 being the trivial upper bound). Are there other examples of point sets that exhibit this trait? What is there to be gained by understanding this question better? In this largely expository talk, I will answer these questions and hopefully more. All work presented in joint with Ben Lund.

November 15: Jiaoyang Huang (Harvard University)

Title: Invertibility of adjacency matrices for random d-regular graphs

Abstract: The singularity problem of random matrices asks the probability that a given discrete random matrix is singular. The first such result was obtained by Komlós in 1967. He showed a Bernoulli random matrix is singular with probability $o (1)$ . This question can be reformulated for the adjacency matrices of random graphs, either directed or undirected. The most challenging case is when the random graph is sparse. In this talk, I will prove that for random directed and undirected $d$ -regular graphs, their adjacency matrices are invertible with high probability for all $d \geq 3$ . The idea is to study the adjacency matrices over a finite field, and the proof combines a local central limit theorem and a large deviation estimate.

November 22: Thanksgiving

November 29: Michael Damron (Georgia Tech)

Title: Lower bounds for fluctuations in first–passage percolation

Abstract: In first-passage percolation (FPP), one assigns i.i.d. weights to the edges of the cubic lattice $\mathbb{Z}^d$ and analyzes the induced weighted graph metric. If $T(x,y)$ is the distance between vertices $x$ and $y,$ then a primary question in the model is: what is the order of the fluctuations of $T(o,x)$ ? It is expected that the variance of $T(o,x)$ grows like the norm of $x$ to a power strictly less than $1,$ but the best lower bounds available are of order $\log|x|.$ This result was found in the ’90s and there has not been any improvement since. In this talk, we discuss the problem of getting stronger fluctuation bounds: to show that $T(o,x)$ is with high probability not contained in an interval of size $o(\log |x|)^{1/2},$ and similar statements for FPP in thin cylinders. Such a statement has been proved for special edge-weight distributions by Pemantle-Peres (’95) and Chatterjee (’17). In ongoing work with J. Hanson, C. Houdré, and C. Xu, we aim to extend these bounds to general edge-weight distributions. I will explain some of the methods we are using, including an old and elementary “small ball” probability result for functions on the hypercube.

December 6: Yuval Peled (NYU)

Title: Enumeration and randomized constructions of hypertrees

Abstract: Over thirty years ago, Kalai proved a beautiful d-dimensional analog of Cayley’s formula for the number of n-vertex trees. Namely, he enumerated d-dimensional hypertrees weighted by the squared size of their (d-1)-dimensional homology group. This, however, does not answer the more basic problem of unweighted enumeration of d-hypertrees, which is our concern here. We analyze a random-greedy construction of d-hypertrees and show it significantly improves the previous known lower bound for their number. Second, we introduce a model of random 1-out d-dimensional complexes, and show that it has a negligible d-dimensional homology with high probability.

Joint work with Nati Linial.