Hoffman Bounds on Cycles and Hypercubes

From Spectra to Extremal Parameters

An adjacency spectrum can constrain how large an independent set can be and how many colors a graph requires. Cycles and hypercubes are useful test cases: their eigenvalues can be calculated explicitly, and their independent sets and colorings have simple constructions. Comparing the spectral estimates with those constructions shows both the power and the limitations of Hoffman’s bounds.

All graphs considered here are finite and simple. An independent set is a set of vertices no two of which are adjacent; its maximum possible size is the independence number \(\alpha(G)\). A proper coloring assigns colors to vertices so adjacent vertices receive different colors. The smallest number of colors in such a coloring is the chromatic number \(\chi(G)\). The adjacency matrix \(\mathbf A(G)\) has entry \(1\) at positions corresponding to adjacent vertices and entry \(0\) elsewhere.

Proof. Let \(S\) be an independent set of size \(a\), and let \(x\) be its indicator vector: \(x_v=1\) for \(v\in S\) and \(x_v=0\) otherwise. Write \(\mathbf 1\) for the all-ones vector. Since \(G\) is \(d\)-regular, \(\mathbf A(G)\mathbf 1=d\mathbf 1\). Decompose \(x=(a/n)\mathbf 1+y\), where \(y\) is orthogonal to \(\mathbf 1\). Then \(\|y\|^2=a-a^2/n\), because \(\|x\|^2=a\) and \(\|(a/n)\mathbf 1\|^2=a^2/n\). Independence gives \(x^{T}\mathbf A(G)x=0\): this quadratic form counts ordered adjacent pairs from \(S\), and there are none. The cross term between \(\mathbf 1\) and \(y\) is zero, so $$ 0=x^{T}\mathbf A(G)x=\frac{d a^2}{n}+y^{T}\mathbf A(G)y \ge \frac{d a^2}{n}+\tau\left(a-\frac{a^2}{n}\right). $$ The inequality follows by expanding \(y\) in an orthonormal eigenbasis: every eigenvalue is at least \(\tau\). If \(a>0\), rearranging gives \(a(d-\tau)\le -n\tau\), hence the independent-set bound. If \(a=0\), that bound holds because its right-hand side is positive. For the coloring bound, each of the \(q=\chi(G)\) color classes is independent, so each has size at most \(n(-\tau)/(d-\tau)\). Summing their sizes gives \(n\le qn(-\tau)/(d-\tau)\), or \(q\ge (d-\tau)/(-\tau)=1-d/\tau\). \(\square\)

The spectral bounds are real-valued, while \(\alpha(G)\) and \(\chi(G)\) are integers. Thus an upper bound on \(\alpha(G)\) can be rounded down, and a lower bound on \(\chi(G)\) can be rounded up. The equality or sharpness of a bound is a separate question: it should be checked against constructions or other arguments.

Spectra of Cycles

For \(n\ge3\), the cycle \(C_n\) has vertex set \(\{0,1,\ldots,n-1\}\) and edges joining consecutive indices modulo \(n\). It is 2-regular. Its adjacency eigenvalues are $$ \lambda_j=2\cos\left(\frac{2\pi j}{n}\right),\qquad j=0,1,\ldots,n-1. $$ One way to verify this formula is to use the vector whose coordinate at vertex \(k\) is \(z_j^k\), where \(z_j=\exp(2\pi i j/n)\). The two neighbors of \(k\) have coordinates \(z_j^{k-1}\) and \(z_j^{k+1}\), whose sum is \((z_j+z_j^{-1})z_j^k=2\cos(2\pi j/n)z_j^k\). These \(n\) vectors form a basis: vectors for distinct \(j\) are orthogonal by the finite geometric-sum identity. Therefore the displayed values give the full spectrum.

If \(n\) is even, the least eigenvalue is \(-2\), attained at \(j=n/2\). If \(n\) is odd, the angles closest to \(\pi\) occur at \(j=(n-1)/2\) and \(j=(n+1)/2\), and the least eigenvalue is \(-2\cos(\pi/n)\). For odd \(n\ge3\), this cosine is positive.

How the Bounds Behave on All Cycles

For an even cycle, substituting \(n\), \(d=2\), and \(\tau=-2\) gives $$ \alpha(C_n)\le \frac{n\cdot2}{2+2}=\frac n2, \qquad \chi(C_n)\ge 1-\frac{2}{-2}=2. $$ Both estimates are exact. Taking alternate vertices gives an independent set of size \(n/2\), and alternating two colors around the cycle gives a proper coloring.

For an odd cycle, set \(c=\cos(\pi/n)\). The least eigenvalue is \(-2c\), so the bounds become $$ \alpha(C_n)\le\frac{nc}{1+c}, \qquad \chi(C_n)\ge1+\frac1c. $$ The first real-valued estimate is strictly less than \((n+1)/2\): indeed, \((n+1)(1+c)-2nc=n+1-(n-1)c>2>0\), since \(c<1\). As \(\alpha(C_n)\) is an integer, this proves \(\alpha(C_n)\le(n-1)/2\). The bound is attained by selecting alternate vertices up to vertex \(n-2\), giving \(\{0,2,\ldots,n-3\}\).

For the chromatic estimate, \(c<1\) gives \(1+1/c>2\), so the integer \(\chi(C_n)\) is at least \(3\). Three colors suffice: alternate two colors on vertices \(0,1,\ldots,n-2\), and give vertex \(n-1\) a third color. The final vertex is adjacent to \(n-2\) and \(0\), both of which have one of the first two colors, so this is proper. Thus every odd cycle has independence number \((n-1)/2\) and chromatic number \(3\); the Hoffman bounds give these exact integer values.

Spectra and Bounds for Hypercubes

For an integer \(r\ge1\), the hypercube \(Q_r\) has as vertices all binary strings of length \(r\); two strings are adjacent exactly when they differ in one coordinate. It has \(2^r\) vertices and is \(r\)-regular, since any one of the \(r\) coordinates can be flipped to produce a neighbor.

For each subset \(S\subseteq\{1,\ldots,r\}\), define a vector \(f_S\) by \(f_S(x)=(-1)^{\sum_{i\in S}x_i}\). At a vertex \(x\), the adjacency operator sums \(f_S\) over the strings obtained by flipping one coordinate. Flipping a coordinate in \(S\) changes the sign; flipping a coordinate outside \(S\) preserves it. Therefore $$ \mathbf A(Q_r)f_S=(r-2|S|)f_S. $$ These vectors form an orthogonal basis. For two distinct subsets \(S,T\), their coordinatewise product is \(f_{S\triangle T}\), where \(S\triangle T\) is their nonempty symmetric difference. Summing that product over all strings gives zero: flipping any fixed coordinate in \(S\triangle T\) pairs terms of opposite signs. Each vector has squared length \(2^r\). Consequently the eigenvalues are \(r-2k\), with multiplicity \(\binom{r}{k}\) for \(k=0,\ldots,r\), and the least eigenvalue is \(\tau=-r\).

For \(r\ge1\), the Hoffman bounds now read $$ \alpha(Q_r)\le\frac{2^r r}{r+r}=2^{r-1}, \qquad \chi(Q_r)\ge1-\frac r{-r}=2. $$ The parity classes attain both estimates. The strings with an even number of \(1\)s and those with an odd number of \(1\)s each have \(2^{r-1}\) elements: flipping the first coordinate is a bijection between the classes. Every edge changes parity, so each class is independent and the two classes give a proper two-coloring. Thus \(\alpha(Q_r)=2^{r-1}\) and \(\chi(Q_r)=2\).

Common Pitfall: Use the Least Eigenvalue and Round Correctly

For the Hoffman bounds, \(\tau\) means the least adjacency eigenvalue, not an arbitrary negative eigenvalue. For \(C_5\), for instance, the eigenvalue \((\sqrt5-1)/2\) is positive, while the least one is \(-(1+\sqrt5)/2\). Using an eigenvalue that is not least does not justify the bound. A second mistake is to treat a noninteger bound as an exact parameter or round in the wrong direction. For \(C_5\), \(\alpha(C_5)\le\sqrt5\) implies \(\alpha(C_5)\le2\), while \(\chi(C_5)\ge\sqrt5\) implies \(\chi(C_5)\ge3\). Rounding the first value up or the second down would discard the useful integer information.

The special case \(Q_0\) is a single vertex, not covered by the theorem’s \(d>0\) hypothesis: its degree and least eigenvalue are both \(0\), so the displayed Hoffman formulas would involve a zero denominator. Directly, its independence number and chromatic number are both \(1\). For every \(r\ge1\), the least eigenvalue of \(Q_r\) is negative and the bounds apply as stated.