3 papers
cs.DS2026
Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection
Alexander Morgan, Chenghao Guo
We formulate and analyze a heterogeneous random hypergraph model, and we provide an achieveability result for recovery of hyperedges from the observed projected graph. We observe a…
math.CO2025
Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
Guy Bresler, Chenghao Guo, Yury Polyanskiy +1
Consider a -uniform random hypergraph on vertices in which hyperedges are included iid so that the average degree is . The projection of a hypergraph is a graph on the…
math.ST2025
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…