Bela Bollobas

(Mathematics, Cambridge, UK & Memphis, TN, USA)

Phase transitions and local limit theorems

Date Friday, October 3, 2014

For $nge rge 2$ and $0<p<1$, let $H^r_{n,p}$ be the random $r$-uniform hypergraph with vertex set $[n]={1,2, dots ,n}$ in which each of the $nchoose r$ possible hyperedges is present independently with probability $p$, and normalize by writing $p=p(n)=lambda (r-2)!n^{-r+1}$ where $lambda=lambda(n)$.

The random hypergraph $H^r_{n,p}$ undergoes a phase transition at $lambda=1$, where a giant component first emerges, as shown by Erdös and Rényi in the graph case. For $lambda>1$ constant, Behrisch, Coja-Oghlan and Kang not only found the asymptotic order of the giant component, but proved joint central and local limit theorems for its order (number of vertices) and size (number of edges). Their local limit result gives an asymptotic formula for the probability that the order and size take any pair of values in the `typical' range, and easily translates to an asymptotic formula for the number of connected hypergraphs with a given number of vertices and a given `excess' or `nullity' which is of the same order as the number of vertices.

System Message: WARNING/2 (<string>, line 3); backlink

Inline interpreted text or phrase reference start-string without end-string.

System Message: WARNING/2 (<string>, line 3); backlink

Inline interpreted text or phrase reference start-string without end-string.

System Message: WARNING/2 (<string>, line 3); backlink

Inline interpreted text or phrase reference start-string without end-string.

As in the graph case, the situation when $lambdato 1$ from above is much more delicate. In joint work with Oliver Riordan we have managed to extend the bivariate local limit result to the rest of the supercritical regime, i.e., when $lambda(n)=1+varepsilon(n)$ with $varepsilon=o(1)$ and $varepsilon^3ntoinfty$. This leads to an asymptotic formula for the number of connected hypergraphs with a given number $n$ of vertices and given excess $ell$, whenever $ell=o(n)$ and $elltoinfty$. Our formula extends the one proved by Karonski and Luczak in 1997 by direct enumerative methods.

In this talk I shall survey some of the results concerning phase transitions and local limit theorems, and describe a number of methods used to prove them, going into very little detail and keeping the presentation very simple.