Integrable Probability

Speaker: 

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

Host: 

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

Speaker: 

Gwen McKinley

Institution: 

MIT

Time: 

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

Host: 

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

Speaker: 

Felix Krahmer

Institution: 

TU Munich

Time: 

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

Host: 

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

Modewise Johnson-Lindenstrauss embeddings for tensors

Speaker: 

Elizaveta Rebrova

Institution: 

UCLA

Time: 

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

Host: 

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

Speaker: 

Benson Au

Institution: 

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.

Pages

Subscribe to RSS - Combinatorics and Probability