All Questions
Tagged with cayley-graphs gr.group-theory
26
questions
76
votes
6
answers
9k
views
Which graphs are Cayley graphs?
Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another.
My main ...
- 220k
26
votes
4
answers
2k
views
What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?
It's known that every position of Rubik's cube can be solved in 20 moves or less. That page includes a nice table of the number of positions of Rubik's cube which can be solved in k moves, for $k = 0,...
- 13.7k
19
votes
3
answers
2k
views
Infinitely many finitely generated groups having the same Cayley graph
Is there an unlabeled locally-finite graph which is a Cayley graph of an infinitely many non-isomorphic groups with respect to suitably chosen generating sets?
- 1,271
18
votes
7
answers
3k
views
Spectral properties of Cayley graphs
Let $G$ be a finite group. Do eigenvalues of its Cayley graph say anything about the algebraic properties of $G$? The spectrum of Cayley graph may depend on the presentation, so it's not a good ...
- 3,271
12
votes
2
answers
713
views
Is the Petersen graph a "Cayley graph" of some more general group-like structure?
The Petersen graph is the smallest vertex-transitive graph which is not a Cayley graph. Is it the "Cayley graph" of some slightly more general group-like structure?
- 1,803
11
votes
4
answers
1k
views
Is there a Cayley graph of a non-abelian finite group that is not isomorphic to any Cayley graph of any abelian group?
It's the first question I post here :) I'm sorry if the question is too specific or if it's somehow repeating others.
In other words, my question is the following. Consider a Cayley graph $\Gamma$ of ...
- 111
6
votes
1
answer
221
views
Vanishing of certain coefficients coming from Coxeter groups
Let $\left(W\text{, }S\right)$ be a Coxeter system. For every $w\in W$ let us write $\left|w\right|$ for the length of $w$. Set $\lambda\left(e\right)=1$ where $e\in W$ denotes the neutral element of ...
- 741
6
votes
1
answer
137
views
Does the visual boundary of any one-ended Cayley graph contain at least three points?
Let $\Gamma$ be a Cayley graph of a finitely generated group. We can define the visual boundary of $\Gamma$ with respect to some base vertex $b$, denoted $\partial \Gamma$, as the set of geodesic rays ...
- 537
6
votes
1
answer
244
views
Is the function $k(g,h) = \frac{1}{1+\lvert gh^{-1}\rvert}$ positive definite?
Let $G$ be a finite group, $S \subset G$ a generating set, closed under taking inverses, and $\lvert\cdot\rvert$ the word length with respect to this set $S$.
Question. Is the function $k(g,h) = \...
- 2,126
5
votes
1
answer
312
views
$C_4\times C_2 : C_2$: what does this mean?
I am reading this paper where the object $C_4\times C_2 : C_2$ is used as a group structure. I know that $C_n$ is a cyclic group but don't know what kind of operation between groups is identified by ...
- 219
5
votes
2
answers
751
views
A generously vertex transitive graph which is not Cayley?
A graph is vertex transitive if $x \mapsto y$ by an automorphism.
A graph is generously vertex transitive if $x \mapsto y \mapsto x$ by an automorphism.
Simple facts:
GVT $\rightarrow$ unimodular. ...
- 153
5
votes
1
answer
374
views
Cayley graph properties
Consider an infinite graph that satisfies the following property: if any finite set of vertices is removed (and all the adjacent edges), then the resulting graph has only one infinite connected ...
5
votes
0
answers
189
views
Groups of non-orientable genus 1 and 2
The non-orientable genus (aka crosscap-number) $\overline{\gamma}(G)$ of a finite group $G$ is the minimum non-orientable genus among all its connected Cayley graphs (and $0$ if $G$ has a planar ...
- 150
5
votes
0
answers
155
views
When is a Schreier coset graph vertex transitive
When is a Schreier Coset graph on a group $G$ with subgroup $H$ and symmetric generating set $S$(without identity) vertex transitive?
It is well known that when $H$ is normal, the Schreier coset graph ...
- 1,841
5
votes
0
answers
277
views
Complexity of property of being vertex-transitive resp. of being a Cayley graph
Suppose I gave you a finite graph, and asked you whether it was vertex-transitive. How hard is that algorithmically?
The second question is: suppose I gave you a vertex transitive finite graph, and ...
- 95.3k
4
votes
1
answer
249
views
Diameter of Cayley graphs of finite simple groups
Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...
- 225
4
votes
1
answer
144
views
Diameter for permutations of bounded support
Let $S\subset \textrm{Sym}(n)$ be a set of permutations each of which is of bounded support, that is, each $\sigma\in S$ moves $O(1)$ elements of $\{1,2,\dotsc,n\}$. Let $\Gamma$ be the graph whose ...
- 19.1k
3
votes
1
answer
129
views
Bandwidth of finite groups
For a generating set $S$ of a group $G$ denote by $\mathrm{Cay}(G,S)$ the corresponding Cayley graph.
For a finite graph $A$ denote by $\beta(A)$ its bandwidth.
Question: Has the "group bandwidth&...
- 31
3
votes
0
answers
357
views
What about a Cayley n-complex for n>2?
Let $G$ be a finitely presented group. The Cayley graph of the finite generating set is a $1$-complex where the $0$-cells are the elements of $G$ and the $1$-cells are given by the generators (...
- 25.5k
3
votes
0
answers
211
views
Growth functions of finite group - computation, typical behaviour, surveys?
Looking on the growth function for Rubik's group and symmetric group, one sees rather different behaviour:
Rubik's growth in LOG scale (see MO322877):
S_n n=9 growth and nice fit by normal ...
- 22.9k
3
votes
0
answers
289
views
Induced graphs of Cayley graph
I have a Cayley graph $\mathrm{Cay}(G,S)$, its group presentation $G=\langle S | R \rangle$, and it becomes a metric graph by assigning a length equal to $1$ to each edge. I also have an induced ...
- 31
2
votes
2
answers
235
views
Distance regular Cayley graphs on $Z_2^n$?
Let $Z_2^n$ be group $Z_2 \times Z_2 \times \cdots \times Z_2$ with operation Exclusive-or. I'd like to know if the $Cay(Z_2^n,S)$ for $S \subset Z_2^n \setminus \{0\}$ is distance regular graph or ...
- 29
1
vote
0
answers
83
views
Example of family of Cayley graphs with Ramanujan behaviour on finite $p$-groups
This is a very general question: are there known examples of Ramanujan behaviour of Cayley graphs obtained from family of finite p-groups?
${\mathrm{\bf Adjacency~matrix:}}$ Given a graph ${\mathcal{G}...
- 405
0
votes
2
answers
134
views
coloring infinite vertex transitive graph without large cliques
Let $G$ be an infinite vertex-transitive graph (this means that for every $u,w \in V(G)$ there exists an automorphism $\tau$ of $G$ such that $\tau(u) = v$).
We assume that $G$ is undirected, and does ...
- 11.2k
0
votes
0
answers
74
views
Distances on spheres in Cayley graphs of non-amenable groups
Let $G$ be a non-amenable group (or perhaps more generally, a group with exponential growth). For any $\epsilon>0$, define the shell of radius r, $S_\epsilon(r)$, as the set of points that lie at a ...
- 21
-1
votes
1
answer
195
views
Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques
Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
- 1,841