On the bisection width of the transposition network

✍ Scribed by Kalpakis, Konstantinos; Yesha, Yaacov

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 103 KB
• Volume: 29
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199701)29:1<69::aid-net7>3.0.co;2-a

✦ Synopsis

The transposition network T n of order n! is the Cayley graph of the symmetric group S n with generators the set of all transpositions in S n . Finding the bisection width of the transposition network is an open question posed by F. T. Leighton. We resolve this question for n even, by showing that the bisection width of the transposition network T n is equal to nn!/4. When n ¢ 2 is odd, we show that the bisection width of the transposition network T n is (1 / o(1))nn!/4. In doing so, we determine the second smallest eigenvalue of the adjacency matrix of T n . Further, given a Cayley graph of a finite group G, with m conjugacy classes and with a set of generators closed under taking conjugates and not containing the identity of G, we show how to construct an m 1 m integer matrix Q, from the conjugacy classes of G, such that the set of eigenvalues of Q is equal to the set of eigenvalues of the adjacency matrix A of the given Cayley graph. Hence, when the order of G is large compared to the number of its conjugacy classes, a faster method for computing the eigenvalues of A is provided.