کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4657530 | 1343745 | 2006 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the expansion rate of Margulis expanders On the expansion rate of Margulis expanders](/preview/png/4657530.png)
In this note we determine exactly the expansion rate of an infinite 4-regular expander graph which is a variant of an expander due to Margulis. The vertex set of this graph consists of all points in the plane. The point (x,y)(x,y) is adjacent to the points S(x,y),S-1(x,y),T(x,y),T-1(x,y)S(x,y),S-1(x,y),T(x,y),T-1(x,y) where S(x,y)=(x,x+y)S(x,y)=(x,x+y) and T(x,y)=(x+y,y)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,|S(A)∪S-1(A)∪T(A)∪T-1(A)∪A||A|≥2,where |B||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.
Journal: Journal of Combinatorial Theory, Series B - Volume 96, Issue 3, May 2006, Pages 436–442