{"id":"df175c24-9a38-4977-882e-839b4a14b7f9","arxiv_id":"2505.14138","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The optimal induced-subgraph sample size for detecting correlation in the Gaussian Wigner model is s ≈ sqrt(max(n log n / log(1/(1-ρ^2)), n)).","lead":"This paper finds the smallest number of vertices to sample from each of two large correlated random graphs so that their hidden relationship can be detected without knowing the vertex correspondence. The required sample size is about the square root of the graph size, with a larger factor when the correlation is weak.","discovery_kind":"new_application","skeptic_critique":null,"referee_report":null,"author_rebuttal":null,"desk_editor":null,"rs_alignment":null,"lean_confirmation":null,"pith_extraction":null,"created_at":"2026-08-07T15:45:18.065057+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":null,"supporting_citations":[],"review_version":1}