Amenable graph

A bounded-degree infinite graph is amenable when there are finite nonempty vertex sets $W_n$ such that $|{\partial }^{+}{W}_n|/|W_n|\to 0$, where ${\partial }^{+}{W}_n$ is the set of vertices outside $W_n$ adjacent to it. These are graph Følner sets. Amenability makes surface contributions negligible compared with volume. The square lattice and any periodic finite decoration of it are examples.

A finite nonempty vertex set in an amenable graph is a Følner set with tolerance $\epsilon$ if its external boundary has size at most $\epsilon$ times its volume. A graph Følner sequence consists of such sets with tolerances tending to zero. For a bounded-degree graph, every fixed-thickness boundary layer also has negligible relative volume along this sequence.