ChapterZero

Spectral spread of Graphs

Nikiforov’s July 2010 arXiv paper on the application of Ky Fan norms to graphs poses, among others, the following question: what is the maximal spectral spread of a simple graph of order ?

Here when we refer to the spectrum of a graph, we mean the spectrum of the adjacency matrix of that graph, so we are interested in finding

$\displaystyle \chi(n) = \max_{|v(G)| = n} \mu_1(G) - \mu_n(G).$

The adjacency matrix of a graph is symmetric, so its singular values are simply the absolute values of its eigenvalues. Recall that the Ky Fan k-norm of a matrix is the sum of its top k singular values; it follows that the Ky Fan k-norm of a graph is the sum of the largest k moduli of its eigenvalues. In particular, the Ky Fan two-norm of a graph is given by

$\displaystyle \|G\|_{(2)} = \max\{\mu_1(G) + |\mu_2(G)|, \mu_1(G) + |\mu_n(G)| \}.$

The paper shows that in fact, if is sufficiently large, then in the graph which achieves $\chi(n)$ , $|\mu_n(G)| > |\mu_2(G)|$ so that $\|G\|_{(2)} = \mu_1(G) - \mu_n(G)$ , and the spectral spread of the graph is given by the Ky-fan two norm. So whatever we know about Ky Fan norms can be used.

Here’s a possible avenue towards answering this question, almost entirely due to the observations of one of my colleagues. First, it turns out that the Ky Fan k-norm is the infimal convolution of the trace norm (aka the Ky Fan n-norm) and a scaled spectral norm (aka the Ky Fan 1-norm):

$\displaystyle \|A\|_{(k)} = \inf \{ \|U\|_{(n)} + k \|V\|_{(1)} \,:\, A = U + V \}.$

Some results on infimal convolutions $f = \|\cdot\|_1 \diamond \|\cdot\|_2$ of norms:

is a norm
$\displaystyle f^\star = \|\cdot\|_1^\star + \|\cdot\|_2^\star = I_{B_{\|\cdot\|_1^\star}} + I_{B_{\|\cdot\|_2^\star}} = I_{B_{\|\cdot\|_1^\star} \cap B_{\|\cdot\|_2^\star}}$

where $I_A(x) = \begin{cases} 0 & x \in A \\ \infty & x \not\in A \end{cases}$ is the convex indicator function of a set.

which imply that the unit ball of the norm (trace) dual to is $B_{\|\cdot\|_1^\star} \cap B_{\|\cdot\|_2^\star}.$ The spectral and trace norms are trace dual, so we have

$\displaystyle B_{\|\cdot\|_{(k)}^\star} = B_{\|\cdot\|_{(2)}} \cap \left(k B_{\|\cdot\|_{(n)}}\right).$

Pulling these results together, for sufficiently large,

$\displaystyle \begin{aligned} \chi(n) & = \max_{|v(G)| = n} \mu_1(G) - \mu_n(G) = \max_{A} \|A\|_{(2)} = \max_{A} \max_{D \in B_{\|\cdot\|_{(2)}^\star}} \langle A, D \rangle \\ & = \max_{D \in B_{\|\cdot\|_{(2)}^\star}} \max_A \langle A, D \rangle, \end{aligned}$

where is in the set of symmetric hollow 0-1 matrices. Since our ambient space is the set of symmetric matrices, the are also symmetric. It follows that we can achieve the maximum over by choosing $A_{ij}$ to be 0 zero when $D_{ij}$ is negative, and 1 otherwise. Recalling that is also hollow, this gives

$\displaystyle \chi(n) = \max_{D \in B_{\|\cdot\|_{(2)}^\star}} \sum_{i\neq j} D_{ij}^{+} = \max_{\{D \,:\, \|D\|_{(1)} \leq 1 \text { and } \|D\|_{(n)} \leq 2\}} \sum_{i \neq j} D_{ij}^+.$

This seems like a more geometric reformulation of the problem. Potentially, this bound could let us find lower bounds for $\chi(n)$ by choosing particular choices of , and could even lead to a direct resolution of the problem.

A side note: if $J : X \hookrightarrow Y$ is the inclusion operator between , the space of hollow symmetric matrices with the $\|\cdot\|_{1 \rightarrow \infty}$ norm, and , the space of symmetric matrices with the Ky Fan 2-norm, then $\|J\| \leq 2 \chi(n).$ I doubt this will ever be a useful observation

Possibly relevant posts:

Nuclear norm stuff (3/18/2010)
Trace dual of the $\|\cdot\|_{\infty\rightarrow 1}$ norm (1/19/2010)
Some Schatten norm stuff (6/17/2008)

Tags: convex, duality, geometry, graph, matrix, norm, optimization, problem

Spectral spread of Graphs

Possibly relevant posts:

Leave a comment

Archives

intelligently designed

light and not filling

Tags