TY - JOUR

T1 - The Grothendieck constant of random and pseudo-random graphs

AU - Alon, Noga

AU - Berger, Eli

N1 - Funding Information:
The first author’s research was supported in part by the Israel Science Foundation, by a USA–Israel BSF grant, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2008/5

Y1 - 2008/5

N2 - 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.

AB - 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.

KW - Grothendieck constant of a graph

KW - Random graphs

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=41149128402&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=41149128402&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2006.06.004

DO - 10.1016/j.disopt.2006.06.004

M3 - Article

AN - SCOPUS:41149128402

VL - 5

SP - 323

EP - 327

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

IS - 2

ER -