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

70 questions
Filter by
Sorted by
Tagged with
139 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.5k
164 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.5k
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
116 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.5k
119 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. ...
• 24.5k
96 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.5k
228 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.5k
208 views

158 views

### Bruhat-Tits tree as Cayley graph of free group

$\DeclareMathOperator\BT{BT}\DeclareMathOperator\GL{GL}$Let $p > 2$ be a prime and $n = \frac{p + 1}{2}$. We can identify the vertices of Bruhat-Tits tree $\BT(\mathbb Q_p)$ with the elements in ...
• 71
72 views

• 211
245 views

• 405
115 views

### Procedure to color the edges of a circulant graph

From the first theorem in this paper, it is clear that a cayley graph on abelian group for all generating sets of even order is class $1$, that is can be edge colored in exactly $\Delta$ colors. But, ...
• 2,079
73 views

### how do I find eigenvalues of Cayley graph for one subset given a different subset

How do I find eigenvalues for the adjacency matrix of Cayley graph $X(S_n,S)$ where $S_n$ is the symmetric group of order $n$ and $S$ is the set of transpositions $(i,i+1)$, if the eigenvalues of the ...
192 views

### Which line graphs of Cayley graphs are Cayley

When are the line graphs of Cayley graphs Cayley? From this link we can know when the line graphs of complete graphs are cayley. But, my question pertains to the larger class of Cayley graphs. Are ...
• 2,079
1 vote
187 views

### Cayley graphs on $Z_{11}$ and $Z_p$

I want to find all cayley graphs on $Z_{11}$. I know how many connected cayley graphs exist but i want to find all of them, connected or not, to find their eigenvalues. I found some of them and a ...
• 219
64 views

### Path-covering for vertex-transitive graphs

I have the following dummy problem: Claim - There exists $N$ such that for $n > N$, if $G_n$ be a connected directed vertex-transitive graph with $n$ vertices, then there exists a set $S$ of paths ...
• 3,489
212 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,079
1 vote
241 views

### Cayley graphs do not have isolated maximal cliques

Let a Cayley graph $G$ of a group $H$ with respect to the generating set $\{s_i\}$ have a clique of order $> 2$. In addition assume the graph $G$ is non-complete. If the clique size is less than ...
• 2,079