Expanders obtained from affine transformations Export

@article{citeulike:4622718, abstract = {Abstract\ \ A bipartite graphG=(U, V, E) is an (n, k, δ, α) expander if |U|=|V|=n, |E|≦kn, and for anyX⊆U with |X|≦αn, |Γ G (X)|≧(1+δ(1−|X|/n)) |X|, whereΓ G (X) is the set of nodes inV connected to nodes inX with edges inE. We show, using relatively elementary analysis in linear algebra, that the problem of estimating the coefficientδ of a bipartite graph is reduced to that of estimating the second largest eigenvalue of a matrix related to the graph. In particular, we consider the case where the bipartite graphs are defined from affine transformations, and obtain some general results on estimating the eigenvalues of the matrix by using the discrete Fourier transform. These results are then used to estimate the expanding coefficients of bipartite graphs obtained from two-dimensional affine transformations and those obtained from one-dimensional ones.}, author = {Jimbo, Shuji and Maruoka, Akira}, citeulike-article-id = {4622718}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/BF02579322}, citeulike-linkout-1 = {http://www.springerlink.com/content/6w2126413464n387}, day = {23}, doi = {10.1007/BF02579322}, journal = {Combinatorica}, keywords = {algorithms, combinatorics, complexity}, month = {December}, number = {4}, pages = {343--355}, posted-at = {2009-05-24 18:55:25}, priority = {2}, title = {Expanders obtained from affine transformations}, url = {http://dx.doi.org/10.1007/BF02579322}, volume = {7}, year = {1987} }

TY - JOUR ID - citeulike:4622718 L3 - citeulike-article-id:4622718 N2 - Abstract  A bipartite graphG=(U, V, E) is an (n, k, δ, α) expander if |U|=|V|=n, |E|≦kn, and for anyX⊆U with |X|≦αn, |Γ G (X)|≧(1+δ(1−|X|/n)) |X|, whereΓ G (X) is the set of nodes inV connected to nodes inX with edges inE. We show, using relatively elementary analysis in linear algebra, that the problem of estimating the coefficientδ of a bipartite graph is reduced to that of estimating the second largest eigenvalue of a matrix related to the graph. In particular, we consider the case where the bipartite graphs are defined from affine transformations, and obtain some general results on estimating the eigenvalues of the matrix by using the discrete Fourier transform. These results are then used to estimate the expanding coefficients of bipartite graphs obtained from two-dimensional affine transformations and those obtained from one-dimensional ones. IS - 4 JF - Combinatorica EP - 355 TI - Expanders obtained from affine transformations VL - 7 SP - 343 KW - algorithms KW - combinatorics KW - complexity AU - Jimbo, Shuji AU - Maruoka, Akira PY - 1987/12/23/ UR - http://dx.doi.org/10.1007/BF02579322 ER -