# 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
Filter by
Sorted by
Tagged with
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
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
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 ...
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
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
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
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 ...
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 ...
1 vote
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
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
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
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
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
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
193 views

1 vote
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
170 views

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
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 ...
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
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
196 views

• 35
174 views

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