Thresholds for Reconstruction of Random Hypergraphs From Graph Projections

Guy Bresler, Chenghao Guo, Yury Polyanskiy

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 o…