# TBA

Matt Larson

Stanford

## Time:

Tuesday, April 21, 2020 - 11:00am

## Location:

Rowland Hall, 340P

# Integrable Probability

Ivan Corwin

## Institution:

Columbia University

## Time:

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

## Location:

TBA

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

# TBA

Cesar Cuenta

Cal Tech

## Time:

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

340R

# 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.