Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
eigenvalue; discrepancy; quasirandomness; Cayley graph
eigenvalue; discrepancy; quasirandomness; Cayley graph
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.
References:
[1] Alon, N.: Eigenvalues and expanders. Combinatorica 6 (1986), 83-96. DOI 10.1007/BF02579166 | MR 0875835 | Zbl 0661.05053
[2] Alon, N., Chung, F. R. K.: Explicit construction of linear sized tolerant networks. Discrete Math. 72 (1988), 15-19. DOI 10.1016/0012-365X(88)90189-6 | MR 0975519 | Zbl 0657.05068
[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 10.1137/070709529 | MR 2644348 | Zbl 1227.05225
[4] Alon, N., Milman, V. D.: $\lambda_1$, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38 (1985), 73-88. DOI 10.1016/0095-8956(85)90092-9 | MR 0782626
[5] Alon, N., Spencer, J. H.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization John Wiley & Sons, Hoboken (2008). MR 2437651 | Zbl 1148.05001
[6] Babai, L.: Spectra of Cayley graphs. J. Comb. Theory, Ser. B 27 (1979), 180-189. DOI 10.1016/0095-8956(79)90079-0 | MR 0546860 | Zbl 0338.05110
[7] Bilu, Y., Linial, N.: Lifts, discrepancy and nearly optimal spectral gap. Combinatorica 26 (2006), 495-519. DOI 10.1007/s00493-006-0029-7 | MR 2279667 | Zbl 1121.05054
[8] Chung, F., Graham, R.: Sparse quasi-random graphs. Combinatorica 22 (2002), 217-244. DOI 10.1007/s004930200010 | MR 1909084 | Zbl 0997.05090
[9] Chung, F. R. K., Graham, R. L., Wilson, R. M.: Quasi-random graphs. Combinatorica 9 (1989), 345-362. DOI 10.1007/BF02125347 | MR 1054011 | Zbl 0715.05057
[10] Conlon, D., Fox, J., Zhao, Y.: Extremal results in sparse pseudorandom graphs. Adv. Math. 256 (2014), 206-290. DOI 10.1016/j.aim.2013.12.004 | MR 3177293 | Zbl 1285.05096
[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 10.1147/rd.175.0420 | MR 0329965 | Zbl 0259.05112
[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 10.21136/CMJ.1975.101357 | MR 0387321 | Zbl 0437.15004
[15] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. DOI 10.21136/CMJ.1973.101168 | MR 0318007 | Zbl 0265.05119
[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 10.1016/0095-8956(88)90040-8 | MR 0941440 | Zbl 0658.05015
[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 0203.52503
[19] Kohayakawa, Y., Rödl, V.: Regular pairs in sparse random graphs I. Random Struct. Algorithms 22 (2003), 359-434. MR 1980964 | Zbl 1022.05076
[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 10.1007/BF02787543 | MR 2041225 | Zbl 1055.05138
[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 10.1007/978-3-540-32439-3_10 | MR 2223394 | Zbl 1098.05075
[22] Lovász, L.: Combinatorial Problems and Exercises. AMS Chelsea Publishing, Providence (2007). MR 2321240 | Zbl 1120.05001
[23] Lov{á}sz, L.: Spectra of graphs with transitive groups. Period. Math. Hung. 6 (1975), 191-195. DOI 10.1007/BF02018821 | MR 0398886 | Zbl 0395.05057
[24] Rödl, V.: On universality of graphs with uniformly distributed edges. Discrete Math. 59 (1986), 125-134. DOI 10.1016/0012-365X(86)90076-2 | MR 0837962 | Zbl 0619.05035
[25] Serre, J.-P.: Linear Representations of Finite Groups. Graduate Texts in Mathematics 42 Springer, New York (1977). DOI 10.1007/978-1-4684-9458-7_1 | MR 0450380 | Zbl 0355.20006
[26] Sinclair, A., Jerrum, M.: Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82 (1989), 93-133. DOI 10.1016/0890-5401(89)90067-9 | MR 1003059 | Zbl 0668.05060
[27] Spielman, D.: Spectral graph theory. Combinatorial Scientific Computing Chapman & Hall/CRC Comput. Sci. Ser. CRC Press, Boca Raton, FL (2012), 495-524. DOI 10.1201/b11644-19 | MR 2952760
[28] Spielman, D. A., Teng, S.-H: Spectral partitioning works: planar graphs and finite element meshes. Linear Algebra Appl. 421 (2007), 284-305. MR 2294342 | Zbl 1122.05062
[29] Tanner, R. M.: Explicit concentrators from generalized $N$-gons. SIAM J. Algebraic Discrete Methods 5 (1984), 287-293. DOI 10.1137/0605030 | MR 0752035 | Zbl 0554.05045
[30] Thomason, A.: Pseudo-random graphs. Random graphs '85 Ann. Discrete Math. 33 North-Holland, Amsterdam (1987), 307-331. MR 0930498 | Zbl 0672.05068
[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 0905280 | Zbl 0672.05068
Search
Partner of
