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/