Questions tagged [cayley-graphs]
Questions concerning Cayley graphs, regardless of whether the group be finite, infinite, abelian, non-abelian. Strong connections to geometric group theory.
71
questions
0
votes
1
answer
112
views
Chain of automorphism groups
Let $\mathrm{Aut}(\Gamma)$ be the automorphism group of a graph $\Gamma$. Also suppose that $\mathrm{Cay}(G,S)$ is the Cayley graph of a group $G$ with respect to the generating set $S$. Consider the ...
2
votes
0
answers
143
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 ...
2
votes
0
answers
165
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 ...
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 ...
3
votes
0
answers
118
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 ...
5
votes
0
answers
120
views
Does the permutohedron satisfy any minimal distortion property for graph metric vs Euclidean distance?
We can look on the permutohedron as a kind of "embedding" of the Cayley graph of $S_n$ to the Euclidean space. (That Cayley graph is constructed by the standard generators, i.e. ...
3
votes
0
answers
97
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....
7
votes
0
answers
229
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 ...
4
votes
0
answers
208
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/...
1
vote
0
answers
67
views
Commutative Schur ring over non-abelian group
Is there a commutative (or even symmetric) Schur ring $S\subset\mathbb{C}G$ over a non-abelian group $G$, which is not isomorphic (preserving both the products) to a Schur ring $S'\subset\mathbb{C}G'$ ...
22
votes
4
answers
2k
views
Open problems which might benefit from computational experiments
Question: I wonder what are the open problems , where computational experiments might me helpful? (Setting some bounds, excluding some cases, shaping some expectations ).
Grant program: The context of ...
4
votes
1
answer
240
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 ...
2
votes
0
answers
65
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 ? ...
0
votes
0
answers
88
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 ...
3
votes
1
answer
100
views
Edge coloring of a graph on alternating groups
Let $G$ be the Cayley graph on the alternating group $A_n\,n\ge4$ with generating set $$S=\begin{cases}\{(1,2,3),(1,3,2),\\(1,2,\ldots,n),(1,n,n-1,\ldots,2)\}, &n\ \text{odd}\\ \{(1,2,3),(1,3,2),\\...