Geodesic
Discrepancy and eigenvalues of Cayley graphs
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 941-954
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This affirmatively answers a question of Chung and Graham (2002) for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.
We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This affirmatively answers a question of Chung and Graham (2002) for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.
DOI : 10.1007/s10587-016-0302-x
Classification : 05C50, 05C80
Keywords: eigenvalue; discrepancy; quasirandomness; Cayley graph 
@article{10_1007_s10587_016_0302_x,
     author = {Kohayakawa, Yoshiharu and R\"odl, Vojt\v{e}ch and Schacht, Mathias},
     title = {Discrepancy and eigenvalues of {Cayley} graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {941--954},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0302-x},
     mrnumber = {3556877},
     zbl = {06644043},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0302-x/}
}
TY  - JOUR
AU  - Kohayakawa, Yoshiharu
AU  - Rödl, Vojtěch
AU  - Schacht, Mathias
TI  - Discrepancy and eigenvalues of Cayley graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 941
EP  - 954
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0302-x/
DO  - 10.1007/s10587-016-0302-x
LA  - en
ID  - 10_1007_s10587_016_0302_x
ER  - 
%0 Journal Article
%A Kohayakawa, Yoshiharu
%A Rödl, Vojtěch
%A Schacht, Mathias
%T Discrepancy and eigenvalues of Cayley graphs
%J Czechoslovak Mathematical Journal
%D 2016
%P 941-954
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0302-x/
%R 10.1007/s10587-016-0302-x
%G en
%F 10_1007_s10587_016_0302_x
Kohayakawa, Yoshiharu; Rödl, Vojtěch; Schacht, Mathias. Discrepancy and eigenvalues of Cayley graphs. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 941-954. doi: 10.1007/s10587-016-0302-x

[1] Alon, N.: Eigenvalues and expanders. Combinatorica 6 (1986), 83-96. | DOI | MR | Zbl

[2] Alon, N., Chung, F. R. K.: Explicit construction of linear sized tolerant networks. Discrete Math. 72 (1988), 15-19. | DOI | MR | Zbl

[3] Alon, N., Coja-Oghlan, A., Hàn, H., Kang, M., Rödl, V., Schacht, M.: Quasi-randomness and algorithmic regularity for graphs with general degree distributions. SIAM J. Comput. 39 (2010), 2336-2362. | DOI | MR | Zbl

[4] Alon, N., Milman, V. D.: $\lambda_1$, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38 (1985), 73-88. | DOI | MR

[5] Alon, N., Spencer, J. H.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization John Wiley & Sons, Hoboken (2008). | MR | Zbl

[6] Babai, L.: Spectra of Cayley graphs. J. Comb. Theory, Ser. B 27 (1979), 180-189. | DOI | MR | Zbl

[7] Bilu, Y., Linial, N.: Lifts, discrepancy and nearly optimal spectral gap. Combinatorica 26 (2006), 495-519. | DOI | MR | Zbl

[8] Chung, F., Graham, R.: Sparse quasi-random graphs. Combinatorica 22 (2002), 217-244. | DOI | MR | Zbl

[9] Chung, F. R. K., Graham, R. L., Wilson, R. M.: Quasi-random graphs. Combinatorica 9 (1989), 345-362. | DOI | MR | Zbl

[10] Conlon, D., Fox, J., Zhao, Y.: Extremal results in sparse pseudorandom graphs. Adv. Math. 256 (2014), 206-290. | DOI | MR | Zbl

[11] Conlon, D., Zhao, Y.: Quasirandom Cayley graphs. Available at ArXiv: 1603.03025 [math.CO].

[12] Donath, W. E., Hoffman, A. J.: Lower bounds for the partitioning of graphs. IBM J. Res. Dev. 17 (1973), 420-425. | DOI | MR | Zbl

[13] Donath, W. E., Hoffman, A. J.: Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices. (1972), IBM Techn. Disclosure Bull. 15 938-944.

[14] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619-633. | DOI | MR | Zbl

[15] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | DOI | MR | Zbl

[16] Frankl, P., Rödl, V., Wilson, R. M.: The number of submatrices of a given type in a Hadamard matrix and related results. J. Comb. Theory, Ser. B 44 (1988), 317-328. | DOI | MR | Zbl

[17] Gowers, W. T.: Personal communication.

[18] Hall, K. M.: R-dimensional quadratic placement algorithm. (1970), Management Science Series A (Theory) 17 219-229. | Zbl

[19] Kohayakawa, Y., Rödl, V.: Regular pairs in sparse random graphs I. Random Struct. Algorithms 22 (2003), 359-434. | MR | Zbl

[20] Kohayakawa, Y., Rödl, V., Sissokho, P.: Embedding graphs with bounded degree in sparse pseudorandom graphs. Isr. J. Math. 139 (2004), 93-137. | DOI | MR | Zbl

[21] Krivelevich, M., Sudakov, B.: Pseudo-random graphs. E. Györi More Sets, Graphs and Numbers Bolyai Society Mathematical Studies 15 Springer, Berlin (2006), 199-262. | DOI | MR | Zbl

[22] Lovász, L.: Combinatorial Problems and Exercises. AMS Chelsea Publishing, Providence (2007). | MR | Zbl

[23] Lov{á}sz, L.: Spectra of graphs with transitive groups. Period. Math. Hung. 6 (1975), 191-195. | DOI | MR | Zbl

[24] Rödl, V.: On universality of graphs with uniformly distributed edges. Discrete Math. 59 (1986), 125-134. | DOI | MR | Zbl

[25] Serre, J.-P.: Linear Representations of Finite Groups. Graduate Texts in Mathematics 42 Springer, New York (1977). | DOI | MR | Zbl

[26] Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82 (1989), 93-133. | DOI | MR | Zbl

[27] Spielman, D.: Spectral graph theory. Combinatorial Scientific Computing Chapman & Hall/CRC Comput. Sci. Ser. CRC Press, Boca Raton, FL (2012), 495-524. | DOI | MR

[28] Spielman, D. A., Teng, S.-H: Spectral partitioning works: planar graphs and finite element meshes. Linear Algebra Appl. 421 (2007), 284-305. | MR | Zbl

[29] Tanner, R. M.: Explicit concentrators from generalized $N$-gons. SIAM J. Algebraic Discrete Methods 5 (1984), 287-293. | DOI | MR | Zbl

[30] Thomason, A.: Pseudo-random graphs. Random graphs '85 Ann. Discrete Math. 33 North-Holland, Amsterdam (1987), 307-331. | MR | Zbl

[31] Thomason, A.: Random graphs, strongly regular graphs and pseudo-random graphs. Surveys in Combinatorics 1987 London Math. Soc. Lecture Note Ser. 123 Cambridge Univ. Press, Cambridge (1987), 173-195. | MR | Zbl

Cité par Sources :