Spectrally indistinguishable pseudorandom graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918218857185280 |
|---|---|
| author | Forey, Arthur Fresán, Javier Kowalski, Emmanuel Wigderson, Yuval |
| author_facet | Forey, Arthur Fresán, Javier Kowalski, Emmanuel Wigderson, Yuval |
| contents | We construct explicit families of graphs whose eigenvalues are asymptotically distributed according to Wigner's semicircle law; in other words, that are spectrally indistinguishable from random graphs. However, in other respects they are strikingly dissimilar from random graphs; for example, they are $K_{2,3}$-free graphs with almost the maximum possible edge density. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_21351 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spectrally indistinguishable pseudorandom graphs Forey, Arthur Fresán, Javier Kowalski, Emmanuel Wigderson, Yuval Combinatorics Discrete Mathematics Number Theory 11T23, 05C35, 05C48 We construct explicit families of graphs whose eigenvalues are asymptotically distributed according to Wigner's semicircle law; in other words, that are spectrally indistinguishable from random graphs. However, in other respects they are strikingly dissimilar from random graphs; for example, they are $K_{2,3}$-free graphs with almost the maximum possible edge density. |
| title | Spectrally indistinguishable pseudorandom graphs |
| topic | Combinatorics Discrete Mathematics Number Theory 11T23, 05C35, 05C48 |
| url | https://arxiv.org/abs/2511.21351 |