Improved Expansion of Random Cayley Graphs
In Random Cayley Graphs and Expanders, N. Alon and Y. Roichman proved that for every ε > 0 there is a finite c(ε) such that for any sufficiently large group G, the expected value of the second largest (in absolute value) eigenvalue of the normalized adjacency matrix of the Cayley grap...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2004-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Online Access: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/205 |
| _version_ | 1818010340563091456 |
|---|---|
| author | Po-Shen Loh Leonard J. Schulman |
| author_facet | Po-Shen Loh Leonard J. Schulman |
| author_sort | Po-Shen Loh |
| collection | DOAJ |
| description | In Random Cayley Graphs and Expanders, N. Alon and Y. Roichman proved that for every ε > 0 there is a finite c(ε) such that for any sufficiently large group G, the expected value of the second largest (in absolute value) eigenvalue of the normalized adjacency matrix of the Cayley graph with respect to c(ε) log |G| random elements is less than ε. We reduce the number of elements to c(ε)log D(G) (for the same c), where D(G) is the sum of the dimensions of the irreducible representations of G. In sufficiently non-abelian families of groups (as measured by these dimensions), log D(G) is asymptotically (1/2)log|G|. As is well known, a small eigenvalue implies large graph expansion (and conversely); see Tanner84 and AlonMilman84-2,AlonMilman84-1. For any specified eigenvalue or expansion, therefore, random Cayley graphs (of sufficiently non-abelian groups) require only half as many edges as was previously known. |
| first_indexed | 2024-04-14T05:54:02Z |
| format | Article |
| id | doaj.art-55c510ef3e29497bb433f95a346e8688 |
| institution | Directory Open Access Journal |
| issn | 1462-7264 1365-8050 |
| language | English |
| last_indexed | 2024-04-14T05:54:02Z |
| publishDate | 2004-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-55c510ef3e29497bb433f95a346e86882022-12-22T02:09:00ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1462-72641365-80502004-12-0162Improved Expansion of Random Cayley GraphsPo-Shen LohLeonard J. SchulmanIn Random Cayley Graphs and Expanders, N. Alon and Y. Roichman proved that for every ε > 0 there is a finite c(ε) such that for any sufficiently large group G, the expected value of the second largest (in absolute value) eigenvalue of the normalized adjacency matrix of the Cayley graph with respect to c(ε) log |G| random elements is less than ε. We reduce the number of elements to c(ε)log D(G) (for the same c), where D(G) is the sum of the dimensions of the irreducible representations of G. In sufficiently non-abelian families of groups (as measured by these dimensions), log D(G) is asymptotically (1/2)log|G|. As is well known, a small eigenvalue implies large graph expansion (and conversely); see Tanner84 and AlonMilman84-2,AlonMilman84-1. For any specified eigenvalue or expansion, therefore, random Cayley graphs (of sufficiently non-abelian groups) require only half as many edges as was previously known.http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/205 |
| spellingShingle | Po-Shen Loh Leonard J. Schulman Improved Expansion of Random Cayley Graphs Discrete Mathematics & Theoretical Computer Science |
| title | Improved Expansion of Random Cayley Graphs |
| title_full | Improved Expansion of Random Cayley Graphs |
| title_fullStr | Improved Expansion of Random Cayley Graphs |
| title_full_unstemmed | Improved Expansion of Random Cayley Graphs |
| title_short | Improved Expansion of Random Cayley Graphs |
| title_sort | improved expansion of random cayley graphs |
| url | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/205 |
| work_keys_str_mv | AT poshenloh improvedexpansionofrandomcayleygraphs AT leonardjschulman improvedexpansionofrandomcayleygraphs |