Explicit Ramsey graphs and orthonormal labelings

Noga Alon ^{∗}

Submitted: August 22, 1994; Accepted October 29, 1994

Abstract We describe an explicit construction of triangle-free graphs with no independent sets of size m and with Ω(m^{3/2}) vertices, improving a sequence of previous constructions by various authors. As a byproduct we show that the maximum possible value of the Lovász θ-function of a graph on n vertices with no independent set of size 3 is Θ(n^{1/3}), slightly improving a result of Kashin and Konyagin who showed that this maximum is at least Ω(n^{1/3}/ log n) and at most O(n^{1/3}). Our results imply that the maximum possible Euclidean norm of a sum of n unit vectors in R^{n}, so that among any three of them some two are orthogonal, is Θ(n^{2/3}).

1 Introduction

Let R(3, m) denote the maximum number of vertices of a triangle-free graph whose independence number is at most m. The problem of determining or estimating R(3,m) is a well studied Ramsey type problem. Ajtai, Komlós and Szemerédi proved in [1] that R(3, m) ≤ O(m^{2}/ log m), (see also [17] for an estimate with a better constant). Improving a result of Erdös , who showed in [7] that R(3, m) ≥ Ω((m/ log m)^{2}), (see also [18], [13] or [4] for a simpler proof), Kim [10] proved, very recently, that the upper bound is tight, up to a constant factor, that is: R(3, m) = Θ(m^{2}/ log m). His proof, as well as that of Erdös, is probabilistic, and does not supply any explicit construction of such a graph. The problem of finding an explicit construction of triangle-free graphs of independence number m and many vertices has also received a considerable amount of attention. Erdös [8] gave an explicit construction of such graphs with

Ω(m^{(2 log 2)/3(log 3−log 2)}) = Ω(m^{1.13})

vertices. This has been improved by Cleve and Dagum [6], and improved further by Chung, Cleve and Dagum in [5], where the authors present a construction with

Ω(m^{log 6/ log 4}) = Ω(m^{1.29})

∗AT & T Bell Labs, Murray Hill, NJ 07974, USA and Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel. Research supported in part by a United States Israel BSF Grant.

the electronic journal of combinatorics 1 (1994),#R12 2 vertices. The best known explicit construction is given in [2], where the number of vertices is Ω(m^{4/3}).

Here we improve this bound and describe an explicit construction of triangle free graphs with independence numbers m and Ω(m^{3/2}) vertices. Our graphs are Cayley graphs and their construction is based on some of the properties of certain Dual BCH error-correcting codes. The bound on their independence numbers follows from an estimate of their Lovász θ-function. This fascinating function, introduced by Lovász in [14], can be defined as follows. If G = (V, E) is a graph, an orthonormal labeling of G is a family (b_{v})_{v∈V} of unit vectors in an Euclidean space so that if u and v are distinct non-adjacent vertices, then b_{u}^{t}b_{v} = 0, that is, b_{u} and b_{v} are orthogonal. The θ-number θ(G) is the minimum, over all orthonormal labelings b_{v} of G and over all unit vectors c, of

max_{v∈V} \frac{1}{(c^{t}b_{v})^{2}} .

It is known (and easy; see [14]) that the independence number of G does not exceed θ(G). The graphs G_{n} we construct here are triangle free graphs on n vertices satisfying θ(G_{n}) = Θ(n^{2/3}), and hence the independence number of G_{n} is at most O(n^{2/3}).

The construction and the properties of the θ-function settle a geometric problem posed by Lovász and partially solved by Kashin and Konyagin [12], [9]. Let Δ_{n} denote the maximum possible value of the Euclidean norm || ∑_{i=1}^{n} u_{i}|| of the sum of n unit vectors u_{1}, …, u_{n} in R^{n}, so that among any three of them some two are orthogonal. Motivated by the study of the θ-function, Lovász raised the problem of determining the order of magnitude of Δ_{n}. In [12] it is shown that Δ_{n} ≤ O(n^{2/3}) and in [9] it is proved that this is nearly tight, namely that Δ_{n} ≥ Ω(n^{2/3}/(log n)^{1/2}). Here we show that the upper bound is tight up to a constant factor, that is:

Δ_{n} = Θ(n^{2/3}).

The rest of this note is organized as follows. In Section 2 we construct our graphs and estimate their θ-numbers and their independence numbers. The resulting lower bound for Δ_{n} is described in Section 3. Our method in these sections combines the ideas of [9] with those in [2]. The final Section 4 contains some concluding remarks.

2 The graphs

For a positive integer k, let F_{k} = GF (2^{k}) denote the finite field with 2^{k} elements. The elements of F_{k} are represented, as usual, by binary vectors of length k. If a, b and c are three such vectors, let (a, b, c) denote their concatenation, i.e., the binary vector of length 3k whose coordinates are those of a, followed by those of b and those of c. Suppose k is not divisible by 3 and put n = 2^{3k}. Let W_{0} be the set of all nonzero elements α ∈ F_{k} so that the leftmost bit in the binary representation of α^{7} is 0, and let W_{1} be the set of all nonzero elements α ∈ F_{k} for which the leftmost bit of α^{7} is the electronic journal of combinatorics 1 (1994),#R12 3 1. Since 3 does not divide k, 7 does not divide 2^{k} − 1 and hence |W_{0}| = 2^{k−1} − 1 and |W_{1}| = 2^{k−1}, as when α ranges over all nonzero elements of F_{k} so does α^{7}.

Let G_{n} be the graph whose vertices are all n = 2^{3k} binary vectors of length 3k, where two vectors u and v are adjacent if and only if there exist w_{0} ∈ W_{0} and w_{1} ∈ W_{1} so that u + v = (w_{0}, w_{0}^{3}, w_{0}^{5}) + (w_{1}, w_{1}^{3}, w_{1}^{5}), where here the powers are computed in the field F_{k} and the addition is addition modulo 2. Note that G_{n} is the Cayley graph of the additive group (Z_{2})^{3k} with respect to the generating set S = U_{0}+U_{1} = {u_{0}+u_{1} : u_{0} ∈ U_{0}, u_{1} ∈ U_{1}}, where U_{0} = {(w_{0}, w_{0}^{3}, w_{0}^{5}) : w_{0} ∈ W_{0}}, and U_{1} is defined similarly. The following theorem summerizes some of the properties of the graphs G_{n}.

Theorem 2.1 If k is not divisible by 3 and n = 2^{3k} then G_{n} is a d_{n} = 2^{k−1}(2^{k−1} − 1)-regular graph on n = 2^{3k} vertices with the following properties.

1. G_{n} is triangle-free.

2. Every eigenvalue μ of G_{n}, besides the largest, satisfies

−9 · 2^{k} − 3 · 2^{k/2} − 1/4 ≤ μ ≤ 4 · 2^{k} + 2 · 2^{k/2} + 1/4.

3. The θ-function of G_{n} satisfies

θ(G_{n}) ≤ n\frac{36 · 2^{k} + 12 · 2^{k/2} + 1}{2^{k}(2^{k} − 2) + 36 · 2^{k} + 12 · 2^{k/2} + 1} ≤ (36 + o(1))n^{2/3},

where here the o(1) term tends to 0 as n tends to infinity.

Proof. The graph G_{n} is the Cayley graph of Z_{2}^{3k} with respect to the generating set S = S_{n} = U_{0} + U_{1}, where U_{i} are defined as above.

Let A_{0} be the 3k by 2^{k−1} − 1 binary matrix whose columns are all vectors of U_{0}, and let A_{1} be the 3k by 2^{k−1} matrix whose columns are all vectors of U_{1}. Let A = [A_{0}, A_{1}] be the 3k by 2^{k} − 1 matrix whose columns are all those of A_{0} and those of A_{1}. This matrix is the parity check matrix of a binary BCH-code of designed distance 7 (see, e.g., [16], Chapter 9), and hence every set of six columns of A is linearly independent over GF (2). In particular, all the sums (u_{0}+u_{1})_{u_{0}∈U_{0},u_{1}∈U_{1}} are distinct and hence |S_{n}| = |U_{0}||U_{1}|. It follows that G_{n} has 2^{3k} vertices and it is |S_{n}| = 2^{k−1}(2^{k−1} −1) regular.

The fact that G_{n} is triangle-free is equivalent to the fact that the sum (modulo 2) of any set of 3 elements of S_{n} is not the zero-vector. Let u_{0} + u_{1}, u′_{0} + u′_{1} and u”_{0} + u”_{1} be three distinct elements of S_{n}, where u_{0}, u′_{0}, u”_{0} ∈ U_{0} and u_{1}, u′_{1}, u”_{1} ∈ U_{1}. If the sum (modulo 2) of these six vectors is zero then, since every six columns of A are linearly independent, every vector must appear an even number of times in the sequence (u_{0}, u′_{0}, u”_{0}, u_{1}, u′_{1}, u”_{1}). However, since U_{0} and U_{1} are disjoint this implies that every vector must appear an even number of times in the sequence (u_{0}, u′_{0}, u”_{0}) and this is clearly impossible. This proves part 1 of the theorem. the electronic journal of combinatorics 1 (1994),#R12 4

In order to prove part 2 we argue as follows. Recall that the eigenvalues of Cayley graphs of abelian groups can be computed easily in terms of the characters of the group. This result, decsribed in, e.g., [15], implies that the eigenvalues of the graph G_{n} are all the numbers

∑_{s∈S_{n}} χ(s),

where χ is a character of Z_{2}^{3k}. By the definition of S_{n}, these eigenvalues are precisely all the numbers

( ∑_{u_{0}∈U_{0}} χ(u_{0}))( ∑_{u_{1}∈U_{1}} χ(u_{1})).

It follows that these eigenvalues can be expressed in terms of the Hamming weights of the linear combinations (over GF (2)) of the rows of the matrices A_{0} and A_{1} as follows. Each linear combination of the rows of A of Hamming weight x + y, where the Hamming weight of its projection on the columns of A_{0} is x and the weight of its projection on the columns of A_{1} is y, corresponds to the eigenvalue

(2^{k−1} − 1 − 2x)(2^{k−1} − 2y).

Our objective is thus to bound these quantities.

The linear combinations of the rows of A are simply all words of the code whose generating matrix is A, which is the dual of the BCH-code whose parity-check matrix is A. It is known (see [16], pages 280-281) that the Carlitz-Uchiyama bound implies that the Hamming weight x + y of each non-zero codeword of this dual code satisfies

2^{k−1} − 2^{1+k/2} ≤ x + y ≤ 2^{k−1} + 2^{1+k/2}.  (1)

Let p denote the characteristic vector of W_{1}, that is, the binary vector indexed by the non-zero elements of F_{k} which has a 1 in each coordinate indexed by a member of W_{1} and a 0 in each coordinate indexed by a member of W_{0}. Note that the sum (modulo 2) of p and any linear combination of the rows of A is a non-zero codeword in the dual of the BCH-code with designed distance 9. Therefore, by the Carlitz-Uchiyama bound, the Hamming weight of the sum of p with the linear combination considered above, which is x + (2^{k−1} − y), satisfies

2^{k−1} − 3 · 2^{k/2} ≤ x + 2^{k−1} − y ≤ 2^{k−1} + 3 · 2^{k/2}.  (2)

Since for any two reals a and b,

−(\frac{a − b}{2})^{2} ≤ ab ≤ (\frac{a + b}{2})^{2}

we conclude from (1) that

(2^{k−1} − 1 − 2x)(2^{k−1} − 2y) ≤ \frac{(2^{k} − 1 − 2(x + y))^{2}}{4} ≤ 4 · 2^{k} + 2 · 2^{k/2} + 1/4.

Similarly, (2) implies that

(2^{k−1} − 1 − 2x)(2^{k−1} − 2y) ≥ −\frac{(1 + 2(x − y))^{2}}{4} ≥ −9 · 2^{k} − 3 · 2^{k/2} − 1/4.

This completes the proof of part 2 of the theorem.

Part 3 follows from part 2 together with Theorem 9 of [14] which asserts that for d-regular graphs G with eigenvalues d = λ_{1} ≥ λ_{2} ≥ … ≥ λ_{n},

θ(G) ≤ \frac{−nλ_{n}}{λ_{1} − λ_{n}} .

It is worth noting that the fact that the right hand side in the last inequality bounds the independence number of G is due to A. J. Hoffman. □

Since the independence number of each graph G does not exceed θ(G) the following result follows.

Corollary 2.2 If k is not divisible by 3 and n = 2^{3k}, then the graph G_{n} is a triangle-free graph with independence number at most (36 + o(1))n^{2/3}. □

Let G_{n} be one of the graphs above and let \overline{G}_{n} denote its complement. Since G_{n} is a Cayley graph, Theorem 8 in [14] implies that θ(\overline{G}_{n})θ(G_{n}) = n and hence, by Theorem 2.1, θ(\overline{G}_{n}) ≥ (1 + o(1))\frac{1}{36}n^{1/3}.

In [9] it is proved (in a somewhat disguised form), that for any graph H with n vertices and no independent set of size 3, θ(H) ≤ 2^{2/3}n^{1/3}. (See also [3] for an extension). Since \overline{G}_{n} has no independent set of size 3 and since for every graph H, θ(H)θ(\overline{H}) ≥ n (see Corollary 2 of [14]) the following result follows.

Corollary 2.3 If k is not divisible by 3 and n = 2^{3k}, then θ(G_{n}) = Θ(n^{2/3}) and θ(\overline{G}_{n}) = Θ(n^{1/3}). Therefore, the minimum possible value of the θ-number of a triangle-free graph on n vertices is Θ(n^{2/3}) and the maximum possible value of the θ-number of an n-vertex graph with no independent set of size 3 is Θ(n^{1/3}).

3 Nearly orthogonal systems of vectors

A system of n unit vectors u_{1}, …, u_{n} in R^{n} is called nearly orthogonal if any set of three vectors of the system contains an orthogonal pair. Let Δ_{n} denote the maximum possible value of the Euclidean norm || ∑_{i=1}^{n} u_{i}||, where the maximum is taken over all systems u_{1}, …, u_{n} of nearly orthogonal vectors. Lovász raised the problem of determining the order of magnitude of Δ_{n}. Konyagin showed in [12] that Δ_{n} ≤ O(n^{2/3}) and that

Δ_{n} ≥ Ω(n^{4/3−log 3/2 log 2}) ≥ Ω(n^{0.54}).

The lower bound was improved by Kashin and Konyagin in [9], where it is shown that

Δ_{n} ≥ Ω(n^{2/3}/(log n)^{1/2})

.

The following theorem asserts that the upper bound is tight up to a constant factor.

Theorem 3.1 There exists an absolute positive constant a so that for every n

Δ_{n} ≥ an^{2/3}.

Thus, Δ_{n} = Θ(n^{2/3}).

Proof. It clearly suffices to prove the lower bound for values of n of the form n = 2^{3k}, where k is an integer and 3 does not divide k. Fix such an n, let G = G_{n} = (V, E) be the graph constructed in the previous section and define θ = θ(G). By Theorem 2.1, θ ≤ (36 + o(1))n^{2/3}. By the definition of θ there exists an orthonormal labeling (b_{v})_{v∈V} of G and a unit vector c so that (c^{t}b_{v})^{2} ≥ 1/θ for every v ∈ V. Therefore, the norm of the projection of each b_{v} on c is at least 1/\sqrt{θ} and by assigning appropriate signs to the vectors b_{v} we can ensure that all these projections are in the same direction. With this choice of signs, the norm of the projection of ∑_{v∈V} b_{v} on c is at least n/\sqrt{θ}, implying that

|| ∑_{v∈V} b_{v}|| ≥ n/\sqrt{θ} ≥ (\frac{1}{6} − o(1))n^{2/3}.

Note that since the vectors b_{v} form an orthonormal labeling of G, which is triangle-free, among any three of them there are some two which are orthogonal. This implies that (b_{v})_{v∈V} is a nearly orthogonal system and shows that for every n = 2^{3k} as above

Δ_{n} ≥ (\frac{1}{6} − o(1))n^{2/3},

completing the proof of the theorem. □

4 Concluding remarks

The method applied here for explicut constructions of triangle-free graphs with small independence numbers cannot yield asymptotically better constructions. This is because the independence number is bounded here by bounding the θ-number which, by Corollary 2.3, cannot be smaller than Θ(n^{2/3}) for any triangle-free graph on n vertices.

Some of the results of [9] can be extended. In a forthcoming paper with N. Kahale [3] we show that for every k ≥ 3 and every graph H on n vertices with no independent set of size k,

θ(H) ≤ Mn^{1−2/k},  (3)

the electronic journal of combinatorics 1 (1994),#R12 7 for some absolute positive constant M. It is not known if this is tight for k > 3. Combining this with some of the properties of the θ-function, this can be used to show that for every k ≥ 3 and any system of n unit vectors u_{1}, …, u_{n} in R^{n} so that among any k of them some two are orthogonal, the inequality

|| ∑_{i=1}^{n} u_{i}|| ≤ O(n^{1−1/k})

holds. This is also not known to be tight for k > 3. Lovász (cf. [11]) conjectured that there exists an absolute constant c so that for every graph H on n vertices and no independent set of size k,

θ(H) ≤ ck\sqrt{n}.

Note that this conjecture, if true, would imply that the estimate (3) above is not tight for all fixed k > 4. Acknowledgment I would like to thank Nabil Kahale for helpful comments and Rob Calderbank for fruitful suggestions that improved the presentation significantly.

References

[1] M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Combinatorial Theory Ser. A 29 (1980), 354-360.

[2] N. Alon, Tough Ramsey graphs without short cycles, to appear.

[3] N. Alon and N. Kahale, in preparation.

[4] N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, 1991.

[5] F. R. K. Chung, R. Cleve and P. Dagum, A note on constructive lower bounds for the Ramsey numbers R(3, t), J. Combinatorial Theory Ser. B 57 (1993), 150-155.

[6] R. Cleve and P. Dagum, A constructive Ω(t^{1.26}) lower bound for the Ramsey number R(3, t), Inter. Comp. Sci. Inst. Tech. Rep. TR-89-009, 1989.

[7] P. Erdös, Graph Theory and Probability, II, Canad. J. Math. 13 (1961), 346-352.

[8] P. Erdös, On the construction of certain graphs, J. Combinatorial Theory 17 (1966), 149-153.

[9] B. S. Kashin and S. V. Konyagin, On systems of vectors in a Hilbert space, Trudy Mat. Inst. imeni V. A. Steklova 157 (1981), 64-67. English translation in: Proc. of the Steklov Institute of Mathematics (AMS 1983), 67-70.

[10] J. H. Kim, The Ramsey number R(3, t) has order of magnitude t^{2}/ log t, to appear. the electronic journal of combinatorics 1 (1994),#R12 8 [11] D. E. Knuth, The sandwich theorem, Electronic Journal of Combinatorics A1 (1994), 48pp.

[12] S. V. Konyagin, Systems of vectors in Euclidean space and an extremal problem for polynomials, Mat. Zametki 29 (1981), 63-74. English translation in: Mathematical Notes of the Academy of the USSR 29 (1981), 33-39.

[13] M. Krivelevich, Bounding Ramsey numbers through large deviation inequalities, to appear.

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

[15] L. Lovász, Combinatorial Problems and Exercises, North Holland, Amsterdam, 1979, Problem 11.8.

[16] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1977.

[17] J. B. Shearer, A note on the independence number of a triangle-free graph, Discrete Math. 46 (1983), 83-87.

[18] J. Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math. 20 (1977), 69-76.