Discrepancy and eigenvalues of Cayley graphs

Yoshiharu Kohayakawa; Vojtěch Rödl; Mathias Schacht

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 3, page 941-954
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Kohayakawa, Yoshiharu, Rödl, Vojtěch, and Schacht, Mathias. "Discrepancy and eigenvalues of Cayley graphs." Czechoslovak Mathematical Journal 66.3 (2016): 941-954. <http://eudml.org/doc/286820>.

@article{Kohayakawa2016,
abstract = {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.},
author = {Kohayakawa, Yoshiharu, Rödl, Vojtěch, Schacht, Mathias},
journal = {Czechoslovak Mathematical Journal},
keywords = {eigenvalue; discrepancy; quasirandomness; Cayley graph},
language = {eng},
number = {3},
pages = {941-954},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Discrepancy and eigenvalues of Cayley graphs},
url = {http://eudml.org/doc/286820},
volume = {66},
year = {2016},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 3
SP - 941
EP - 954
AB - 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.
LA - eng
KW - eigenvalue; discrepancy; quasirandomness; Cayley graph
UR - http://eudml.org/doc/286820
ER -

References

top
  1. Alon, N., 10.1007/BF02579166, Combinatorica 6 (1986), 83-96. (1986) Zbl0661.05053MR0875835DOI10.1007/BF02579166
  2. Alon, N., Chung, F. R. K., 10.1016/0012-365X(88)90189-6, Discrete Math. 72 (1988), 15-19. (1988) Zbl0657.05068MR0975519DOI10.1016/0012-365X(88)90189-6
  3. Alon, N., Coja-Oghlan, A., Hàn, H., Kang, M., Rödl, V., Schacht, M., 10.1137/070709529, SIAM J. Comput. 39 (2010), 2336-2362. (2010) Zbl1227.05225MR2644348DOI10.1137/070709529
  4. Alon, N., Milman, V. D., 10.1016/0095-8956(85)90092-9, J. Combin. Theory Ser. B 38 (1985), 73-88. (1985) MR0782626DOI10.1016/0095-8956(85)90092-9
  5. Alon, N., Spencer, J. H., The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization John Wiley & Sons, Hoboken (2008). (2008) Zbl1148.05001MR2437651
  6. Babai, L., 10.1016/0095-8956(79)90079-0, J. Comb. Theory, Ser. B 27 (1979), 180-189. (1979) Zbl0338.05110MR0546860DOI10.1016/0095-8956(79)90079-0
  7. Bilu, Y., Linial, N., 10.1007/s00493-006-0029-7, Combinatorica 26 (2006), 495-519. (2006) Zbl1121.05054MR2279667DOI10.1007/s00493-006-0029-7
  8. Chung, F., Graham, R., 10.1007/s004930200010, Combinatorica 22 (2002), 217-244. (2002) Zbl0997.05090MR1909084DOI10.1007/s004930200010
  9. Chung, F. R. K., Graham, R. L., Wilson, R. M., 10.1007/BF02125347, Combinatorica 9 (1989), 345-362. (1989) Zbl0715.05057MR1054011DOI10.1007/BF02125347
  10. Conlon, D., Fox, J., Zhao, Y., 10.1016/j.aim.2013.12.004, Adv. Math. 256 (2014), 206-290. (2014) Zbl1285.05096MR3177293DOI10.1016/j.aim.2013.12.004
  11. Conlon, D., Zhao, Y., Quasirandom Cayley graphs, Available at ArXiv: 1603.03025 [math.CO]. 
  12. Donath, W. E., Hoffman, A. J., 10.1147/rd.175.0420, IBM J. Res. Dev. 17 (1973), 420-425. (1973) Zbl0259.05112MR0329965DOI10.1147/rd.175.0420
  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. (1972) 
  14. Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J. 25 (1975), 619-633. (1975) Zbl0437.15004MR0387321
  15. Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007
  16. Frankl, P., Rödl, V., Wilson, R. M., 10.1016/0095-8956(88)90040-8, J. Comb. Theory, Ser. B 44 (1988), 317-328. (1988) Zbl0658.05015MR0941440DOI10.1016/0095-8956(88)90040-8
  17. Gowers, W. T., Personal communication, . 
  18. Hall, K. M., R-dimensional quadratic placement algorithm, (1970), Management Science Series A (Theory) 17 219-229. (1970) Zbl0203.52503
  19. Kohayakawa, Y., Rödl, V., Regular pairs in sparse random graphs I, Random Struct. Algorithms 22 (2003), 359-434. (2003) Zbl1022.05076MR1980964
  20. Kohayakawa, Y., Rödl, V., Sissokho, P., 10.1007/BF02787543, Isr. J. Math. 139 (2004), 93-137. (2004) Zbl1055.05138MR2041225DOI10.1007/BF02787543
  21. Krivelevich, M., Sudakov, B., 10.1007/978-3-540-32439-3_10, E. Györi More Sets, Graphs and Numbers Bolyai Society Mathematical Studies 15 Springer, Berlin (2006), 199-262. (2006) Zbl1098.05075MR2223394DOI10.1007/978-3-540-32439-3_10
  22. Lovász, L., Combinatorial Problems and Exercises, AMS Chelsea Publishing, Providence (2007). (2007) Zbl1120.05001MR2321240
  23. Lov{á}sz, L., 10.1007/BF02018821, Period. Math. Hung. 6 (1975), 191-195. (1975) Zbl0395.05057MR0398886DOI10.1007/BF02018821
  24. Rödl, V., 10.1016/0012-365X(86)90076-2, Discrete Math. 59 (1986), 125-134. (1986) Zbl0619.05035MR0837962DOI10.1016/0012-365X(86)90076-2
  25. Serre, J.-P., 10.1007/978-1-4684-9458-7_1, Graduate Texts in Mathematics 42 Springer, New York (1977). (1977) Zbl0355.20006MR0450380DOI10.1007/978-1-4684-9458-7_1
  26. Sinclair, A., Jerrum, M., 10.1016/0890-5401(89)90067-9, Inf. Comput. 82 (1989), 93-133. (1989) Zbl0668.05060MR1003059DOI10.1016/0890-5401(89)90067-9
  27. Spielman, D., 10.1201/b11644-19, Combinatorial Scientific Computing Chapman & Hall/CRC Comput. Sci. Ser. CRC Press, Boca Raton, FL (2012), 495-524. (2012) MR2952760DOI10.1201/b11644-19
  28. Spielman, D. A., Teng, S.-H, Spectral partitioning works: planar graphs and finite element meshes, Linear Algebra Appl. 421 (2007), 284-305. (2007) Zbl1122.05062MR2294342
  29. Tanner, R. M., 10.1137/0605030, SIAM J. Algebraic Discrete Methods 5 (1984), 287-293. (1984) Zbl0554.05045MR0752035DOI10.1137/0605030
  30. Thomason, A., Pseudo-random graphs, Random graphs '85 Ann. Discrete Math. 33 North-Holland, Amsterdam (1987), 307-331. (1987) Zbl0672.05068MR0930498
  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. (1987) Zbl0672.05068MR0905280

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.