Quadratic Forms on Graphs

Noga Alon ^{∗} Konstantin Makarychev ^{†} Yury Makarychev ^{‡} Assaf Naor ^{§}

Abstract

We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A : E → ℝ,

sup_{f:V →S^{|V |−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩ ≤ K sup_{φ:V →{−1,+1}} ∑_{{u,v}∈E} A(u, v) · φ(u)φ(v).

The classical Grothendieck inequality corresponds to the case of bipartite graphs, but the case of general graphs is shown to have various algorithmic applications. Indeed, our work 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. We give upper and lower estimates for the integrality gap of this program. We show that the integrality gap is O(log ϑ(\overline{G})), where ϑ(\overline{G}) is the Lovász Theta Function of the complement of G, which is always smaller than the chromatic number of G. This yields an efficient constant factor approximation algorithm for the above maximization problem for a wide range of graphs G. We also show that the maximum possible integrality gap is always at least Ω(log ω(G)), where ω(G) is the clique number of G. In particular it follows that the maximum possible integrality gap for the complete graph on n vertices with no loops is Θ(log n). More generally, the maximum possible integrality gap for any perfect graph with chromatic number n is Θ(log n). The lower bound for the complete graph improves a result of Kashin and Szarek on Gram matrices of uniformly bounded functions, and settles a problem of Megretski and of Charikar and Wirth.

1 Introduction

An important inequality of A. Grothendieck [14] (see also [21]) states that for every n × m matrix (a_{ij}) and every choice of unit vectors x_{1}, …, x_{n}, y_{1}, …, y_{m} ∈ S^{n+m−1} there exists a choice of signs ε_{1}, …, ε_{n}, δ_{1}, …, δ_{m} ∈ {−1, +1} for which

∑_{i=1}^{n} ∑_{j=1}^{m} a_{ij}⟨x_{i}, y_{j}⟩ ≤ K_{G} ∑_{i=1}^{n} ∑_{j=1}^{m} a_{ij}ε_{i}δ_{j}.  (1)

∗Schools of Mathematics and Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel and IAS, Princeton, NJ 08540, USA. Email: nogaa@tau.ac.il. Research supported in part by the Israel Science Foundation, by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University and by the Von Neumann Fund.

†Department of Computer Science, Princeton University. Email: kmakaryc@cs.princeton.edu. Research supported by NSF grants CCR-0205594, CCR-0237113, DOE award DE-FG02-02ER25594 and a Gordon Wu fellowship.

‡Department of Computer Science, Princeton University. Email: ymakaryc@cs.princeton.edu. Research supported by NSF grants CCR-0205594, CCR-0237113, DOE award DE-FG02-02ER25594 and a Gordon Wu fellowship.

§Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399, USA. Email: anaor@microsoft.com.

Here K_{G} is a universal constant, the best value of which is unknown (in [20] it is shown that K_{G} ≤ π/[2 log(1 + \sqrt{2})] = 1.782...). In [3] Grothendieck’s inequality was shown to have various algorithmic applications including the efficient construction of Szemerédi partitions of graphs and the estimation of the cutnorm of matrices, which yields efficient approximation algorithms for dense graph problems, using the methods of [12].

A quadratic variant of Grothendieck’s inequality was studied in [10], where it was shown that there is a universal constant C > 0 such that for every n×n matrix (a_{ij}) and every x_{1}, …, x_{n} ∈ S^{n−1} there are signs ε_{1}, …, ε_{n} ∈ {−1, +1} for which

∑_{\begin{matrix}i,j∈\{1,...,n\} \\ i≠j \end{matrix}} a_{ij}⟨x_{i}, x_{j}⟩ ≤ C log n ∑_{\begin{matrix}i,j∈\{1,...,n\} \\ i≠j \end{matrix}} a_{ij}ε_{i}ε_{j}.  (2)

This was also proved by Megretski in [25] and by Nemirovski, Roos and Terlaky in [26]. Various algorithmic applications of (2) were presented in [10], including an O(log n) approximation algorithm for the maximum correlation clustering problem suggested in [6] (and discussed in greater detail below). The authors of [10] (as well as the author of [25]) asked whether the logarithmic upper bound in (2) can be improved to a constant. In this paper we show that the log n term in (2) is in fact optimal. Our construction is based on a refinement of a recent result of Kashin and Szarek [19], who established an Ω(\sqrt{log n}) lower bound. Moreover, unlike in the classical functional analytic setting, inequalities (1) and (2) belong to a more general family of inequalities, all of which have algorithmic significance. Specifically, given a graph G = (V, E) we define the Grothendieck constant of G, denoted K(G), to be the least constant K such that for every matrix A : V ×V → ℝ:

sup_{f:V →S^{|V |−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩ ≤ K sup_{φ:V →{−1,+1}} ∑_{{u,v}∈E} A(u, v) · φ(u)φ(v).

Grothendieck’s inequality (1) simply states that if G is bipartite then K(G) = O(1). On the other hand, inequality (2) states that for the complete graph K_{n}, K(K_{n}) = O(log n).

In this paper we initiate a systematic study of the parameter K(G). We show that there is a natural way to interpolate between the bipartite case (1) and the case of the complete graph (2). Namely, we show that for every loop-free graph G,

Ω(log ω(G)) = K(G) = O(log ϑ(\overline{G})),

where ω(G) is the clique number of G (i.e., the size of the largest clique in G), and ϑ(\overline{G}) is the Lovász theta function of the complement of G, denoted \overline{G} (see Section 3 for a definition of the Lovász theta function). As shown in [23], for every graph G, ω(G) ≤ ϑ(\overline{G}) ≤ χ(G), where χ(G) is the chromatic number of G. It follows that K(G) = Θ(log ϑ(\overline{G})) = Θ(log χ(G)) for every perfect graph G. The proofs are algorithmic, and provide efficient randomized algorithms for finding a function φ that approximates the maximum possible value of a given quadratic form

∑_{{u,v}∈E} A(u, v) · φ(u)φ(v) over all φ : V → {−1, +1}  (3)

up to a factor of K(G) for any loop-free graph G.

Various related results are also obtained. We hope that this will initiate future investigation of the interesting graph parameter K(G) and its algorithmic applications.

The rest of the paper is organized as follows. After presenting a few basic results and definitions in Section 2, we prove, in Section 3, that K(G) ≤ O(log ϑ(\overline{G})), and obtain some related results. The fact that K(G) ≥ Ω(log ω(G)) is established in Section 4. Sections 5 and 6 contain some algorithmic consequences, and various additional remarks including several new Grothendieck-type inequalities. We end in Section 7, with several open problems.

2 Definitions and basic facts

Let G = (V, E) be a graph on n vertices, which may have loops. We introduce the following parameters:

Definition 2.1 (The Grothendieck constant of G). Denote by K(G) the least constant K such that for every matrix A : V × V → ℝ:

sup_{f:V →S^{n−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩ ≤ K sup_{φ:V →{−1,+1}} ∑_{{u,v}∈E} A(u, v) · φ(u)φ(v),

The following definition plays a central role in the ensuing arguments. It is a formalization, and a generalization to the graph theoretical setting, of a concept studied in [19].

Definition 2.2 (The Gram representation constant of G). Denote by R(G) the infimum over constants R such that for every f : V → S^{n−1} there is a function F : V → L_{∞}[0, 1] so that for every v ∈ V we have ∥F (v)∥_{∞} ≤ R and for every {u, v} ∈ E,

⟨f(u), f(v)⟩ = ⟨F (u), F (v)⟩ ≡ ∫_{0}^{1} F (u)(t)F (v)(t)dt.

The finiteness of the constants R(G) and K(G) for loopless graphs follows from Lemma 3.1 below, and the following simple lemma which relates these two parameters:

Lemma 2.3. Let G be a graph without loops. Then K(G) = R(G)^{2}.

Proof. To prove that K(G) ≤ R(G)^{2} fix R > R(G) and f : V → S^{n−1}. There is a function F : V → L_{∞}[0, 1] such that for every v ∈ V we have ∥F (v)∥_{∞} ≤ R and for every {u, v} ∈ E, ⟨f(u), f(v)⟩ = ⟨F (u), F (v)⟩. Then for every A : V × V → ℝ

∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩ = ∫_{0}^{1} ( ∑_{{u,v}∈E} A(u, v) · ⟨F (u)(t), F (v)(t)⟩) dt
≤ sup_{g:V →[−R,R]} ∑_{{u,v}∈E} A(u, v) · g(u)g(v)
= R^{2} sup_{φ:V →{−1,+1}} ∑_{{u,v}∈E} A(u, v) · φ(u)φ(v),

where we have used the fact that since G has no loops, the functional ∑_{{u,v}∈E} A(u, v) · g(u)g(v) is linear in each of the variables {g(v)}_{v∈V}.

In the reverse direction, for each f : V → S^{n−1} define M(f) := (⟨f(u), f(v)⟩)_{{u,v}∈E} ⊆ ℝ^{E}. Similarly, each φ : V → {−1, 1} defines M(φ) := (φ(u)φ(v))_{{u,v}∈E} ⊆ ℝ^{E}. Clearly

conv{M(φ) : φ : V → {−1, 1}} ⊆ conv{M(f) : f : V → S^{n−1}}.

On the other hand, by the separation theorem, the validity of the inequality

sup_{f:V →S^{n−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩ ≤ K(G) · sup_{φ:V →{−1,+1}} ∑_{{u,v}∈E} A(u, v) · φ(u)φ(v)

for all A : V × V → ℝ, implies that

conv{M(f) : f : V → S^{n−1}} ⊆ K(G) · conv{M(φ) : φ : V → {−1, 1}}.

Thus for every f : V → S^{n−1} there are weights {λ_{g} : g : V → {−1, +1}} which satisfy ∑_{g:V →{−1,+1}} λ_{g} = 1, λ_{g} ≥ 0, and for every {u, v} ∈ E

⟨f(u), f(v)⟩ = K(G) ∑_{g:V →{−1,+1}} λ_{g} · g(u)g(v).

Partition the interval [0, 1] into subintervals {I_{g} : g : V → {−1, +1}} such that the length of I_{g} is λ_{g}. For every v ∈ V let F (v) be the function which takes the value \sqrt{K(G)}g(v) on I_{g}. The above identity becomes simply: ⟨f(u), f(v)⟩ = ⟨F (u), F (v)⟩, as required.

Remark 2.1. The proof above easily implies that for every graph G (that may contain loops), R(G)^{2} is equal to the following slight modification of K(G), denoted K′(G), which is defined to be the least constant K′ such that for every matrix A : V × V → ℝ:

sup_{f:V →S^{n−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩ ≤ K′ sup_{φ:V →[−1,+1]} ∑_{{u,v}∈E} A(u, v) · φ(u)φ(v),

3 Upper bounds

Observe that if H is a subgraph of G then R(H) ≤ R(G). In [10] Charikar and Wirth show that for the complete graph on n-vertices, denoted K_{n}, K(K_{n}) = O(log n). See also [25], [26] for similar proofs. This fact is a corollary of the following estimate:

Lemma 3.1. Let K_{n}^{⟲} denote the complete graph on n vertices with loops. Then

R(K_{n}^{⟲}) = O (\sqrt{log n}) .

Proof. The simple argument we present is taken from [19]. Denote by σ the normalized surface measure on S^{n−1}. By a straightforward computation, for some universal constant c,

σ \{x ∈ S^{n−1} : ∥x∥_{∞} ≤ c\sqrt{\frac{log n}{n}}\} ≥ 1 − \frac{1}{2n}.

By rotation invariance, for every x ∈ S^{n−1}, the random variable on the orthogonal group O(n) given by U ↦ Ux is uniformly distributed on S^{n−1}. It follows that for every f : V → S^{n−1} there is a rotation U ∈ O(n) such that for all v ∈ V, ∥U(f(v))∥_{∞} ≤ c\sqrt{\frac{log n}{n}}. Let F (v) be the function on [0, 1] such that F (v)(t) ≡ \sqrt{n} · (U(f(v)))_{j} for (j − 1)/n ≤ t < j/n. Then ∥F (v)∥_{∞} = O(\sqrt{log n}) and ⟨F (u), F (v)⟩ = ⟨U(f(u)), U(f(v))⟩ = ⟨f(u), f(v)⟩. This shows that R(K_{n}^{⟲}) = O (\sqrt{log n}).

Remark 3.1. For any n ≥ 3, K(K_{n}^{⟲}) = ∞. Indeed, suppose that 1/3 > ϵ > 0, and consider the 3 by 3 matrix A_{ij} defined by A_{ij} = −1 for all i ≠ j and A_{ii} = −1 + ϵ for all i. It is easy to see that the maximum of the sum ∑_{ij} A_{ij}⟨u_{i}, u_{j}⟩ for unit vectors u_{i} is at least 3ϵ, whereas the maximum of the quadratic form ∑_{ij} A_{ij}x_{i}x_{j} over {−1, 1}^{3} is 3ϵ − 1 , which is negative. In fact, for any graph G that has at least one loop, if K(G) exists, then it must be 1 (as we can consider a matrix A in which the only nonzero entry is −1, at the loop, or 1, at the loop).

Remark 3.2. When allowing negative entries on the diagonal, the integrality gap in the quadratic program may be infinite, as observed above, since the maximum over the discrete cube may be negative while the one over Gram matrices is positive. In fact, a stronger (simple) assertion holds. If P and NP differ, there is no polynomial time algorithm that approximates the maximum of the quadratic form above over the discrete cube up to any factor (even one that grows with n arbitrarily fast). This is because by defining the matrix A as one corresponding to the maximum cut of a graph (see the construction in [3] for more details), and by putting an appropriate constant in, say, A_{11}, letting all other diagonal entries of A be zero, we can, by an obvious binary search, find the value of the maximum cut of a graph precisely, if we can determine if the maximum of the quadratic form over the discrete cube is positive or negative.

We proceed to prove two theorems which strengthen the upper bound K(K_{n}) = O(log n). In Section 4 we show that in fact K(K_{n}) = Ω(log n). This improves upon the lower bound Ω (\sqrt{log n}) which was proved by Szarek and Kashin in [19].

Definition 3.2. A strict vector k-coloring of a graph G = (V, E) is a mapping s : V → ℓ_{2}, such that all vectors s(u) are unit vectors, and for every two adjacent vertices u and v ⟨s(u), s(v)⟩ = −1/(k − 1). Observe that we can always assume that s takes values in a |V |-dimensional Euclidean space.

A graph is strictly vector k-colorable if it has a strict vector k-coloring. The strict vector chromatic number of a graph is the smallest real k for which the graph is strictly vector k-colorable.

The notion of strict vector colorability was introduced by Karger, Motwani, and Sudan in [18]. They showed that the strict vector chromatic number of a graph G is equal to the Lovász theta function of the complement of G, ϑ(\overline{G}), which is bounded by the chromatic number of G. For the sake of completeness we recall that the original definition in [23] of the Lovász theta function of a graph on the vertices \{1, …, n\} is the minimum of max_{1≤i≤n} \frac{1}{⟨x_{i},y⟩^{2}} , where the minimum is taken over all choices of unit vectors x_{i} and y such that x_{i} and x_{j} are orthogonal for every pair of non-adjacent vertices i, j (we will not use this definition in what follows).

Theorem 3.3. For any loop-free graph G = (V, E), K(G) = O (log ϑ(\overline{G})).

The proof of Theorem 3.3 is based on the proof of Grothendieck’s inequality appearing in [15], but requires several additional ideas as well. Before passing to the proof we introduce some notation, and motivate the ensuing arguments by recalling the reasoning in [15].

Let g_{1}, g_{2}, … be i.i.d. standard Gaussian random variables, defined on some probability space (Ω, P). Consider the Gaussian Hilbert space H, which is defined as the following closed subspace of L_{2}(Ω):

H = {∑_{i=1}^{∞} a_{i}g_{i} : ∑_{i=1}^{∞} a_{i}^{2} < ∞} .

The scalar product on L_{2}(Ω) (and hence also on H) is defined for X, Y ∈ L_{2}(Ω) by ⟨X, Y ⟩ = 𝔼(X · Y). We denote by B(H) and B(L_{2}(Ω)) the unit balls of H and L_{2}(Ω), respectively.

Define:

Γ = sup_{f:V →B(H)} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩,  (4)

and

Δ = sup_{φ:V →[−1,+1]} ∑_{{u,v}∈E} A(u, v) · φ(u)φ(v).  (5)

Our goal is to bound the ratio Γ/Δ.

For every M > 0 and ψ ∈ L_{2}(Ω), denote the truncation of ψ at M by

ψ^{M}(x) = \{ \begin{matrix}ψ(x) & if |ψ(x)| ≤ M \\ M & if ψ(x) > M \\ −M & if ψ(x) < −M. \end{matrix}  (6)

Fix f : V → B(H) for which

Γ = ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩.

The existence of f follows from a straightforward compactness argument.

The basic idea is to relate Γ to the scalar case via truncation. Specifically, fix M > 0 and assume that there exists a mapping h : V → H′, for some Hilbert space H′, for which it is possible to write

Γ = ∑_{{u,v}∈E} A(u, v) · ⟨f(u)^{M}, f(v)^{M}⟩ + ∑_{{u,v}∈E} A(u, v) · ⟨h(u), h(v)⟩.  (7)

The first term in (7) is bounded by relating to the scalar case:

∑_{{u,v}∈E} A(u, v) · ⟨f(u)^{M}, f(v)^{M}⟩ = 𝔼 ∑_{{u,v}∈E} A(u, v) · f(u)^{M} · f(v)^{M} ≤ M^{2}Δ.  (8)

When G is a bipartite graph with sides R, L (i.e. in the setting of the classical Grothendieck inequality), the proof in [15] proceeds by simply taking in (7) h : V → L_{2}(Ω) ⊕ L_{2}(Ω) given by

h(v) = \{ \begin{matrix}(f(v) − f(v)^{M}) ⊕ f(v)^{M} & v ∈ L, \\ f(v) ⊕ (f(v) − f(v)^{M}) & v ∈ R. \end{matrix}

Since all the elements of B(H) have the same distribution as a Gaussian random variable with mean zero and variance at most one, we see that for M ≥ 1 and every v ∈ V,

∥f(v) − f(v)^{M}∥_{2}^{2} = \sqrt{\frac{2}{π}} ∫_{M}^{∞} x^{2}e^{−x^{2}/2}dx ≤ 2Me^{−M^{2}/2}.  (9)

Thus, in this case, by the definition of Γ,

∑_{\begin{matrix}u∈L \\ v∈R \end{matrix}} A(u, v) · ⟨h(u), h(v)⟩ ≤ 2\sqrt{2M}e^{−M^{2}/4} · Γ.  (10)

Plugging (8) and (10) into (7) we see that Γ ≤ M^{2}Δ + 2\sqrt{2M}e^{−M^{2}/4} · Γ. Choosing M large enough we deduce that Γ = O(Δ), which concludes the proof of Grothendieck’s inequality in [15].

When the graph G = (V, E) is not necessarily bipartite, we can still bound the second term in (7) as follows:

∑_{{u,v}∈E} A(u, v) · ⟨h(u), h(v)⟩ ≤ (max_{v∈V} ∥h(v)∥_{H′})^{2} · Γ.

We thus have the following

Corollary 3.4. Fix M > 0 and assume that (7) holds. Assume also that for every v ∈ V, ∥h(v)∥_{H′}^{2} ≤ \frac{1}{2}, then Γ ≤ 2M^{2}Δ.

We are now in position to conclude the proof of Theorem 3.3.

Proof of Theorem 3.3. Denote k = ϑ(\overline{G}). Let s : V → ℓ_{2} be a strict vector k-coloring of G. Let U = ℓ_{2} ⊕ ℝ. Define two mappings t, t̂: V → U as follows

t(u) = (\sqrt{\frac{k − 1}{k}}s(u)) ⊕ (\sqrt{\frac{1}{k}} · e_{1}) ,

and

t̂(u) = (−\sqrt{\frac{k − 1}{k}}s(u)) ⊕ (\sqrt{\frac{1}{k}} · e_{1}) .

Then, t(u) and t̂(u) are unit vectors. Moreover, for every adjacent vertices u and v we have ⟨t(u), t(v)⟩ = ⟨t̂(u), t̂(v)⟩ = 0, and ⟨t(u), t̂(v)⟩ = \frac{2}{k}.

Let Γ and Δ be as in (4) and (5), respectively. Our goal is to show that Γ = O(log k · Δ). As before, we fix f : V → B(H) for which

Γ = ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩.

Consider the function h : V → U ⊗ L_{2}(Ω) defined as follows:

h(u) = \frac{1}{4}t(u) ⊗ (f(u) + f(u)^{M}) + k · t̂(u) ⊗ (f(u) − f(u)^{M}).

With this definition one readily checks that identity (7) holds true. Moreover, for every v ∈ V,

∥h(v)∥_{U⊗L_{2}(Ω)}^{2} ≤ (\frac{1}{2} + k∥f(u) − f(u)^{M}∥_{L_{2}(Ω)})^{2} ≤ (\frac{1}{2} + k\sqrt{2M}e^{−M^{2}/4})^{2} ,

where we have used the bound (9). Choosing, say, M = 8\sqrt{log k} yields that for every v ∈ V, ∥h(v)∥_{U⊗L_{2}(Ω)}^{2} ≤ \frac{1}{2}, so that by Corollary 3.4 Γ ≤ (128 log k)Δ.

Remark 3.3. Since the strict vector chromatic number is less than or equal to the chromatic number χ(G), the result above implies that for any loop-free graph G, K(G) = O (log χ(G)).

We sketch below an alternative proof of Theorem 3.3. Although this proof is similar in spirit to the one above, we believe it sheds a different light on the problem. The argument is based on the following new characterization of the theta function, which may be interesting in its own right.

Theorem 3.5. For a loop-free graph G = (V, E) on |V | = n vertices, let Z = Z(G) denote the least constant Z such that for every matrix A : V × V → ℝ:

− inf_{g:V →S^{n−1}} ∑_{{u,v}∈E} A(u, v) · ⟨g(u), g(v)⟩ ≤ Z sup_{f:V →S^{n−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩. (11)

Then Z = ϑ(\overline{G}) − 1.

Proof. Put k = ϑ(\overline{G}). We first show that Z(G) ≤ k − 1. Fix a function g : V → S^{n−1}. Let s : V → ℓ_{2} be a strict vector k-coloring of G. Consider the function t(v) : V → S^{n−1} ⊗ ℓ_{2} defined as follows:

t(v) = g(v) ⊗ s(v).

Then for any v ∈ V, t(v) is a unit vector. Thus

∑_{{u,v}∈E} A(u, v) · ⟨t(u), t(v)⟩ ≤ sup_{f:V →S^{n−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩.

On the other hand,

∑_{{u,v}∈E} A(u, v) · ⟨t(u), t(v)⟩ = ∑_{{u,v}∈E} A(u, v) · ⟨g(u), g(v)⟩ · ⟨s(u), s(v)⟩

= −\frac{1}{k − 1} ∑_{\{u,v\}∈E} A(u, v) · ⟨g(u), g(v)⟩.

Hence

− ∑_{{u,v}∈E} A(u, v) · ⟨g(u), g(v)⟩ ≤ (k − 1) sup_{f:V →S^{n−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩.

As this holds for every g as above, it follows that indeed Z(G) ≤ k − 1.

Next, we show that k − 1 ≤ Z = Z(G). By the separation theorem, the validity of the inequality (11) for all matrices A implies that for every function g : V → S^{n−1}, the vector −(⟨g(u), g(v)⟩)_{{u,v}∈E} lies in the convex hull of the set of all vectors in ℝ^{E} of the form Z · (⟨f(u), f(v)⟩)_{{u,v}∈E}, as f ranges over all functions f : V → S^{n−1}. As the latter set is convex it follows that −(⟨g(u), g(v)⟩)_{{u,v}∈E} lies in this set. In particular, this holds for the vector obtained by taking a constant g : V → S^{n−1}, implying that there is an s : V → S^{n−1} such that ⟨s(u), s(v)⟩ = −\frac{1}{Z} for all \{u, v\} ∈ E. By the definition of the theta function, this implies that k − 1 ≤ Z, as needed.

It is worth noting that one of the known characterizations of the theta function, obtained in [23], implies that ϑ(\overline{G}) − 1 is the least constant Z′ such that for every matrix A : V × V → ℝ

− inf_{g:V →ℝ} ∑_{{u,v}∈E} A(u, v) · g(u)g(v) ≤ Z′ sup_{f:V →ℝ} ∑_{{u,v}∈E} A(u, v) · f(u)f(v).

This can be viewed as a one-dimensional analogue of the theorem above.

An immediate consequence of Theorem 3.5 is the following.

Corollary 3.6. For any loop-free graph G = (V, E), for every matrix A : V ×V → ℝ and for every g, h : V → S^{n−1}:

| ∑_{\{u,v\}∈E} A(u, v) · ⟨g(u), h(v)⟩| ≤ ϑ(\overline{G}) sup_{f:V →S^{n−1}} ∑_{\{u,v\}∈E} A(u, v) · ⟨f(u), f(v)⟩.

Proof. This follows from the following simple observation:

∑_{\{u,v\}∈E} A(u, v) · ⟨g(u), h(v)⟩ = ∑_{\{u,v\}∈E} A(u, v) · ⟨\frac{g(u) + h(u)}{2}, \frac{g(v) + h(v)}{2}⟩

− ∑_{\{u,v\}∈E} A(u, v) · ⟨\frac{g(u) − h(u)}{2}, \frac{g(v) − h(v)}{2}⟩

≤ sup_{f:V →S^{n−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩ −

inf_{f′:V →S^{n−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f′(u), f′(v)⟩

≤ ϑ(\overline{G}) sup_{f:V →S^{n−1}} ∑_{\{u,v\}∈E} A(u, v) · ⟨f(u), f(v)⟩,

where in the last line we used Theorem 3.5.

We can now sketch another proof of Theorem 3.3. Let Γ, Δ, B(H), f and f^{M} be as before. Now,

Γ = ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩
= ∑_{{u,v}∈E} A(u, v) · ⟨f(u)^{M}, f(v)^{M}⟩

+\frac{1}{2} ∑_{\{u,v\}∈E} A(u, v) · ⟨f(u) + f(u)^{M}, f(v) − f(v)^{M}⟩

+\frac{1}{2} ∑_{\{u,v\}∈E} A(u, v) · ⟨f(u) − f(u)^{M}, f(v) + f(v)^{M}⟩.  (12)

To bound the two last terms in (12) consider the functions g, h :→ L_{2}(Ω) given for u, v ∈ V by

g(u) = \frac{f(u) + f(u)^{M}}{2} and h(v) = \frac{f(v) − f(v)^{M}}{max_{w∈V} ∥f(w) − f(w)^{M}∥_{L_{2}(Ω)}} .

Then by Corollary 3.6 and (9) we get that

\frac{1}{2} ∑_{\{u,v\}∈E} A(u, v) · ⟨f(u) + f(u)^{M}, f(v) − f(v)^{M}⟩

= (max_{w∈V} ∥f(w) − f(w)^{M}∥_{L_{2}(Ω)}) · ∑_{{u,v}∈E} A(u, v) · ⟨g(u), h(v)⟩
≤ \sqrt{2M}e^{−M^{2}/4} · sup_{g′,h′:V →B(L_{2}(Ω))} ∑_{\{u,v\}∈E} A(u, v) · ⟨g′(u), h′(v)⟩
= \sqrt{2M}e^{−M^{2}/4} · sup_{g′,h′:V →S^{n−1}} ∑_{\{u,v\}∈E} A(u, v) · ⟨g′(u), h′(v)⟩
≤ k\sqrt{2M}e^{−M^{2}/4} · Γ.

Similarly,

\frac{1}{2} ∑_{\{u,v\}∈E} A(u, v) · ⟨f(u) − f(u)^{M}, f(v) + f(v)^{M}⟩ ≤ k\sqrt{2M}e^{−M^{2}/4} · Γ.

Plugging these estimates, together with (8), into (12) we conclude that

Γ ≤ M^{2}Δ + 2k\sqrt{2M}e^{−M^{2}/4} · Γ.

Choosing, as before, M = 8\sqrt{log k}, and simplifying, yields the assertion of Theorem 3.3.

Our next upper bound shows that for matrices with zeros on the diagonal whose entries are highly non-uniform, a better bound can be obtained for the constant K in the inequality appearing in Definition 2.1. This upper bound implies the O(log n) upper bound by the Cauchy-Schwartz inequality.

Theorem 3.7. There exists a universal constant C > 0 such that for every n × n matrix (a_{ij}) with a_{ii} = 0 for all i:

max_{∥x_{i}∥_{2}=1} ∑_{i,j=1}^{n} a_{ij}⟨x_{i}, x_{j}⟩ ≤ C log (\frac{∑_{i,j=1}^{n} |a_{ij}|}{\sqrt{∑_{i,j=1}^{n} a_{ij}^{2}}} ) · max_{ε_{i}∈\{−1,+1\}} ∑_{i,j=1}^{n} a_{ij}ε_{i}ε_{j}.

Proof. By the argument of [10], it is enough to show that the maximum of the quadratic form ⟨Ax, x⟩ over the discrete cube {−1, 1}^{n} is at least Ω(σ), where σ^{2} = ∑_{ij} a_{ij}^{2}. Let X be the random variable X = ⟨Ax, x⟩, where x = (x_{1}, …, x_{n}) and x_{i} are independent, identically distributed, uniform random variables on {−1, 1}. As a_{ii} = 0 for all i, the expectation of X is zero. Moreover, E(X^{2}) = ∑_{ij} a_{ij}^{2} = σ^{2}. Since X is a polynomial of degree two, the Bonamie-Beckner inequality [8] implies that E(X^{4}) = O(σ^{4}) (see also Lemma 3.3 in [4] for a direct argument). By part (ii) of Lemma 3.2 in [4], if the expectation of a random variable X is 0, E(X^{2}) = σ^{2} > 0 and E(X^{4}) ≤ bσ^{4}, then X exceeds \frac{σ}{4\sqrt{b}} with positive probability. This completes the proof.

4 A tight lower bound for the complete graph

In this section we refine the method of [19] and show that K(K_{n}) = Θ(log n).

Lemma 4.1. Let N be a 1-net in S^{d−1} (i.e. a maximal 1-separated subset of S^{n−1}). Assume that there is a function F : N → L_{∞}[0, 1] such that for every distinct x, y ∈ N we have ⟨x, y⟩ = ⟨F (x), F (y)⟩, and for every x ∈ N we have 1 ≤ ∥F (x)∥_{2}^{2} ≤ 1 + \frac{d}{3^{d+4}} . Then

max_{x∈N} ∥F (x)∥_{∞} ≥ \frac{\sqrt{d}}{8}.

Proof. By standard volume estimates, |N | ≤ 3^{d}. Let {e_{x}}_{x∈N} be the standard unit basis of ℝ^{N}. For every x ∈ N define w_{x} ∈ ℝ^{d} ⊕ ℝ^{N} by w_{x} = x + \sqrt{∥F (x)∥_{2}^{2} − 1} · e_{x}. Then ∥w_{x}∥_{2} = ∥F (x)∥_{2} and for every distinct x, y ∈ N we have ⟨w_{x}, w_{y}⟩ = ⟨x, y⟩ = ⟨F (x), F (y)⟩. It follows that the mapping T : span{w_{x} : x ∈ N } → span{F (N)} given by T (w_{x}) = F (x) is a linear isometry. Let T̃ : ℝ^{d} ⊕ ℝ^{N} → L_{2}[0, 1] be an arbitrary linear isometry which extends T.

Let ψ_{1}, …, ψ_{d} be an arbitrary orthonormal basis of T̃(ℝ^{d}) and for every t ∈ [0, 1] define

ρ_{t} = (∑_{i=1}^{d} \frac{ψ_{i}(t)}{\sqrt{∑_{i=1}^{d} ψ_{i}^{2}(t)}}ψ_{i}) · 1_{\{∑_{i=1}^{d} ψ_{i}^{2}(t)>0\}} ∈ T̃(B),

where B denotes the unit ball of ℝ^{d}. Since N is a 1-net in S^{d−1}, conv(N) ⊇ \frac{1}{2}B, so that conv(T̃(N)) ⊇ \frac{1}{2} T̃(B). It follows that for every t ∈ [0, 1] there is some x(t) ∈ N such that

T̃(x(t))(t) ≥ \frac{1}{2}ρ_{t}(t) = \frac{1}{2}\sqrt{∑_{i=1}^{d} ψ_{i}^{2}(t)}.  (13)

Define A = \{t ∈ [0, 1] : ∑_{i=1}^{d} ψ_{i}^{2}(t) ≥ \frac{d}{2}\} and for every x ∈ N put A_{x} = \{t ∈ A : x(t) = x\}.

Since ∑_{i=1}^{d} ∫_{0}^{1} ψ_{i}^{2}(t)dt = d and ∑_{i=1}^{d} ∫_{[0,1]\A} ψ_{i}^{2}(t)dt < d/2 it follows that ∑_{i=1}^{d} ∫_{A} ψ_{i}^{2}(t)dt > d/2. It follows from (13) that ∑_{x∈N} ∫_{A_{x}} T̃(x)^{2}(t)dt = ∫_{A} T̃(x(t))^{2}(t)dt > d/8. So, there is some x ∈ N for which ∫_{A_{x}} T̃(x)^{2}(t)dt ≥ d/(8|N |) > d/(8 · 3^{d}).

We claim that ∥F (x)∥_{∞} > ^{\frac{\sqrt{d}}{8}}. Indeed, assuming the contrary we have that for every t ∈ A_{x}, T̃(x)(t) − F (x)(t) > \frac{1}{2} T̃(x)(t), since for every t ∈ A_{x}, T̃(x)(t) ≥ \frac{1}{2}ρ_{t}(t) ≥ ^{\frac{\sqrt{d}}{4}}. But

∥F (x)∥_{2}^{2} − 1 = ∥w_{x} − x∥_{2}^{2} = ∥T̃(w_{x}) − T̃(x)∥_{2}^{2} ≥ ∫_{A_{x}}[F (x) − T̃(x)]^{2}(t)dt ≥ ∫_{A_{x}} \frac{T̃(x)^{2}(t)}{4}dt > \frac{d}{3^{d+4}} ,

contradicting our assumption.

Theorem 4.2. There exists a universal constant c > 0 such that for every integer n,

K(K_{n}) ≥ c log n.

Proof. Fix integers d, k and let N be a minimal 1-net in S^{d−1}. By the definition of the Gram representation constant, applied to the multi-set in which each element of N appears exactly k times, there are {f_{x,i} : x ∈ N , i ∈ {1, …, k}} ⊆ L_{∞}[0, 1] such that ∥f_{x,i}∥_{∞} ≤ R(K_{k3^{d}}) for every x and i, and for every distinct (x, i), (y, j) ∈ N × {1, …, k}:

⟨f_{x,i}, f_{y,j}⟩ = \{ \begin{matrix}⟨x, y⟩ & x ≠ y \\ 1 & x = y. \end{matrix}

Define F : N → L_{∞}[0, 1] by F (x) = \frac{1}{k} ∑_{i=1}^{k} f_{x,i}. Then for every distinct x, y ∈ N we have that ⟨F (x), F (y)⟩ = ⟨x, y⟩. Moreover, for every x ∈ N, using Lemma 3.1, we have that

∥F (x)∥_{2}^{2} = \frac{k(k − 1)}{k^{2}} + \frac{1}{k^{2}} ∑_{i=1}^{k} ∥f_{x,i}∥_{2}^{2} ≤ 1 − \frac{1}{k} + \frac{R(K_{k3^{d}})^{2}}{k} = 1 + O (\frac{log(k3^{d})}{k}) ≤ 1 + \frac{d}{3^{d+4}} , (14)

where we have chosen k = 6^{d}, and d is assumed to be large enough. Now, for every distinct i, j ∈ {1, …, k} we have that ∥f_{x,i}∥_{2}^{2} + ∥f_{x,j}∥_{2}^{2} ≥ 2⟨f_{x,i}, f_{x,j}⟩ = 2. Averaging this inequality over all such i, j we find that \frac{1}{k} ∑_{i=1}^{k} ∥f_{x,i}∥_{2}^{2} ≥ 1. By (14) we deduce that 1 ≤ ∥F (x)∥_{2}^{2} ≤ 1 + \frac{d}{3^{d+4}} , so that by Lemma 4.1, R(K_{18^{d}}) = Ω(\sqrt{d}). Since R(K_{n}) = \sqrt{K(K_{n})} is increasing in n, it follows that K(K_{n}) = Ω(log n).

5 Applications and examples

5.1 Algorithmic consequences

Our results yield polynomial time randomized algorithms for the following problem: Given a graph G = (V, E) and A : V × V → ℝ, we wish to approximate up to a small multiplicative factor the value of

β := max_{φ:V →{−1,1}} ∑_{{u,v}∈E} A(u, v) · φ(u)φ(v).  (15)

As we shall see presently, this combinatorial optimization problem encompasses several interesting algorithmic questions. A natural approach to the efficient evaluation of β is via semidefinite relaxation, namely we consider the value β^{∗} given by

β^{∗} := max_{f:V →S^{|V |−1}} ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩.  (16)

The continuous optimization problem in (16) is called the natural semidefinite relaxation of the combinatorial optimization problem in (15). Clearly β^{∗} ≥ β.

The advantage of passing to β^{∗} is that such a semidefinite optimization problem can be solved in polynomial time (up to an arbitrarily small additive error) using the ellipsoid algorithm (see, e.g., [13] for details on semidefinite programming). Hence, we can efficiently produce a mapping f : V → S^{|V |−1} such that ∑_{{u,v}∈E} A(u, v)·⟨f(u), f(v)⟩ ≥ (1−o(1))β^{∗}. The proofs of all of our upper bounds (namely Theorem 3.3 and Theorem 3.7) are algorithmic in the sense that they efficiently produce φ : V → {−1, 1} for which ∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩ is at most the constant ensured by these theorems times ∑_{{u,v}∈E} A(u, v) · φ(u)φ(v). Indeed, the proof of Theorem 3.3 shows that the algorithm simply has to generate |V | independent standard Gaussian random variables {g_{u}}_{u∈V} and consider the random scalar-valued function h : V → [−1, 1] given by

h(v) = \frac{1}{M} (∑_{u∈V} f(v)_{u}g_{u})^{M} ,

where M = 8\sqrt{log ϑ(\overline{G})} (observe that ϑ(\overline{G}) itself can be computed in polynomial time using senidefinite programming). As G has no loops, ∑_{{u,v}∈E} A(u, v)·h(u)h(v) is a linear function in each entry h(u), and we can thus shift each value of h(u) that lies in the open interval (−1, 1), in its turn, to the boundary, without decreasing the value of the quadratic form. Thus β^{∗} ≤ O(log ϑ(\overline{G})) · β, and in fact our randomized algorithm produces a distribution over functions φ : V :→ {−1, 1} such that in expectation ∑_{\{u,v\}∈E} A(u, v) · φ(u)φ(v) ≥ β/[O(log ϑ(\overline{G}))]. A similar algorithm can be designed by replacing the Gaussian random variables by independent, uniform ±1 Bernoulli random variables- see the argument in [3] for more details.

As observed in [3], the problem of finding the maximum of (3) is MAX-SNP hard even when the graph G is bipartite, and hence it is interesting to find efficiently an approximation of it. Some algorithmic applications (of the bipartite case) are given in [3]. Here we describe two additional natural applications.

The first application arises in the study of the spin glass model in mathematical physics. In this model, there is a system of atoms each of which has a spin that can point either up or down. Some of the pairs of atoms have non-negligible interactions. The system can be described by a graph G = (V, E), with a (not necessarily positive) weight A(u, v) for each edge uv ∈ E. The atoms are the vertices, the spin of the atom v is f(v) ∈ {−1, 1}, where 1 represents the “up” position, the weights A(u, v) represent the interactions between u and v, and the energy of the system (when there is no external field) is given by its Hamiltonian H = − ∑_{uv∈E} A(u, v)f(u)f(v). A ground state is a state that minimizes the energy, and thus the problem of finding a ground state is precisely that of finding the maximum of the integer program (3). See, e.g., [24], pp. 352-355, [27], and the references therein for more details.

It is known that if the graph G is planar, one can find a ground state in polynomial time using matching algorithms (see [7]), but in general this problem (which is equivalent to that of maximizing (3)) is NP-hard (and in fact even hard to approximate). Our technique here thus supplies an efficient way to find a configuration that approximates the minimum energy, and in many cases this approximation is up to a constant factor.

An additional algorithmic application of the fact one can find efficiently an approximation of (3) arises in the problem of maximizing correlation in correlation clustering.

Typical clustering problems involve the partitioning of a data set into classes which are small in some quantitative (typically metric) sense. In contrast, in correlation clustering, first considered in [6] (and referred to as clustering with qualitative information in [9]), we are given a judgement graph G = (V, E) and for every {u, v} ∈ E a real number A(u, v) which is interpreted as a judgement of the similarity of u and v. In the simplest case A(u, v) ∈ {1, −1}, where if A(u, v) = 1 then u, v are said to be similar, and if A(u, v) = −1 then u, v are said to be dissimilar. Given a partition of V into clusters, a pair is called an agreement if it is a similar pair within one cluster or a dissimilar pair across two distinct clusters. Analogously, a disagreement is a similar pair across two different clusters or a dissimilar pair in one cluster. In the maximum correlation problem (MAXCORR) the goal is to partition V so that the correlation is maximized, where the correlation of a partition is the difference of the number of agreements and the number of disagreements. In the case of general weights, for a partition P of V into pairwise disjoint clusters, the value of the partition, denoted by k(P), is the sum of all positive entries A(u, v) for u, v that lie in the same cluster, minus the sum of all positive entries A(u, v) for u, v that lie in distinct clusters, minus the sum of all values |A(u, v)| for negative entries A(u, v), where u, v lie in the same cluster, plus the sum of all values |A(u, v)| for negative entries A(u, v), where u, v lie in distinct clusters. The objective is to find a partition P whose value approximates the maximum possible value over all partitions.

The authors of [10] show that (2) can be used to provide an Ω(1/ log n) approximation algorithm for the maximum correlation in the correlation clustering problem when the judgement graph is the complete graph on n vertices. They prove that the maximum possible value of k(P) is at most 3 times the maximum between the value k_{n} of the trivial partition into clusters of size 1, and the maximum possible value v_{2} of a partition into two clusters. The latter is easily seen to be equivalent to the maximum of (3), and hence any algorithm that finds a solution giving at least an α-fraction of the maximum of (3) provides an α/3-approximation algorithm for the maximum correlation clustering problem (this can be slightly improved to \frac{α}{2+α} by being a bit more careful- see [10]). The authors of [10] conclude that there is an efficient Ω(1/ log n) approximation algorithm for the maximum correlation clustering problem for any graph G with n vertices. By the results here, the approximation guarantee can be improved to Ω(1/K(G)) = Ω(1/ log(ϑ(\overline{G}))). In particular, this is Ω(1) for any bounded degree graph or any graph with a bounded chromatic number or genus - in all these cases and some additional ones considered in the next subsection no constant factor approximation algorithm for MAXCORR was previously known.

5.2 Restricted families of graphs

By Theorems 3.3 and 4.2, if G is a graph containing a clique of size whose logarithm is proportional to the logarithm of the theta function of \overline{G}, then K(G) = Θ(log ω(G)). In particular, this holds for any perfect graph G, as in this case ω(G) = χ(G) = ϑ(\overline{G}). Note that certain classes of perfect graphs, like comparability graphs or chordal graphs, occur in various applications, and therefore it might be desirable to optimize quadratic forms as in (3) on such graphs. Since the chromatic number of perfect graphs can be determined in polynomial time, it follows that in such cases we can determine the value of K(G) up to a constant factor, and in case it is smaller than n^{ϵ} where n is the number of vertices, we can obtain a guaranteed improved approximation of (3).

Moreover, by the remark above and the fact that ϑ(\overline{G}) ≤ χ(G) for every G, K(G) = Θ(log(χ(G))) for any graph G whose chromatic number is bounded by a polynomial of the size of its largest clique. There are various known classes of such graphs, including complements of intersection graphs of the edges of hypergraphs with certain properties. See, for example, [2], [11]. Another interesting family of classes of graphs for which this holds is obtained as follows. Let k ≥ 2 be an integer, and let G_{k} denote the family of all graphs which contain no induced star on k vertices. In particular, G_{2} is the family of all unions of pairwise vertex disjoint cliques, and G_{3} is the family of all claw-free graphs. An easy application of Ramsey Theorem implies that the maximum degree Δ of any graph G ∈ G_{k} whose largest clique is of size ω, is at most ω^{k−1}. This implies that the chromatic number χ of any such graph is at most ω^{k−1} + 1, showing that (for fixed k) its Grothendieck constant is Θ(log Δ) = Θ(log ω) = Θ(log χ). Since the maximum degree (as well as the fact that G ∈ G_{k} for some fixed k) can be computed efficiently, this is another case in which we can compute the value of K(G) up to a constant factor.

A graph G is d-degenerate if any subgraph of it contains a vertex of degree at most d. It is easy and well known that any such graph is d + 1-colorable, and that there is a linear time algorithm that finds, for a given graph G, the smallest number d such that G is d-degenerate. In particular, graphs of genus g are O(\sqrt{g})-degenerate, implying that their Grothendieck constant is O(log g).

Other classes of graphs for which the clique number is proportional (with a universal constant) to the chromatic number (and hence also to the theta function of the complement), are intersection graphs of a family of homothetic copies of a fixed convex set in the plane- see [17]. A few additional examples appear in the next subsection.

5.3 New Grothendieck-type inequalities

Theorem 3.3 enables us to generate new Grothendieck type Inequalities, and Theorem 4.2 can be used to show that in some cases these are essentially tight. We list here several examples that seem interesting.

Let m > 2k > 1 be integers. The Kneser graph S(m, k) is the graph whose n = \binom{m}{k} vertices are all k-subsets of an m-element set, where two vertices are adjacent iff the corresponding subsets are disjoint. The clique number of S(m, k) is clearly ⌊m/k⌋, and as shown in [22], its chromatic number is m − 2k + 2. Its theta function, computed in [23], is \binom{m−1}{k−1}, and as this graph is vertex transitive, the product of its theta function and that of its complement is the number of its vertices (see [23]). It thus follows that the theta-function of the complement of S(m, k) is m/k. We conclude that the Grothendieck constant of S(m, k) is Θ(log(m/k)). This gives the following Grothendieck-type inequality.

Proposition 5.1. There exists an absolute constant c such that the following holds. Let m > 2k > 1 be positive integers. Put M = \{1, 2, …, m\}, n = \binom{m}{k}, and let A(I, J) be a real number for each pair of disjoint k-subsets I, J of M. Then for every vectors x_{I} of Euclidean norm 1, there are signs ϵ_{I} ∈ {−1, 1} such that

∑_{\begin{matrix}I,J⊂M \\ |I|=|J|=k \\ I∩J=∅ \end{matrix}} A(I, J)⟨x_{I}, x_{J}⟩ ≤ c log (\frac{m}{k}) ∑_{\begin{matrix}I,J⊂M \\ |I|=|J|=k \\ I∩J=∅ \end{matrix}} A(I, J)ϵ_{I}ϵ_{J}.

Moreover, the above inequality is tight, up to the constant factor c, for all admissible values of m and k.

Let D_{m} denote the line graph of the directed complete graph on m vertices. This is the graph whose vertices are all ordered pairs (i, j) with i, j ∈ M = {1, 2, …, m}, i ≠ j, in which (i, j) is adjacent to (j, k) for all for all admissible i, j, k ∈ M. It is known that the chromatic number of this graph is (1 + o(1)) log_{2} m, and it is not difficult to see that its clique number is 2 and its fractional chromatic number is at most 4, (see, for example, [5]). As shown in [23], the theta function of the complement of any graph is bounded by its fractional chromatic number. This gives the following inequality.

Proposition 5.2. There exists an absolute constant c such that the following holds. Let m be a positive integer, and let A(i, j, k) be a real for each i, j, k ∈ M, i ≠ j, j ≠ k. Then for every m(m − 1) vectors x_{i,j}, (i, j ∈ M, i ≠ j) of Euclidean norm 1, there are signs ϵ_{i,j} ∈ {−1, 1} such that

∑_{\begin{matrix}i,j,k∈M \\ i≠j≠k \end{matrix}} A(i, j, k)⟨x_{i,j}, x_{j,k}⟩ ≤ c ∑_{\begin{matrix}i,j,k∈M \\ i≠j≠k \end{matrix}} A(i, j, k)ϵ_{i,j}ϵ_{j,k}.

Let n = 2^{m}, and let M be as before. Let G be the comparability graph of all subsets of M, ordered by inclusion. Then G is a perfect graph, and its clique number is m + 1 = log n + 1. As G is perfect, this is also its chromatic number (and the theta function of its complement), providing the following inequality.

Proposition 5.3. There exists an absolute constant c such that the following holds. Let m be a positive integer, put n = 2^{m}, and let A(I, J) be a real for each I ⊊ J ⊆ M. Then for every n vectors x_{I}, (I ⊆ M) of Euclidean norm 1, there are signs ϵ_{I} ∈ {−1, 1} such that

∑_{I⊊J⊆M} A(I, J)⟨x_{I}, x_{J}⟩ ≤ c log log n ∑_{I⊊J⊆M} A(I, J)ϵ_{I}ϵ_{J}.

This is tight, up to the constant c.

6 Further inequalities

6.1 Tensor products and analytic functions

Let G = (V, E) be an n-vertex graph and f_{1}, …, f_{k} : V → S^{n−1}. Consider the function f : V → ℓ_{2} given by the tensor product f(v) = f_{1}(v) ⊗ f_{2}(v) ⊗ ⋯ ⊗ f_{k}(v). By the definition of K(G), for every A : V × V → ℝ we have that

∑_{{u,v}∈E} A(u, v) · ∏_{i=1}^{k}⟨f_{i}(u), f_{i}(v)⟩ ≤ K(G) max_{g:V →{−1,+1}} ∑_{{u,v}∈E} A(u, v) · g(u)g(v).

It follows that for every real analytic function Ψ : ℝ^{k} → ℝ, all of whose Taylor coefficients are non-negative, the following inequality holds true:

∑_{{u,v}∈E} A(u, v) · Ψ (⟨f_{1}(u), f_{1}(v)⟩, …, ⟨f_{k}(u), f_{k}(v)⟩)
≤ K(G) · Ψ(1, …, 1) max_{g:V →{−1,+1}} ∑_{{u,v}∈E} A(u, v) · g(u)g(v).

Similarly, there exists a function F : V → L_{∞}[0, 1] such that for every v ∈ V, ∥F (v)∥_{∞} ≤ R(G) · \sqrt{Ψ(1, …, 1)} and

{u, v} ∈ E ⟹ Ψ (⟨f_{1}(u), f_{1}(v)⟩, …, ⟨f_{k}(u), f_{k}(v)⟩) = ⟨F (u), F (v)⟩.

6.2 The homogenous Grothendieck inequality

The classical Grothendieck inequality has the following equivalent homogenous formulation: For every n × m matrix (a_{ij}),

sup_{x_{i},y_{j}∈ℓ_{2}} \frac{∑_{i=1}^{n} ∑_{j=1}^{m} a_{ij}⟨x_{i}, y_{j}⟩}{max_{i,j}(∥x_{i}∥_{2} · ∥y_{j}∥_{2})} ≤ K_{G} · sup_{x_{i},y_{j}∈ℝ} \frac{∑_{i=1}^{n} ∑_{j=1}^{m} a_{ij}x_{i}y_{j}}{max_{i,j}(|x_{i}| · |y_{j}|)} ,

where K_{G} is Grothendieck’s constant. Indeed, we clearly have that

sup_{x_{i},y_{j}∈ℝ} \frac{∑_{i=1}^{n} ∑_{j=1}^{m} a_{ij}x_{i}y_{j}}{max_{i,j}(|x_{i}| · |y_{j}|)} = sup_{ε_{i},δ_{j}∈\{−1,1\}} ∑_{i=1}^{n} ∑_{j=1}^{m} a_{ij}ε_{i}δ_{j},

and an analogous equality holds in the vector valued case.

For non-bipartite graphs the above phenomenon is no longer valid. To see this fix an integer m and consider the graph G = (V, E) where V = {u_{i}}_{i=1}^{m^{2}} ∪ {v_{j}}_{j=1}^{m} and

E = {{u_{i}, u_{j}} : i ≠ j} ∪ {{u_{i}, v_{j}} : 1 ≤ i ≤ m^{2}, 1 ≤ j ≤ m}.

Define a symmetric matrix A : V × V → ℝ via A(u_{i}, u_{j}) = −1 for all i ≠ j and A(u_{i}, v_{j}) = A(v_{j}, u_{i}) = 1 for all i ∈ {1, …, m^{2}} and j ∈ {1, …, m}. We claim that

max_{ε_{u}∈{−1,1}} ∑_{{u,v}∈E} A(u, v)ε_{u}ε_{v} ≤ 2m^{2}.

Indeed, fix {ε_{u}}_{u∈V} ⊆ {−1, 1}^{V} and define S = ∑_{i=1}^{m^{2}} ε_{u_{i}}. Then

∑_{\{u,v\}∈E} A(u, v)ε_{u}ε_{v} = − ∑_{\begin{matrix}i,j∈\{1,...,m^{2}\} \\ i≠j \end{matrix}} ε_{u_{i}}ε_{u_{j}} + 2 ∑_{i=1}^{m^{2}} ∑_{j=1}^{m} ε_{u_{i}}ε_{v_{j}}

= m^{2} − S^{2} + 2S ∑_{j=1}^{m} ε_{v_{j}}
≤ m^{2} − S^{2} + 2m|S|
≤ 2m^{2}.

On the other hand,

sup_{x_{u}∈ℝ} \frac{∑_{\{u,v\}∈E} A(u, v)x_{u}x_{v}}{max_{\{u,v\}∈E}(|x_{u}| · |x_{v}|)} ≥ m^{3} + m.

Indeed, let x_{u_{i}} = \frac{1}{\sqrt{m}} and x_{v_{j}} = \sqrt{m}. Then

\frac{∑_{\{u,v\}∈E} A(u, v)x_{u}x_{v}}{max_{\{u,v\}∈E}(|x_{u}| · |x_{v}|)} = −\frac{m^{4} − m^{2}}{m} + 2m^{3} = m^{3} + m.

In view of this example, it is of interest to study the natural homogenous extension of Grothendieck’s inequality in the case of arbitrary graphs. We do not attempt to study this independently interesting notion here, except for the following variant of Theorem 3.3:

Proposition 6.1. There is a universal constant C > 0 such that for every loop-free graph G = (V, E) and for every A : V × V → ℝ,

sup_{f:V →ℓ_{2}} \frac{∑_{\{u,v\}∈E} A(u, v)⟨f(u), f(v)⟩}{max_{\{u,v\}∈E}(∥f(u)∥_{2} · ∥f(v)∥_{2})} ≤ (C log ϑ(\overline{G})) · sup_{f:V →ℝ} \frac{∑_{\{u,v\}∈E} A(u, v)f(u)f(v)}{max_{\{u,v\}∈E}(|f(u)| · |f(v)|)}.

Proof. We shall use the notation of the proof of Theorem 3.3. Let Φ be the least constant ϕ > 0 such that for every f : V → L_{2}(Ω)

∑_{{u,v}∈E} A(u, v) · ⟨f(u), f(v)⟩ ≤ ϕ · max_{{u,v}∈E} (∥f(u)∥_{L_{2}(Ω)} · ∥f(v)∥_{L_{2}(Ω)}) .

We clearly have that Φ ≤ |V |^{2} · max_{u,v∈V} |A(u, v)| < ∞.

Fix ρ > 0 such that for every f : V → ℝ

∑_{{u,v}∈E} A(u, v) · f(u)f(v) ≤ ρ · max_{{u,v}∈E} (|f(u)| · |f(v)|) .

We will conclude once we show that Φ ≤ C log k · ρ.

Fix f : V → H for which

∑_{\{u,v\}∈E} A(u, v) · ⟨f(u), f(v)⟩ ≥ \frac{Φ}{2} · max_{\{u,v\}∈E} (∥f(u)∥_{L_{2}(Ω)} · ∥f(v)∥_{L_{2}(Ω)}) .

The existence of f follows from the fact that H and L_{2}(Ω) are isometric.

Observe that the following identity holds true:

\frac{Φ}{2} · max_{\{u,v\}∈E} (∥f(u)∥_{L_{2}(Ω)} · ∥f(v)∥_{L_{2}(Ω)}) ≤ ∑_{\{u,v\}∈E} A(u, v) · ⟨f(u), f(v)⟩)

= ∑_{{u,v}∈E} A(u, v) · ⟨f(u)^{M∥f(u)∥_{L_{2}(Ω)}}, f(v)^{M∥f(v)∥_{L_{2}(Ω)}}⟩ +

\frac{1}{2} ∑_{\{u,v\}∈E} A(u, v) · ⟨f(u) + f(u)^{M∥f(v)∥_{L_{2}(Ω)}}, f(v) − f(v)^{M∥f(v)∥_{L_{2}(Ω)}}⟩ +

\frac{1}{2} ∑_{\{u,v\}∈E} A(u, v) · ⟨f(u) − f(u)^{M∥f(v)∥_{L_{2}(Ω)}}, f(v) + f(v)^{M∥f(v)∥_{L_{2}(Ω)}}⟩ .  (17)

Now,

∑_{{u,v}∈E} A(u, v) · ⟨f(u)^{M∥f(u)∥_{L_{2}(Ω)}}, f(v)^{M∥f(v)∥_{L_{2}(Ω)}}⟩ ≤ M^{2} · max_{{u,v}∈E} (∥f(u)∥_{L_{2}(Ω)} · ∥f(v)∥_{L_{2}(Ω)}) · ρ.

Additionally, by the definition of Φ, the sum of additional terms in (17) is bounded by (as in Theorem 3.3)

(\frac{1}{2} + 8kMe^{−M^{2}/4})^{2} · Φ · max_{\{u,v\}∈E} (∥f(u)∥_{L_{2}(Ω)} · ∥f(v)∥_{L_{2}(Ω)}) ,

Plugging these estimates into (17) we get that:

\frac{Φ}{2} ≤ M^{2} · ρ + (\frac{1}{2} + 8kMe^{−M^{2}/4})^{2} · Φ.

Choosing M = 4\sqrt{log k}, and simplifying, yields the required result.

7 Open problems

The investigation of the parameter K(G) and the optimization problem (3) leads to several interesting problems that remain open. In particular, we mention the following.

• Find an explicit family of matrices showing that K(K_{n}) = Ω(log n).

• Is there a lower bound for K(G) in terms of ϑ(\overline{G})?

• Can the optimal value of (3) be approximated efficiently within a constant factor ? It is easy to see that this problem is MAX-SNP hard even for bipartite graphs, as observed in [3], but it will be interesting to show that for general graphs it cannot be approximated efficiently to within any constant factor.

• Let G = G(n, 1/2) be the random graph on n labelled vertices obtained by picking each pair of distinct vertices to form an edge, randomly and independently, with probability 1/2. Is it true that almost surely (that is, with probability that tends to 1 as n tends to infinity), K(G) = Θ(log n) ?

Note that it is known that the clique number of G is, almost surely, Θ(log n), and the theta function of its complement is, almost surely, Θ(\sqrt{n}), (see [16]), implying that the Grothendieck constant K(G) lies between Θ(log log n) and Θ(log n), and that for this example it differs considerably either from the logarithm of the clique number or from that of the theta function of \overline{G}. Another example of a family of graphs with an even larger difference between these logarithms is given in [1], where graphs on n vertices with clique number 2 for which ϑ(\overline{G}) = Θ(n^{1/3}) are constructed.

Acknowledgement. We are grateful to Itai Benjamini for pointing out the connection to the spin glass model, and we thank Moses Charikar for useful comments and suggestions. We also thank the anonymous referees for several comments that improved the presentation of our results.

Added in proof. Some of the problems posed above have been addressed in the recent manuscript “On non-approximability for quadratic programs”, by S. Arora, E. Berger, E. Hazan, G. Kindler and S. Safra. It is shown there that there exists a constant γ > 0 such that if NP ⊈ DT IME (n^{(log n)^{3}}), then the optimal value of (3), in the case G = K_{n}, cannot be approximated in polynomial time to a factor smaller than O ((log n)^{γ}). Additionally, an explicit family of matrices is constructed, showing that K(K_{n}) = Ω (\frac{log n}{log log n}).

References

[1] N. Alon, Explicit Ramsey graphs and orthonormal labelings, The Electronic J. Combinatorics 1 (1994), R12, 8pp.

[2] N. Alon, Covering a hypergraph of subgraphs, Discrete Mathematics 257 (2002), 249-254.

[3] N. Alon and A. Naor, Approximating the Cut-Norm via Grothendieck’s Inequality, Proc. of the 36^{th} ACM STOC, 72-80, 2004.

[4] N. Alon, G. Gutin and M. Krivelevich, Algorithms with large domination ratio, J. Algorithms 50 (2004), 118-131.

[5] N. Alon and A. Orlitsky, Repeated communication and Ramsey graphs, IEEE Transactions on Information Theory 41 (1995), 1276-1289.

[6] N. Bansal, A. Blum and S. Chowla, Correlation Clustering, Proc. of the 43 IEEE FOCS, 238-247, 2002.

[7] F. Barahona, On the computational complexity of Ising spin glass models, J. Phys. A: Math. Gen. 15 (1982), 3241-3253.

[8] A. Bonamie, Etude de coefficients Fourier des fonctiones de L^{p}(G). Ann. Inst. Fourier 20, 335-402, 1970.

[9] M. Charikar, V. Guruswami and A. Wirth, Clustering with qualitative information. Proc. of the 44 IEEE FOCS, 524–533, 2003.

[10] M. Charikar and A. Wirth, Maximizing quadratic programs: extending Grothendieck’s Inequality, FOCS 2004, 54-60.

[11] G. Ding, P. D. Seymour and P. Winkler, Bounding the vertex cover number of a hypergraph, Combinatorica 14 (1994), 23–34.

[12] A. M. Frieze and R. Kannan, Quick Approximation to matrices and applications, Combinatorica 19 (1999), 175–200.

[13] M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), 169–197.

[14] A. Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. Sao paolo, 8:1-79, 1953.

[15] W. B. Johnson and J. Lindenstrauss, Basic concepts in the geometry of Banach spaces, Handbook of the geometry of Banach spaces, Vol. I, 1–84, North-Holland, Amsterdam, 2001.

[16] F. Juhász, The asymptotic behaviour of Lovász’ θ function for random graphs, Combinatorica 2 (1982), 153–155.

[17] S.-J. Kim, A. Kostochka and K. Nakprasit, On the Chromatic Number of Intersection Graphs of Convex Sets in the Plane, The Electronic J. Combinatorics 11 (2004), R52, 12pp.

[18] D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM, Vol. 45(2), 1998, pp. 246-265.

[19] B. S. Kashin and S. J. Szarek, On the Gram Matrices of Systems of Uniformly Bounded Functions. Proceedings of the Steklov Institute of Mathematics, Vol. 243, 2003, pp. 227-233.

[20] J. Krivine, Sur la constante de Grothendieck. C. R. Acad. Sci. Paris Ser. A-B, 284:445-446, 1977.

[21] J. Lindenstrauss and A. Pełczyński, Absolutely summing operators in L_{p} spaces and their applications. Studia Math. 29, 275-326, 1968.

[22] L. Lovász. Kneser’s conjecture, chromatic number and homotopy, Journal of Combinatorial Theory, 25:319–324, 1978.

[23] L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information Theory 25(1) (1979), pp. 1-7.

[24] L. Lovász and M. D. Plummer, Matching Theory, North Holland, Amsterdam (1986).

[25] A. Megretski, Relaxation of Quadratic Programs in Operator Theory and System Analysis. In Systems, Approximation, Singular Integral Operators, and Related Topics (Bordeaux, 2000), Basel: Birkhäuser, 2001, pp. 365-392.

[26] A. Nemirovski, C. Roos and T. Terlaky, On Maximization of Quadratic Form over Intersection of Ellipsoids with Common Center. Mathematical Programming, 1999, Vol. 86 Issue 3, pp. 463-473.

[27] M. Talagrand, Spin glasses: a challenge for mathematicians. Cavity and mean field models, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge, 46. Springer-Verlag, Berlin, 2003.