Remarks on partitions into expanders

2020/01/06 by Vigolo, Federico
#05C75 51F99 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.2001.01522

Abstract

In this note we give a short proof that graphs having no linearly small Følner sets can be partitioned into a union of expanders. We use this fact to prove a partition result for graphs admitting linearly small maximal Følner sets and we deduce that a family of such graphs must contain a family of expanders. We also show that the existence of partitions into expanders is a quasi-isometry invariant.

Related

• A note on the structure of expanders
• Sublinear expanders and their applications
• Expanders - how to find them, and what to find in them
• A continuum of expanders
• Multi-way expansion constants and partitions of a graph