4
$\begingroup$

Here's what seems to be an annoying technicality when dealing with loops in graphs.

In the literature on expander graphs (and surely not only), it seems to be the convention that a loop at vertex $v$ in an undirected graph contributes 1 to the degree, and 1 to the corresponding diagonal entry in the adjacency matrix. For example see how Vadhan sets up graphs in section 2.4.2 here.

On the other hand, when we deal with covering maps of graphs, it is natural and necessary to consider loops as adding 2 to the degree (and 2 to the diagonal of the matrix). This is because the definition of a covering map $p:G\to H$ requires the star of a vertex $v$ of $G$ to map bijectively to the star of $p(v)$, and loops contribute two segments to the star. Correspondingly, people who have been constructing expanders by coverings have adopted this convention.

However, changing the convention changes the adjacency matrix, and thus the eigenvalues - so it seems people adopting different conventions are using different notions of spectral expansion; yet I've been looking around for some reference addressing this issue and found nothing.

(On the other hand, note that for directed graphs this problem doesn't occur, since in both conventions directed loops contribute 1 to out-degree and 1 to in-degree, and add 1 to the adjacency matrix.)

My question is, broadly speaking, how can we reconcile these two conventions? I know for example that loops don't matter if we use the Laplacian to measure expansion, but this is only true for the unnormalized Laplacian, and as far as I undersand, spectral expansion for irregular graphs is defined using the normalied Laplacian.

Edit: I realize this question is vague, so I'll provide some context for where it comes from. I'm constructing families of directed expanders $G_1,G_2,\ldots$ with covering maps $G_{n+1}\to G_n$ (so-called towers of expanders). In the directed world everything is fine since the treatment of loops in the definition of spectral expansion and in the definition of covering maps agree.

Naturally, it is desirable to have a way to convert towers of directed expanders into towers of undirected ones. The most natural thing is to add the 'transpose' graph to each graph in the family: if the original adjacency matrix was $A_{G_n}$, the new one will be $A_{G_n} + A_{G_n}^T$. We have a nice bound on the spectral expansion of this matrix from the spectral expansion of $A_{G_n}$. But when we try to get an undirected graph from the matrix $A_{G_n}+A_{G_n}^T$, we hit a wall, because the conventions about loops differ: we either have to sacrifice covering or the eigenvalue bound.

From reading some papers, it seems like people are glossing over this distinction, and in effect implicitly using two different definitions of spectral expansion. Maybe it's not a huge deal, but it seems unfortunate.

$\endgroup$
  • 3
    $\begingroup$ One possible convention is to regard graphs as being directed by default. Then "undirected" means having the additional structure of an involution on edges that switches source and target, and now there's the question of whether you allow this involution to have fixed points ("self-adjoint" edges). $\endgroup$ – Qiaochu Yuan Aug 18 '16 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.