Separation [Thm]Take a random graph G(N,p)with ω(Iog4NN)≤p≤1-(1). Its adjacency matrix,as a bi-variate function f,has the following w.p.1-0(1) Q(①=ΩIog(pN) ·Q*(⑤≥Q()=2(log(1/disc(f). disc(f)is related to o2(D-1/2AD-1/2),which can be bounded by O(1/pN)for a random graph.Separation • [Thm] Take a random graph G(N,p) with ω(log4N/N) ≤ p ≤ 1-Ω(1). Its adjacency matrix, as a bi-variate function f, has the following w.p. 1-o(1) Q(f) = Ω(log(pN)). • Q*(f) ≥ Q(f) = Ω(log(1/disc(f))). • disc(f) is related to σ2 (D-1/2AD-1/2), which can be bounded by O(1/√pN) for a random graph