pith. sign in

arxiv: 2503.09591 · v2 · submitted 2025-03-12 · 🧮 math.CO

Edge isoperimetry of lattices

Cameron Strachan , Konrad Swanepoel This is my paper

Pith reviewed 2026-05-22 23:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords Cayley graphsedge isoperimetryinteger latticesZ^disoperimetric orderingoptimal subsetstriangular lattice
0
0 comments X

The pith

There exists a Cayley graph on Z^d for d at least 2 with no ordering of the lattice where each finite prefix minimizes the edge boundary.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a Cayley graph G_d on the d-dimensional integer lattice, for d at least 2, that serves as a counterexample to the question of whether every such graph admits an ordering in which the first n vertices always form a minimum edge-boundary set. In this graph, not only does no such ordering exist, but no optimal set can be extended to an infinite ascending chain of optimal sets. This stands in contrast to the positive result known for the one-dimensional case. Separately, the authors exhibit a more complex two-dimensional Cayley graph on a modified triangular lattice that does admit such an ordering.

Core claim

We present an example of a Cayley graph G_d on Z^d (for all d≥2) for which there is no such ordering. Furthermore, we show that for all n and any optimal n-vertex subset S_n of G_d, there is no infinite sequence S_n ⊂ S_{n+1} ⊂ … of optimal sets. Our second result is a positive example for the unit-length triangular lattice (which is isomorphic to Z^2) where two vertices are connected by an edge if their distance is 1 or √3. We show that this graph has such an ordering.

What carries the argument

The Cayley graph G_d on Z^d defined by a specific choice of generators that prevents any optimal finite set from extending into an infinite chain of optimal sets.

If this is right

  • No such ordering of Z^d exists for the constructed G_d.
  • No optimal n-set in G_d can begin an infinite ascending chain of optimal sets.
  • The one-dimensional integer line admits such an ordering.
  • The specified triangular lattice graph on Z^2 admits such an ordering.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The property of admitting an isoperimetric ordering depends on the precise choice of generators rather than holding for all Cayley graphs on Z^d.
  • The triangular lattice example indicates that adding longer-range connections can sometimes restore the ordering property in two dimensions.
  • Similar generator-dependent failures may occur for other finitely generated groups beyond Z^d.

Load-bearing premise

The generators chosen for the counterexample graph G_d make its isoperimetric minimizers impossible to chain into an infinite ascending sequence.

What would settle it

An explicit construction of an infinite nested sequence of optimal subsets in G_d, each minimizing the edge boundary for its size, would falsify the no-chaining result.

Figures

Figures reproduced from arXiv: 2503.09591 by Cameron Strachan, Konrad Swanepoel.

Figure 1
Figure 1. Figure 1: Generating set of Theorem 2 to the EIP. In other words, they showed that any Cayley graph on Z has nested solutions starting at a sufficiently large size. We give a negative answer to the question of Barber and Erde for all d ≥ 2 by giving an explicit example of a Cayley graph without nested solutions. Furthermore, we show this example does not have nested solutions regardless of any starting point. Thus, … view at source ↗
Figure 2
Figure 2. Figure 2: The extremal subgraph of ΛU with 24k 2 − 24k + 7 vertices (k = 2) The first few values of n where e(n) = 6n−4 √ 6n − 6 are n = 7, 55, 151, 295, 487 and 727. In [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The hull of the black points is the set of black and red points [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: What sides of P correspond to the parameters ui and ti (i = 1, . . . , 6) This statement is a stronger version of Theorem 2 restricted to the class P. Before proving this theorem by induction on n, first we prove three lemmas. Lemma 5. For any n-vertex P ∈ P we have n = (t2 + 2t3 + t4 + u3 + u4 + 1)(t1 + 2t2 + t3 + u2 + u3 + 1) −  t2 + t3 + u3 + 1 2  −  t5 + t6 + u6 + 1 2  − X 6 i=1  ti + 1 2  . Proo… view at source ↗
Figure 5
Figure 5. Figure 5: Circumscribed parallelogram (blue) and hexagon (red) of [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: P after removal of a degenerate side remains in P n e(n) e(n) − e(n − 1) n e(n) e(n) − e(n − 1) n e(n) e(n) − e(n − 1) 3 3 21 81 5 39 173 5 4 6 3 22 86 5 40 178 5 5 9 3 23 91 5 41 183 5 6 13 4 24 96 5 42 189 6 7 18 5 25 101 5 43 194 5 8 21 3 26 106 5 44 199 5 9 25 4 27 111 5 45 204 5 10 30 5 28 116 5 46 210 6 11 34 4 29 121 5 47 215 5 12 39 5 30 126 5 48 220 5 13 43 4 31 132 6 49 225 5 14 48 5 32 137 5 50 … view at source ↗
Figure 7
Figure 7. Figure 7: Removing vertices of tj = t2 and adding them to ui = u4 u3 = 2 t3 = 2 u4 = 2 t4 = 2 u5 = 2 t5 = 1 u6 = 3 t6 = 1 u1 = 5 t1 = 1 u2 = 1 t2 = 2 [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Updated parameters of P that is missing part of a side Notice by updating these parameters we have strictly decreased P6 k=1 uk and strictly increased P6 k=1 tk. So if we repeat this process, after a finite number of times, we will obtain max{u1, u2, . . . , u6} − 3 ≤ min{t1, t2, . . . , t6}. The only problem is that when we do this process once, we may have transformed P so that one of its sides is partia… view at source ↗
Figure 9
Figure 9. Figure 9: Process when there is a partially-filled side [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Depiction of process when a degenerate side is created [PITH_FULL_IMAGE:figures/full_fig_p016_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Process depicting shift when L is parallel to a short edge v1 v2 v ′ 2 v ′ 1 v4 v3 (a) L parallel to a long edge (b) Translate vertices above line by −g2, red vertices represent overlaps [PITH_FULL_IMAGE:figures/full_fig_p021_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Process depicting shift when L is parallel to a long edge edge that crossed L is maintained after this shift, so the edges of ΛU [S] can only increase. This process must stop after a finite number of shifts as the area of ΛU [S] strictly decreases. Now suppose L is parallel to a long edge (say parallel to 2g1 − g2 as in Fig￾ure 12a). We apply a unit shift perpendicular to L (direction −g2 in Figure 12b) t… view at source ↗
Figure 13
Figure 13. Figure 13: The first 55 terms in the ordering of Λ [PITH_FULL_IMAGE:figures/full_fig_p024_13.png] view at source ↗
read the original abstract

We present two results related to an edge-isoperimetric question for Cayley graphs on the integer lattice asked by Ben Barber and Joshua Erde [Isoperimetry of Integer Lattices, Discrete Analysis 7 (2018)]. For any (undirected) graph $G$, the edge boundary of a subset of vertices $S$ is the number of edges between $S$ and its complement in $G$. Barber and Erde asked whether for any Cayley graph on $\mathbb{Z}^d$, there is always an ordering of $\mathbb{Z}^d$ such that for each $n$, the first $n$ terms minimize the edge boundary among all subsets of size $n$. First, we present an example of a Cayley graph $G_d$ on $\mathbb{Z}^d$ (for all $d\geq 2$) for which there is no such ordering. Furthermore, we show that for all $n$ and any optimal $n$-vertex subset $S_n$ of $G_d$, there is no infinite sequence $S_n\subset S_{n+1}\subset S_{n+2}\subset\cdots$ of optimal sets $S_i$, where $|S_i|=i$ for $i\geq n$. This is to be contrasted with the positive result in $\mathbb{Z}^1$ shown by Joseph Briggs and Chris Wells [arXiv:2402.14087]. Our second result is a positive example for the unit-length triangular lattice (which is isomorphic to $\mathbb{Z}^2$) where two vertices are connected by an edge if their distance is $1$ or $\sqrt{3}$. We show that this graph has such an ordering. This is the most complicated example known to us of a two-dimensional Cayley graph for which an ordering exists.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript resolves a question of Barber and Erde on whether every Cayley graph on Z^d admits an ordering of the vertices such that the initial segments minimize the edge boundary for every cardinality n. For each d ≥ 2 it supplies an explicit Cayley graph G_d on Z^d together with a proof that no such ordering exists; moreover, it shows that no optimal n-set can be extended to an infinite ascending chain of optimal sets. As a contrasting positive result, the authors exhibit such an ordering for the Cayley graph on Z^2 whose generators correspond to distances 1 and √3 in the triangular lattice.

Significance. If the constructions and proofs hold, the paper supplies the first explicit negative examples to the Barber–Erde question in dimension d ≥ 2, together with a strictly stronger non-extendability statement. The positive result on the triangular lattice is presented as the most intricate known two-dimensional case with the property. The arguments rest on parameter-free explicit generators and direct combinatorial case analysis rather than asymptotic or probabilistic methods.

minor comments (3)
  1. [Section 3 (construction of G_d)] The abstract states that G_d is defined by a specific choice of generators, but the main text should include an explicit listing of those generators (e.g., as a finite subset of Z^d) at the beginning of the construction section so that the subsequent case analysis can be followed without back-reference.
  2. [Introduction / final paragraph] The claim that the triangular-lattice example is “the most complicated example known to us” would benefit from a brief sentence or footnote citing the previously known two-dimensional positive examples.
  3. [Throughout] Notation for the edge boundary |∂S| and for the optimal sets S_n should be introduced once in a preliminary section and used consistently; the current draft occasionally switches between ∂S and the verbal description.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the results, and recommendation for minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript establishes its claims via explicit generator sets for the counterexample Cayley graphs G_d together with case-by-case verification that no infinite ascending chain of optimal sets exists, and a separate explicit edge set for the triangular lattice that admits an ordering. Both arguments are direct, parameter-free combinatorial proofs that do not invoke fitted quantities, self-referential definitions, or load-bearing self-citations whose validity depends on the present work. The cited positive result in one dimension is used only for contrast and is independently established elsewhere.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper relies on standard definitions of Cayley graphs and edge boundaries; its main addition is a concrete counterexample construction rather than new axioms or fitted quantities.

axioms (1)
  • standard math Cayley graphs on abelian groups are vertex-transitive and defined by a finite generating set
    Used throughout to define the graphs under study.
invented entities (1)
  • G_d no independent evidence
    purpose: Counterexample Cayley graph on Z^d without the desired ordering property
    Constructed specifically to demonstrate non-existence for d≥2.

pith-pipeline@v0.9.0 · 5853 in / 1291 out tokens · 34441 ms · 2026-05-22T23:43:56.690180+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    (2018), Paper No

    Ben Barber and Joshua Erde,Isoperimetry in integer lattices, Discrete Anal. (2018), Paper No. 7, 16. MR3819052

    work page 2018

  2. [2]

    Ben Barber, Joshua Erde, Peter Keevash, and Alexander Roberts,Isoperimetric stability in lattices, Proc. Amer. Math. Soc.151(2023), no. 12, 5021–5029. MR4648905

    work page 2023

  3. [3]

    A. J. Bernstein,Maximally connected arrays on then-cube, SIAM J. Appl. Math.15 (1967), 1485–1489. MR223260

    work page 1967

  4. [4]

    4, 299–314

    B´ ela Bollob´ as and Imre Leader,Edge-isoperimetric inequalities in the grid, Combinator- ica11(1991), no. 4, 299–314. MR1137765

    work page 1991

  5. [5]

    Geom.6(1996), no

    Peter Brass,Erd˝ os distance problems in normed spaces, Comput. Geom.6(1996), no. 4, 195–214. MR1392310

    work page 1996

  6. [6]

    Joseph Briggs and Chris Wells,Phase transitions in isoperimetric problems on the inte- gers, 2024

    work page 2024

  7. [7]

    1-3, 67–86

    Gy¨ orgy Csizmadia,The multiplicity of the two smallest distances among points, Discrete Math.194(1999), no. 1-3, 67–86. MR1654972

    work page 1999

  8. [8]

    Frank Harary and Heiko Harborth,Extremal animals, J. Combin. Inform. System Sci.1 (1976), no. 1, 1–8. MR457263

    work page 1976

  9. [9]

    Math29(1974), 14–15

    Heiko Harborth,Solution to problem 664 A, Elem. Math29(1974), 14–15

    work page 1974

  10. [10]

    L. H. Harper,Optimal assignments of numbers to vertices, J. Soc. Indust. Appl. Math. 12(1964), 131–135. MR162737

    work page 1964

  11. [11]

    MR1863367

    ,The edge-isoperimetric problem for regular planar tesselations, Ars Combin.61 (2001), 47–63. MR1863367

    work page 2001

  12. [12]

    90, Cambridge University Press, Cambridge, 2004

    ,Global methods for combinatorial isoperimetric problems, Cambridge Stud- ies in Advanced Mathematics, vol. 90, Cambridge University Press, Cambridge, 2004. MR2035509

    work page 2004

  13. [13]

    2, 157–163

    Sergiu Hart,A note on the edges of then-cube, Discrete Math.14(1976), no. 2, 157–163. MR396293

    work page 1976

  14. [14]

    Lindsey II,Assignment of numbers to vertices, Amer

    John H. Lindsey II,Assignment of numbers to vertices, Amer. Math. Monthly71(1964), 508–516. MR168489

    work page 1964

  15. [15]

    L. H. Loomis and H. Whitney,An inequality related to the isoperimetric inequality, Bull. Amer. Math. Soc.55(1949), 961–962. MR31538

    work page 1949

  16. [16]

    Vesztergombi,Bounds on the number of small distances in a finite planar set, Studia Sci

    K. Vesztergombi,Bounds on the number of small distances in a finite planar set, Studia Sci. Math. Hungar.22(1987), no. 1-4, 95–101. MR913897 26 u1 u2 u3 u4 u5 u6 t1 t2 t3 t4 t5 t6 f(n) Side k−1k−1k−1k−1k−1k−1k−2k−2k−2k−2k−2k−2 6n− √96n−96 k k k−1k−1k−1k−1k−3k−2k−2k−2k−2k−2 6n− √96n−47t 1 k k+ 1k k−1k−1k−1k−3k−3k−2k−2k−2k−2 6n− √96n+ 4t 2 k k−2k k−1k−1k−1k...

    work page 1987