×

On the expansion rate of Margulis expanders. (English) Zbl 1089.05071

We determine exactly the expansion rate of an infinite 4-regular expander graph which is a variant of an expander due to G. A. Margulis [Probl. Peredači Inform. 9, No. 4, 71–80 (1973; Zbl 0312.22011)]. The vertex set of this graph consists of all points in the plane. The point \((x,y)\) is adjacent to the points \(S(x,y),S^{-1}(x,y),T(x,y),T^{-1}(x,y)\) where \(S(x,y)=(x,x+y)\) and \(T(x,y)=(x+y,y)\). We show that the expansion rate of this 4-regular graph is 2. The main technical result asserts that for any compact planar set \(A\) of finite positive measure, \[ \frac{|S(A)\cup S^{-1}(A)\cup T(A)\cup T^{-1}(A)\cup A|}{|A|}\geq 2, \] where \(|B|\) is the Lebesgue measure of \(B\). The proof is completely elementary and is based on symmetrization – a classical method in the area of isoperimetric problems. We also use symmetrization to prove a similar result for a directed version of the same graph.

MSC:

05C99 Graph theory

Citations:

Zbl 0312.22011
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gabber, O.; Galil, Z., Explicit constructions of linear size superconcentrators, FOCS, 20, 364-370 (1979)
[2] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan conjectures and explicit constructions of expanders, STOC, 86, 240-246 (1986)
[3] Lubotzky, A., Discrete Groups, Expanding Graphs and Invariant Measures (1994), Birkhäuser: Birkhäuser Basel · Zbl 0826.22012
[4] Margulis, G. A., Explicit constructions of concentrators, Problemy Peredachi Informatsii, 9, 4, 71-80; (1973), Problems of Information Transmission, Plenum, New York, 1975 (English translation) · Zbl 0312.22011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.