Discrete Mathematics Seminar - Local spectra and symmetric powers of walk-regular graphs

Dates

Wednesday, April 7, 2021 - 13:00 to 14:00

Speaker: Miquel Ángel Fiol (Universitat Politècnica de Catalunya, Barcelona)

Title: Local spectra and symmetric powers of walk-regular graphs

Abstract:

The u-local spectrum of a graph G, introduced by Garriga, Yebra, and the speaker, consists of the local eigenvalues and mutiplicities of a vertex u. The local spectrum gives similar information as the (standard) spectrum when G is 'seen' from the vertex u. From the local spectra we can define their corresponding local characteristic functions, which can be seen as a factorization of the characteristic polynomial of G.

When G is walk-regular, that is, the number of closed l-walks rooted at a vertex u only depends on l>=0, every vertex has the same local spectrum, and all the vertex-deleted subgraphs are cospectral. The symmetric k-power of a graph G (also known as its k-token graph) has as vertices the k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G.

In this talk, we discuss some properties of the local spectra, focusing on the case of walk-regular graphs and their symmetric powers. For instance, some of the results  are used to derive lower and upper bounds for the spectral radius of the token graphs, which in some cases become exact values.