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$.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
26 views

Converse for Cayley digraphs

"It can be shown that, conversely,..... for some group."- can you clearly show or provide good references for proof of the converse? Also, I would appreciate more of an explanation for ...
user avatar
  • 218
1 vote
1 answer
59 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 ...
user avatar
  • 6,547
0 votes
1 answer
51 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 ...
user avatar
  • 6,547
8 votes
1 answer
121 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 ...
user avatar
  • 2,196
5 votes
2 answers
71 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 ...
user avatar
  • 111
1 vote
1 answer
64 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(\...
user avatar
  • 2,328
5 votes
1 answer
59 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 ...
user avatar
  • 153
5 votes
0 answers
86 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 ...
user avatar
  • 717
2 votes
1 answer
76 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 ...
user avatar
0 votes
1 answer
30 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$...
user avatar
  • 1
4 votes
1 answer
88 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 ...
user avatar
  • 67
2 votes
1 answer
163 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....
user avatar
0 votes
1 answer
63 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 ...
user avatar
  • 155
4 votes
2 answers
107 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 ...
user avatar
  • 715
2 votes
0 answers
40 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 ...
user avatar
  • 89
0 votes
1 answer
63 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 &...
user avatar
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 ...
user avatar
1 vote
2 answers
59 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 ...
user avatar
  • 7,377
0 votes
1 answer
114 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 $\...
user avatar
  • 55
1 vote
0 answers
40 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 ...
user avatar
  • 468
0 votes
0 answers
49 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?
user avatar
2 votes
1 answer
148 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,...
user avatar
2 votes
1 answer
58 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 ...
user avatar
-1 votes
1 answer
25 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 ...
user avatar
2 votes
0 answers
32 views

Different metrics on Cayley graphs

On every (say undirected, for simplicity) Cayley graph $\Gamma(G, S)$ we have the word ("geodesic") metric, that is $d_w(g, h)$ is the minimum of lenghts of paths joining $g$ to $h$. This ...
user avatar
0 votes
1 answer
98 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. ...
user avatar
  • 6,547
3 votes
1 answer
63 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 ...
user avatar
  • 549
2 votes
1 answer
113 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)...
user avatar
  • 1,137
0 votes
0 answers
142 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 ...
user avatar
0 votes
0 answers
25 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 ...
user avatar
3 votes
0 answers
65 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 ...
user avatar
1 vote
0 answers
33 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 ...
user avatar
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?
user avatar
0 votes
1 answer
54 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!
user avatar
0 votes
0 answers
85 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 ...
user avatar
4 votes
1 answer
237 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 ...
user avatar
  • 137
0 votes
1 answer
86 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}^{...
user avatar
  • 35
2 votes
0 answers
147 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+\...
user avatar
  • 17.8k
1 vote
2 answers
91 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, ...
user avatar
  • 2,126
3 votes
0 answers
105 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. ...
user avatar
  • 2,126
2 votes
1 answer
167 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}$$ (...
user avatar
  • 379
0 votes
2 answers
116 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 ...
user avatar
  • 173
2 votes
1 answer
35 views

Can a Hamiltonian cycle of an undirected Cayley graph contain inverses of the generating elements?

Let $G$ be a finite group and $S$ be a subset of $G$. Let us define the Cayley graph of $G$ with respect to $S$ as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed. Definition: The ...
user avatar
3 votes
0 answers
35 views

Does a longest cycle contain maximum number of each generating element

Let $G$ be a finite group and $S$ be a subset of $G$. We define the Cayley graph of $G$ with respect to $S$ as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed. Definition: The Cayley ...
user avatar
2 votes
0 answers
42 views

What can be said about the stationary distribution of the Latch Cube?

Katsuhiko Okamoto's Latch Cube is similar to the standard $3\times 3$ Rubik's cube with the added features that on one of the faces of each of the edge cubies, there is an arrow identifying a ...
user avatar
  • 253
1 vote
0 answers
34 views

The longest cycle and relation between the generating elements of a Cayley graph

Let $G$ be a finite group and $S$ be a subset of $G$. We define the Cayley graph of $G$ with respect to $S$ as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed. Definition: The Cayley ...
user avatar
2 votes
1 answer
86 views

Difference between the Cayley Graph and the Cayley Sum Graph.

Could someone help me visualize the difference between the following graphs? Take $G$ to be a group generated by the symmetric generating set $S$. Take $g, h$ to be elements of $G$. We define the ...
user avatar
2 votes
0 answers
35 views

Representing relationships shown by cycles in Cayley graphs using congruence relations and solving them

Consider a finite group $G=\mathbb{Z}_3 \times \mathbb{Z}_5$. Let the undirected Cayley graph of the group be gererated by $\{s,s^{-1}, t, t^{-1}\}$, where $|s|=3, |t|=5$. Then different cycles in the ...
user avatar
1 vote
0 answers
15 views

Finding the relationship between generating elements represented by a Hamiltonian cycle of a Cayley graph

Consider an undirected Cayley graph of a finite group $\mathbb{Z}_p \times \mathbb{Z}_q$, where $p$ and $q$ are distinct primes. Let the generating set for the Cayley graph be $S=\{g_p, g_q\}$, where $...
user avatar
0 votes
0 answers
29 views

Relationship between the generating elements given by the Hamiltonian cycle of a Cayley graph

Consider the Cayley graph of $\mathbb{Z}_3 \times \mathbb{Z}_5$ generated by the generating set $S=\{g_1=(1,0), g_2=(0,1)\}$. Then $|g_1|=3, |g_2|=5$. Consider a Hamiltonian cycle, $ABCDEFGHIKJLMNO$. ...
user avatar