3 papers
math.CO2021
Non-existence of annular separators in geometric graphs
Farzam Ebrahimnejad, James R. Lee
Benjamini and Papasoglou (2011) showed that planar graphs with uniform polynomial volume growth admit -dimensional annular separators: The vertices at graph distance from an…
cs.DS2021
Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan
We show that the ratio of the number of near perfect matchings to the number of perfect matchings in -regular strong expander (non-bipartite) graphs, with vertices, is a po…
math.PR2020
On planar graphs of uniform polynomial growth
Farzam Ebrahimnejad, James R. Lee
Consider an infinite planar graph with uniform polynomial growth of degree d > 2. Many examples of such graphs exhibit similar geometric and spectral properties, and it has been co…