New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix
The purpose of this article is to improve existing lower bounds on the chromatic number χ. Let μ[subscript 1],…,μ[subscript n] be the eigenvalues of the adjacency matrix sorted in non-increasing order. First, we prove the lower bound χ ≥ 1 + max[subscript m]{∑[m over i=1]μ[subscript i]/ − ∑[m over...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Electronic Journal of Combinatorics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/89814 |
| _version_ | 1826195094133276672 |
|---|---|
| author | Wocjan, Pawel Elphick, Clive |
| author2 | Massachusetts Institute of Technology. Center for Theoretical Physics |
| author_facet | Massachusetts Institute of Technology. Center for Theoretical Physics Wocjan, Pawel Elphick, Clive |
| author_sort | Wocjan, Pawel |
| collection | MIT |
| description | The purpose of this article is to improve existing lower bounds on the chromatic number χ. Let μ[subscript 1],…,μ[subscript n] be the eigenvalues of the adjacency matrix sorted in non-increasing order.
First, we prove the lower bound χ ≥ 1 + max[subscript m]{∑[m over i=1]μ[subscript i]/ − ∑[m over i=1]μ[subscript n−i+1]} for m = 1,…,n − 1. This generalizes the Hoffman lower bound which only involves the maximum and minimum eigenvalues, i.e., the case m = 1. We provide several examples for which the new bound exceeds the Hoffman lower bound.
Second, we conjecture the lower bound χ ≥ 1 + s[superscript +/s[superscript −], where s[superscript +] and s[superscript −] are the sums of the squares of positive and negative eigenvalues, respectively. To corroborate this conjecture, we prove the bound χ ≥ s[superscript +]/s[superscript −]. We show that the conjectured lower bound is true for several families of graphs. We also performed various searches for a counter-example, but none was found.
Our proofs rely on a new technique of considering a family of conjugates of the adjacency matrix, which add to the zero matrix, and use majorization of spectra of self-adjoint matrices.
We also show that the above bounds are actually lower bounds on the normalized orthogonal rank of a graph, which is always less than or equal to the chromatic number. The normalized orthogonal rank is the minimum dimension making it possible to assign vectors with entries of modulus one to the vertices such that two such vectors are orthogonal if the corresponding vertices are connected.
All these bounds are also valid when we replace the adjacency matrix A by W ∗ A where W is an arbitrary self-adjoint matrix and ∗ denotes the Schur product, that is, entrywise product of W and A. |
| first_indexed | 2024-09-23T10:07:15Z |
| format | Article |
| id | mit-1721.1/89814 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:07:15Z |
| publishDate | 2014 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | mit-1721.1/898142022-09-26T15:49:27Z New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix Wocjan, Pawel Elphick, Clive Massachusetts Institute of Technology. Center for Theoretical Physics Massachusetts Institute of Technology. Department of Mathematics Wocjan, Pawel The purpose of this article is to improve existing lower bounds on the chromatic number χ. Let μ[subscript 1],…,μ[subscript n] be the eigenvalues of the adjacency matrix sorted in non-increasing order. First, we prove the lower bound χ ≥ 1 + max[subscript m]{∑[m over i=1]μ[subscript i]/ − ∑[m over i=1]μ[subscript n−i+1]} for m = 1,…,n − 1. This generalizes the Hoffman lower bound which only involves the maximum and minimum eigenvalues, i.e., the case m = 1. We provide several examples for which the new bound exceeds the Hoffman lower bound. Second, we conjecture the lower bound χ ≥ 1 + s[superscript +/s[superscript −], where s[superscript +] and s[superscript −] are the sums of the squares of positive and negative eigenvalues, respectively. To corroborate this conjecture, we prove the bound χ ≥ s[superscript +]/s[superscript −]. We show that the conjectured lower bound is true for several families of graphs. We also performed various searches for a counter-example, but none was found. Our proofs rely on a new technique of considering a family of conjugates of the adjacency matrix, which add to the zero matrix, and use majorization of spectra of self-adjoint matrices. We also show that the above bounds are actually lower bounds on the normalized orthogonal rank of a graph, which is always less than or equal to the chromatic number. The normalized orthogonal rank is the minimum dimension making it possible to assign vectors with entries of modulus one to the vertices such that two such vectors are orthogonal if the corresponding vertices are connected. All these bounds are also valid when we replace the adjacency matrix A by W ∗ A where W is an arbitrary self-adjoint matrix and ∗ denotes the Schur product, that is, entrywise product of W and A. National Science Foundation (U.S.) (CAREER Award CCF-0746600) National Science Foundation (U.S.). Science and Technology Center for Science of Information (Grant CCF-0939370) 2014-09-18T17:26:51Z 2014-09-18T17:26:51Z 2013-09 2012-09 Article http://purl.org/eprint/type/JournalArticle 1077-8926 http://hdl.handle.net/1721.1/89814 Wocjan, Pawel, and Clive Elphick. "New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix." Electronic Journal of Combinatorics, Volume 20, Issue 3 (2013). en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p39 Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Electronic Journal of Combinatorics Electronic Journal of Combinatorics |
| spellingShingle | Wocjan, Pawel Elphick, Clive New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix |
| title | New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix |
| title_full | New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix |
| title_fullStr | New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix |
| title_full_unstemmed | New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix |
| title_short | New Spectral Bounds on the Chromatic Number Encompassing all Eigenvalues of the Adjacency Matrix |
| title_sort | new spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix |
| url | http://hdl.handle.net/1721.1/89814 |
| work_keys_str_mv | AT wocjanpawel newspectralboundsonthechromaticnumberencompassingalleigenvaluesoftheadjacencymatrix AT elphickclive newspectralboundsonthechromaticnumberencompassingalleigenvaluesoftheadjacencymatrix |