The Grothendieck constant of random and pseudo-random graphs

Noga Alon, Eli Berger

Research output: Contribution to journalArticle

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

Original languageEnglish (US)
Pages (from-to)323-327
Number of pages5
JournalDiscrete Optimization
Volume5
Issue number2
DOIs
StatePublished - May 1 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