All Questions
Tagged with finite-groups cayley-graphs
20 questions
1
vote
1
answer
80
views
What are the efficient algorithms to compute Hamiltonian paths on Cayley graphs of finite groups ? Can GAP do it?
The famous Lovasz conjecture predicts existence of the Hamiltonian path on Cayley graphs. In general finding such a path is NP-complete problem, but there are many heuristic algorithms.
Question 1: ...
- 24.9k
2
votes
0
answers
153
views
How good is approximation of distance function on the Cayley graph by "Fourier" basis coming from the irreducible representations?
Consider finite group $G$ , symmetric set of its elements $S$, construct a Cayley graph.
Consider $d(g)$ - word metric or distance on the Cayley graph from identity to $g$.
As any function on a group ...
- 24.9k
2
votes
0
answers
167
views
How to choose N policemen positions to catch a drunk driver in the most effective way (on a Cayley graph of a finite group)?
Consider a Cayley graph of some big finite group. Consider random walk on such a graph - think of it as drunk driver. Fix some number $N$ which is much smaller than group size.
Question 1: How to ...
- 24.9k
12
votes
1
answer
1k
views
Necessary and sufficient conditions for the Cayley graph to be bipartite
Let $G$ be a finite group with identity $1$. If $S$ be an inverse closed generated subset of $G$, then $S$ is called a Cayley subset of $G$.The Cayley graph $\Gamma=\operatorname{Cay}(G, S)$ is a ...
- 173
3
votes
0
answers
125
views
Short path problem on Cayley graphs as language translation task (from "Permutlandski" to "Cayleylandski"(s) :). Reference/suggestion request
Context: Algorithms to find short paths on Cayley graphs of (finite) groups are of some interest - see below.
There can be several approaches to that task. One of ideas coming to my mind - in some ...
- 24.9k
3
votes
0
answers
109
views
What Cayley graphs arise as nodes+edges from "nice" polytopes and when are these polytopes convex?
The Permutohedron is a remarkable convex polytope in $R^n$, such that its nodes are indexed by permutations and edges correspond to the Cayley graph of $S_n$ with respect to the standard generators, i....
- 24.9k
7
votes
0
answers
233
views
Growth of spheres in FINITE nilpotent groups - Gaussian approximation (central limit theorem)?
Standard setup. Consider a group and choose generators. Word-metric (or in the other words - distance on the Cayley graph of the group+generators) - converts a group into a metric space, which is ...
- 24.9k
4
votes
0
answers
227
views
Polynomials of growth for finite Heisenberg groups
Take a standard finite Heisenberg group with two standard generators and let's consider its growth polynomial - the polynomial which coefficients are equal to the sphere sizes.
For example for $H_3(Z/...
4
votes
1
answer
251
views
Diameter of the "Masterball-puzzle" permutation groups by a kind of Cartier-Foata enumeration?
There is an wonderful blog post by Jordan S. Ellenberg SHOULD YOU BE SURPRISED BY THE DIAMETER OF THE NXNXN RUBIK’S GROUP?. Which explains how one can come to $N^2log(N)$ estimate of the diameter of ...
- 24.9k
2
votes
0
answers
71
views
Distance distribution for Cayley graphs of the fintie Heisenberg groups H3(Z/nZ) approaches Gaussian for large "n"?
I wonder several questions about Cayley graphs of finite Heisenberg groups H3(Z/nZ).
Question 1: do we know the diameter dependence on "n", at least for the standard choice of generators ? ...
- 24.9k
6
votes
1
answer
245
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) = \...
- 3,064
1
vote
0
answers
90
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
-1
votes
1
answer
215
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$. ...
- 2,089
4
votes
2
answers
485
views
Transposition Cayley graphs are planar
Consider the Cayley graph $G$ with vertex set the elements of the symmetric group $S_n$ and generating set the set of minimal transposition generators of the group $S_n$, that is the set $S=\{(12),(13)...
- 2,089
5
votes
1
answer
385
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
1
answer
275
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$ ...
- 237
4
votes
1
answer
152
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 ...
- 20.2k
3
votes
0
answers
303
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 ...
- 24.9k
20
votes
4
answers
2k
views
Cayley graph of $A_5$ with generators $(1,2,3,4,5),(1,4,3,2,5)$
The Cayley graph of $A_5$ with two generators of order 5 seems rather complicated. What is its graph genus (orientable or non-orientable)?
The best I could get by trial and error is an embedding ...
- 24.8k
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