Exercise 6.16: Graphs and Adjacency Matrices

chapter 6

Define $\tau \subset \mathbb{N}$ to be the set of indices associated with members of an $s$-clique, $v^{\mathrm{\top }}Av=s$ for $v_i=\frac{{\mathbb{1}}_{i\in \tau }}{\sqrt{s}}$, implying $\Vert A{\Vert }_2\ge s$.

For the upper bound, take $v$ to an eigenvector such that $\Vert Av{\Vert }_2=\Vert A{\Vert }_2$, and $i$ to be an index for which $|v_i|=\Vert v{\Vert }_{\mathrm{\infty }}$. Then $$\begin{array}{}\text{(1)}& \Vert A{\Vert }_2|v_i|=|[Av{]}_i|\le \Vert Av{\Vert }_{\mathrm{\infty }}\le \Vert A{\Vert }_{\mathrm{\infty }}|v_i|.\end{array}$$ Since $v\ne 0$, the above implies $\Vert A{\Vert }_2\le \Vert A{\Vert }_{\mathrm{\infty }}$. We conclude by observing $\Vert A{\Vert }_{\mathrm{\infty }}=\underset{i}{max}\Vert A_{i\cdot }\Vert =s$ which follows by the assumed maximum degree $s-1$ (remember $A$ is defined with ones on the diagonal here).