The Grothendieck constant of random and pseudo-random graphs

The Grothendieck constant of a graph G = (V, E) is the least constant K such that for every matrix A : V × V → R, under(max, f : V → S^{| V | - 1}) under(∑, {u, v} ∈ E) A (u, v) {dot operator} 〈 f (u), f (v) 〉 ≤ K under(max, ε{lunate} : V → {- 1, + 1}) under(∑, {u, v} ∈ E) A (u, v) {dot operator} ε{lunate} (u) ε{lunate} (v) . The investigation of this parameter, introduced in [N. Alon, K. Makarychev, Y. Makarychev, A. Naor, Quadratic forms on graphs, in: Proc. of the 37th ACM STOC, ACM Press, Baltimore, 2005, pp. 486-493 (Also: Invent. Math. 163 (2006) 499-522)], is motivated by the algorithmic problem of maximizing the quadratic form ∑_{{u, v} ∈ E} A (u, v) ε{lunate} (u) ε{lunate} (v) over all ε{lunate} : V → {- 1, 1}, which arises in the study of correlation clustering and in the investigation of the spin glass model. In the present note we show that for the random graph G (n, p) the value of this parameter is, almost surely, Θ (log (n p)). This settles a problem raised in [N. Alon, K. Makarychev, Y. Makarychev, A. Naor, Quadratic forms on graphs, in: Proc. of the 37th ACM STOC, ACM Press, Baltimore, 2005, pp. 486-493 (Also: Invent. Math. 163 (2006) 499-522)]. We also obtain a similar estimate for regular graphs in which the absolute value of each nontrivial eigenvalue is small.