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

Interlacing Particle Systems and Special Functions

Speaker: 

Cesar Cuenta

Institution: 

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

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.

Finding perfect matchings in hypergraphs

Speaker: 

Asaf Ferber

Institution: 

UCI

Time: 

Tuesday, September 24, 2019 - 11:00am to 12:00pm

Host: 

Location: 

RH 340N

In this talk we will survey some open problems and recent results in probabilistic and extremal combinatorics related to finding perfect matchings in hypergraphs. The general plan (if time permits) is to motivate the general problem, discuss it for graphs, explain the difficulty when passing to hypergraphs, relate the basic problem to an unsolved probabilistic inequality which was conjectured by Feige, sketch some useful tools for tackling these problems, and report on some recent developments in the area.

A combinatorial approach to the quantitative invertibility of random matrices

Speaker: 

Vishesh Jain

Institution: 

MIT

Time: 

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

Host: 

Location: 

RH 340N

Let s_n(M) denote the smallest singular value of an n x n random (possibly complex) matrix M. We will discuss a novel combinatorial approach (in particular, not using either inverse Littlewood--Offord theory or net arguments) for obtaining upper bounds on the probability that s_n(M) is smaller than a given number for quite general random matrix models. Such estimates are a fundamental part of the non-asymptotic theory of random matrices and have applications to the strong circular law, numerical linear algebra etc. In several cases of interest, our approach provides stronger bounds than those obtained by Tao and Vu using inverse Littlewood-Offord theory. 

Eigenvalue gaps of sparse random matrices

Speaker: 

Kyle Luh

Institution: 

Harvard University

Time: 

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

Host: 

Location: 

RH 340N

We will discuss some recent work on quantifying the gaps between eigenvalues of sparse random matrices.  Before these results, it was not even known if the eigenvalues were distinct for this class of random matrices.  We will also touch upon how these results relate to random graphs, the graph isomorphism problem and nodal domains.  This is joint work with Van Vu and Patrick Lopatto.

Analyzing Hybrid Randomized and Greedy Projection Methods

Speaker: 

Jamie Haddock

Institution: 

UCLA

Time: 

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

Host: 

Location: 

RH 340N

Stochastic iterative algorithms have gained recent interest for solving large-scale systems of equations, Ax=y. One such example is the Randomized Kaczmarz (RK) algorithm, which acts only on single rows of the matrix A at a time. While RK randomly selects a row, Motzkin's algorithm employs a greedy row selection; meanwhile the Sampling Kaczmarz-Motzkin (SKM) algorithm combines these two strategies. In this talk, we present an improved convergence analysis for SKM which interpolates between RK and Motzkin's algorithm.  

Pages

Subscribe to RSS - Combinatorics and Probability