Publication

The Isoperimetric Problem in Regular Trees

Marc Troyanov
2026

Abstract

We investigate the inner vertex-isoperimetric problem on the d-regular tree T d. For each integer k ≥ 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}. We introduce a boundary invariant, called the boundary branching excess τ (D), and show that it provides a simple criterion for optimality. A domain D ⊂ T d is isoperimetrically optimal if and only if τ (D) ≤ d − 2. Finally, we show that every domain in 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 .

Official source

https://infoscience.epfl.ch/entities/publication/c5de0fd0-ac51-4c0d-97bb-cbada480daee

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Marc Troyanov
2026

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/c5de0fd0-ac51-4c0d-97bb-cbada480daee

About this result

Related concepts (28)

Isoperimetric inequality

In mathematics, the isoperimetric inequality is a geometric inequality involving the perimeter of a set and its volume. In -dimensional space the inequality lower bounds the surface area or perimeter of a set by its volume , where is a unit sphere. The equality holds only when is a sphere in . On a plane, i.e. when , the isoperimetric inequality relates the square of the circumference of a closed curve and the area of a plane region it encloses. Isoperimetric literally means "having the same perimeter".

Domain name

In the Internet, a domain name is a string that identifies a realm of administrative autonomy, authority or control. Domain names are often used to identify services provided through the Internet, such as websites, email services and more. As of 2017, 330.6 million domain names had been registered. Domain names are used in various networking contexts and for application-specific naming and addressing purposes. In general, a domain name identifies a network domain or an Internet Protocol (IP) resource, such as a personal computer used to access the Internet, or a server computer.

Regular expression

A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation. Regular expression techniques are developed in theoretical computer science and formal language theory. The concept of regular expressions began in the 1950s, when the American mathematician Stephen Cole Kleene formalized the concept of a regular language.