{"id":"arxiv/2603.01268","url":"https://arxiv.org/abs/2603.01268","tags":["cs.DS","cs.IT","math.PR","math.ST"],"score":0,"title":"Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection","domain":"cs.DS","source":"arxiv","authors":["Alexander Morgan","Chenghao Guo"],"reviews":0,"subject":"cs.DS","summary":"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 projected graph which combines random hyperedges across all degrees, where a projected edge appears if and only if both vertices appear in at least one hyperedge. Our goal is to reconstruct the original set of hyperedges of degree $d_j$ for some $j$. Our achievability result is based on the idea of selecting maximal cliques of size $d_j$ in the projected graph, and we show that this algorithm succeeds under a…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-01","reactions":{}}