Longest increasing and decreasing subsequences

Speaker: 

Richard Stanley

Institution: 

University of Miami

Time: 

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

Host: 

Location: 

RH 306

An increasing subsequence of a permutation $a_1, a_2,\dots, a_n$ of 
$1,2,\dots, n$ is a subsequence $b_1,b_2,\dots,b_k$ satisfying 
$b_1<b_2<\cdots<b_k$, and similarly for decreasing subsequence. The 
earliest result in this area is due to Erd\H{o}s and Szekeres in 1935: any 
permuation of $1,2,\dots,pq+1$ has an increasing subsequnce of length 
$p+1$ or a decreasing subsequence of length $q+1$. This result turns out 
to be closely connected to the RSK algorithm from the representation 
theory of the symmetric group. A lot of work has been devoted to the 
length $k$ of the longest increasing subsequence of a permutation 
$1,2,\dots,n$, beginning with Ulam's question of determining the average 
value of this number over all such permutations, and culminating with the 
result of Baik-Deift-Johansson on the limiting distribution of this 
length. There are many interesting analogues of longest increasing 
subsequences, such as longest alternating subsequences, i.e., 
subsequences $b_1,b_2,\dots, b_k$ of a permutation $a_1, a_2,\dots, a_n$ 
satisfying $b_1>b_2<b_3>b_4<\cdots$. The limiting distribution of the 
length of the longest alternating subsequence of a random permutation 
behaves very differently from the length of the longest increasing 
subsequence.  We will survey these highlights from the theory of 
increasing and decreasing subsequences.

Random matrix point processes via stochastic processes

Speaker: 

Elliot Paquette

Institution: 

The Ohio State University

Time: 

Thursday, January 10, 2019 - 12:00pm to 1:00pm

Location: 

RH 340P

In 2007, Virág and Válko introduced the Brownian carousel, a dynamical system that describes the eigenvalues of a canonical class of random matrices. This dynamical system can be reduced to a diffusion, the stochastic sine equation, a beautiful probabilistic object requiring no random matrix theory to understand. Many features of the limiting eigenvalue point process, the Sine--beta process, can then be studied via this stochastic process. We will sketch how this stochastic process is connected to eigenvalues of a random matrix and sketch an approach to two questions about the stochastic sine equation: deviations for the counting Sine--beta counting function and a functional central limit theorem.

Based on joint works with Diane Holcomb, Gaultier Lambert, Bálint Vet\H{o}, and Bálint Virág.

Stochatically modeled reaction networks : positive recurrence and mixing times.

Speaker: 

Jinsu Kim

Institution: 

UCI

Time: 

Tuesday, December 4, 2018 - 11:00am to 12:00pm

Host: 

Location: 

306 RH

 

A reaction network is a graphical configuration that describes an interaction between species (molecules). If the abundances of the network system is small, then the randomness inherent in the molecular
interactions is important to the system dynamics, and the abundances are modeled stochastically as a jump by jump fashion continuous-time Markov chain. One of challenging issues facing researchers who study biological

systems is the often extraordinarily complicated structure of their interaction networks. Thus, how to characterize network structures that induce characteristic behaviors of the system dynamics is one of the major open questions in this literature.

In this talk, I will provide an analytic approach to find a class of reaction networks whose associated Markov process has a stationary distribution. Moreover I will talk about the convergence rate for the process to its stationary distribution with the mixing time.

On the smallest singular value of unstructured heavy-tailed matrices

Speaker: 

Galyna Livshyts

Institution: 

Georgia Tech

Time: 

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

Host: 

Location: 

RH 306

In this talk we discuss questions related to invertibility of random matrices, and the estimates for the smallest singular value. We outline the main results: an optimal small-ball behavior for the smallest singular value of square matrices under mild assumptions, and an essentially optimal small ball behavior for heavy-tailed rectangular random matrices. We make several remarks and outline some examples. We then explain the relation between such estimates and net constructions, and outline our main result in regards to existence of a net around the sphere with good properties. If time permits, we outline two more implications of this result.

The diffusion analogue to a tree-valued Markov chain.

Speaker: 

Noah Forman

Institution: 

University of Washington

Time: 

Friday, November 16, 2018 - 1:00pm to 2:00pm

Host: 

Location: 

340P

 

 

In '99, David Aldous conjectured that a certain natural "random walk" on the space of binary combinatorial trees should have a continuum analogue, which would be a diffusion on the Gromov-Hausdorff space of continuum trees. This talk discusses ongoing work by F-Pal-Rizzolo-Winkel that has recently verified this conjecture with a path-wise construction of the diffusion. This construction combines our work on dynamics of certain projections of the combinatorial tree-valued random walk with our previous construction of interval-partition-valued diffusions.

Minimal Gaussian partitions, clustering hardness and voting

Speaker: 

Steven Heilman

Institution: 

USC

Time: 

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

Host: 

Location: 

RH 306

A single soap bubble has a spherical shape since it minimizes its surface area subject to a fixed enclosed volume of air.  When two soap bubbles collide, they form a “double-bubble” composed of three spherical caps.  The double-bubble minimizes total surface area among all sets enclosing two fixed volumes.  This was proven mathematically in a landmark result by Hutchings-Morgan-Ritore-Ros and Reichardt using the calculus of variations in the early 2000s.  The analogous case of three or more Euclidean sets is considered difficult if not impossible.  However, if we replace Lebesgue measure in these problems with the Gaussian measure, then recent work of myself (for 3 sets) and of Milman-Neeman (for any number of sets) can actually solve these problems.  We also use the calculus of variations.  Time permitting, we will discuss an improvement to the Milman-Neeman result and applications to optimal clustering of data and to designing elections that are resilient to hacking.  http://arxiv.org/abs/1901.03934

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

Pages

Subscribe to RSS - Combinatorics and Probability