Multi-way expansion constants and partitions of a graph

Abstract

In this paper, we consider a relation between $k$-way expansion constant of a finite graph and the expansion constants of subgraphs in a $k$-partition of the graph. Using this relation, we show that a sequence of finite graphs which have uniformly bounded $k+1$-way expansion constants and uniformly bounded degrees can be divided into $k$ or less sequences of expanders. Furthermore, we prove that such sequence of finite graphs is not coarsely embeddable into any Hilbert space.

The previous version has a mistake in Theorem 2, so I give a result similar to Theorem 2, and reprove the other results in the previous version using it

Cited by in corpus (3)

• Eigenvalue ratios of nonnegatively curved graphs
• Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
• Multi-way expanders and imprimitive group actions on graphs