Some Questions — Question 23

Definitions and mathematical statement

Let $G=(V,E)$ be a connected infinite locally finite vertex-transitive graph. Vertex transitivity means that for any $u,v\in V$ some graph automorphism maps $u$ to $v$. Let $d_G$ be the graph distance, namely the minimum number of edges in a path between two vertices.

For a finite set $A\subset V$, define its external vertex boundary by \[ \partial A=\{x\in V\setminus A:\text{some }a\in A\text{ is adjacent to }x\}. \] For every choice of a vertex $b\in V$, prove or disprove the inequality \[ \sum_{x\in\partial A}d_G(b,x)\ \geq\ |A|. \] The empty set satisfies the inequality automatically; the substantive case is nonempty $A$. No connectedness or convexity condition is imposed on $A$, and $b$ may lie inside or outside $A$. Each boundary vertex occurs once in the sum, regardless of how many neighbors it has in $A$.

The graph is infinite to exclude the immediate obstruction $A=V$ in a finite graph, where the boundary would be empty. Local finiteness guarantees that the displayed sum is finite. The claimed constant is exactly one, with no dependence on the common vertex degree or the particular graph. Proving only a bound with a graph-dependent multiplicative constant does not establish the assertion.

Short English statement

Does the sum of distances from any vertex to the external boundary of a finite set always dominate the set’s size?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 1200023 (AMR-011-0023), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Abert - Some questions (pdf) (2010), Question 23. Original source indexed by AMR-011-0023. https://www.renyi.hu/~abert/questions.pdf.