Sharp isoperimetric inequalities for infinite plane graphs with bounded\n vertex and face degrees

2020/09/09 by B. G. Oh, Oh, Byung-Geun, Byung-Geun Oh
Mathematics · Computer Science · #Graph theory and applications #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2009.04394

Abstract

We provide sharp bounds for the isoperimetric constants of infinite plane\ngraphs (tessellations) with bounded vertex and face degrees. For example, if\nG is a plane graph satisfying the inequalities p₁ \≤ deg v \≤\np₂ for v \∈ V(G) and q₁ \≤ deg f \≤ q₂ for f \∈ F(G),\nwhere p₁, p₂, q₁, and q₂ are natural numbers such that 1/p_i + 1/q_i\n\≤ 1/2, i=1,2, then we show that \
Phi (p₁, q₁)
leq
inf_S\n
frac|
partial S||V(S)|
leq
Phi (p₂, q₂), where the infimum is taken\nover all finite nonempty subgraphs S \⊂ G, \∂ S is the set of\nedges connecting S to G \∖ S, and \Φ(p,q) is defined by \
Phi\n(p, q) = (p-2)
sqrt1 -
frac4(p-2)(q-2). For p₁=3 this gives an\naffirmative answer to a conjecture by Lawrencenko, Plummer, and Zha from 2002,\nand for general p_i and q_i our result fully resolves a question posed in\nthe book by Lyons and Peres from 2016, where they extended the conjecture of\nLawrencenko et al. to the above form.\n

Related

• Isoperimetric inequalities in Riemann surfaces and graphs
• Strong Isoperimetric Inequality for Tessellating Quantum Graphs
• The Boundary of a Graph and its Isoperimetric Inequality
• Pinched exponential volume growth implies an infinite dimensional isoperimetric inequality
• Edge Isoperimetric Inequalities for Powers of the Hypercube