Sharp isoperimetric inequalities for infinite plane graphs with bounded vertex and face degrees
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2020
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914916006363136 |
|---|---|
| author | Oh, Byung-Geun |
| author_facet | Oh, Byung-Geun |
| contents | We provide sharp bounds for the isoperimetric constants of infinite plane graphs (tessellations) with bounded vertex and face degrees. For example, if $G$ is a plane graph satisfying the inequalities $p_1 \leq \mbox{deg}\ v \leq p_2$ for $v \in V(G)$ and $q_1 \leq \mbox{deg}\ f \leq q_2$ for $f \in F(G)$, where $p_1, p_2, q_1$, and $q_2$ are natural numbers such that $1/p_i + 1/q_i \leq 1/2$, $i=1,2$, then we show that \[ Φ(p_1, q_1) \leq \inf_S \frac{|\partial S|}{|V(S)|} \leq Φ(p_2, q_2), \] where the infimum is taken over all finite nonempty subgraphs $S \subset G$, $\partial S$ is the set of edges connecting $S$ to $G \setminus S$, and $Φ(p,q)$ is defined by \[ Φ(p, q) = (p-2) \sqrt{1 - \frac{4}{(p-2)(q-2)}}. \] For $p_1=3$ this gives an affirmative answer to a conjecture by Lawrencenko, Plummer, and Zha from 2002, and for general $p_i$ and $q_i$ our result fully resolves a question posed in the book by Lyons and Peres from 2016, where they extended the conjecture of Lawrencenko et al. to the above form. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2009_04394 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Sharp isoperimetric inequalities for infinite plane graphs with bounded vertex and face degrees Oh, Byung-Geun Combinatorics Metric Geometry 05C10, 05B45, 05C63, 52C20 We provide sharp bounds for the isoperimetric constants of infinite plane graphs (tessellations) with bounded vertex and face degrees. For example, if $G$ is a plane graph satisfying the inequalities $p_1 \leq \mbox{deg}\ v \leq p_2$ for $v \in V(G)$ and $q_1 \leq \mbox{deg}\ f \leq q_2$ for $f \in F(G)$, where $p_1, p_2, q_1$, and $q_2$ are natural numbers such that $1/p_i + 1/q_i \leq 1/2$, $i=1,2$, then we show that \[ Φ(p_1, q_1) \leq \inf_S \frac{|\partial S|}{|V(S)|} \leq Φ(p_2, q_2), \] where the infimum is taken over all finite nonempty subgraphs $S \subset G$, $\partial S$ is the set of edges connecting $S$ to $G \setminus S$, and $Φ(p,q)$ is defined by \[ Φ(p, q) = (p-2) \sqrt{1 - \frac{4}{(p-2)(q-2)}}. \] For $p_1=3$ this gives an affirmative answer to a conjecture by Lawrencenko, Plummer, and Zha from 2002, and for general $p_i$ and $q_i$ our result fully resolves a question posed in the book by Lyons and Peres from 2016, where they extended the conjecture of Lawrencenko et al. to the above form. |
| title | Sharp isoperimetric inequalities for infinite plane graphs with bounded vertex and face degrees |
| topic | Combinatorics Metric Geometry 05C10, 05B45, 05C63, 52C20 |
| url | https://arxiv.org/abs/2009.04394 |