Thumbnail
Access Restriction
Open

Author Loh, Po-Shen ♦ Schulman, Leonard J.
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Non-abelian Group ♦ Large Group ♦ Specified Eigenvalue ♦ Non-abelian Family ♦ Many Edge ♦ Cayley Graph ♦ Normalized Adjacency Matrix ♦ Log Random Element ♦ Random Cayley Graph ♦ Expected Value ♦ Irreducible Representation ♦ Absolute Value
Description Alon and Roichman (1994) 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(ε)logD(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), logD(G) is asymptotically (1/2)log G . As is well known, a small eigenvalue implies large graph expansion (and conversely); see Tanner (1984) and Alon and Milman (1984, 1985). 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.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2004-01-01
Journal Discrete Mathematics and Theoretical Computer Science