Non-isomorphic Cayley Graphs with Same Random Walk Distributions
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_ | 1866916721085906944 |
|---|---|
| author | Ishikawa, Masao Nakano, Fumihiko Sadahiro, Taizo |
| author_facet | Ishikawa, Masao Nakano, Fumihiko Sadahiro, Taizo |
| contents | We construct an infinite family of triples (G,S1, S2) each consisting of a group G and a pair (S1, S2) of distinct subsets of G with the following properties. i The two Cayley graphs Cay(G, S1) and Cay(G,S2) are non-isomorphic. ii The distributions of the simple random walks on Cay(G,S1) and Cay(G,S2) are the same if one takes an appropriate correspondence between the two vertex sets at each step. iii The spectral set of Cay(G, Si) is decomposed into a disjoint union of two subsets A and B_i of the equal size which satisfies B1 = -B2. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_01666 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Non-isomorphic Cayley Graphs with Same Random Walk Distributions Ishikawa, Masao Nakano, Fumihiko Sadahiro, Taizo Combinatorics 05C81 We construct an infinite family of triples (G,S1, S2) each consisting of a group G and a pair (S1, S2) of distinct subsets of G with the following properties. i The two Cayley graphs Cay(G, S1) and Cay(G,S2) are non-isomorphic. ii The distributions of the simple random walks on Cay(G,S1) and Cay(G,S2) are the same if one takes an appropriate correspondence between the two vertex sets at each step. iii The spectral set of Cay(G, Si) is decomposed into a disjoint union of two subsets A and B_i of the equal size which satisfies B1 = -B2. |
| title | Non-isomorphic Cayley Graphs with Same Random Walk Distributions |
| topic | Combinatorics 05C81 |
| url | https://arxiv.org/abs/2408.01666 |