Lower bounds for the isoperimetric numbers of random regular graphs

Abstract

The vertex isoperimetric number of a graph $G=(V,E)$ is the minimum of the ratio $|{\partial }_{V}U|/|U|$ where $U$ ranges over all nonempty subsets of $V$ with $|U|/|V|\le u$ and ${\partial }_{V}U$ is the set of all vertices adjacent to $U$ but not in $U$. The analogously defined edge isoperimetric number---with ${\partial }_{V}U$ replaced by ${\partial }_{E}U$, the set of all edges with exactly one endpoint in $U$---has been studied extensively. Here we study random regular graphs. For the case $u=1/2$, we give asymptotically almost sure lower bounds for the vertex isoperimetric number for all $d\ge 3$. Moreover, we obtain a lower bound on the asymptotics as $d\to \infty$. We also provide asymptotically almost sure lower bounds on $|{\partial }_{E}U|/|U|$ in terms of an upper bound on the size of $U$ and analyse the bounds as $d\to \infty$.

24 pages, 3 tables; minor edits

References in corpus (1)

• Local Improvement Gives Better Expanders

Cited by in corpus (4)

• From Graph Isoperimetric Inequality to Network Connectivity -- A New Approach
• Cops and Robbers on Multi-Layer Graphs
• A Metastability Result for the Contact Process on a Random Regular Graph
• Modularity of regular and treelike graphs