An interesting spectral gap problem, from Jim Fill
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912541326704640 |
|---|---|
| author | Fill, James Allen |
| author_facet | Fill, James Allen |
| contents | At the request of Laszlo Babai, founder and an editor of the free online journal Theory of Computing (ToC), theoryofcomputing.org, in August, 2025, I am posting on the arXiv, essentially unedited and not updated, a combination of two closely related sets of unpublished notes from 2003. ToC is keen on publishing links to all bibliography items, and a paper soon to be published there makes progress on a conjecture in my 2003 notes. The sections "The problem", "Evidence in favor of the conjecture", "Facts about the spectral structure of the matrix $K$", and "Stronger conjectures" previously formed a document entitled "An interesting spectral gap problem, from Jim Fill". The sections "Introduction: Self-organizing lists" and "The move-ahead-$1$ (MA1) rule" formed a document entitled "Background on the gap problem". The two sets of notes have inspired some research, including (as one example, with no attempt here at a literature survey) a 2022 paper by Bhakta, Miracle, Randall, and Streib cited in this arXiv document. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_12557 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An interesting spectral gap problem, from Jim Fill Fill, James Allen Probability Combinatorics 60J10 At the request of Laszlo Babai, founder and an editor of the free online journal Theory of Computing (ToC), theoryofcomputing.org, in August, 2025, I am posting on the arXiv, essentially unedited and not updated, a combination of two closely related sets of unpublished notes from 2003. ToC is keen on publishing links to all bibliography items, and a paper soon to be published there makes progress on a conjecture in my 2003 notes. The sections "The problem", "Evidence in favor of the conjecture", "Facts about the spectral structure of the matrix $K$", and "Stronger conjectures" previously formed a document entitled "An interesting spectral gap problem, from Jim Fill". The sections "Introduction: Self-organizing lists" and "The move-ahead-$1$ (MA1) rule" formed a document entitled "Background on the gap problem". The two sets of notes have inspired some research, including (as one example, with no attempt here at a literature survey) a 2022 paper by Bhakta, Miracle, Randall, and Streib cited in this arXiv document. |
| title | An interesting spectral gap problem, from Jim Fill |
| topic | Probability Combinatorics 60J10 |
| url | https://arxiv.org/abs/2508.12557 |