Combinatorics, Probability and Computing



On the Edge-Expansion of Graphs


NOGA ALON a1 1
a1 Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel (e-mail: noga@math.tau.ac.il)

Abstract

It is shown that if n>n0(d) then any d-regular graph G=(V, E) on n vertices contains a set of u=[lfloor O: left floor]n/2[rfloor C: right floor] vertices which is joined by at most (d/2−c[surd radical]d)u edges to the rest of the graph, where c>0 is some absolute constant. This is tight, up to the value of c.

(Received December 24 1995)
(Revised May 31 1996)



Footnotes

1 Research supported in part by a USA Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.