Skip to main content

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
0 votes
0 answers
33 views

Is there some higher-dimensional polytope that represents the Rubik's Cube group?

I recently found a Pocket Cube and while trying to find instructions on how to solve it, I got sucked into the whole Rubik maths rabbit hole. I was wondering if the Rubik's group can be represented by ...
Mircode's user avatar
  • 101
0 votes
1 answer
51 views

How would a category theorist describe the Cayley graph of a group w.r.t. a subset?

Background: The question at hand is in line with previous questions of mine, such as: How would a category theorist describe Green's relations? Describing the Wreath product categorically. I ask ...
Shaun's user avatar
  • 45.5k
0 votes
0 answers
26 views

Cayley Graph of permutations

Let $[p]=\{1,..,p\}$ where $p\in \mathbb{N}$. Let $P(n,r)$ denote the set of all injective functions from $[r]$ to $[n]$ and write a typical element as $\sigma=[\sigma(1),...,\sigma(r)]$ where $1\leq\...
Eshita Basak's user avatar
1 vote
0 answers
119 views

Growh generating function for finite Heisenberg groups

Take standard 2d-Heisenberg group over finite ring Z/p. Choose standard generators $x_i, y_i$. Consider generating polynomial for growth: $ g(t) = \sum_i g_i t^i $ , where $g_i$ are the ball sizes. ...
Alexander Chervov's user avatar
2 votes
1 answer
62 views

Schutzenberger graphs of an Inverse Semigroup?

I recently came across the idea of extending the well-known Cayley graph construction for semigroups and learned that the outcome does not have all the expected properties even for the nice classes of ...
Bumblebee's user avatar
  • 18.3k
1 vote
1 answer
47 views

Spectrum of circulant block matrix of circulant blocks (Adjacency matrix of discrete torus)

I am currently investigating the spectrum of a matrix $M \in \mathbb{R}^{12 \times 12}$. The matrix has the following form, $$ M = \begin{bmatrix} 0 & 1 & 0 & 1 & 1 & 0 &...
SebastianP's user avatar
0 votes
0 answers
34 views

How Cayley diagram change without requirement that actions are determined?

The question is from the book "Visual group theory" by Nathan Carter. The book doesn't give an answer to this exercise so I post it here. It is the Exercise 2.14 at the page 24 of the pdf ...
Liker's user avatar
  • 101
3 votes
1 answer
129 views

Diameter of the Cayley graph of $\mathbb{Z}_n$

So, I have $G = \mathbb{Z}_n$ and $T_n = \{g\in\mathbb{Z}_n: \operatorname{gcd}(g,n) = 1\} = \mathbb{Z}_n^*$. I need to find the diameter of $\Gamma(G,T_n)$. What have I tried: we can obviously try to ...
verfassungsgedenktag's user avatar
3 votes
1 answer
58 views

Questions about harmonic functions on Cayley graphs

I am reading A proof of Gromov’s theorem by Terence Tao, where I encountered harmonic (and Lipschitz) functions on Cayley graphs, here is the definition: Let $G$ be an infinite group generate by a ...
Quzs's user avatar
  • 326
0 votes
0 answers
34 views

Closest Equivalent to Cayley Graphs for Partial Groupoids?

[A partial groupoid (half-magma) is a set S equipped with a (single-valued) partial binary operation, as in Bruck's Survey of Binary Systems.] This question may be nonsensical, given that the duality ...
shea's user avatar
  • 21
0 votes
0 answers
91 views

Cayley tree reachable nodes proof

Imagine being in the central node of a Cayley Tree graph like this one: Cayle Tree, K =3 and D = 5 For a number of reachable t steps (t<D) prove that the reacheable nodes from the center equal: $$ ...
Cretheus7's user avatar
2 votes
0 answers
125 views

Cayley graph of a finitely generated group $G$

Good time of day! I'm trying to show that: "The Cayley graph of a finitely generated group $G$ is quasi-isometric to a line if and only if $G$ has a cyclic subgroup of finite index". My ...
Victory's user avatar
  • 411
0 votes
1 answer
79 views

Why is the quotient of Cayley graph by its group action homeomorphic to a wedge of circles?

Let $X$ be a Cayley graph of a group $G$ generated by a set $S$. I would like to show that $X/G$ is homeomorphic to the wedge sum of $|S|$ circles. More specifically, construct a explicity ...
Horned Sphere's user avatar
3 votes
3 answers
191 views

Can two non-isomorphic groups have the same Cayley graphs?

The question I was originally thinking about was: Can $T_3$, the three-regular tree (the infinite tree with each vertex having valency 3) be the Cayley graph of some group with some generating set? ...
Aditya's user avatar
  • 930
1 vote
0 answers
28 views

Isomorphic (un)coloured Cayley (di)graphs of non-isomorphic groups

I've been recently trying to understand the precise properties of Cayley graphs in order to inform my students about some group theory. From this answer I understand that if we consider Cayley ...
Dmitry Ivanov's user avatar
0 votes
0 answers
37 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 ...
Greg's user avatar
  • 1
3 votes
0 answers
58 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 ...
Pelota's user avatar
  • 843
1 vote
1 answer
46 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 ...
Jonathon K's user avatar
0 votes
1 answer
231 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 ...
aritracb's user avatar
  • 745
2 votes
1 answer
100 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 ...
quuuuuin's user avatar
  • 637
0 votes
1 answer
113 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 ...
squareandroot's user avatar
2 votes
1 answer
60 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 ...
Tamir Dror's user avatar
1 vote
1 answer
129 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 ...
FUUNK1000's user avatar
  • 861
2 votes
0 answers
78 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 ...
unknown's user avatar
  • 1,010
1 vote
1 answer
115 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 ...
vidyarthi's user avatar
  • 7,065
0 votes
1 answer
628 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 ...
vidyarthi's user avatar
  • 7,065
8 votes
1 answer
149 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 ...
Saúl RM's user avatar
  • 3,535
7 votes
2 answers
538 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 ...
epsilon's user avatar
  • 151
1 vote
1 answer
401 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(\...
Math101's user avatar
  • 4,653
5 votes
1 answer
103 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 ...
eraoul's user avatar
  • 153
5 votes
0 answers
226 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 ...
Zelox's user avatar
  • 857
2 votes
1 answer
131 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 ...
kefirofil's user avatar
0 votes
1 answer
91 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$...
TaoFu's user avatar
  • 1
4 votes
1 answer
117 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 ...
boolean's user avatar
  • 67
3 votes
1 answer
632 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....
michiganbiker898's user avatar
0 votes
1 answer
146 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 ...
Newrion's user avatar
  • 361
4 votes
2 answers
205 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 ...
SFSH's user avatar
  • 941
2 votes
0 answers
72 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 ...
Hasini's user avatar
  • 201
0 votes
1 answer
69 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 &...
Buddhini Angelika's user avatar
1 vote
1 answer
31 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 ...
Buddhini Angelika's user avatar
1 vote
2 answers
91 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 ...
geodude's user avatar
  • 8,097
0 votes
1 answer
291 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 $\...
Daniel's user avatar
  • 87
1 vote
0 answers
53 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 ...
6-0's user avatar
  • 654
0 votes
0 answers
53 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?
soleha alhaddar's user avatar
2 votes
1 answer
193 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,...
Buddhini Angelika's user avatar
2 votes
1 answer
105 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 ...
brokoner12's user avatar
-1 votes
1 answer
63 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 ...
Buddhini Angelika's user avatar
0 votes
1 answer
229 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. ...
vidyarthi's user avatar
  • 7,065
3 votes
1 answer
100 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 ...
Harald's user avatar
  • 611
2 votes
1 answer
351 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)...
klein4's user avatar
  • 1,257

1
2 3 4 5