Cayley graphs are graphs obtained from a group $G$ in a such way that vertices are elements of the group and edges are added using some generating set $S\subseteq G$.

learn more… | top users | synonyms

0
votes
1answer
68 views

Cayley graph of the fundamental group of the 2-torus

Does anybody knows some description or some good picture on the internet for the Cayley graph of the fundamental group of the 2-torus, when this is constructed by connected sum of two torus. I know, ...
0
votes
0answers
41 views

A disadvantage of a kin system [closed]

I read an article recently. It says that there is a group of indigenous Australians. Their kin system can be described by a Cayley diagram of the dihedral group of degree $6$. As the following figure ...
2
votes
1answer
42 views

Plot Cayley graphs for generic element groups

I'm a beginner in Abstract Algebra, currently trying to solve all exercises in "A Book of Abstract Algebra" by Pinter. I was wondering if there is a way to draw Cayley graphs for generic element ...
0
votes
0answers
38 views

Find all permutation sequences with only neighbor swaps

I am trying to essentially do what was done at this link, except for five elements instead of four. The link gives all of the possible sequences of permutations of four elements with the following 2 ...
2
votes
1answer
27 views

Cayley graph with minimal generating set?

The answer to this question could be trivial ! Definition: Let $G$ be a group and $S$ a symmetric subset of $G$ (i.e., $s \in S$ iff $s^{ −1} \in S$), the Cayley graph $Cay(G; S)$ of $G$ w.r.t. $S$ ...
0
votes
1answer
79 views

How to construct a Cayley Table? [closed]

I have a set G = {e,a,b,c,d,f,g,h,i,j,k,l,m,n,o,p} which forms a group, (G, *) which is shown in the Cayley Digraph below. How do I go about constructing a Cayley table of (G,*), assuming e is the ...
0
votes
0answers
21 views

Cayley graph for Frieze groups

I wonder how I can draw the Cayley graph for Frieze groups? For the group p11g with translations and glide reflections only (and a translation is obtained by two glide reflections), how do I show ...
0
votes
0answers
47 views

Cayley Graph of $SL_2(\mathbb{Z})$

As the title suggest, I'm interested in depicting (if possible) the Cayley graph of the special linear group $SL_2(\mathbb{Z})$. I know one has to start with a presentation of the group so $$SL_2(\...
1
vote
0answers
51 views

Semigroup of matrices and expander Cayley graphs

I am interested in proving or disproving that certain Cayley graphs are expander. Let $S$ be the multiplicative semigroup of matrices generated by $A = \left( \begin{array}{cc} a & b \\ 0 & ...
5
votes
1answer
120 views

Expository articles on Cayley Graphs?

Does anyone know of any expository articles on Cayley graphs? I have some background in both group theory and graph theory, and know a little bit of algebraic topology. In particular, I am hoping to ...
1
vote
1answer
30 views

Find the Cayley graph of the group $G = ( \mathbb{Z}/2 \mathbb{Z}) × ( \mathbb{Z}/2 \mathbb{Z})$ with generating set ${(1, 0),(0, 1)}$.

I am quite new to geometric group theory and can't really visualize the way the Cayley graph changes when you change the generating set. I found many possible graphs here but I don't really see how to ...
0
votes
1answer
29 views

Are there any examples of groups with a 4-regular cayley graph with an euler characteristic of 2?

The motivation here is that I'm looking for a group that topologically (based on its Cayley Graph) behaves like a sphere, but algebraically is similar to the direct product of two cyclic groups (which ...
1
vote
0answers
46 views

Which of these Cayley graphs are isomorphic? (Pinter, Book of Abstract Algebra, Chapter 9)

Work so far (please correct if wrong): I think none of them are isomorphic to each other except for maybe the bottom two. My real question is: What kind of group would the last one (the solid hexagon)...
3
votes
1answer
92 views

Cayley graphs of groups [closed]

(Directed & undirected) Cayley graphs of groups have been studied a lot in the literature. I would like to know the answer to the following questions. Please give your valuable suggestions. Is ...
1
vote
0answers
28 views

Adam isomorphism of circulant graphs

Let $C(n; S)$ denote a circulant graph on $n$ vertices (the vertices can be labeled $0,\ldots,n-1$), and connection set $S = \{s_1, \ldots, s_k \}$. Let $1 \leq \mu < n$ be relatively prime to $n$. ...
3
votes
0answers
69 views

What is the diameter of the Cayley graph of $S_n$ w.r.t the generator $\{(12),(23),…,(n−1n)\}$?

Given a symmetric group $S_n $ and the generator set : $S = \{(12),(23), . . . ,(n − 1 n) \}$ is there any closed form expression for the diameter of the Cayley graph generated by this set of ...
1
vote
3answers
114 views

How to find the number of spanning trees for a cube?

Can you tell me a way of finding the total number of spanning trees in a $Q_d$ undirected labelled graph for $d = 3$. I know that the answer is 384, but the way (I know there are many.) of finding ...
0
votes
0answers
41 views

What is the Schreier graph of this group/subgroup/generating set?

Let $G=\langle Pa, b\mid a^3 = \mathrm{id}, (ba)^2 = \mathrm{id}\rangle $, $H = \langle b\rangle$ , and $S = \{a, b\}$. I have been trying to figure out what elements are in this group by finding the ...
1
vote
3answers
161 views

Cayley graph is a tree iff group is free

I am looking at this proof of this claim that the cayley graph is a tree iff g is a free group with generating set S. For the direction '$\implies $' I see that they have assumed that there are two ...
0
votes
1answer
118 views

Proving the continuation of the Cayley-Hamilton theorem from Schur's triangularization theorem

The Cayley-Hamilton theorem says that every square matrix can satisfy its own characteristic equation, $p(\lambda) = 0$, or $p(\mathbf{A}) = \mathbf{0}$. The question is to show how the Cayley-...
2
votes
1answer
145 views

About Cayley graphs on finite fields.

If one is given $n$ vectors of length $n$ $\in \mathbb{F}_{p^k}^n$ for some prime number $p$ and $k \in \mathbb{Z}^+$ then how can one check if they are linearly independent? (the issue is if there ...
0
votes
1answer
150 views

Left and right multiplication for Cayley graphs

Correct me if I am wrong but I have written down the following: Let $X$ be a finite group, with subset $S$ and corresponding Cayley graph $G$. The edge set for a Cayley graph is defined such that ...
2
votes
3answers
186 views

Clear up definition of cayley graph

I have come across two definitions of Cayley graphs, both very similar but one being more general. I have been working with the more general definition which is: A Cayley graph of a group 􏰎$X$ ...
2
votes
1answer
78 views

Decomposition of a group whose Cayley graph is a tree

This is an exercise taken from Chapter 9 of a French book, Géométrie et Théorie des Groupes. It says, roughly, the following: Show that a finitely generated hyperbolic group, whose Cayley graph is a ...
1
vote
1answer
179 views

Drawing a directed graph in Maple

I have been playing around with some Maple today for a semigroup/ graph theory style project. I want to draw a left cayley graph with vertices $\{1,....,12\}$ and edges $[5, 5]$, $\{[6, 2].[7, 1], [1, ...
1
vote
1answer
53 views

Is the Cayley graph of a free group dense on the Poincare disc?

In other words, every point inside the disc corresponds to a word (possibly of infinite length) of the free group; Is that correct? With this embedding:
0
votes
1answer
43 views

Proof of a Cayley graph result.

I am searching now for the most explicative and easy understand in this level (I am a second year student) proof of the following result: A Cayley graph is connected iff S generates G where G is a ...
0
votes
1answer
40 views

What is the notion of “character” in the context of Cayley graphs?

I am looking at these notes, http://www.eecs.berkeley.edu/~luca/books/expanders.pdf On page 37, Lemma 5.16, the notion of "character" defined seems to be any map from the finite Abelian group to $\...
0
votes
0answers
22 views

Question of Cayley graphs of certain group

I want to draw the Cayley graph of $S_4$ with respect the rotations of the cube 90º with respect the y axis (is the one pointing up and I will call it $g_1$) and with respect the x axis (the one ...
2
votes
1answer
90 views

Factor Group Lemma of Cayley Graph

Factor Group Lemma: Suppose that 1.$N$ is a cyclic, normal subgroup of group $G$. 2.$(s_1,s_2,\ldots,s_m)$ is a hamiltonian cycle in $Cay(G/N;S). 3.The product $s_1s_2\cdots s_m$ generates $N$. ...
2
votes
1answer
73 views

Did I map this group right?

I am trying to get a group with 8 elements. This is a Cayley table of $\mathbb Z_2 \times \mathbb Z_4$. Is this right? $$ \begin{array}{c|cccc} & 1 & 2 & 3 & 4\\ \hline 1 & 1 &...
6
votes
1answer
123 views

on Cayley diagrams

is the picture the Cayley Graph of the group $\langle a,b,c\mid a^2, b^2,c^2\rangle$ ? What would it be for $\langle a,b,c\mid a^2b^2c^2\rangle$?
2
votes
2answers
113 views

Proof: directed cycle?

A directed cycle graph is a directed version of a cycle graph, with all the edges being oriented in the same direction. In a directed graph, a set of edges which contains at least one edge (or arc) ...
2
votes
1answer
123 views

Cayley graphs of finite 2-generator groups

Let $G=\left<a,b\right>$ be a finite 2-generator group and $\Gamma$ its Cayley graph with respect to $\{a,b\}$. Is it true that $\Gamma\setminus\{e,f\}$ is connected for two arbitrarily chosen ...
0
votes
1answer
37 views

Are These Graphs Circulant?

We will say a circulant graph is a graph whose adjacency matrix is circulant (even if the graph is disconnected). Let $R$ be a Dedekind domain, and let $I$ be an ideal of $R$ such that $R/I$ is finite ...
2
votes
0answers
65 views

s4≀s2 visually?

What does the polytope whose symmetry is (exactly, not larger isomorphisms) s4≀s2 look like? Does anyone know of a full decomposition of its construction, i.e. lattices, hasse diagrams, cayley graphs, ...
1
vote
1answer
27 views

Clarification from a proof that a certain type of graph can be endowed with a group operation

I need some help sorting out a construction of a group out of the vertices of a digraph with a certain property. I'll just throw some definitions here first... Definitions. An alphabet $A$...
3
votes
3answers
180 views

Viewing an abelian group using cayley diagram

I cannot understand this way of viewing whether a group is abelian using cayley's diagram: (from Visual group theory book) What I can't understand is that while checking being abelian we check $ab=...
1
vote
1answer
55 views

Order of an element in direct product using cayley's diagram

How can I find the order of element (1,1) of the group $C_4\times C_3$ visually in the diagram below :
1
vote
1answer
53 views

Elements in the same coset and the Cayley Diagram

A question from Visual group theory, by Nathan Carter. In a Cayley diagram, if $aH$ is a coset of a subgroup $H$ of a group $G$ and $b$ belongs to $aH$, why is it that every node that can be reached ...
3
votes
0answers
46 views

Diameter of undirected graph

Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we remove the orientation of the arcs, thus getting an undirected graph $G'$ with diameter $D'$. Obviously, $D' \leq D$....
0
votes
0answers
63 views

How many trees, not necessarily spanning, are there with exactly m edges and n vertices?

I've been struggling with this combinatorical question and got very confused: Given $n$ vertices: $\{v_1,v_2,\ldots,v_n\}$, in how many ways can a tree be assembled upon them, not necessarily ...
2
votes
1answer
90 views

Cayley graph of an amalgam

I was wondering what the Cayley graph of an amalgam $A*B$ (over $\{ 1\}$ ) is? $A, B$ are finitely generated. Can't work it out.
0
votes
1answer
125 views

Ramanujan (LPS) graph construction

In the original LPS article they mention two constructions for Ramanujan graphs, one with order $q^3$ nodes and the other in order $q$. My question is regarding the second construction (which is ...
8
votes
1answer
265 views

Applications of Cayley Graphs in Physics

I have been recently reading about Cayley graphs and character theory. It is evident that Cayley graphs are very useful tool in theoretical computer science. In physics, Cayley graphs seem do appear ...
2
votes
1answer
78 views

Quasi-isometry of Schreier coset graphs

Let $G$ be a finitely generated group and $H$ a subgroup. For any choice of a generating set $X$ we can form the Schreier coset graph. Is this graph independent of the generating set up to quasi-...
1
vote
0answers
48 views

A Question about Cayley Graph [duplicate]

Petersen graph is this graph: Petersen graph can not be a Cayley graph. How to prove that? Can someone give a general method to judge a graph is or not a Cayley graph?
6
votes
1answer
272 views

What does the Cayley graph of the Grigorchuk group 'look like'?

I've recently renewed my interest in tilings, and as a result have taken some splashes into Word Processing in Groups (in search of good information on the automatic groups related to hyperbolic ...
2
votes
1answer
343 views

Software for generating Cayley graphs of $\mathbb Z_n$?

Does it exist any program (for linux) which can generate a nice Cayley graph of any $\mathbb Z_n$? (If it's possible to create such a graph at all, that is.) (where perhaps $n ≤ 100$ or something ...
1
vote
4answers
272 views

Without using Cayley’s theorem, prove that there are at most $n^{2n−2}$ labelled trees with n vertices.

I am studying for a test I have and I found a past problem which I have no idea how to go about doing.. My thoughts are. I know not to use Cayley's theorem but it says that there are $n^{n-2}$ ...