The non-expanding links conjecture for bounded-degree graph sequences

Let GG be a finite graph. For a vertex subset SVGS\subset V_G with 0<SG/20<\lvert S\rvert\leq \lvert G\rvert/2, let S\partial S be its outer vertex boundary, and define the expansion of GG by

h=infSVG:0<SG/2SS.h=\inf_{S\subset V_G:\,0<\lvert S\rvert\leq \lvert G\rvert/2}\frac{\lvert\partial S\rvert}{\lvert S\rvert}.

The graph GG is an hh-expander if its expansion is at least hh, and a sequence of graphs is an expander family if some h>0h>0 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.