Eigenvectors of the De Bruijn Graph Laplacian: A Natural Basis for the Cut and Cycle Space
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916431765962752 |
|---|---|
| author | Philippakis, Anthony Mallinar, Neil Pandit, Parthe Belkin, Mikhail |
| author_facet | Philippakis, Anthony Mallinar, Neil Pandit, Parthe Belkin, Mikhail |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_07622 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Eigenvectors of the De Bruijn Graph Laplacian: A Natural Basis for the Cut and Cycle Space Philippakis, Anthony Mallinar, Neil Pandit, Parthe Belkin, Mikhail Combinatorics Rings and Algebras 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. |
| title | Eigenvectors of the De Bruijn Graph Laplacian: A Natural Basis for the Cut and Cycle Space |
| topic | Combinatorics Rings and Algebras |
| url | https://arxiv.org/abs/2410.07622 |