Edge universality of separable covariance matrices

Speaker: 

Fan Yang

Institution: 

UCLA

Time: 

Tuesday, November 20, 2018 - 11:00am to 12:00pm

 

 In this talk, we consider the largest singular value of the so-called separable covariance matrix Y=A^{1/2}XB^{1/2}, where X is a random matrix with i.i.d. entries and A, B are deterministic covariance matrices (which are non-negative definite symmetric). The separable covariance matrix is commonly used in e.g. environmental study, wireless communications and financial study to model sampling data with spatio-temporal correlations. However, the spectral properties of separable covariance matrices are much less known compared with sample covariance matrices.  

 

Recently, we prove that the distribution of the largest singular value of Y converges to the Tracy-Widom law under the minimal moment assumption on the entries of X. This is the first edge universality result for separable covariance matrices. As a corollary, if B=I, we obtain the edge universality for sample covariance matrices with correlated data and heavy tails. This improves the previous results for sample covariance matrices, which usually assume diagonal A or high moments of the X entries. The core parts of the proof are two comparison arguments: the Lindeberg replacement method, and a continuous self-consistent comparison argument.

Universality and Delocalization of Random Band Matrices

Speaker: 

Jun Yin

Institution: 

UCLA

Time: 

Tuesday, November 6, 2018 - 11:00am to 12:00pm

Location: 

RH 306

We consider N × N symmetric one-dimensional random band matrices with general distribution of the entries and band width $W$.   The localization - delocalization conjecture predicts that there is a phase transition on the behaviors of  eigenvectors and  eigenvalues of the band matrices. It occurs at $W=N^{1/2}$. For wider-band matrix, the eigenvalues satisfied the so called sine-kernal distribution, and the eigenvectors are delocalized. With Bourgade, Yau and Fan, we proved that it holds when $W\gg N^{3/4}$. The previous best work required $W=\Omega(N).$ 

 

On 1-factorizations of graphs

Speaker: 

Asaf Ferber

Institution: 

MIT

Time: 

Tuesday, October 30, 2018 - 11:00am to 12:00pm

Host: 

Location: 

RH 306

A 1-factorization of a graph G is a partitioning of its edges into perfect matchings. Clearly, if a graph G admits a 1-factorization then it must be regular, and the converse is easily verified to be false. In the special case where G is bipartite, it is an easy exercise to show that G has a 1-factorization, and observe that a 1-factorization corresponds to a partial Latin Square.  

In this talk we survey known results/conjectures regarding the existence and the number of 1-factorizations in graphs and the related problem about the existence of a proper edge coloring of a graph with exactly \Delta(G) colors.  Moreover, we prove that every `nice' d-regular pseudorandom graph has a 1-factorization. In particular, as a corollary, we obtain that for every d=\omega(1), a random d-regular graph typically has a 1-factorization.  This extends and completely solves a problem of Molloy, Robalewska, Robinson, and Wormald  (showed it for all constant d greater than or equal to 3).

 

Joint with: Vishesh Jain (PhD student in MIT).

Large deviations of subgraph counts for sparse random graphs

Speaker: 

Nicholas Cook

Institution: 

UCLA

Time: 

Tuesday, November 27, 2018 - 11:00am to 12:00pm

Location: 

RH 306

In their breakthrough 2011 paper, Chatterjee and Varadhan established a large deviations principle (LDP) for the Erdös-Rényi graph G(N,p), viewed as a measure on the space of graphons with the cut metric topology. This yields LDPs for subgraph counts, such as the number of triangles in G(N,p), as these are continuous functions of graphons. However, as with other applications of graphon theory, the LDP is only useful for dense graphs, with p ϵ (0,1) fixed independent of N. 

Since then, the effort to extend the LDP to sparse graphs with p ~ N^{-c} for some fixed c>0 has spurred rapid developments in the theory of "nonlinear large deviations". We will report on recent results increasing the sparsity range for the LDP, in particular allowing c as large as 1/2 for cycle counts, improving on previous results of Chatterjee-Dembo and Eldan. These come as applications of new quantitative versions of the classic regularity and counting lemmas from extremal graph theory, optimized for sparse random graphs. (Joint work with Amir Dembo.)

Lower-tail large deviations of the KPZ equation

Speaker: 

Li-Cheng Tsai

Institution: 

Columbia University

Time: 

Tuesday, October 23, 2018 - 11:00am to 12:00pm

Host: 

Location: 

306 RH

Regarding time as a scaling parameter, we prove the one-point, lower tail Large Deviation Principle (LDP) of the KPZ equation, with an explicit rate function. This result confirms existing physics predictions. We utilize a formula from [Borodin Gorin 16] to convert LDP of the KPZ equation to calculating an exponential moment of the Airy point process, and analyze the latter via stochastic Airy operator and Riccati transform.

Pages

Subscribe to RSS - Combinatorics and Probability