NODE BISECTORS OF CAYLEY-GRAPHS

A node bisector of a graph Gamma is a subset Omega of the nodes of Gam ma such that Gamma may be expressed as the disjoint union Gamma = Omeg a(1) boolean OR Omega boolean OR Omega(2), where \Omega(1)\ greater th an or equal to 1/3\Gamma\, Omega(2) greater than or equal to 1/3\Gamma \, and where any path from Omega(1) to Omega(2) must pass through Omeg a. Suppose Gamma is the Cayley graph of an abelian group G with respec t to a generating set of cardinality r, regarded as an undirected grap h, Then we show that r has a node bisector of order at most c\G\(1-1/r ) where c is a constant depending only on r. We show that the exponent in this result is the best possible.