The Grothendieck constant of random and pseudo-random graphs

Noga Alon, Eli Berger

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)323-327
Number of pages5
JournalDiscrete Optimization
Volume5
Issue number2
DOIs
StatePublished - May 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Grothendieck constant of a graph
  • Random graphs
  • Semidefinite programming

Fingerprint Dive into the research topics of 'The Grothendieck constant of random and pseudo-random graphs'. Together they form a unique fingerprint.

Cite this