вход по аккаунту



код для вставкиСкачать
Rank and Chromatic
Number of a Graph
Andreı̆ Kotlov
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
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.
1997 John Wiley & Sons, Inc.
CCC 0364-9024/97/010001-08
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
.) 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.
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.
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
is strictly larger than that of M , e.g., because it contains the vector
(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
−1’s. In other words, M 0 = 2M − J, and hence
√ |rk(M ) − rk(M )| ≤ 1. One can look at the
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
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
x = x(s) =
The number of vectors in Rr+1 with pairwise angles at least ϕ is at most
[x(sin ϕ)]r 2o(r)
as r → ∞.
In our case sin ϕ = 2 t/n − t2 /n2 . Setting τ = t/n, we obtain
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
τ . 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:
= x(s) ln
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
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.
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
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.
Let A be any graph, and let µ denote the size of a largest twin class in A. Then
α(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) ≥
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
Corollary 2.
Let K be a twin-free graph, and A, its subgraph. Then
α(A) ≥
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 .
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 |.
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
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 .
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
(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.
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
α(G) ≥ 2α(A) ≥ 2
14 |G|
> [by assumption (4)] >
+ 2µ −
9 C∆
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.
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
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) ≥
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|,
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 ).
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.
N. Alon and P. Seymour, A counterexample to the rank-coloring conjecture, J. Graph Theory 13 (1989),
S. Fajtlowicz, On conjectures of graffiti, Discrete Math. 72 (1988), 113–118.
P. M. Gruber and J. M. Wills (eds.), Handbook of convex geometry, Volume B, North-Holland, Amsterdam (1993), 826.
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.
A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), 185–189.
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.
N. Nisan and A. Wigderson, On rank vs. communication complexity, Proc. of the 35th FOCS (1994),
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.
R. Raz and B. Spieker, On the log-rank conjecture in communication complexity. Proc. of the 34th
FOCS (1993), 168–176.
C. van Nuffelen, A bound for the chromatic number of a graph, Amer. Math. Monthly 83 (1976),
Без категории
Размер файла
105 Кб
Пожаловаться на содержимое документа