Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.12557 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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.