Questions tagged [cayley-graphs]
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$.
189
questions
0
votes
0
answers
34
views
Truncation of a Cayley graph
How do you show that the Cayley graph Cay ($A_4$, {(0,1,2), (0,2,1), (0, 1), (2, 3)}) is the truncation of $K_4$? What's its automorphism group? Remark: $A_4$ is the alternating group and $K_4$ is the ...
- 1
3
votes
0
answers
40
views
Is there always a nonbipartite Cayley graph?
The question is exactly as in the title. To be more precise, let $G$ be a fin. gen. group and let $C(G,S)$ be its Cayley graph (where $S$ is a set of generators of $G$ such that $S^{-1}=S$). Obviously ...
- 280
1
vote
1
answer
22
views
Interpretation of group elements in Cayley graph vs matrix representation
Recently when learning group theory, I came across Cayley graphs and upon looking at how can be labelled, I was confused.
Take the $D_4$ dihedral group for example. From wikipedia there is a Cayley ...
- 13
0
votes
1
answer
80
views
Is the universal cover of figure-8 contractible?
The universal cover of the figure-8 is the Cayley graph of the free group on $2$ generators with generating set $\{a,b\}$. So it is a tree. I know that finite trees are contractible. But this Cayley ...
- 769
0
votes
0
answers
76
views
Find the covering space of $S^1\vee S^1$ corresponding to the subgroup $\langle a,(ab)^n\rangle$ of $\pi_1(S^1\vee S^1)$
I am trying to solve the following exercise:
Let $a$ and $b$ be the generators of the fundamental group:
$$\pi_1(S^1\vee S^1)\cong \langle a,b\rangle.$$
Let $H$ be the subgroup generated by $a,(ab)^n$...
- 1,059
2
votes
1
answer
61
views
Cayley complex of $\langle a|a^2\rangle$ is a covering of $\mathbb{R}P^2$
In Hatcher Example 1.47, we constructed the $2$-fold cover of $\mathbb{R}P^2$ by finding the Cayley complex of $G=\langle a|a^2\rangle$. I understand the construction and how the $2$-cells are ...
- 477
0
votes
1
answer
73
views
Why is the random walk on the modular group transient?
I have been reading about random walks on Cayley graphs of groups lately and stumbled across the walk on the modular group $\mathbb{Z}/(2\mathbb{Z}) * \mathbb{Z}/(3\mathbb{Z})$, where $*$ denotes the ...
2
votes
1
answer
56
views
Sum on product of two charcteres, which runs on symmetric generating set
Let $G$ be a finite (not necessarily abelian) group and let $S$ be a symmetric generating set of $G$, i.e. if $s\in S$ then $s^{-1} \in S$.
Let $\chi$ be an irreducible character of $G$. I have ...
- 21
1
vote
1
answer
76
views
Find the Cayley Graph of $\langle a,b\mid a^2,b^2,(ab)^2\rangle$
I am trying to find the Cayley Graph the group $$G=\langle a,b\mid a^2,b^2,(ab)^2\rangle.$$
It is easy to prove that $G$ is isomorphic to the dihedral group $D_4$, and $G$ must have $8$ elements.
I am ...
- 809
2
votes
0
answers
72
views
is there an explicit construction of Ramanujan graphs (preferably in GAP)?
This book gives explicit constructions of Ramanujan expander graphs $X^{p,q}$ in terms of Cayley graphs of subsets in $PSL(2,q)$ or $PGL(2,q)$. It seems there's enough detail to write a program in GAP ...
- 894
1
vote
1
answer
82
views
Checking for indepenedent sets in a bipartite graph with equal number of odd and even elements in SageMath
By using the IndependentSets module in SageMath, we can list all the independent sets of a graph. Suppose I have a bipartite graph on the Symmetric Group with partite sets consisting of even and odd ...
- 6,718
0
votes
1
answer
309
views
Constructing Cayley Graphs in SageMath
I am having confusions in constructing a Cayley Graph in Sage Math. Say, I want to construct the Cayley graph on the Symmetric Group $S_4$ with respect to the generating set consisting of all ...
- 6,718
8
votes
1
answer
134
views
Are jumps in the growth function of an infinite group increasing?
Let $G$ be a group with a $S$ a finite subset of $G$ generating it, with $\{e\}\in S$ and $S=S^{-1}$, and let $\gamma_G^S$ be the growth function of $G$ respect to $S$, that is, $\gamma_G^S(l)$ is the ...
- 3,099
5
votes
2
answers
222
views
The number of closed paths in the square lattice $\mathbb{Z}^2$ with length $n$ and starting and ending points at $(0,0)$.
I'm thinking about this problem right now.
Problem:Consider a lattice point consisting of $\mathbb{Z}^2$ points.
If $n$ is even, i.e., $n=2p$, then
Show that the number of closed paths in the square ...
- 131
1
vote
1
answer
193
views
Quasi-isometry of finitely generated group
Let $\Gamma$ be a finitely generated group, with two generating sets $S_1,S_2$. Deduce, from the Milnor - Svarc lemma, that $Cay(\Gamma, S_1)$ and $Cay(\Gamma,S_2)$ are quasi isometric, where $Cay(\...
- 3,663
5
votes
1
answer
69
views
Order 12 group with 3 generators, can I reduce to 2 generators?
I'm just getting back into group theory after studying it quite a few years ago. I ran into a seemingly-simple question as I was getting started, looking for advice.
I was looking at the dihedral ...
- 153
5
votes
0
answers
142
views
What is the Cayley graph for alternating group A6?
According to ATLAS of Group Representations, the alternating group $A_6$ is a group of order 360 which has presentation
$$
\langle a,b \mid a^2 = b^4 = (ab)^5 = (ab^2)^5 = 1 \rangle.
$$
If we draw its ...
- 777
2
votes
1
answer
102
views
Do there exists conditions we can put on two groups which have the same growth rate, so that their Cayley graphs are isomorphic?
Given a finitely generated group $G$ with a generating set $S$, we can define the growth rate function of a group, denote it $\#_{G,S}(n)$. It is clear that two groups having the same growth rate ...
- 35
0
votes
1
answer
51
views
Detail in construction on Ramanujan graph by LPS
Consider this paper written by Lubotzky, Phillips and Sarnak (1986) on expander graphs.
Below definition 2.2, they let $p,q$ be primes both congruent to $1\mod{4}$. Then they claim that there are $p+1$...
- 1
4
votes
1
answer
106
views
2-generated finite non-Abelian simple groups and the existence of Hamiltonian cycles in their Cayley graph
Given that $G = \langle a, b\rangle$ and that $a$ is an involution, when is it the case that there exists $c, d$ such that $G =
\langle c, d\rangle$ and $cd$ is an involution?
At present, I am ...
- 67
2
votes
1
answer
305
views
Normal covering spaces of the wedge sum of $n$ circles
Exercise 1.31 in Hatcher's Algebraic Topology states the following:
Show that the normal covering spaces of $S^1 \vee S^1$ are precisely the graphs that are Cayley graphs of groups with two generators....
- 1,399
0
votes
1
answer
92
views
Why Frucht's Theorem is only true for Finite Groups?
The statement of the Frucht's Theorem as follows:
"Every Finite Group is Automorphism Group of some graph."
The proof involves a result that the group of color preserving Automorphisms of a ...
- 317
4
votes
2
answers
158
views
Automorphisms of Cayley graphs of $\mathbb{Z}$
My goal is to show that there are no finite generating sets $A$ and $B$ such that $\mathrm{Cay}(\mathbb{Z},A)$ is isomorphic to $\mathrm{Cay}(\mathbb{Z}\times \mathbb{Z}_2, B)$. My idea for this is to ...
- 735
2
votes
0
answers
45
views
The Hamiltonian cycle in a Cayley graph whose corresponding group has a finite cyclic normal subgroup [closed]
Let $S$ generate a finite group $G$ and $s \in S$ such that $\langle s\rangle \trianglelefteq G$, ${\rm Cay}(G/\langle s\rangle,S)$ has a Hamiltonian cycle.
Let $(s_1,s_2, \cdots, s_n)$ be the ...
- 89
0
votes
1
answer
67
views
Using PlotGraph command from JupyterViz in MyBinder [closed]
I am executing a program "Newprogram.gap" in GAP file in My Binder. There, I have an output which is an adjacency matrix, $A$ corresponding to a Cayley graph.
1). I need to add the command &...
1
vote
1
answer
28
views
Sequence of elements representing a Hamiltonian cycle and the generating element of a subgroup
Let $S$ be a subset of a finite group $G$. The Cayley graph $Cay(G,S)$ can be defined as the graph whose vertices are the elements of $G$, with an edge joining $g$ and $gs$, for every $g \in G$ and $s ...
1
vote
2
answers
78
views
Cayley graph with opposite action: is the group abelian?
Let $G$ be a group, let $S$ be a set of generators and let $\Gamma=\Gamma(G,S)$ be the Cayley graph, where there is an edge between $g$ and $h$ if and only if $h=gs$ for some $s\in S$.
We know that ...
- 7,567
0
votes
1
answer
170
views
Cayley graph of an infinite group using GAP
I have a finitely presented group which is infinite, and I wish to create a visual representation of its Cayley graph using GAP.
If possible I would like to do this using YAGS package.
My group is $\...
- 55
1
vote
0
answers
49
views
Cayley Graphs 1-factorization 4-cycles
Let $X$ be a connected graph on $2^n$ vertices for $n ≥ 1$.
Prove that $X$ is a Cayley graph of $\mathit{Z}\,_n^2$
if and only if X has a $1$-factorization such that the union of any two
$1$-factors ...
- 562
0
votes
0
answers
51
views
visualization of Cayley graph in GAP [duplicate]
I want to draw a Cayley graph of a group using GAP after I get a list. Is there a way to visualize that Cayley graph ?
Or is there any other software to do it?
2
votes
1
answer
154
views
Cayley graphs obtained for different generating elements with the same orders in a finite group
When we consider the finite group $\mathbb{Z}_p \times \mathbb{Z}_p$, where $p$ is a prime, $p>2$, the set with the pair of elements $\{(0,1), (1,0)\}$ can generate the group. Moreover, a set $\{(1,...
2
votes
1
answer
77
views
rate of escape free group with 2 generators
I want to find rate of escape (drift) on free group (with d generators).
From here (page 2): https://arxiv.org/pdf/math/0506129.pdf I know the answer = 1
But I can't fully figure out why
I know there ...
- 133
-1
votes
1
answer
38
views
Will a path in Cayley graphs end at unique vertices when started at distinct vertices and traversed along same edges
Let $G$ be a finite group and $S$ be a subset of $G$. Let the Cayley graph of $G$ with respect to $S$ be defined as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed.
"The Cayley ...
0
votes
1
answer
142
views
Cayley graphs of product of groups
From this question, we have that the Cayley graph of direct product of two groups is a cartesian product of some cayley graphs on the factor groups. But, I do not see this translation easily.
...
- 6,718
3
votes
1
answer
79
views
Does the group growth rate limit the number of edges going out of a vertex in its Cayley graph?
The growth rate of a group $B_n(G, T)$ is based on the number of vertices that can be reached from a given one by $n$ steps along an edge in the Cayley graph of the group, where $G$ is the group (or ...
- 601
2
votes
1
answer
196
views
Automorphism group of a Cayley graph
Let $G$ be a group. Let $\Gamma = \Gamma(G,X)$ be the Cayley graph of $G$ defined with respect to a generating set $X$. I want to show that $G\cong \text{Aut}(\Gamma)$. Note that by $\text{Aut}(\Gamma)...
- 1,227
0
votes
0
answers
214
views
What are the advantages of Hamiltonian paths/cycles in Cayley graphs when considering their applications
If a function (like a hash function) maps a vertex of a connected Cayley graph to another vertex which will be the ending point of a Hamiltonian path, is there a particular advantage over a function ...
0
votes
0
answers
28
views
Determining the automorphism of a vertex transitive/Cayley graph which will map a vertex to another given vertex under some conditions
A Cayley graph is a vertex-transitive graph, meaning that given any two vertices $v_1, v_2$ in the vertex set of the graph $X$ ($V(X)$), there exists an automorphism $\phi:V(X) \rightarrow V(X)$, such ...
3
votes
0
answers
94
views
Geometric Interpretations of the Automorphism Group of a Group?
I saw this question recently, which asks for a "geometric" example where a certain automorphism doesn't exist. Since some counterexamples are well known, I thought it should be a simple task ...
- 31.5k
1
vote
0
answers
39
views
Number of each generating elements of the Cayley graph appearing in a Hamiltonian cycle
Let $G$ be a finite group and $S$ be a subset of $G$. Let the Cayley graph of $G$ with respect to $S$ be $Cay(G,S)$, provided that $1 {\not\in} S$ and $S$ is inverse closed.
Consider the Cayley graph ...
0
votes
0
answers
34
views
Code for commands in GAP [duplicate]
Is there a way we can check and refer the source codes which execute the commands like "CayleyGraph()", "SemidirectProduct()" which are used for computations in GAP software?
0
votes
1
answer
157
views
Every Cayley graph is vertex transitive
I cannot come up with a proof of the following statement (which is true according to wikipedia):
Every Cayley graph is vertex-transitive.
Can anyone enlighten me?
Thanks!
- 23
0
votes
0
answers
110
views
Show that a Cayley digraph is strongly connected if and only if it is weakly connected.
Show that a Cayley digraph is strongly connected if and only if it is weakly connected.
(A digraph is strongly connected if there is a directed path between any two vertices. It is weakly
connected if ...
- 1
4
votes
1
answer
268
views
Application of Cayley’s theorem in Sylow’s theorem
I’ve just started reading Sylow’s theorems. I have heard that Cayley’s theorems are applied in Sylow’s theorem. Can someone exactly point out where in the three Sylow’s theorem is Cayley’s theorem ...
- 127
0
votes
1
answer
97
views
Number of undirected trees with unlabled vertices and labeled edges
I would appreciate some help coming up with an expression for the number of spanning trees of an undirected graph with m labeled edges but m+1 unlabled vertices.
The answer is supposed to be ${m+1}^{...
- 35
2
votes
0
answers
174
views
general properties for Cayley graphs of hyperbolic triangle groups
Is it possible to derive some general properties for Cayley graphs of hyperbolic triangle groups, presented as
$$
\langle a,b,c | a^2=b^2=c^2=(ab)^p=(bc)^q=(ca)^r=1\rangle \text{, with } \frac1p+\...
- 18k
1
vote
2
answers
123
views
Groups with two ends: showing that either $E\Delta gE$ is finite or $(E\Delta gE)^\complement$ is finite.
Let $G$ be a finitely generated group with $e(G) = 2$, and let
$\Gamma$ be a Cayley graph of $G$. There is then a finite subgraph $C$
such that $\Gamma \setminus C$ has exactly two connected, ...
- 2,273
3
votes
0
answers
125
views
Geometric Group Theory, Meier lemma 11.30 about a two-ended groups $G$
This is probably a basic algebraic (or even set-theoretic) matter. I am reading "Groups, Graphs and Trees" by J. Meier.
It's about Lemma 11.30 which is left as an exercise to the reader. ...
- 2,273
2
votes
1
answer
203
views
Seeking a combinatorial proof of $2n^{n-3} = \sum_{m=1}^{n-1}\binom{n-2}{m-1}m^{m-2}(n-m)^{n-m-2}$
I need to prove the following using Combinatorial proof: (Not using math laws But finding two similar Combinatorial problems)
$$2n^{n-3} = \sum_{m=1}^{n-1}\binom{n-2}{m-1}m^{m-2}(n-m)^{n-m-2}$$
(...
- 401
0
votes
2
answers
172
views
Cayley Graph and Cayley Digraph
I am trying to understand the definition of a Cayley graph of a group $G$:
Is Cayley graph and Cayley Digraph the same thing?
If Cayley graph and digraph have the same meaning, then can we define an ...
- 191