[edit]

# Thresholds for Reconstruction of Random Hypergraphs From Graph Projections

*Proceedings of Thirty Seventh Conference on Learning Theory*, PMLR 247:632-647, 2024.

#### Abstract

The graph projection of a hypergraph is a simple graph with the same vertex set and with an edge between each pair of vertices that appear in a hyperedge. We consider the problem of reconstructing a random $d$-uniform hypergraph from its projection. Feasibility of this task depends on $d$ and the density of hyperedges in the random hypergraph. For $d=3$ we precisely determine the threshold, while for $d\geq 4$ we give bounds. All of our feasibility results are obtained by exhibiting an efficient algorithm for reconstructing the original hypergraph, while infeasibility is information-theoretic. Our results also apply to mildly inhomogeneous random hypergrahps, including hypergraph stochastic block models. A consequence of our results is that claims from the 2023 COLT paper gaudio’23 are disproved.