The distribution of the number of node neighbors in random hypergraphs (Q2843755)

The notion of hypergraph is a generalization of graphs, where instead of a set of edges we have a set of nodes (called hyperedges) that connect subsets of vertices (rather than only two edges at a time). The rank of a node is the number of vertices involved in the node, so that usual graphs are hypergraphs of uniform rank 2. This work considers random hypergraphs with nodes of uniform rank \(k \geq 2\), where each possible hyperedge is present with some uniform probability \(p\). The author computes the distribution of the number of neighbors of an edge. Since unlike in the graph case, there is some overlap between hyperedges, this number is not the same as the degree of the vertices, and the computation becomes harder. The proof is based on computing the number of ways a given number of hyperedges with fixed rank may connect exactly \(k\) vertices to a given vertex. The author also explicits the asymptotics of the distribution in the sparse and dense regimes.