Conjecture 0.1 — Is there an infinite expander?

Definitions and mathematical statement

Let $G=(V,E)$ be an infinite connected simple graph with $\sup_{v\in V}\deg(v)<\infty$. Distances count edges, and $B_G(v,r)=\{x:d_G(v,x)\le r\}$ for an integer $r\ge0$. For $S\subseteq V$, define its external vertex boundary by \[ \partial_G S=\{x\in V\setminus S:\text{some }y\in S\text{ satisfies }\{x,y\}\in E\}. \] Call $G$ an infinite expander in the question's special sense if there is a single $c>0$ such that, for every center $v$, radius $r$, and set $S\subseteq V$ with $0<|S\cap B_G(v,r)|<|B_G(v,r)|/2$, one has \[ |\partial_G S\cap B_G(v,r)|>c|S\cap B_G(v,r)|. \] Prove that no such graph exists.

Equivalently, the finite induced graphs on all metric balls cannot have their vertex expansion uniformly bounded below by a positive constant. Indeed, testing the displayed condition on subsets of a ball gives its internal expansion inequality; conversely the internal boundary of $S\cap B$ inside $B$ is contained in $\partial_G S\cap B$. Empty subsets and singleton balls impose no condition. Changing strict inequalities to non-strict ones with a smaller positive constant does not change the existence question.

The uniformity over centers is essential: expansion of balls about one selected root does not suffice. This notion is also much stronger than positive Cheeger constant of the infinite graph, because boundary edges leaving the ball do not contribute to the ball's internal expansion.

Short English statement

Can every finite metric ball of one infinite bounded-degree graph have a uniform positive expansion constant?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 10000001 (AMR-099-0001), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Benjamini - Problems, Conjecture 0.1, PostScript page 1. Original source indexed by AMR-099-0001. https://www.wisdom.weizmann.ac.il/~itai/infexp.ps.
• S3 I. Benjamini, Coarse Geometry and Randomness, primary Saint-Flour notes; the numbered question and its surrounding definitions. https://arquivo.pt/noFrame/replay/20201231041548id_/http://www.wisdom.weizmann.ac.il/~itai/stflouraug24.pdf.