Spectral recovery of a planted triangle-dense subgraph

Benjamin McKenna; Cheng Mao; Sam van der Poel

arxiv: 2606.17604 · v1 · pith:B7CUS2JAnew · submitted 2026-06-16 · 💻 cs.DS · math.PR· math.ST· stat.TH

Spectral recovery of a planted triangle-dense subgraph

Sam van der Poel , Cheng Mao , Benjamin McKenna This is my paper

Pith reviewed 2026-06-26 22:19 UTC · model grok-4.3

classification 💻 cs.DS math.PRmath.STstat.TH

keywords spectral recoveryplanted subgraphtriangle denseErdős-Rényi graphsemidefinite programcomputational thresholdgraph matrixsigned triangle counts

0 comments

The pith

A matrix of local signed triangle counts lets spectral methods recover a planted triangle-dense subgraph in a random graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines recovering a k-vertex subgraph that is dense in triangles after it is planted inside an Erdős-Rényi random graph on n vertices. It introduces a spectral algorithm and a semidefinite program that both operate on a matrix whose entries are the local signed triangle counts between pairs of vertices. Spectral analysis of this matrix yields recovery guarantees, and the work supplies evidence of a statistical-to-computational gap in which efficient algorithms require k at least on the order of sqrt(n) while information-theoretic recovery remains possible down to logarithmic k.

Core claim

The authors establish that the matrix of local signed triangle counts carries a spectral signal from the planted subgraph sufficient for recovery by spectral methods and SDP, with the computational threshold for recovery at least on the order of sqrt(n) while the information-theoretic threshold is at most logarithmic in n.

What carries the argument

The matrix whose entries are local signed triangle counts; it aggregates local triangle information to produce a bias that spectral methods can detect.

If this is right

The algorithms recover the subgraph when its size k is large enough for the triangle-count matrix to exhibit a detectable spectral gap.
Recovery is computationally feasible for k at least sqrt(n) but remains information-theoretically possible for k as small as log n.
The same statistical-to-computational gap appears here as in the planted-clique problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Higher-order counts such as triangles can generate stronger recovery signals than edge counts alone in planted subgraph problems.
The matrix construction may extend to recovery tasks involving other dense motifs in random graphs.
The gap indicates that low-degree methods are limited, suggesting inherent computational hardness below sqrt(n).

Load-bearing premise

The planted triangle-dense subgraph produces a signal in the local signed triangle count matrix that is distinguishable from the random graph noise by spectral methods.

What would settle it

If the leading eigenvector of the triangle-count matrix shows no correlation with the planted vertices when k is around sqrt(n), the recovery guarantee would fail.

read the original abstract

Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on $k$ vertices is planted in an Erd\H{o}s-R\'enyi random graph on $n$ vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program, both of which use a graph matrix whose entries are local signed triangle counts. Theoretical guarantees for these algorithms are established through spectral analysis of the graph matrix. Finally, we provide evidence showing a statistical-to-computational gap analogous to that for the planted clique problem. The computational threshold in terms of the subgraph size $k$ is at least $\sqrt{n}$ in the framework of low-degree polynomial algorithms, while the information-theoretic threshold is at most logarithmic in $n$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a signed-triangle-count matrix for spectral and SDP recovery of a planted triangle-dense subgraph, plus an explicit stat-comp gap at sqrt(n) versus log n.

read the letter

The main thing is the matrix whose entries are local signed triangle counts. They run a simple spectral method and an SDP on it to recover the planted k-set inside an ER graph when the planted part is triangle-dense.

This construction is new relative to standard adjacency spectral methods; the triangle counts supply the signal that fits the model. The paper works out the spectral analysis to get recovery guarantees and states the low-degree lower bound at k ~ sqrt(n) while information-theoretic recovery reaches down to log n. That gap statement is clean and directly analogous to planted clique but applied here.

The paper does well by defining the matrix explicitly, giving two algorithms, and tying everything to the average-case model without obvious circularity. The approach stays grounded in existing spectral techniques.

Soft spots are minor. The triangle-dense assumption is built into the planting process rather than derived, which narrows the model but matches the problem statement. Exact dependence on the background edge probability p should be checked in the proofs for the full range of parameters. Nothing load-bearing looks broken from the description.

This is for people working on planted subgraph recovery and average-case graph algorithms. A reader interested in spectral methods or stat-comp gaps gets concrete value from the matrix and the threshold claims. I would send it to peer review.

Referee Report

1 major / 0 minor

Summary. The paper studies the triangle-densest-k-subgraph problem in an average-case model by planting a triangle-dense subgraph on k vertices inside an Erdős-Rényi graph on n vertices. It proposes a spectral algorithm and an SDP that both operate on a matrix whose entries are local signed triangle counts, claims theoretical recovery guarantees established via spectral analysis of this matrix, and supplies evidence for a statistical-to-computational gap (computational threshold at least √n under low-degree polynomial algorithms; information-theoretic threshold at most logarithmic in n).

Significance. If the claimed guarantees and gap evidence hold, the work would extend signed-adjacency spectral techniques to the triangle-dense setting and exhibit a stat-comp gap mirroring the planted-clique case, which is of interest for average-case subgraph recovery.

major comments (1)

Abstract: the abstract asserts theoretical guarantees via spectral analysis and evidence for a gap, yet supplies none of the actual theorems, parameter regimes, or proof sketches; without these details the support for the central claims cannot be evaluated.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their feedback. We address the single major comment below.

read point-by-point responses

Referee: Abstract: the abstract asserts theoretical guarantees via spectral analysis and evidence for a gap, yet supplies none of the actual theorems, parameter regimes, or proof sketches; without these details the support for the central claims cannot be evaluated.

Authors: We agree that the abstract is high-level and does not include explicit theorem statements or parameter regimes. In the revised version we will expand the abstract to state the main recovery guarantee (exact recovery of the planted subgraph with high probability when k = Ω(√n log n) or similar, depending on the precise threshold derived), the information-theoretic threshold of O(log n), and the low-degree computational lower bound of Ω(√n), along with a one-sentence description of the signed-triangle matrix used in the spectral and SDP analyses. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation constructs a new matrix whose entries are local signed triangle counts, then invokes standard spectral norm bounds and SDP analysis on that matrix to obtain recovery guarantees. No step reduces a claimed prediction to a fitted parameter by construction, no load-bearing uniqueness theorem is imported via self-citation, and the low-degree polynomial lower bound is an external framework rather than an internal tautology. The planted model and matrix definition are independent of the recovery claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the average-case planted model and the assumption that the signed triangle count matrix yields a usable signal; no free parameters, additional axioms, or invented entities are stated in the abstract.

axioms (1)

domain assumption A triangle-dense subgraph is planted inside an Erdős-Rényi random graph.
This is the generative model under which recovery is studied.

pith-pipeline@v0.9.1-grok · 5700 in / 1208 out tokens · 41343 ms · 2026-06-26T22:19:20.437588+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 3 canonical work pages

[1]

Graph matrices: Norm bounds and applications.arXiv preprint arXiv:1604.03423,

Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. Graph matrices: Norm bounds and applications.arXiv preprint arXiv:1604.03423,

work page arXiv
[2]

Random Structures and Algo- rithms

Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. InProceedings of the Eighth International Conference “Random Structures and Algo- rithms” (Poznan, 1997), volume 13, pages 457–466,

1997
[3]

Detecting high log-densities—anO(n 1/4)approximation for densestk-subgraph

Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log-densities—anO(n 1/4)approximation for densestk-subgraph. InSTOC’10— Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 201–210. ACM, New York,

2010
[4]

Exponential and moment inequalities forU-statistics

Evarist Gin´e, Rafał Latała, and Joel Zinn. Exponential and moment inequalities forU-statistics. In High dimensional probability, II (Seattle, WA, 1999), volume 47 ofProgr. Probab., pages 13–38. Birkh¨auser Boston, Boston, MA,

1999
[5]

Seshadhri

Rishi Gupta, Tim Roughgarden, and C. Seshadhri. Decompositions of triangle-dense graphs. In ITCS’14—Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science, pages 471–481. ACM, New York,

2014
[6]

Random geometric graphs with smooth kernels: sharp detection threshold and a spectral conjecture.arXiv preprint arXiv:2602.14998,

Cheng Mao, Yihong Wu, and Jiaming Xu. Random geometric graphs with smooth kernels: sharp detection threshold and a spectral conjecture.arXiv preprint arXiv:2602.14998,

work page arXiv
[7]

Concentration of polynomial random matrices via Efron- Stein inequalities

Goutham Rajendran and Madhur Tulsiani. Concentration of polynomial random matrices via Efron- Stein inequalities. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pages 3614–3653. SIAM,

2023
[8]

High-dimensional statistics.arXiv preprint arXiv:2310.19244,

Philippe Rigollet and Jan-Christian H ¨utter. High-dimensional statistics.arXiv preprint arXiv:2310.19244,

work page arXiv
[9]

Local triangle-densest subgraphs

Raman Samusevich, Maximilien Danisch, and Mauro Sozio. Local triangle-densest subgraphs. In 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 33–40. IEEE,

2016
[10]

Additional proofs for the spectral method Continuing from Section 3, we bound each of the terms in (13) to prove Proposition 3.2

Appendix A. Additional proofs for the spectral method Continuing from Section 3, we bound each of the terms in (13) to prove Proposition 3.2. A.1. Analyzing the signal term To analyze the matrixK2 ◦K, we first show that it is close to(XX⊤)◦(XX ⊤)up to normalization. Lemma A.1There is an absolute constantC >0such that the following holds for anyδ∈(0,1). If...

2023
[11]

Moreover, letH d ℓ denote the space of real harmonic polynomials of degreeℓonR d

CD 2 (t). Moreover, letH d ℓ denote the space of real harmonic polynomials of degreeℓonR d. By Corol- lary 1.1.4 in Dai and Xu (2013),dimH d 0 = 1and m:= dimH d 2 = d+ 1 2 −1.(19) Letϕ 0 ≡1, and letϕ 1, . . . , ϕm be an orthonormal basis ofH d 2 . The addition formula for spherical harmonics, (1.2.8) in Dai and Xu (2013), states that D+ 2 D CD 2 (X ⊤ i Xj...

2013
[12]

ProofThe first statement holds by the definition ofQ

log 2(m+1) δ k . ProofThe first statement holds by the definition ofQ. To bound the norm, we note that ∥YΛY⊤ −QΛQ ⊤∥=∥QRΛR ⊤Q⊤ −QΛQ ⊤∥=∥RΛR ⊤ −Λ∥. In the QR decompositionY=QR, the first columns ofYandQare the same andRis upper triangular, so the first column ofRise 1, the first standard basis vector inR m+1. Moreover,Λ 22 = · · ·=Λ m+1,m+1 from Lemma A.2....

2019
[13]

The proof of this goes as in (22); since Wisn×nwhereasW [k] isk×k, we just replacekwithneverywhere in the argument

Moreover, by Theorem F.1 and Lemma A.4, for an absolute constantC 1 >0, ∥W∥ ≤C 1 p np+ log(n/δ)(23) with probability at least1−δ, as long asnp≥Clog(2n/δ). The proof of this goes as in (22); since Wisn×nwhereasW [k] isk×k, we just replacekwithneverywhere in the argument. The result then follows. Lemma A.7There is an absolute constantC >0such that the follo...

2012
[14]

• d2 p3k2 n1/2plogn: Since d k ≤ p3/4 C√n, we have d2 p3k2 n1/2plog(n)≤ n1/2 log(n) p2 · p3/2 C2n = log(n) C2(np)1/2 = 1 C2 · log2(n) np 1/2

• d2 p3k2 np3/2: The assumptionk≥C √nd/p3/4 is sufficient. • d2 p3k2 n1/2plogn: Since d k ≤ p3/4 C√n, we have d2 p3k2 n1/2plog(n)≤ n1/2 log(n) p2 · p3/2 C2n = log(n) C2(np)1/2 = 1 C2 · log2(n) np 1/2 . Previously we showed that, under our main assumption, we havenp 3/2 ≥C, so thatp≥ Cn−2/3. This means thatnp≥Cn 1/3, and thuslog 2(n)/(np) =o(1). 24 SPECTRA...

2023
[15]

Using the fact that∥Z 2 jr ∥∞ ≤1,EZ 2 jr ≤K, andVar[Z 2 jr]≤K, Bernstein’s inequality implies that for allr∈[n]\ {i}, the event X j∈[n]\{i,r} Z2 jr ≲nK+ r nKlog n δ + log n δ ≲nK(24) occurs with probability at least1−δ/n, using the assumptionnK≥log(n/δ). Hence by applying (24)ntimes (n−1times corresponding with the indexesr∈[n]\ {i}and once to the sum ove...

2012
[16]

We can rewrite S= X 2≤j,l≤k j̸=l ⟨X1, Xj⟩⟨X1, Xl⟩⟨Xj, Xl⟩.(33) Define the centered kernelh: (S d−1)2 →Rby h(x, y) :=⟨X 1, x⟩⟨X1, y⟩⟨x, y⟩ − 1 d ⟨X1, x⟩2 − 1 d ⟨X1, y⟩2 + 1 d2 .(34) ForY∼Unif(S d−1)and any fixedx∈S d−1, we have EY [⟨X1, x⟩⟨X1, Y⟩⟨x, Y⟩ |X 1] =⟨X 1, x⟩ ·X ⊤ 1 E[Y Y ⊤]x= 1 d ⟨X1, x⟩2 , EY [⟨X1, Y⟩ 2 |X 1] = 1 d ⟨X1, X1⟩2 = 1 d , which implie...

2018
[17]

Equation (35) shows that, conditional onX 1, the kernel his canonical in the sense needed to apply (Gin ´e et al., 2000, Theorem 3.3). This result is written in terms of various norms and expectations ofh, which we now estimate using the simpler forms of A,B,C, andDappearing before (Gin ´e et al., 2000, Corollary 3.4). Bound forA.It is easy to see thatA=∥...

2000
[18]

extractsj

+O 1 d2 ≤ C d2 .(40) The same estimate holds withxandYinterchanged, hence B2 = (k−1) ∥EY h(·, Y) 2∥∞ +∥E X h(X,·) 2∥∞ ≲ k d2 , 34 SPECTRALRECOVERY OF APLANTEDTRIANGLE-DENSESUBGRAPH where the implicit constant is universal. Similarly, taking expectation of (40) overx=Xand using E[⟨X1, X⟩2] = 1/dgivesE[h(X, Y) 2]≲1/d 3, which implies C2 = (k−1) 2 E[h(X, Y) ...

2000
[19]

Hence it follows from Lemma C.4 (applied withδ/2andn=k) that |S1|≲ pk√ d log k δ + r pk d log2 k δ with probability at least1−δ/2

First note thatS 1 is preciselySas defined in (45), except with the sum over l∈[k]instead ofj∈[n]. Hence it follows from Lemma C.4 (applied withδ/2andn=k) that |S1|≲ pk√ d log k δ + r pk d log2 k δ with probability at least1−δ/2. We will now bound|S 2|. Letc >0be the constant from the decoupling inequality for order-2 kernels (Theorem 3.4.1 in de la Pe˜na...

2012
[20]

The following lemma now follows from the proof of Theorem 2.2 of Schramm and Wein (2022) (see also p

S i B i = X β⊆α E h 1{α\ S 2 =β} · ¯Aα∩(S 2)i · ¯Bβ = X β⊆α Mαβ ¯Bβ , where Mαβ :=E h 1 α\ S 2 =β · ¯Aα∩(S 2)i . The following lemma now follows from the proof of Theorem 2.2 of Schramm and Wein (2022) (see also p. 17 of the technical appendix). Lemma D.1 (Schramm and Wein (2022))LetAandBbe as defined above. SupposeM αα ̸= 0 for allα⊆ [n] 2 with|α| ≤D. Th...

2022
[21]

Finally we bound|E[ ¯Aα ·θ]|

S ii =P α\ S 2 =β · |E ¯Aα |V(α)⊆ S | =P α\ S 2 =β · E Y ij∈α Aij −pp p(1−p) =P α\ S 2 =β · p 1−p |α|/2 E Y ij∈α ⟨Xi, Xj⟩ ≤P α\ S 2 =β ≤r |V(α\β)| . Finally we bound|E[ ¯Aα ·θ]|. LetX 1, . . . , X|V(α)| be i.i.d. uniformly distributed on the sphereSd−1. SinceE ¯Aα | S ·θ̸= 0only ifV(α)∪ {1} ⊆ S, we have E[ ¯Aα ·θ] =E S E ¯Aα | S ·θ =P{V(α)∪ {1} ⊆ S} ·E ¯A...

2022
[22]

Thus in the remainder we may assumek=o(n), where ˆSis defined by (7)

then|S ∗ ∩ ˆS| ≥ϵkwith high probability (recall ˆSis defined as a randomk-subset of[n]when k= Θ(n)). Thus in the remainder we may assumek=o(n), where ˆSis defined by (7). For all subsetsA, B, C⊆[n]define τ(A, B, C) := X i∈A,j∈B,l∈C ¯Aij ¯Ajl ¯Ali and writeτ(A)≡τ(A, A, A). Moreover, define T1(A) :=τ(A,S ∗ \A,S ∗ \A), T 2(A) :=τ(A, A,S ∗ \A), T 3(A) :=τ(A),...

2013
[23]

To apply Theorem 2.1 from Janson (2004), note that the maximum degree of the dependency graph of the random variables{ ¯Aij ¯Ajl ¯Ali}i∈B,j,l∈S ∗\A (conditional onX) is at most3k

Notice thatE[T 4 |X] = 0with probability 1, since for 47 VAN DERPOELMAOM CKENNA i∈Bandj∈ S ∗ \A, the random variableA ij is centered and independent of all else. To apply Theorem 2.1 from Janson (2004), note that the maximum degree of the dependency graph of the random variables{ ¯Aij ¯Ajl ¯Ali}i∈B,j,l∈S ∗\A (conditional onX) is at most3k. We thus have P{...

2004
[24]

ForT 6, we need not even condition onXsinceT 6 is simply the signed triangle count of an Erd˝os–R´enyi random graph

ForT 5, the maximum degree of the dependency graph of the variables{ ¯Aij ¯Ajl ¯Ali}i,j∈B,l∈S ∗\A (conditional onX) is again at most3k. ForT 6, we need not even condition onXsinceT 6 is simply the signed triangle count of an Erd˝os–R´enyi random graph. Appendix F. Probability and linear algebra tools The following theorem is useful for multiple proofs in ...

2016

[1] [1]

Graph matrices: Norm bounds and applications.arXiv preprint arXiv:1604.03423,

Kwangjun Ahn, Dhruv Medarametla, and Aaron Potechin. Graph matrices: Norm bounds and applications.arXiv preprint arXiv:1604.03423,

work page arXiv

[2] [2]

Random Structures and Algo- rithms

Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. InProceedings of the Eighth International Conference “Random Structures and Algo- rithms” (Poznan, 1997), volume 13, pages 457–466,

1997

[3] [3]

Detecting high log-densities—anO(n 1/4)approximation for densestk-subgraph

Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log-densities—anO(n 1/4)approximation for densestk-subgraph. InSTOC’10— Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 201–210. ACM, New York,

2010

[4] [4]

Exponential and moment inequalities forU-statistics

Evarist Gin´e, Rafał Latała, and Joel Zinn. Exponential and moment inequalities forU-statistics. In High dimensional probability, II (Seattle, WA, 1999), volume 47 ofProgr. Probab., pages 13–38. Birkh¨auser Boston, Boston, MA,

1999

[5] [5]

Seshadhri

Rishi Gupta, Tim Roughgarden, and C. Seshadhri. Decompositions of triangle-dense graphs. In ITCS’14—Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science, pages 471–481. ACM, New York,

2014

[6] [6]

Random geometric graphs with smooth kernels: sharp detection threshold and a spectral conjecture.arXiv preprint arXiv:2602.14998,

Cheng Mao, Yihong Wu, and Jiaming Xu. Random geometric graphs with smooth kernels: sharp detection threshold and a spectral conjecture.arXiv preprint arXiv:2602.14998,

work page arXiv

[7] [7]

Concentration of polynomial random matrices via Efron- Stein inequalities

Goutham Rajendran and Madhur Tulsiani. Concentration of polynomial random matrices via Efron- Stein inequalities. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pages 3614–3653. SIAM,

2023

[8] [8]

High-dimensional statistics.arXiv preprint arXiv:2310.19244,

Philippe Rigollet and Jan-Christian H ¨utter. High-dimensional statistics.arXiv preprint arXiv:2310.19244,

work page arXiv

[9] [9]

Local triangle-densest subgraphs

Raman Samusevich, Maximilien Danisch, and Mauro Sozio. Local triangle-densest subgraphs. In 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 33–40. IEEE,

2016

[10] [10]

Additional proofs for the spectral method Continuing from Section 3, we bound each of the terms in (13) to prove Proposition 3.2

Appendix A. Additional proofs for the spectral method Continuing from Section 3, we bound each of the terms in (13) to prove Proposition 3.2. A.1. Analyzing the signal term To analyze the matrixK2 ◦K, we first show that it is close to(XX⊤)◦(XX ⊤)up to normalization. Lemma A.1There is an absolute constantC >0such that the following holds for anyδ∈(0,1). If...

2023

[11] [11]

Moreover, letH d ℓ denote the space of real harmonic polynomials of degreeℓonR d

CD 2 (t). Moreover, letH d ℓ denote the space of real harmonic polynomials of degreeℓonR d. By Corol- lary 1.1.4 in Dai and Xu (2013),dimH d 0 = 1and m:= dimH d 2 = d+ 1 2 −1.(19) Letϕ 0 ≡1, and letϕ 1, . . . , ϕm be an orthonormal basis ofH d 2 . The addition formula for spherical harmonics, (1.2.8) in Dai and Xu (2013), states that D+ 2 D CD 2 (X ⊤ i Xj...

2013

[12] [12]

ProofThe first statement holds by the definition ofQ

log 2(m+1) δ k . ProofThe first statement holds by the definition ofQ. To bound the norm, we note that ∥YΛY⊤ −QΛQ ⊤∥=∥QRΛR ⊤Q⊤ −QΛQ ⊤∥=∥RΛR ⊤ −Λ∥. In the QR decompositionY=QR, the first columns ofYandQare the same andRis upper triangular, so the first column ofRise 1, the first standard basis vector inR m+1. Moreover,Λ 22 = · · ·=Λ m+1,m+1 from Lemma A.2....

2019

[13] [13]

The proof of this goes as in (22); since Wisn×nwhereasW [k] isk×k, we just replacekwithneverywhere in the argument

Moreover, by Theorem F.1 and Lemma A.4, for an absolute constantC 1 >0, ∥W∥ ≤C 1 p np+ log(n/δ)(23) with probability at least1−δ, as long asnp≥Clog(2n/δ). The proof of this goes as in (22); since Wisn×nwhereasW [k] isk×k, we just replacekwithneverywhere in the argument. The result then follows. Lemma A.7There is an absolute constantC >0such that the follo...

2012

[14] [14]

• d2 p3k2 n1/2plogn: Since d k ≤ p3/4 C√n, we have d2 p3k2 n1/2plog(n)≤ n1/2 log(n) p2 · p3/2 C2n = log(n) C2(np)1/2 = 1 C2 · log2(n) np 1/2

• d2 p3k2 np3/2: The assumptionk≥C √nd/p3/4 is sufficient. • d2 p3k2 n1/2plogn: Since d k ≤ p3/4 C√n, we have d2 p3k2 n1/2plog(n)≤ n1/2 log(n) p2 · p3/2 C2n = log(n) C2(np)1/2 = 1 C2 · log2(n) np 1/2 . Previously we showed that, under our main assumption, we havenp 3/2 ≥C, so thatp≥ Cn−2/3. This means thatnp≥Cn 1/3, and thuslog 2(n)/(np) =o(1). 24 SPECTRA...

2023

[15] [15]

Using the fact that∥Z 2 jr ∥∞ ≤1,EZ 2 jr ≤K, andVar[Z 2 jr]≤K, Bernstein’s inequality implies that for allr∈[n]\ {i}, the event X j∈[n]\{i,r} Z2 jr ≲nK+ r nKlog n δ + log n δ ≲nK(24) occurs with probability at least1−δ/n, using the assumptionnK≥log(n/δ). Hence by applying (24)ntimes (n−1times corresponding with the indexesr∈[n]\ {i}and once to the sum ove...

2012

[16] [16]

We can rewrite S= X 2≤j,l≤k j̸=l ⟨X1, Xj⟩⟨X1, Xl⟩⟨Xj, Xl⟩.(33) Define the centered kernelh: (S d−1)2 →Rby h(x, y) :=⟨X 1, x⟩⟨X1, y⟩⟨x, y⟩ − 1 d ⟨X1, x⟩2 − 1 d ⟨X1, y⟩2 + 1 d2 .(34) ForY∼Unif(S d−1)and any fixedx∈S d−1, we have EY [⟨X1, x⟩⟨X1, Y⟩⟨x, Y⟩ |X 1] =⟨X 1, x⟩ ·X ⊤ 1 E[Y Y ⊤]x= 1 d ⟨X1, x⟩2 , EY [⟨X1, Y⟩ 2 |X 1] = 1 d ⟨X1, X1⟩2 = 1 d , which implie...

2018

[17] [17]

Equation (35) shows that, conditional onX 1, the kernel his canonical in the sense needed to apply (Gin ´e et al., 2000, Theorem 3.3). This result is written in terms of various norms and expectations ofh, which we now estimate using the simpler forms of A,B,C, andDappearing before (Gin ´e et al., 2000, Corollary 3.4). Bound forA.It is easy to see thatA=∥...

2000

[18] [18]

extractsj

+O 1 d2 ≤ C d2 .(40) The same estimate holds withxandYinterchanged, hence B2 = (k−1) ∥EY h(·, Y) 2∥∞ +∥E X h(X,·) 2∥∞ ≲ k d2 , 34 SPECTRALRECOVERY OF APLANTEDTRIANGLE-DENSESUBGRAPH where the implicit constant is universal. Similarly, taking expectation of (40) overx=Xand using E[⟨X1, X⟩2] = 1/dgivesE[h(X, Y) 2]≲1/d 3, which implies C2 = (k−1) 2 E[h(X, Y) ...

2000

[19] [19]

Hence it follows from Lemma C.4 (applied withδ/2andn=k) that |S1|≲ pk√ d log k δ + r pk d log2 k δ with probability at least1−δ/2

First note thatS 1 is preciselySas defined in (45), except with the sum over l∈[k]instead ofj∈[n]. Hence it follows from Lemma C.4 (applied withδ/2andn=k) that |S1|≲ pk√ d log k δ + r pk d log2 k δ with probability at least1−δ/2. We will now bound|S 2|. Letc >0be the constant from the decoupling inequality for order-2 kernels (Theorem 3.4.1 in de la Pe˜na...

2012

[20] [20]

The following lemma now follows from the proof of Theorem 2.2 of Schramm and Wein (2022) (see also p

S i B i = X β⊆α E h 1{α\ S 2 =β} · ¯Aα∩(S 2)i · ¯Bβ = X β⊆α Mαβ ¯Bβ , where Mαβ :=E h 1 α\ S 2 =β · ¯Aα∩(S 2)i . The following lemma now follows from the proof of Theorem 2.2 of Schramm and Wein (2022) (see also p. 17 of the technical appendix). Lemma D.1 (Schramm and Wein (2022))LetAandBbe as defined above. SupposeM αα ̸= 0 for allα⊆ [n] 2 with|α| ≤D. Th...

2022

[21] [21]

Finally we bound|E[ ¯Aα ·θ]|

S ii =P α\ S 2 =β · |E ¯Aα |V(α)⊆ S | =P α\ S 2 =β · E Y ij∈α Aij −pp p(1−p) =P α\ S 2 =β · p 1−p |α|/2 E Y ij∈α ⟨Xi, Xj⟩ ≤P α\ S 2 =β ≤r |V(α\β)| . Finally we bound|E[ ¯Aα ·θ]|. LetX 1, . . . , X|V(α)| be i.i.d. uniformly distributed on the sphereSd−1. SinceE ¯Aα | S ·θ̸= 0only ifV(α)∪ {1} ⊆ S, we have E[ ¯Aα ·θ] =E S E ¯Aα | S ·θ =P{V(α)∪ {1} ⊆ S} ·E ¯A...

2022

[22] [22]

Thus in the remainder we may assumek=o(n), where ˆSis defined by (7)

then|S ∗ ∩ ˆS| ≥ϵkwith high probability (recall ˆSis defined as a randomk-subset of[n]when k= Θ(n)). Thus in the remainder we may assumek=o(n), where ˆSis defined by (7). For all subsetsA, B, C⊆[n]define τ(A, B, C) := X i∈A,j∈B,l∈C ¯Aij ¯Ajl ¯Ali and writeτ(A)≡τ(A, A, A). Moreover, define T1(A) :=τ(A,S ∗ \A,S ∗ \A), T 2(A) :=τ(A, A,S ∗ \A), T 3(A) :=τ(A),...

2013

[23] [23]

To apply Theorem 2.1 from Janson (2004), note that the maximum degree of the dependency graph of the random variables{ ¯Aij ¯Ajl ¯Ali}i∈B,j,l∈S ∗\A (conditional onX) is at most3k

Notice thatE[T 4 |X] = 0with probability 1, since for 47 VAN DERPOELMAOM CKENNA i∈Bandj∈ S ∗ \A, the random variableA ij is centered and independent of all else. To apply Theorem 2.1 from Janson (2004), note that the maximum degree of the dependency graph of the random variables{ ¯Aij ¯Ajl ¯Ali}i∈B,j,l∈S ∗\A (conditional onX) is at most3k. We thus have P{...

2004

[24] [24]

ForT 6, we need not even condition onXsinceT 6 is simply the signed triangle count of an Erd˝os–R´enyi random graph

ForT 5, the maximum degree of the dependency graph of the variables{ ¯Aij ¯Ajl ¯Ali}i,j∈B,l∈S ∗\A (conditional onX) is again at most3k. ForT 6, we need not even condition onXsinceT 6 is simply the signed triangle count of an Erd˝os–R´enyi random graph. Appendix F. Probability and linear algebra tools The following theorem is useful for multiple proofs in ...

2016