✦ LIBER ✦

Expansion Properties of Cayley Graphs of the Alternating Groups

✍ Scribed by Yuval Roichman

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 360 KB
Volume: 79
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1997.2786

No coin nor oath required. For personal study only.

✦ Synopsis

Let C be a conjugacy class in the alternating group A n , and let supp(C) be the number of nonfixed digits under the action of a permutation in C. For every 1>$>0 and n 5 there exists a constant c=c($)>0 such that if supp(C) $n then the undirected Cayley graph X(A n , C) is a c expander. A family of such Cayley graphs with supp(C)=o(-n) is not a family of c-expanders. For every $>0, if supp(C) -3n then sets of vertices of order at most ( 12 &$)(n&(nÂsupp(C)))! in X(A n , C) expand. The proof of the last result combines spectral and representation theory techniques with direct combinatorial arguments. 1997 Academic Press the following problem [Lu1, 10.3.4 10.3.5]: Can the symmetric groups (or families of groups of Lie type over a fixed finite field) be made a family of Cayley graphs which are c-expanders? See also [BHKLS]. The case of article no. TA972786 281 0097-3165Â97 25.00

📜 SIMILAR VOLUMES

Neighbourhood Graphs of Cayley Graphs fo

Neighbourhood Graphs of Cayley Graphs for Finitely-generated Groups

✍ Markus Neuhauser 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 134 KB

In this short note the neighbourhood graph of a Cayley graph is considered. It has, as nodes, a symmetric generating set of a finitely-generated group . Two nodes are connected by an edge if one is obtained from the other by multiplication on the right by one of the generators. Two necessary conditi

Random Subgraphs of Cayley Graphs overp-

Random Subgraphs of Cayley Graphs overp-Groups

✍ C.M. Reidys 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 146 KB

The subject of this paper is the size of the largest component in random subgraphs of Cayley graphs, X n , taken over a class of p-groups, G n . G n consists of p-groups, G n , with the following properties: , where K is some positive constant. We consider Cayley graphs X n = (G n , S n ), where S

On the Isomorphisms of Cayley Graphs of

On the Isomorphisms of Cayley Graphs of Abelian Groups

✍ Yan-Quan Feng; Yan-Pei Liu; Ming-Yao Xu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 190 KB

Let G be a finite group, S a subset of G=f1g; and let Cay ðG; SÞ denote the Cayley digraph of G with respect to S: If, for any subset T of G=f1g; CayðG; SÞ ffi CayðG; T Þ implies that S a ¼ T for some a 2 AutðGÞ; then S is called a CI-subset. The group G is called a CIM-group if for any minimal gene

Regularities on the Cayley Graphs of Gro

Regularities on the Cayley Graphs of Groups of Linear Growth

✍ Roberto Incitti 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 197 KB

In this paper a short proof is given of a theorem of M . Gromov in a particular case using a combinatorial argument .

Panpositionable hamiltonicity of the alt

Panpositionable hamiltonicity of the alternating group graphs

✍ Yuan-Hsiang Teng; Jimmy J.M. Tan; Lih-Hsing Hsu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 352 KB

Hamiltonian Decompositions of Cayley Gra

Hamiltonian Decompositions of Cayley Graphs on Abelian Groups of Odd Order

✍ Jiuqiang Liu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 380 KB

Alspach has conjectured that any 2k-regular connected Cayley graph cay(A, S) on a finite abelian group A can be decomposed into k hamiltonian cycles. In this paper, the conjecture is shown to be true if S=[s 1 , s 2 , ..., s k ] is a minimal generating set of an abelian group A of odd order (where a