Rank and Chromatic Number of a Graph Andreı̆ Kotlov DEPARTMENT OF MATHEMATICS YALE UNIVERSITY NEW HAVEN, CT 06520 E-mail: avkotlov@math.uwaterloo.ca Received June 6, 1996 Abstract: It was proved (A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph √ Theory 23 (1996), 185–189) that the number of vertices in a twin-free graph is O(( 2)r ) where r is the rank of the adjacency matrix. This bound was shown to√be tight. We c 1997 John show that the chromatic number of a graph is o(∆r ) where ∆ = 4/3 < 2. Wiley & Sons, Inc. J Graph Theory 26: 1–8, 1997 Keywords: rank, chromatic number, independence number 1. INTRODUCTION It was conjectured in 1976 by C. van Nuffelen [10] that the chromatic number of any graph with at least one edge does not exceed the rank of its adjacency matrix. Interest in this conjecture was increased substantially when it was rediscovered, independently, by a computer [2], and, perhaps even more significantly, when its connection to a fundamental problem in the theory of communication complexity was observed by Lovász [6]. The first counterexample to van Nuffelen’s conjecture was obtained in 1989 by Alon and Seymour [1]. They constructed a graph with chromatic number 32 and with an adjacency matrix of rank 29. In 1992 Razborov showed that the gap between the chromatic number and the rank of the adjacency matrix was superlinear [8]. In 1993 Raz and Spieker [9] proved that the chromatic number was not bounded by any polynomial in the rank. The best result known so far is due to Nisan and Wigderson [7]. It gives (if translated to these terms) an infinite family of graphs with α rank r and with chromatic number χ = 2Ω(log r) , where α = log3 6 > 1. c 1997 John Wiley & Sons, Inc. CCC 0364-9024/97/010001-08 2 JOURNAL OF GRAPH THEORY In this paper we investigate the upper bound on the chromatic number of a graph in terms of the rank r of its adjacency matrix. We call a graph twin-free if its nodes have pairwise different sets of neighbors. Recently it was shown in [5] that √ Theorem 1. The number of vertices in a twin-free graph is O(( 2)r ). Moreover, this bound is the best possible. Clearly, this provides an upper bound on the chromatic number as well. We improve it by showing in Section 5 that in fact √ Theorem 3. χ = O(r∆r ), where ∆ = 4/3 < 2. Theorem 3 will be an easy consequence of Theorem 2. The independence number of a twin-free graph α(G) = Ω(|G|/∆r ). In our proof of Theorem 2 we use the result of Kabatjanskiı̆and Levienštein (cf. [4]), also [3]) that gives an upper bound on the number of unit vectors in d-dimensional space with pairwise ‘‘small’’ scalar products (cf. the proof of Lemma 2 below.) From this upper bound we derive that for a given twin-free graph G either its size is ‘‘small’’ (|G| ≤ C∆r ) or it contains a ‘‘large’’ (on at least |G|/∆ vertices) induced subgraph of a smaller rank. It would be desirable to prove that the chromatic number is bounded by a subexponential O(1) .) Suppose that function of the rank, or even a quasipolynomial in the rank (i.e., χ = 2(log r) one could find a way around the Kabatjanskiı̆–Levienštein Theorem, and say prove that for some ∆ > 1 smaller than ours there exists a constant C = C(∆) such that for a given twin-free G, either |G| ≤ C∆r or G contains an induced subgraph of a smaller rank on pat least |G|/∆ vertices. Our method of proof then could be applied unchanged as long as ∆ > 3/2. 2. DEFINITIONS Hereinafter G will be a [simple undirected] graph on n vertices, and M , its adjacency matrix. We set r = rkM . By the rank of a graph we mean the rank of its adjacency matrix, and by its size, the number of vertices. H will denote a largest-size subgraph of G of a smaller rank, rk (H) < r. We set t = |H|. J will denote the all-one matrix whose size will be clear from the context. The neighborhood Γ(u) of a vertex u of a graph is the set of all the vertices adjacent to u. Two vertices u and v are called twins if their neighborhoods coincide: Γ(u) = Γ(v). (In particular, twins are non-adjacent.) A twin class is the set of all the vertices with the same given neighborhood. A largest twin-free induced subgraph of G is the essence of G. The essence of G is unique up to an isomorphism, and is denoted by Gess . It is immediate that the chromatic number χ(Gess ) = χ(G) and rk(Gess ) = rk(G). Often it will be convenient to consider Gess instead of G. 3. PRELIMINARY LEMMAS Throughout this section G is assumed twin-free (i.e., G = Gess ). Lemma 1. No two columns of M coincide in more than t = |H| positions. Proof. Assume the contrary. Without loss of generality, let columns i and j of M coincide in positions 1 through t + 1. Then the first t + 1 rows of M form a submatrix whose right null-space RANK AND CHROMATIC NUMBER 3 is strictly larger than that of M , e.g., because it contains the vector i j (0, . . . , 0, 1, 0, . . . , 0, −1, 0, . . . , 0). Consequently, the subgraph of G spanned by the vertices v1 , . . . , vt+1 has rank smaller than r. This is a contradiction to the maximality of t. Lemma 2. Let ∆ = 4/3. There exists a constant C such that if n ≥ C∆r , then t ≥ n/∆. Proof. Along with M , consider the matrix M 0 obtained from M by replacing all 0’s by 0 −1’s. In other words, M 0 = 2M − J, and hence √ |rk(M ) − rk(M )| ≤ 1. One can look at the 0 columns of M as vectors of euclidean length n in the (r + 1)-dimensional space. Any two of them, say u and v, coincide in at most t positions (by Lemma 1) and disagree in at least n − t. Hence u · v ≤ t − (n − t) = 2t − n. Thus the cosine of the angle between u and v is at most cos ϕ = (2t − n)/n, where 0 < ϕ < π. We may assume that 0 < ϕ ≤ π/2 (or, equivalently, t > n/2), because otherwise the number n of the said vectors is at most 2(r + 1), and the lemma follows. To this end we invoke the following result of Kabatjanskiı̆ and Levienštein to obtain an upper bound on n: Kabatjanskiı̆–Levienštein [4]. Consider the function (1+s)/2s −(1−s)/2s 1−s 1+s . x = x(s) = 2s 2s The number of vectors in Rr+1 with pairwise angles at least ϕ is at most [x(sin ϕ)]r 2o(r) as r → ∞. p In our case sin ϕ = 2 t/n − t2 /n2 . Setting τ = t/n, we obtain p n = o([x(2 τ − τ 2 ) + ]r ) as r → ∞, for any > 0. √ We next consider the equation τ −1 = x(2 τ − τ 2 ). We claim that it has a unique solution, τ0 , in the interval 1/2 < τ < 1. Indeed, the left hand side of the equation is a decreasing function of √ τ . On the other hand, the right hand side is an increasing function of τ , because both 2 τ − τ 2 , 1/2 < τ < 1, and x(s), 0 < s < 1, are decreasing: 1−s dx = x(s) ln <0 ds 1+s for 0 < s < 1. We conclude that the statement of the lemma holds for any value of ∆ > τ0−1 . Using Mathematicar, we obtain that τ0−1 = 1.32837 . . .. In particular, ∆ = 4/3 (which incidently corresponds to ◦ ϕ = 60 ) will do. (One can verify it directly, by substitution; however, the calculations are quite tedious and left out.) Lemma 3. Let H be a maximal subgraph of G of a smaller rank. Then: (a) H does not contain triplets; (b) the rank of H is either r − 1 or r − 2; (c) if H has twins, its rank is exactly r − 2. Proof. Let u be a vertex of G − H. Consider the graph spanned by H and u. Observe that this graph is of rank r (by the maximality of H) and (hence) it is twin-free. Call its adjacency 4 JOURNAL OF GRAPH THEORY FIGURE 1. Matrix M as described in Lemmas 4 and 5. matrix N . Since deleting a row from a 0–1 matrix without twin columns cannot produce three or more identical columns, (a) follows. Since the adjacency matrix of H can be obtained from N by deleting one row and one column that correspond to u, the rank of H is either r − 1 or r − 2, as (b) claims. If H has twins, then deleting from N the row that corresponds to u produces twin columns, and thus this row is not in the linear span of the rest of the rows of N . Hence deleting such a row lowers the rank (by 1). Similarly, deleting the corresponding column from the submatrix just obtained (of a symmetric N ) lowers the rank by another 1, hence (c). Lemma 4. Let H be a largest subgraph of G of a smaller rank, |H| = t, and suppose H has exactly p > 0 twin pairs. Then the vertices of G can be arranged (for some 1 ≤ k ≤ n − t) in the following order: {v1 , . . . , vp , v10 , . . . , vp0 , v2p+1 , . . . , vt , . . . , vt+k , . . . , vn } so that: (a) the first t vertices correspond to H, (b) vi and vi0 are twins in H (1 ≤ i ≤ p), (c) for each i, 1 ≤ i ≤ p, exactly the f irst k of the vertices vt+1 , . . . , vn are adjacent to vi and not to vi0 , (d) exactly the other n − t − k of them are adjacent to vi0 and not to vi , 1 ≤ i ≤ p. Proof. Let the vertices of G be arranged in accordance to (a) and (b). For each 1 ≤ i ≤ p, t + 1 ≤ j ≤ n, there is exactly one edge between vj and {vi , vi0 } (by the maximality of H; zero or two edges would produce two identical (sub)columns of length at least t + 1 in M ). Let {vi , vi0 } be ordered so that (vi , vt+1 ) is an edge for all 1 ≤ i ≤ p. Now note that by the maximality of H, the subgraph of G spanned by H and vt+1 has rank r. Hence rows t + 2 through n are in the linear span of the first t + 1 rows of M . This in particular means that for a given j, t + 2 ≤ j ≤ n, either (vi , vj ) is an edge for all 1 ≤ i ≤ p, or (vi0 , vj ) is an edge for all 1 ≤ i ≤ p (depending on the sign of the coefficient of row t + 1 in the representation of row j as a linear combination of rows 1, . . . , t+1 of M ). This makes an arrangement described by (a) through (d) possible. RANK AND CHROMATIC NUMBER 5 Let us fix such an arrangement. Denote by D the t × p upper left corner of M (i.e., D is the submatrix spanned by the rows 1 through t and the columns 1 through p of M .) The following readily follows from Lemma 4: Lemma 5. log(n − t) ≤ r − rk(D) + 1 (throughout this paper log is base 2). Proof. Let D1 and D2 be the submatrices of M spanned by the rows t + 1 through t + k and t + k + 1 through n respectively, and the columns 2p + 1 through n. Since all of the entries of M with indices ij, t + 1 ≤ i ≤ t + k and p + 1 ≤ j ≤ 2p, are zeros (cf Lemma 4), rk D + rk D1 ≤ r. Similarly, rk D + rk D2 ≤ r. Notice that neither D1 nor D2 can have identical rows, for otherwise so would M in a contradiction with the assumption that G is twin-free. It is an easy exercise to show that the number of pairwise different rows in a 0–1 matrix of rank r is at most 2r . Thus the number of rows in Di is at most 2rkDi , i = 1, 2. Since n − t is exactly the total number of rows in D1 and D2 , we have n − t ≤ 2rkDi + 2rkD2 ≤ 2 · 2r−rkD , and the lemma follows. 4. THE INDEPENDENCE NUMBER In what follows we let ∆ = 4/3 but we could choose any number larger than τ0−1 = 1.32837 . . . , cf. the proof of Lemma 2. Theorem 2. There exists a constant C such that for any twin-free graph G of rank r α(G) ≥ Corollary 1. |G| . C∆r Let A be any graph, and let µ denote the size of a largest twin class in A. Then α(A) ≥ |A| . C∆rk(A)+2dlog µe Proof of Corollary 1. We construct a smallest twin-free graph, K, containing A. We do it by adding to A dlog µe vertices one by one, connecting each new vertex to exactly half (say, rounded up) of every current twin class, and to all other (i.e., non-twin) vertices. Adding each such vertex decreases the size of every twin class, roughly speaking by a factor of 2, and increases the rank of the current graph by 2. Hence after we have added dlog µe vertices the obtained graph, K, is twin-free, as claimed. Moreover, rk (K) = rk(A) + 2dlog µe and thus by Theorem 2, α(K) ≥ |A| |K| ≥ . C∆rk(A)+2dlog µe C∆rk(A)+2dlog µe To conclude the proof, we claim that α(A) = α(K). Assume the contrary, i.e., α(A) < α(K). Let us fix some maximal independent set of size α(K). Notice that this set contains only one vertex, u, of K − A, because K − A is a clique by the construction. Take any other vertex, v, in the independent set. Of course, u and v are independent. But then, by the construction, u is adjacent to some twin v 0 of v (v 0 therefore cannot be in the same independent set as u). Swapping v 0 for u we obtain an independent set entirely in A, and of size α(K). This is a contradiction. We leave it to the reader to argue that any twin-free graph containing A as a subgraph, has rank at least rk (A) + 2dlog µe. We hence obtain 6 JOURNAL OF GRAPH THEORY Corollary 2. Let K be a twin-free graph, and A, its subgraph. Then α(A) ≥ |A| . C∆rk(K) Proof of Theorem 2. (by induction on the rank.) Let C be a constant satisfying the conclusion of Lemma 2. If |G| ≤ C∆r , there is nothing to prove. Thus assume |G| > C∆r . (1) Recall that H denotes a largest subgraph of G of a smaller rank. By Lemma 2, |H| ≥ |G|/∆. If H ess = H, then by induction applied to H, α(G) ≥ α(H) ≥ |H|/C∆r−1 ≥ |G|/C∆r , as required. Thus assume |H| = / |H ess |. ess ess (2) 2 Then by Lemma 3(c), rk H = rk H = r − 2. If |H | ≥ |G|/∆ , then by induction applied to H ess , α(G) ≥ α(H) ≥ α(H ess ) ≥ |H ess /C∆r−2 ≥ |G|/C∆r , as required. Thus assume |G| . (3) ∆2 Denote the number of twin pairs in H by p. (Recall that by Lemma 3(a), H does not have triplets.) Arrange the vertices of G as described in Lemma 4. Let A be the subgraph of H spanned by {v1 , . . . , vp }, and let µ be the size of a largest twin class in A. Notice that α(G) ≥ 2α(A) ≥ 2µ and hence if |G| ≤ 2µC∆r we are done. Thus assume |H ess | < |G| > 2µC∆r . (4) If rk (A) + 2dlog µe ≤ r − 4 then by Corollary 1 (by induction we may assume that it holds for all graphs A such that rk (A) + 2dlog µe < r) we have α(G) ≥ 2α(A) ≥ 2 p |G| > C∆r−4 C∆r (since 2p∆4 = 2(|H| − |H ess |)∆4 > 2(1/∆ − 1/∆2 )|G|∆4 = 32/27|G| > |G|), as required. Thus assume rk(A) + 2dlog µe ≥ r − 3. (5) Consider the first p columns of the adjacency matrix of H. They form a matrix D without twin columns, because H did not have triplets, per Lemma 3(a). At the same time, D contains as a submatrix the matrix A with a largest twin class of size µ. We leave it as an exercise to the reader to conclude that D has rank at least rk(A) + dlog µe ≥ r − 3 − dlog µe. It follows from Lemma 5 that log(|G| − |H|) ≤ r + 1 − rk(D) ≤ r + 1 − (r − 3 − dlog µe) = dlog µe + 4. Hence |G| − |H| ≤ 32µ. But then p = |H| − |H ess | ≥ |G| − 32µ − |H ess | > |G| − 32µ − |G|/∆2 by (3). It follows from Corollary 2 that |A| p 1 64µ |G| α(G) ≥ 2α(A) ≥ 2 ∆2 = 2 ≥ 2 1 − − r−2 2 r rk(H) C∆ ∆ C∆ C∆r−2 C∆ 64µ 14 |G| 64µ |G| 5 = − > [by assumption (4)] > + 2µ − , r r−2 r 9 C∆ C∆ C∆ 9 C∆r−2 which in turn is at least |G|/C∆r for C sufficiently large (e.g., larger than 60). This completes the proof of the theorem. RANK AND CHROMATIC NUMBER 7 5. THE CHROMATIC NUMBER Let χ(G) denote the chromatic number of a graph G. The following inequality is an easy consequence of Theorem 2: Theorem 3. χ(G) ≤ C∆r log |Gess |. Corollary 3. χ(G) = O(r∆r ). √ Since, by Theorem 1, log |Gess | ≤ log{C( 2)r } = r/2 + log C, we immediately have the following Proof of Theorem 3. (by induction on the number of vertices). Without loss of generality we can assume that G is twin-free. By Theorem 2, α(G) ≥ |G| . C∆r Let K denote the subgraph of G obtained by removing some α(G) ≥ |G|/(C∆r ) independent vertices. Then by induction we have: χ(G) ≤ χ(K)+1 ≤ C∆r log |K|+1 ≤ C∆r log |G|+C∆r log C∆r − 1 +1 ≤ C∆r log |G|, C∆r the latter inequality holding true since log(1 − 1/R) ≤ −1/R for every R > 1. Remarks. (1) By doing some more work one could prove a slightly stronger form of Theorem 3, namely χ(G) ≤ C∆r · max{1, log |Gess |/C∆r }. We omit the details. (2) All of the arguments remain valid if ∆ = 4/3 is replaced by any other number greater than τ0−1 = 1.32837 . . . (cf. the proof of Lemma 2). Thus we could e.g. prove that χ(G) = o(1.3284r ). ACKNOWLEDGMENTS The author would like to express his deep gratitude to Professor László Lovász for many valuable discussions, without which this work would not have been possible. He is also grateful to a referee for thoughtful remarks and suggestions for improvement. References [1] N. Alon and P. Seymour, A counterexample to the rank-coloring conjecture, J. Graph Theory 13 (1989), 523–525. [2] S. Fajtlowicz, On conjectures of graffiti, Discrete Math. 72 (1988), 113–118. [3] P. M. Gruber and J. M. Wills (eds.), Handbook of convex geometry, Volume B, North-Holland, Amsterdam (1993), 826. [4] G. A. Kabatjanskiı̆ and V. I. Levienštein, Bounds for packings on a sphere and in space (in Russian), Problemy Peredachi Informatsii 14 (1978), 3–25. [5] A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), 185–189. 8 JOURNAL OF GRAPH THEORY [6] L. Lovász, Communication complexity: a survey, in: Paths, f lows, and VLSI layout, (ed. B. Korte, L. Lovász, H. J. Prömel, A. Schrijver), Springer, New York (1990), 235–265. [7] N. Nisan and A. Wigderson, On rank vs. communication complexity, Proc. of the 35th FOCS (1994), 831–836. [8] A. Razborov, The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear, Discrete Math. 108 (1982), 393–396. [9] R. Raz and B. Spieker, On the log-rank conjecture in communication complexity. Proc. of the 34th FOCS (1993), 168–176. [10] C. van Nuffelen, A bound for the chromatic number of a graph, Amer. Math. Monthly 83 (1976), 265–266.

1/--страниц