Connectivity of random hypergraphs with a given hyperedge size distribution (Q6611000)

A hypergraph \(h=(V_{h},E_{h})\) is a set \(V_{h}=\{1,2,\ldots, n\}\) and a collection \(E_{h}\) of non-empty subsets of \(V_{h}\) called hyperedges. (When all hyperedges have order 2 this is a (simple) graph.) A hypergraph is connected if for every partition of \(V_{h}\) into \(V_{1}\) and \(V_{2}\) there is a hyperedge \(e\) with \(e\cap V_{1}\neq \emptyset\) and \(e\cap V_{2} \neq \emptyset\). This paper is about random hypergraphs, where a random (in a sense to be made precise) set of the hyperedges is present, and the question of when it is connected. While much previous work has focused instead on the case of when a giant component emerges when all hyperedges are of the same order, the present paper, motivated by applications in community detection, deals with the full connectivity threshold and is more interested in the case where there are a range of hyperedge sizes.\N\NThe model in detail is as follows. The empirical hyperedge size distribution of a hypergraph is the probability mass function on \(\{1,2,\ldots, n\}\) \(f(x)=\vert E_{h}\vert^{-1}\sum_{e\in E_{h}}\delta_{e}(x)\) where \(\delta_{e}(x)=1\) if \(x=e\) and is otherwise 0. We now let \(\mathcal{H}_{nmf}\) denote the set of all hypergraphs with vertex set \(\{1,2,\ldots, n\}\), \(m=m_{n}\) edges and empirical hyperedge size distribution \(f=f_{n}\). This set is non-empty precisely when for every \(1\leq i\leq n\) we have \(mf(i)\) is an integer and \(\leq \binom{n}{i}\). In this case, say that \(H_{nmf}\) is a hypergraph sampled uniformly at random from \(\mathcal{H}_{nmf}\).\N\NThe first main result (Theorem 2.1) is a threshold condition for \(H_{nmf}\) to be connected. The criterion depends on the moments \((f)_{r}=\sum_{r=2}^{n}x^{r}f(x)\) (noting that hyperedges of size 1 do not affect connectivity). Specifically, if \(\sum_{i=1}^{n}\binom{n}{i}^{-1}f(i)^{2} \ll m^{-2}\) and \((f)_{0}\lesssim (f)_{2}\) then if \(\log(n)-(m/n)(f)_{1}\rightarrow \infty\) as \(n\rightarrow\infty\) we have \(\mathbb{P}(H_{nmf}\text{ is connected})\rightarrow 0\): however if instead \(\log(n)-(m/n)(f)_{1}\rightarrow -\infty\) as \(n\rightarrow\infty\) we instead get \(\mathbb{P}(H_{nmf}\text{ is connected})\rightarrow 1\). This can be thought of as saying that subject to fairly mild regularity conditions the average hyperedge size suffices to characterise connectivity, with other characteristics such as heavy tails or higher moments not being relevant. Not dissimilar results have been found in studies of the giant component in random graphs.\N\NTheorem 2.1. already implies a result for the case where all hyperedges are of a fixed size \(d\) -- call the random hypergraph \(H_{nmd}\) here -- provided that size is bounded and \(m\ll \binom{n}{d}^{1/2}\), however the authors also prove a result (Theorem 2.2) for the case where \(2\leq d\leq n\) is allowed to be unbounded. That result is that \(\mathbb{P}(H_{nmd}\text{ is connected})\rightarrow 0\) if \(\log(n)+m \log(1-d/n)\rightarrow \infty\) but \(\mathbb{P}(H_{nmd}\text{ is connected})\rightarrow 1\) if \(\log(n)+m \log(1-d/n)\rightarrow -\infty\).\N\NOther (related) results in the paper include on the connectivity of so-called passive intersection graphs (and here an example (3.3) is given to show that some mild regularity condition is needed). The results depend on results on so-called shotgun random hypergraphs. Much of the work in the proofs focuses on controlling the number of isolated vertices, an obvious obstruction to connectivity.