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

CREATORDor Elimelech Wasim Huleihel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE302 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19069

Browse the full library · About the Tower of Babel