2011/12/15 by Tanaka, Mamoru
#05C50 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1112.3434
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.