The non-expanding links conjecture for bounded-degree graph sequences
The non-expanding links conjecture for bounded-degree graph sequences
Let be a finite graph. For a vertex subset with , let be its outer vertex boundary, and define the expansion of by
The graph is an -expander if its expansion is at least , and a sequence of graphs is an expander family if some is a lower bound for the expansion of every graph in the sequence. The links are the graphs under consideration associated with the vertices and radii of the original graphs.
Non-expanding links conjecture. There is no sequence of bounded-degree finite graphs, with size growing to infinity, such that all links in all the graphs form an expander family.
This conjecture asserts that bounded degree and arbitrarily large graph size force at least some links to have vanishing expansion, despite the possibility that the original graphs may exhibit strong expansion. It concerns the interaction between local link structure and global graph expansion; the source provides no resolution, so the conjecture remains open.
Sources & referencesView supporting material
Primary source
Itai Benjamini and John Haslegrave, “Degrees in link graphs of regular graphs”, arXiv:2106.15464 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.