Cheeger constants of nets in transitive graphs

Definitions and mathematical statement

For a graph $H$, write $\partial_H A$ for the vertices outside $A$ adjacent to some vertex of $A$. Define \[ h(H)=\inf_A\frac{|\partial_H A|}{|A|}, \] where $A$ ranges over nonempty finite vertex sets if $H$ is infinite, and over $0<|A|\le |V(H)|/2$ if $H$ is finite. Distances below are shortest-path distances with every edge of length one.

Let $G$ be a connected locally finite vertex-transitive graph and let $k\ge1$ be an integer. Choose any set $N\subseteq V(G)$ maximal under inclusion subject to $d_G(x,y)\ge k$ for distinct $x,y\in N$. The associated $k$-net graph $G_k$ has vertex set $N$, with an edge between two distinct members whenever their distance in $G$ is at most $2k$. Maximality implies every vertex of $G$ lies within distance less than $k$ of $N$.

Whenever $G_k$ has at least two vertices, must \[ h(G_k)\ge h(G)? \] The assertion quantifies over every maximal separated set, not just the existence of a particularly well-chosen net. It covers both finite and infinite transitive graphs. Its comparison uses vertex expansion, so replacing the boundary by an edge count would be a different numerical assertion. The net retains adjacency at scale $2k$ while discarding most original vertices; the question is whether this coarsening can ever reduce the Cheeger constant in the transitive setting.

Short English statement

Can passage to any maximal graph net reduce the vertex Cheeger constant of a transitive graph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 10000011 (AMR-099-0011), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Benjamini - Coarse Geometry and Randomness (Saint-Flour notes), Open problem 1.69, PDF page 15. Original source indexed by AMR-099-0011. https://www.wisdom.weizmann.ac.il/~itai/stflouraug24.pdf#page=15.
• 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.