The rank-coloring and log rank conjectures: Torsten Sillke, 2001-09
Problem 1: (van Nuffelen 1976, Fajtlowicz 1987+1988)
Is for every simple graph G with at least one edge
chromatic_number(G) <= rank(A(G)) ?
Where A(G) is the adjacency matrix of G.
Problem 2: (Lovasz-Saks 1988)
Is there a constant k such that for every graph G
log(chromatic_number(G)) <= log^k(rank(A(G))) ?
Where A(G) is the adjacency matrix of G.
A counterexample to problem 1 was first found by Alon and Seymour in 1989.
There graph was constructed by a Hamming scheme. Let take the hypercube of
order 6 and connect its opposite corners. This graph H has no triangle.
Therefore its complement G has independence number 2. So its chromatic number
is at least 32 (it is 32) but the rank of G is 29. See [Cvetkovic, Doob, Sachs]
how to calculate the eigenvalues of Hamming schemes.
In 1988 I constructed all twin-free graphs with rank upto r = 5.
[Kotlov and Lovasz 1996] showed that the number of vertices of such
a graph is at most O(2^(r/2)). But in all cases the conjecture of
problem 1 was valid. What is the smallest r for which we can find a
graph G with chromatic_number(G) > rank(A(G)) = r?
Problem 2 is still open.
references:
- N. Alon, P. D. Seymour;
A counterexample to the rank-coloring conjecture,
Journal of Graph Theory 13:4 (1989) 523-525
Zbl 674.05029
An example of a simple graph is given which has chromatic number 32 and an
adjacency matrix of rank 29. Thus a conjecture of C. van Nuffelen that the
chromatic number of any graph with at least one edge does not exceed the
rank of its adjacency matrix is disproved. The nice construction is based
on the application of a standard result about eigenvalues of Cayley graphs
of Abelian groups. It remains an open problem whether the chromatic number
is bounded by a polynomial in the rank.
http://citeseer.nj.nec.com/context/542851/0 (Citation Index)
- Bruno Codenotti, Gianna Del Corso, Giovanni Manzini;
Matrix rank and communication complexity,
Linear Algebra and its Applications 304 (2000) 193-200
http://citeseer.nj.nec.com/codenotti00matrix.html
- D. Cvetkovic, Doob, and Sachs;
Spectra of Graphs
Academic Press 1978
- S. Fajtlowicz;
On conjectures of graffiti II,
Congresus Numeratum 60 (1987) 189-198
- S. Fajtlowicz;
On conjectures of graffiti,
Discrete Mathematics 72 (1988) 113-118
- Andrei Kotlov;
Rank and chromatic number of a graph.
Journal of Graph Theory 26, No.1, 1-8 (1997)
Zbl 878.05033
- Kotlov, Andrew; Lovasz, Laszlo
The rank and size of graphs.
Journal of Graph Theory 23, No.2, 185-189 (1996).
Zbl 858.05060
A graph is twin-free if it has no two vertices with precisely the
same sets of neighbours. Theorem: Let $G$ be a twin-free graph on
$n$ vertices, and let $r$ be the rank of its adjacency matrix. Then
$n=O(2^{{r\over 2}})$ as $r\to\infty$. Conversely, given a twin-free
graph on $2\cdot 2^{{r\over 2}}-1$ vertices, of rank $r$, one can
duplicate its vertices, and then join a new vertex by an edge to one
vertex of each twin pair. The graph obtained is again twin-free, has
$2\cdot 2^{{r+2\over 2}}-1$ vertices, and has adjacency matrix of rank
$r+2$; thus the bound is ``best possible''. One application is to
bound the chromatic number.
- Laszlo Lovasz, Michael Saks;
Lattices, M"obius functions and communication complexity,
In: Proc. of the 29th IEEE Symp. FOCS (1988) 81-90
- Laszlo Lovasz, Michael Saks;
communication complexity and combinatorial lattice theory,
Journal of Computer and System Sciences 47 (1993) 322-349
- Noam Nisan, Avi Wigderson;
On Rank vs. Communication Complexity,
Combinatorica 15, (1995) ???
(Proc 35th {IEEE} Symposium on Foundations of Computer Science (1994) 831-836)
http://citeseer.nj.nec.com/nisan94rank.html
- P. Pudlak, V. R"odl
Some combinatorial-algebraic problems from complexity theory
IN: Discrete Mathematics 136 (1994) 253-279
Problem 2: (Lovasz-Saks) p256
- Ran Raz, Boris Spiker;
On the ``log rank''-conjecture in communication complexity,
Combinatorica 15, No.4, (1995) 567-588
(first published: Proc. of the 34th IEEE Symp. FOCS (1993) 168-176)
Zbl 845.68050
Abstract:
We show the existence of a non-constant gap between the communication
complexity of a function and the logarithm of the rank of its input matrix.
We consider the following problem: each of two players gets a perfect
matching between two $n$-element sets of vertices. Their goal is to decide
whether or not the union of the two matchings forms a Hamiltonian cycle.
We prove:
1) The rank of the input matrix over the reals for this problem is
$2^{O(n)}$.
2) The non-deterministic communication complexity of the problem is
$\Omega(n\log\log n)$.
Our result also supplies a superpolynomial gap betweeen the chromatic number
of a graph and the rank of its adjacency matrix. Another conclusion from the
second result is an $\Omega(n \log \log n)$ lower bound for the graph
connectivity problem in the non-deterministic case.
We make use of the theory of group representations for the first result.
The second result is proved by an information theoretic argument.
http://citeseer.nj.nec.com/raz93log.html
- A. A. Razborov;
Applications of matrix methods to the theory of lower bounds in
computational complexity.
Combinatorica 10, No.1, 81-93 (1990).
Zbl 717.68049
One of the hardest tasks of the complexity theory is to discover some
combinatorial or algebraic properties of Boolean functions which would imply
high complexity in interesting computing models. A contribution in this
direction is made here by proving nonpolynomial lower bound on the monotone
formula size for the function ``minimum cover''. Nonpolynomial lower bounds
for monotone complexity were already known, and so the main contribution of
this paper is in the presentation of new, essential simpler methods than
the previous ones for this task. Some connections between this method on
one side, and communication complexity for VLSI and graph complexity on
other side are also shown.
- C. van Nuffelen;
A bound for the chromatic number of a graph,
American Mathematical Monthly 83 (1976) 265-266
- C. van Nuffelen;
Rank and diameter of a graph.
Bull. Soc. Math. Belg., Ser. B 34, 105-112 (1982)
Zbl 541.05043
In this note we prove that the rank of the adjacency matrix
(vertex-vertex matrix) of an undirected graph is an upper bound
for the diameter of this graph.
--
mailto:Torsten.Sillke@uni-bielefeld.de
http://www.mathematik.uni-bielefeld.de/~sillke/