<p>I have been trying to understand the applicability of Grothendieck's constant of a graph G and hardness of approximation of combinatorial problems such as Clique $\omega(G)$, Independent Set $\alpha(G)$ and Chromatic Number $\chi(G)$. The literature seems fairly new and the relevant material is scattered. </p>

<p>The abstract/first section of <a href="http://www.tau.ac.il/~nogaa/PDFS/grothen.pdf" rel="nofollow">this paper</a> provides the following as definition of Grothendieck Constant:</p>

<blockquote>
  <p>Let $G = (V,E)$ be a finite graph and let $a:E\rightarrow\mathbb{R}$,
  $f_{S}:V\rightarrow S$ and $f_{\pm1}:V\rightarrow \{-1,1\}$ be
  functions from edges to reals, vertices to the unit sphere in $|V|-1$ dimensions and
  vertices to $\{-1,1\}$ respectively. </p>
  
  <p>Grothendieck's constant $K(G)$ is the smallest $K$ such that for
  every $a$, we have:</p>
  
  <p>$$ \sup_{f_{S}} \sum_{\{s,t\}\in E} a(s,t)\langle f_{S}(s),f_{S}(t)\rangle\le K\sup_{f_{\pm1}} \sum_{\{s,t\}\in E}a(s,t) f_{\pm1}(s) f_{\pm1}(t) $$</p>
</blockquote>

<ul>
<li>How is this constant calculated and shown explicitly related to hardness of approximation of the above three sample problems ? </li>
<li>Is there a literature survey that provides details of relevance of $K(G)$ to such problems?</li>
<li>Is $K(G) = 1$ when $\chi(G) = 2$ (does anyone know a proof)? (I bet I saw a reference on this but cannot locate again)</li>
</ul>

<p>Some additions:
A survey for mathematicians is provided <a href="http://www.ams.org/journals/bull/2012-49-02/S0273-0979-2011-01348-9/S0273-0979-2011-01348-9.pdf" rel="nofollow">here</a>. </p>

CC BY-SA 3.0
2012-07-08T22:32:15.463Z
(1) I think that the Grothendieck constant of a graph G is usually denoted by K(G), which is different from the original version of Grothendieck’s constant (not of a graph), which is sometimes denoted by K_G.
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-08T22:33:15.150Z
(2) “Is K_G=1 when χ(G)=2?”  No!  The supremum of the Grothendieck constant of graph G over all bipartite graphs G is exactly the original “Grotendieck’s constant.”
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-08T22:49:35.753Z
@TsuyoshiIto For $(1)$ - that is what I implied. I will change the notation. For $(2)$ - Yes that is true. May be I am confusing $1$ with $O(1)$. However I think I am reasonably sure I saw the value quoted.
Turbo
CC BY-SA 3.0
2012-07-08T23:43:57.073Z
As for (2), that is what I said.  It is bounded by a constant for bipartite graphs, where the constant is of course independent of the graph, and this is the original version of the [Grothendieck inequality](http://en.wikipedia.org/wiki/Grothendieck_inequality).  Alon, Makarychev, Makarychev, and Naor ([4] in the survey), who introduced the notion of the Grothendieck constants of graphs, showed that K(G) is bounded by a function of the chromatic number of a graph which grows as O(log χ(G)).
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-09T00:12:48.060Z
By the way, you are still confusing “Grothendieck’s constant” (a universal constant which does not depend on graphs) and “the Grothendieck constant of a graph”.  I do not think that we say “Grothendieck’s constant of a graph.”
Tsuyoshi Ito
CC BY-SA 3.0
2012-07-09T00:17:28.870Z
I do not think that this question is well-posed.  It is based on OP’s vague memory, part of which has already turned out to be imprecise.  I think that OP should check the literature more carefully.
Tsuyoshi Ito
<cc.complexity-theory><graph-theory><co.combinatorics><approximation-hardness>
Grothendieck's constant
Turbo
# Grothendieck's constant

(Asked by: username_0 on 2012-07-08)

I have been trying to understand the applicability of Grothendieck's constant of a graph G and hardness of approximation of combinatorial problems such as Clique $\omega(G)$, Independent Set $\alpha(G)$ and Chromatic Number $\chi(G)$. The literature seems fairly new and the relevant material is scattered.

The abstract/first section of [this paper](http://www.tau.ac.il/~nogaa/PDFS/grothen.pdf) provides the following as definition of Grothendieck Constant:

> Let $G = (V,E)$ be a finite graph and let $a:E\rightarrow\mathbb{R}$,
> $f\_{S}:V\rightarrow S$ and $f\_{\pm1}:V\rightarrow \{-1,1\}$ be
> functions from edges to reals, vertices to the unit sphere in $|V|-1$ dimensions and
> vertices to $\{-1,1\}$ respectively.
>
> Grothendieck's constant $K(G)$ is the smallest $K$ such that for
> every $a$, we have:
>
> $$ \sup\_{f\_{S}} \sum\_{\{s,t\}\in E} a(s,t)\langle f\_{S}(s),f\_{S}(t)\rangle\le K\sup\_{f\_{\pm1}} \sum\_{\{s,t\}\in E}a(s,t) f\_{\pm1}(s) f\_{\pm1}(t) $$

* How is this constant calculated and shown explicitly related to hardness of approximation of the above three sample problems ?
* Is there a literature survey that provides details of relevance of $K(G)$ to such problems?
* Is $K(G) = 1$ when $\chi(G) = 2$ (does anyone know a proof)? (I bet I saw a reference on this but cannot locate again)

Some additions:
A survey for mathematicians is provided [here](http://www.ams.org/journals/bull/2012-49-02/S0273-0979-2011-01348-9/S0273-0979-2011-01348-9.pdf).

**Tags:** cc.complexity-theory, graph-theory, co.combinatorics, approximation-hardness
> **Comments:**
> **username_1**: (1) I think that the Grothendieck constant of a graph G is usually denoted by K(G), which is different from the original version of Grothendieck’s constant (not of a graph), which is sometimes denoted by K_G.  
> **username_1**: (2) “Is K_G=1 when χ(G)=2?”  No!  The supremum of the Grothendieck constant of graph G over all bipartite graphs G is exactly the original “Grotendieck’s constant.”  
> **username_0**: @TsuyoshiIto For $(1)$ - that is what I implied. I will change the notation. For $(2)$ - Yes that is true. May be I am confusing $1$ with $O(1)$. However I think I am reasonably sure I saw the value quoted.  
> **username_1**: As for (2), that is what I said.  It is bounded by a constant for bipartite graphs, where the constant is of course independent of the graph, and this is the original version of the [Grothendieck inequality](http://en.wikipedia.org/wiki/Grothendieck_inequality).  Alon, Makarychev, Makarychev, and Naor ([4] in the survey), who introduced the notion of the Grothendieck constants of graphs, showed that K(G) is bounded by a function of the chromatic number of a graph which grows as O(log χ(G)).  
> **username_1**: By the way, you are still confusing “Grothendieck’s constant” (a universal constant which does not depend on graphs) and “the Grothendieck constant of a graph”.  I do not think that we say “Grothendieck’s constant of a graph.”  
> **username_1**: I do not think that this question is well-posed.  It is based on OP’s vague memory, part of which has already turned out to be imprecise.  I think that OP should check the literature more carefully.  

---

## 0 answers

