The Grothendieck constant of random and pseudo-random graphs

The Grothendieck constant of random and pseudo-random graphs

0.00 Avg rating0 Votes
Article ID: iaor20091330
Country: Netherlands
Volume: 5
Issue: 2
Start Page Number: 323
End Page Number: 327
Publication Date: May 2008
Journal: Discrete Optimization
Authors: ,
Keywords: programming (semidefinite)
Abstract:

The Grothendieck constant of a graph G=(V,E) is the least constant K such that for every matrix A:V×V→R, maxf:V→S|V|−1{u,v}∈E A(u,v) · (f(u), f(v)) ≤ K maxε:V→{−1,+1}{u,v}∈E A(u,v) · ε(u)ε(v). The investigation of this parameter, introduced by Alon et al., is motivated by the algorithmic problem of maximizing the quadratic form {u,v}∈E A(u,v)ε(u)ε(v) over all ε: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(np)). This settles a problem raised by Alon et al.. We also obtain a similar estimate for regular graphs in which the absolute value of each nontrivial eigenvalue is small.

Reviews

Required fields are marked *. Your email address will not be published.