Detecting Arbitrary Planted Subgraphs in Random Graphs
Dor Elimelech Wasim Huleihel · 2025
Read Detecting Arbitrary Planted Subgraphs in Random Graphs by Dor Elimelech Wasim Huleihel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19069.txt.
Introduction
Dor Elimelech and Wasim Huleihel build a general theory for spotting a hidden subgraph inside a random graph, in a 2025 mathematics paper. Planted structure problems ask whether a dense little pattern was secretly added to random noise. Past work handled one pattern at a time. Here the planted piece can be any graph, inside a standard random graph where edges inside the plant are more likely.
The pair pin down the exact thresholds where detection becomes possible, both for any algorithm and for fast ones. In the dense case, only three traits of the plant matter: its edge count, its maximum degree, and its densest piece. Their bounds stay tight across sparse and near-complete regimes studied before. They also find when detection flips sharply from impossible to easy.
Catalog record
| CREATOR | Dor Elimelech Wasim Huleihel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 302 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-19069