The Isoperimetric Problem in Regular Trees
Marc Troyanov · 2026
Read The Isoperimetric Problem in Regular Trees by Marc Troyanov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18769.txt.
Introduction
Troyanov studies the inner vertex isoperimetric problem on regular trees, finding the exact isoperimetric profile for finite connected sets. He introduces a boundary invariant called the boundary branching excess, which gives a simple criterion for optimality. A set is optimal exactly when this excess stays below a threshold set by the tree degree. Every set also admits a canonical decomposition as an iterated gluing of full sets, whose entire boundary consists of leaves, yielding a complete account of all minimizers.
Catalog record
| CREATOR | Marc Troyanov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56164 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.18769
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Isoperimetric Problem in Regular Trees Marc Troyanov Abstract We investigate the inner vertex-isoperimetric problem on the d d -regular tree T d T_{d} . For each integer k ≥ 1 k\geq 1 , we determine the exact value of the inner vertex-isoperimetric profile I d ( k ) = min { | ∂ D | ∣ D ⊂ T d finite and connected , | D | = k } . I_{d}(k)=\min\{|\partial D|\mid D\subset T_{d}\text{ finite and connected},\ |D|=k\}. We introduce a boundary invariant, called the boundary branching excess τ ( D ) \tau(D) , and show that it provides a simple criterion for optimality. A domain D ⊂ T d D\subset T_{d} is isoperimetrically optimal if and only if τ ( D ) ≤ d − 2 \tau(D)\leq d-2 . Finally, we show that every domain in T d T_{d} admits a canonical decomposition as an iterated gluing of full domains , namely domains whose entire boundary consists of leaves. This yields a complete description of all inner vertex-isoperimetric minimizers in T d T_{d} . Keywords: regular tree, isoperimetric profile, discrete isoperimetric inequalities, optimal domains, vertex boundary, Cheeger constant. MSC(2020): 05C05, 05C35, 05C10. 1 Introduction The present paper addresses the inner vertex-isoperimetric problem on the regular tree T_{d} and provides an exact solution together with a complete structural description of optimal domains. This investigation grew out of material developed during the PhD thesis of Bruno Luiz Santos Correia at EPFL [ 4 ] . The thesis contains initial results and observations on the inner isoperimetric problem on the regular tree, including a computation of the isoperimetric profile. In the present paper, we develop these ideas into a complete and systematically organized treatment. 1.1 Statement of the problem The isoperimetric problem in a locally finite graph X addresses the following general question: among all domains D\subset X (that is, finite connected sets of vertices) of fixed cardinality, which ones have the smallest possible boundary? This problem naturally splits into two parts: (i) What is the smallest possible size of the boundary \partial D of a domain D\subset X of given cardinality? (ii) Describe all domains that are optimal , that is, those which attain this minimum. Question (i) corresponds to determining the best possible isoperimetric inequality in X , encoded by the isoperimetric profile I_{X}(k)=\min\left\{\,|\partial D|\mid D\subset X\text{ finite and connected},\ |D|=k\,\right\}. By definition, the isoperimetric inequality |\partial D|\geq I_{X}(|D|) holds for all domains D\subset X , and the isoperimetric profile is the largest function for which this inequality holds for all domains. Question (ii) then consists in describing the structure of all domains D satisfying |\partial D|=I_{X}(|D|). In graph theory, one may consider the outer vertex boundary, the inner vertex boundary, or the edge boundary. In this article we focus on the inner vertex boundary, for which the isoperimetric problem on the regular tree T_{d} is non-trivial; by contrast, the outer and edge boundaries lead to essentially trivial profiles (see Proposition 2.5 ). Despite the extensive literature on isoperimetric inequalities on graphs, we are not aware of any previous work addressing the specific inner vertex-isoperimetric problem on the infinite regular tree considered here. Remark. While edge-isoperimetric problems quantify the total amount of interaction between a domain and its complement, the inner vertex boundary measures the number of vertices within the domain that are directly exposed to the exterior. It is the natural notion of boundary in vertex-based models, such as epidemic spreading, information flow, or failure propagation in networked systems. 1.2 Outline of the paper In Section 2 we introduce the basic graph-theoretic notions and notation used throughout the paper, and recall the relevant boundary notions for domains in graphs. Specializing to the d -regular tree T_{d} , we introduce a natural decomposition of the boundary of a domain into leaves and residual boundary vertices. This leads to the notion of a full domain , namely a domain whose entire boundary consists of leaves. The section concludes with a short proof of the classical identity relating the size of a domain in T_{d} to the size of its outer boundary: |\partial^{\prime}D|=(d-2)\,|D|+2. The exact inner isoperimetric profile of the d -regular tree is established in Section 3 . It is given by I_{d}(k)=\left\lceil\frac{(d-2)k+2}{d-1}\right\rceil. Section 4 investigates isoperimetrically optimal domains in T_{d} . Although one might initially expect metric balls to be the only optimal domains, B. L. Santos Correia observed in his thesis that the class of optimal domains is in fact considerably richer. In this section, we introduce a fundamental invariant, the boundary branching excess \tau(D) , and show that optimality is characterized by the condition \tau(D)\leq d-2 . In particular, full domains satisfy \tau(D)=0 and are therefore optimal. Section 5 is devoted to several equivalent characterizations of full domains, and in Section 6 we study a natural gluing operation along boundary vertices for general domains and analyze the behavior of the invariant \tau under this operation. Section 7 , which forms one of the central parts of the paper, develops a detailed combinatorial description of arbitrary domains in T_{d} . We introduce the stem of a domain, a finite tree that encodes how full components are attached along the residual boundary, establish its basic structural properties, and show how the invariant \tau(D) can be read directly from its combinatorics. See in particular § 7.3 We further prove that any domain in T_{d} can be reconstructed, up to isomorphism, from its stem together with a collection of full domains and suitable gluing data. This leads to a classification of all domains in the regular tree, and in particular of all isoperimetrically optimal domains, summarized in Theorem 7.13 . 1.3 Related work Isoperimetric inequalities, and more generally geometric inequalities, have a long history dating back to the nineteenth century, and there is a vast literature which we do not attempt to survey here. A natural point of entry is the work of C. Pittet [ 11 ] , which introduces the notion of isoperimetric profile from the perspective of Riemannian geometry and highlights the connections between continuous and discrete methods. Isoperimetric inequalities have also been extensively studied in geometric group theory. A fundamental result in this direction is that of Coulhon and Saloff-Coste [ 6 ] , who estimate the isoperimetric profile of a finitely generated group in terms of its growth function. See also [ 5 ] for some recent refined estimates. Discrete isoperimetric problems also play a central role in combinatorics, expansion theory, percolation, random walk, and other probabilistic aspects of graph theory. General background can be found in [ 17 , 18 ] . The exact solution to the isoperimetric problem, including the exact isoperimetric profile and an explicit description of some (or all) minimal sets, is only known in a few cases. A classical example is that of the Hamming cube, whose vertex isoperimetric problem was solved by Harper [ 13 , 14 ] ; see also Leader [ 16 ] for a pedagogical presentation. We further refer to Harper’s monograph [ 15 ] for a broad overview of combinatorial isoperimetric problems and the compression methods often used to study them. More closely related to the present work are recent studies of isoperimetric