| Title:
|
Discrepancy and eigenvalues of Cayley graphs (English) |
| Author:
|
Kohayakawa, Yoshiharu |
| Author:
|
Rödl, Vojtěch |
| Author:
|
Schacht, Mathias |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
941-954 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
eigenvalue |
| Keyword:
|
discrepancy |
| Keyword:
|
quasirandomness |
| Keyword:
|
Cayley graph |
| MSC:
|
05C50 |
| MSC:
|
05C80 |
| idZBL:
|
Zbl 06644043 |
| idMR:
|
MR3556877 |
| DOI:
|
10.1007/s10587-016-0302-x |
| . |
| Date available:
|
2016-10-01T15:39:48Z |
| Last updated:
|
2023-10-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145881 |
| . |
| Reference:
|
[1] Alon, N.: Eigenvalues and expanders.Combinatorica 6 (1986), 83-96. Zbl 0661.05053, MR 0875835, 10.1007/BF02579166 |
| Reference:
|
[2] Alon, N., Chung, F. R. K.: Explicit construction of linear sized tolerant networks.Discrete Math. 72 (1988), 15-19. Zbl 0657.05068, MR 0975519, 10.1016/0012-365X(88)90189-6 |
| Reference:
|
[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. Zbl 1227.05225, MR 2644348, 10.1137/070709529 |
| Reference:
|
[4] Alon, N., Milman, V. D.: $\lambda_1$, isoperimetric inequalities for graphs, and superconcentrators.J. Combin. Theory Ser. B 38 (1985), 73-88. MR 0782626, 10.1016/0095-8956(85)90092-9 |
| Reference:
|
[5] Alon, N., Spencer, J. H.: The Probabilistic Method.Wiley-Interscience Series in Discrete Mathematics and Optimization John Wiley & Sons, Hoboken (2008). Zbl 1148.05001, MR 2437651 |
| Reference:
|
[6] Babai, L.: Spectra of Cayley graphs.J. Comb. Theory, Ser. B 27 (1979), 180-189. Zbl 0338.05110, MR 0546860, 10.1016/0095-8956(79)90079-0 |
| Reference:
|
[7] Bilu, Y., Linial, N.: Lifts, discrepancy and nearly optimal spectral gap.Combinatorica 26 (2006), 495-519. Zbl 1121.05054, MR 2279667, 10.1007/s00493-006-0029-7 |
| Reference:
|
[8] Chung, F., Graham, R.: Sparse quasi-random graphs.Combinatorica 22 (2002), 217-244. Zbl 0997.05090, MR 1909084, 10.1007/s004930200010 |
| Reference:
|
[9] Chung, F. R. K., Graham, R. L., Wilson, R. M.: Quasi-random graphs.Combinatorica 9 (1989), 345-362. Zbl 0715.05057, MR 1054011, 10.1007/BF02125347 |
| Reference:
|
[10] Conlon, D., Fox, J., Zhao, Y.: Extremal results in sparse pseudorandom graphs.Adv. Math. 256 (2014), 206-290. Zbl 1285.05096, MR 3177293, 10.1016/j.aim.2013.12.004 |
| Reference:
|
[11] Conlon, D., Zhao, Y.: Quasirandom Cayley graphs.Available at ArXiv: 1603.03025 [math.CO]. |
| Reference:
|
[12] Donath, W. E., Hoffman, A. J.: Lower bounds for the partitioning of graphs.IBM J. Res. Dev. 17 (1973), 420-425. Zbl 0259.05112, MR 0329965, 10.1147/rd.175.0420 |
| Reference:
|
[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. |
| Reference:
|
[14] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory.Czech. Math. J. 25 (1975), 619-633. Zbl 0437.15004, MR 0387321, 10.21136/CMJ.1975.101357 |
| Reference:
|
[15] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007, 10.21136/CMJ.1973.101168 |
| Reference:
|
[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. Zbl 0658.05015, MR 0941440, 10.1016/0095-8956(88)90040-8 |
| Reference:
|
[17] Gowers, W. T.: Personal communication.. |
| Reference:
|
[18] Hall, K. M.: R-dimensional quadratic placement algorithm.(1970), Management Science Series A (Theory) 17 219-229. Zbl 0203.52503 |
| Reference:
|
[19] Kohayakawa, Y., Rödl, V.: Regular pairs in sparse random graphs I.Random Struct. Algorithms 22 (2003), 359-434. Zbl 1022.05076, MR 1980964 |
| Reference:
|
[20] Kohayakawa, Y., Rödl, V., Sissokho, P.: Embedding graphs with bounded degree in sparse pseudorandom graphs.Isr. J. Math. 139 (2004), 93-137. Zbl 1055.05138, MR 2041225, 10.1007/BF02787543 |
| Reference:
|
[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. Zbl 1098.05075, MR 2223394, 10.1007/978-3-540-32439-3_10 |
| Reference:
|
[22] Lovász, L.: Combinatorial Problems and Exercises.AMS Chelsea Publishing, Providence (2007). Zbl 1120.05001, MR 2321240 |
| Reference:
|
[23] Lov{á}sz, L.: Spectra of graphs with transitive groups.Period. Math. Hung. 6 (1975), 191-195. Zbl 0395.05057, MR 0398886, 10.1007/BF02018821 |
| Reference:
|
[24] Rödl, V.: On universality of graphs with uniformly distributed edges.Discrete Math. 59 (1986), 125-134. Zbl 0619.05035, MR 0837962, 10.1016/0012-365X(86)90076-2 |
| Reference:
|
[25] Serre, J.-P.: Linear Representations of Finite Groups.Graduate Texts in Mathematics 42 Springer, New York (1977). Zbl 0355.20006, MR 0450380, 10.1007/978-1-4684-9458-7_1 |
| Reference:
|
[26] Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing Markov chains.Inf. Comput. 82 (1989), 93-133. Zbl 0668.05060, MR 1003059, 10.1016/0890-5401(89)90067-9 |
| Reference:
|
[27] Spielman, D.: Spectral graph theory.Combinatorial Scientific Computing Chapman & Hall/CRC Comput. Sci. Ser. CRC Press, Boca Raton, FL (2012), 495-524. MR 2952760, 10.1201/b11644-19 |
| Reference:
|
[28] Spielman, D. A., Teng, S.-H: Spectral partitioning works: planar graphs and finite element meshes.Linear Algebra Appl. 421 (2007), 284-305. Zbl 1122.05062, MR 2294342 |
| Reference:
|
[29] Tanner, R. M.: Explicit concentrators from generalized $N$-gons.SIAM J. Algebraic Discrete Methods 5 (1984), 287-293. Zbl 0554.05045, MR 0752035, 10.1137/0605030 |
| Reference:
|
[30] Thomason, A.: Pseudo-random graphs.Random graphs '85 Ann. Discrete Math. 33 North-Holland, Amsterdam (1987), 307-331. Zbl 0672.05068, MR 0930498 |
| Reference:
|
[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. Zbl 0672.05068, MR 0905280 |
| . |
