# Nodal domains of eigenvectors of Erdos-Renyi random graphs

Mark Rudelson

## Institution:

University of Michigan

## Time:

Friday, March 6, 2020 - 2:00pm to 2:50pm

## Location:

RH 340N

A nodal domain of a function is a connected component of the set where this function has a constant sign. Nodal domains of eignefunctions of the Laplacian are classical objects in geometry of manifolds. Their number of nodal domains corresponding to the k-th smallest eigenvalue is bounded by k and it typically increases as k gets larger. About 10 years ago, Dekel, Lee, and Linial proved that with high probability, the number of nodal domains of Erdos-Renyi graphs remains bounded as the size of the graph and the eigenvalues increase.  This runs contrary to the intuition we draw from the world of manifolds. We will survey some recent results on the structure of nodal domains of such graphs. Based in part on the joint work with Han Huang.

# Independent sets in random graphs and random trees

Steven Heilman

USC

## Time:

Tuesday, March 3, 2020 - 11:00am

## Location:

Rowland Hall, 340P

An independent set of size k in a finite undirected graph is a set of k vertices of the graph, no two of which are connected by an edge. The structure of independent sets of size k as k varies is of interest in probability, statistical physics, combinatorics, and computer science. In 1987, Alavi, Malde, Schwenk and Erdos conjectured that the number of independent sets of size k in a tree is a unimodal sequence (this number goes up and then it goes down), and this problem is still open. A variation on this question is: do the number of independent sets of size k form a unimodal sequence for Erdos-Renyi random graphs, or random trees? By adapting an argument of Coja-Oghlan and Efthymiou, we show unimodality for Erdos-Renyi random graphs, random bipartite graphs and random regular graphs (with high probability as the number of vertices in the graph goes to infinity, when the expected degree of a single vertex is large). The case of random trees remains open, as we can only show weak partial results there.

# Integrable Probability

Ivan Corwin

## Institution:

Columbia University

## Time:

Friday, January 31, 2020 - 11:00am to 11:50am

## Location:

340 P

I will describe an example of an integrable probabilistic system and then indicate some of the mathematical structures which unify and underlay the field. The model I will mainly focus on is the Beta random walk in random environment. Time permitting I will also discuss some elements of stochastic vertex models.

# Embedding large minors in weak expanders and in sparse random graphs

## Speaker:

Michael Krivelevich

## Institution:

Tel Aviv University

## Time:

Tuesday, February 18, 2020 - 11:00am

## Location:

340P

A graph G on n vertices is called an alpha-expander if the external neighborhood of every vertex subset U of size |U|<=n/2 in G has size at least alpha*|U|.

Extending and improving the results of Plotkin, Rao and Smith, and of Kleinberg and Rubinfeld from the 90s, we prove that for every alpha>0, an alpha-expander G on n vertices contains every graph H with at most cn/log n vertices and edges as a minor, for c=c(alpha)>0.

Alternatively, every n-vertex graph G without sublinear separators contains all graphs with cn/logn vertices and edges as minors.

Consequently, a supercritical random graph G(n,(1+epsilon)/n) is typically minor-universal for the class of graphs with cn/log n vertices and edges.

The order of magnitude n/log n in the above results is optimal.

A joint work with Rajko Nenadov.

# Super-logarithmic cliques in dense inhomogeneous random graphs

Gwen McKinley

MIT

## Time:

Tuesday, January 14, 2020 - 11:00am to 12:00pm

## Location:

340R

In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1]^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G(n,W), that can be viewed as a generalization of the Erdos-Renyi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order log(n) for the size of the largest clique in G(n,W) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G(n,W) will be of order √n almost surely. We also give a family of examples with clique number of order n^c for any c in (0,1), and some conditions under which the clique number of G(n,W) will be o(√n) or omega(√n). This talk assumes no previous knowledge of graphons.

# On the geometry of polytopes generated by heavy-tailed random vectors

Felix Krahmer

TU Munich

## Time:

Tuesday, December 3, 2019 - 11:00am to 11:50am

## Location:

RH 340N

We present recent results on the geometry of centrally-symmetric random polytopes generated by N independent copies of a random vector X. We show that under minimal assumptions on X, for N>Cn, and with high probability, the polytope contains a deterministic set that is naturally associated with the random vector - namely, the polar of a certain floating body. This solves the long-standing question on whether such a random polytope contains a canonical body. Moreover, by identifying the floating bodies associated with various random vectors we recover the estimates that have been obtained previously, and thanks to the minimal assumptions on X we derive estimates in cases that had been out of reach, involving random polytopes generated by heavy-tailed random vectors (e.g., when X is q-stable or when X has an unconditional structure). Finally, the structural results are used for the study of a fundamental question in compressive sensing - noise blind sparse recovery. This is joint work with the speaker's PhD student Christian Kümmerle (now at Johns Hopkins University) as well as Olivier Guédon (University of Paris-Est Marne La Vallée), Shahar Mendelson (Sorbonne University Paris), and Holger Rauhut (RWTH Aachen).

# On the amount of dependence of the component counting process of a uniform random variable on a combinatorial structure.

Joseph Squillace

UCI

## Time:

Tuesday, November 5, 2019 - 11:00am to 12:00pm

RH 340N

# Interlacing Particle Systems and Special Functions

Cesar Cuenta

Cal Tech

## Time:

Tuesday, February 11, 2020 - 11:00am to 11:50am

## Location:

340R

I will talk about the beta orbital corners process, a natural interpolation (on the dimension of the base field) of orbital measures from random matrix theory. The new result is the convergence in probability of the orbital corners process to a Gaussian process. Our approach is based on the study of asymptotics of the multivariate Bessel functions via explicit formulas. I will also discuss some variations of the problem by means of multivariate special functions.

# Modewise Johnson-Lindenstrauss embeddings for tensors

## Speaker:

Elizaveta Rebrova

UCLA

## Time:

Tuesday, November 12, 2019 - 11:00am to 11:50am

## Location:

RH 340N

The celebrated Johnson-Lindenstrauss lemma is a powerful tool for dimension reduction via simple (often random) projections that approximately preserve the geometry of the larger dimensional objects. I will discuss an extension of this result to low CP-rank tensors. I show how modewise tensor projections preserve tensor geometry in the analogous way, without doing any initial tensor matricization or vectorization. Time permitting, I will also talk about an application to the least squares fitting CP model for tensors. Based on our joint work with Mark Iwen, Deanna Needell, and Ali Zare.

# Finite-rank perturbations of random band matrices via infinitesimal free probability

Benson Au

UCSD

## Time:

Tuesday, October 8, 2019 - 11:00am to 12:00pm

## Location:

RH 340N

Free probability provides a unifying framework for studying random multi-matrix models in the large $N$ limit. Typically, the purview of these techniques is limited to invariant or mean-field ensembles. Nevertheless, we show that random band matrices fit quite naturally into this framework. Our considerations extend to the infinitesimal level, where finer results can be stated for the $\frac{1}{N}$ correction. As an application, we consider the question of outliers for finite-rank perturbations of our model. In particular, we find outliers at the classical positions from the deformed Wigner ensemble. No background in free probability is assumed.