All Questions
Tagged with finite-groups cayley-graphs
10 questions with no upvoted or accepted answers
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/...
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
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
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
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
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