spectral graph theory

Constructing Cospectral Graphs

Last week I had a cold and could not do much thinking. So I spent my time making TikZ pictures for an upcoming talk of mine. This talk is on my recent work with Akihiro Munemasa on constructing cospectral strongly regular graphs. I think that the pictures are nice for a blog post, so here we go.

1. The Spectrum of a Graph

Two graphs {\Gamma} and {\overline{\Gamma}} are called cospectral if their adjacency matrices {A} and {\overline{A}} have the same eigenvalues. This is the same as saying that there is an orthogonal matrix {Q} with {\overline{A} = Q^T A Q}. Any permutation matrix is a valid choice for {Q}, but this is not very interesting as then {\Gamma} and {\overline{\Gamma}} are isomorphic. Chris Godsil and Brendan McKay described one of the easiest interesting choices for {Q} in 1982. For a graph {\Gamma} on {v} vertices, a simplified version of their matrix is

\displaystyle Q = \begin{pmatrix} \frac{1}{m} J_{2m} - I_{2m} & 0 \\ 0 & I_{v-2m} \end{pmatrix}.

(more…)

Advertisements

Translating Terminology: Equitable Partitions and Related Concepts

Permutation Groups, Analysis of Boolean Functions, Finite Geometry, Coding Theory and Algebraic Graph Theory

Important mathematical concepts get reinvented many times. In my recent work with Yuval Filmus we explored objects that are called (in random ordering) Boolean degree 1 functions, Cameron-Liebler line classes, equitable partitions, completely regular strength 0 codes with covering radius 1, intriguing sets, perfect colorings, sets with dual width 1, tactical decompositions or tight sets — all depending on the context and who you ask. While the article with Yuval explains to some extent how these notions connect, a research article does not seem to be the right format to explain all concepts in sufficient detail. This post tries to amend this. It also prepares a future post which will elaborate my research with Yuval in more detail. (more…)

Erdős-Ko-Rado Theorems for Spherical Buildings

Today’s topic combines three of my favorite subjects: Erdős-Ko-Rado theorems (EKR theorems), finite buildings and spectral techniques. All of these topics deserve their own books (and have them, here some examples which I read: Erdos-Ko-Rado Theorems: Algebraic Approaches by Chris Godsil and Karen Meagher, Spectra of Graphs by Andries E. Brouwer and Willem H. Haemers, The Structure of Spherical Buildings by Richard M. Weiss), so I will only touch these topics slightly.

My main aim is to present a variation of the EKR theorem which is motivated by questions about spherical buildings. The variation was recently formulated by Klaus Metsch, Bernhard Mühlherr, and me. If you already know spherical buildings, then you might prefer to read the introduction of our paper instead. (more…)