The phase transition in a random hypergraph (Q1612300): Difference between revisions

A \(d\)-uniform hypergraph \(H\) consists of a set \(V\) of \(n\) vertices and a family \({\mathcal E}\) of \(d\)-element subsets of \(V\) called edges. (Thus a graph is a 2-uniform hypergraph.) Two vertices \(u,v\in V\) are connected if there is a sequence of vertices \(v_{1},\dots v_{r-1}\) and edges \(e_{1},\dots e_{r}\) such that (writing \(u=v_{0}\) and \(v=v_{r}\) for convenience) we have \(\{v_{i},v_{i+1}\} \subseteq e_{i+1}\) for all \(0\leq i\leq (r-1)\). A set \(S\) of vertices is connected if every pair of vertices in \(S\) is connected. A component is a maximal connected subset of \(\{1,2\dots, n\}\): the order of a component is the number of vertices in it. The number of connected \(d\)-uniform hypergraphs with \(r=s(d-1)-k\) vertices and \(s\) edges will be denoted \(C_{d}(s,k)\). We say \(H\) is a tree if (in the same notation) \(k=s(d-1)-r\) is \(-1\), and that it is unicyclic if \(k=0\). (In all asymptotic estimates which follow, \(d\) should be regarded as fixed: thus implied constants are likely to depend on \(d\).) A random hypergraph \({\mathbb{G}}^{d}(n,M(n))\) is a hypergraph chosen uniformly and at random from the \(d\)-uniform labelled hypergraphs on vertex set \(\{1,2,\dots n\}\) and \(M(n)\) edges. We say that a random hypergraph has a certain property \(\wp\) a.a.s if \[ \lim_{n\rightarrow\infty}P\left( {\mathbb{G}}^{d}(n,M(n))\text{ has }\wp\right)=1. \] In the case \(d=2\), i.e. random graphs, a number of by now standard results, summarised in Chapter 6 of \textit{S. Janson, T. Łuczak and A. Ruciński} [Random graphs (Wiley, New York) (2000; Zbl 0968.05003)] show that if \(M(n)=cn\) then for \(c<1/2\) a.a.s. all components are trees or unicyclic, and their order is \(\log(n)\), but for \(c>1/2\) a.a.s one `giant'component, whose order is linear in \(n\), emerges. The situation for \(c\sim 1/2\) is more delicate. Let, for the rest of this review, \(m=m(n)\) be a function of \(n\) such that \(\lim_{n\to\infty} m/n^{2/3}=\infty\) but \(m=o(n)\). It turns out that if \(M=n/2-m\) then a.a.s. all largest components have roughly equal order, but if \(M=n/2+m\) then a.a.s. there is a unique largest component significantly larger than any other component. The first steps towards generalising these results to \({\mathbb{G}}^{d}(n,M)\) for values of \(d>2\) were taken in \textit{J. Schmidt-Pruzan and E. Shamir} [Combinatorica 5, 81-94 (1985; Zbl 0573.05042)]. There it was shown that the size of the largest component is as follows. For \(d\geq 2\), \(M=cn\) and \(c<1/(d(d-1))\), it is a.a.s of the order \(\log(n)\), for \(c=1/(d(d-1))\) it is a.a.s. of the order \(n(2/3)\), and for \(c>1/(d(d-1))\) it is a.a.s of the order \(n\). In the paper under review, the authors study the behaviour when \(M\sim n/(d(d-1))\). The case when \(M=n/(d(d-1))-m\) is not too hard. They first show that a.a.s. all components are either trees or unicyclic. This is done by showing that otherwise they must contain one of two types of structures, and then using the first moment method to show that a.a.s. these two structures are not present. Moreover, using results of \textit{B. I. Selivanov} [Enumeration of homogeneous hypergraphs with a simple cycle structure (in Russian), Komb. Anal. 2, 60-67 (1972)] concerning \(C_{d}(s,-1)\) and \(C_{d}(s,0)\), they obtain (for any fixed \(\ell\)) the limiting distribution of the number of edges in the \(\ell\)th largest unicyclic component of \({\mathbb{G}}^{d}(n,M)\), and the limiting distribution of the number of edges in the \(\ell\)th largest component of \({\mathbb{G}}^{d}(n,M)\) (which is a.a.s. a tree). These results easily imply that a.a.s. there is no component with more than \(n^{2/3}\) edges. The situation for \({\mathbb{G}}^{d}(n,M)\) with \(M=n/(d(d-1))+m\) is harder, and rather than obtaining results for all \(m(n)\) as above (as happens in the random graph case) the authors can only deal with the situation when (in addition to the previous assumptions on \(m\)) we have \(m(n)=o(n^{2/3}\log(n)/\log\log(n))\). For the values of \(M\) considered here, the largest component \(C\) of \({\mathbb{G}}^{d}(n,M)\) is a.a.s. unique. The authors show that \(C\) a.a.s. contains \((1+o(1))2dm/(d-1)\) edges and obtain asymptotics for the probability \(p_{s,k}\) that \(C\) has \(s\) edges and \(s(d-1)-k\) vertices for a certain range of values of \(s\) and \(k\). The proof uses detailed calculations, the fact noted at the end of the last paragraph of this review and an earlier result of the authors \textit{M. Karoński, T. Łuczak} [Discrete Math. 171, 153-167 (1997; Zbl 0876.05041)] concerning the asymptotics of \(C_{d}(n,k)\) for \(k=k(s)\) going to infinity slowly as a function of \(s\). A corollary of their result (which had not even been noted in the case \(d=2\) before) is the joint distribution of the number of edges in \(C\) and the number of vertices in \(C\) (which turns out, after normalisation, to be bivariate normal with correlation \(\sqrt{15}/5\)). They also conjecture that the restriction \(m(n)=o(n^{2/3}\log(n)/\log\log(n))\) can be removed. Finally, they give a local limit theorem for the size of the \(\ell\)th largest component (again \(\ell\) is fixed).