Eigenvectors of the De Bruijn Graph Laplacian: A Natural Basis for the Cut and Cycle Space
Authors:
- Anthony PhilippakisAPAnthony Philippakis
- Neil MallinarNMNeil Mallinar
- Parthe PanditPPParthe Pandit
- Mikhail BelkinMBMikhail Belkin
Preprint
Abstract
We study the Laplacian of the undirected De Bruijn graph over an alphabet $A$ of order $k$. While the eigenvalues of this Laplacian were found in 1998 by Delorme and Tillich [1], an explicit description of its eigenvectors has remained elusive. In this work, we find these eigenvectors in closed form and show that they yield a natural and canonical basis for the cut- and cycle-spaces of De Bruijn graphs. Remarkably, we find that the cycle basis we construct is a basis for the cycle space of both the undirected and the directed De Bruijn graph. This is done by developing an analogue of the Fourier transform on the De Bruijn graph, which acts to diagonalize the Laplacian. Moreover, we show that the cycle-space of De Bruijn graphs, when considering all possible orders of $k$ simultaneously, contains a rich algebraic structure, that of a graded Hopf algebra.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Applications of de Bruijn graphs in microbiome researchiMeta, 2022
- Cycle analysis of Directed Acyclic GraphsPhysica A: Statistical Mechanics and its Applications, 2022
- Semantic text classification: A survey of past and recent advancesInformation Processing & Management, 2018
- Introduction2016
- Tridiagonal Toeplitz matrices: properties and novel applicationsNumerical Linear Algebra with Applications, 2012
- Text Categorization in R: A Reduced N-Gram Approach2012
- SOME HOPF ALGEBRAS OF WORDSGlasgow Mathematical Journal, 2006
- Graph Cuts in Vision and Graphics: Theories and Applications2005
- The Spectrum of de Bruijn and Kautz GraphsEuropean Journal of Combinatorics, 1998
- Circulant matrices and the spectra of de Bruijn graphsUkrainian Mathematical Journal, 1992