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
2
votes
0
answers
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
2
votes
0
answers
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
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
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
5
votes
0
answers
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
3
votes
0
answers
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
7
votes
0
answers
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
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'$ ...
- 211
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
237
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.5k
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 ? ...
- 24.5k
0
votes
0
answers
87
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 ...
- 31
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),\\...
- 2,079
16
votes
0
answers
347
views
Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?
My question is
Let $G$ be an infinite, connected, locally finite, vertex-transitive graph. Must
$G$ have the following substructures?
i) a leafless spanning
tree;
ii) a spanning forest consisting ...
- 1,896
5
votes
0
answers
208
views
(How) does the spectral gap of the $n\times n$ Rubik's cube close with $n$?
Consider the spectrum of the adjacency matrix $A$ of the Cayley graph of the standard, 3x3x3 Rubik's cube generated with the usual quarter-turn and half-turn twists of each face (the Singmaster ...
- 2,133
6
votes
1
answer
171
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 ...
- 609
3
votes
0
answers
191
views
Property $(T)$ for $\mathrm{SL}_2(\mathbb{Z}) \ltimes \mathbb{Z}^2$
(This is in part a request for references and in part a somewhat pedagogical question.)
I gave a course on expanders seven years ago, and I am giving a course on expanders again now. We will soon do ...
- 19.5k
3
votes
1
answer
130
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
5
votes
0
answers
195
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
2
votes
0
answers
143
views
Chromatic numbers of Cayley graphs induced by Hamming balls
The motivation for this question is to find, for a fixed odd $p$ and large $n$, sets $A\subset (\mathbb Z/p\mathbb Z)^n$ with $|A|> cp^n$ for some fixed $c$, where the difference set $A-A:=\{a-a': ...
- 804
2
votes
0
answers
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
3
votes
0
answers
72
views
Hamiltonian cycles in Cayley graph on alternating group
Let $G=\operatorname{Cay}(A_n,S)$ be the Cayley graph on the Alternating group $A_n\quad n\ge4$ with generating set $S=\{(1,2,3),(1,2,4),\ldots,(1,4,2),(1,3,2)\}$. One Hamiltonian cycle in $G$ for $n=...
- 2,079
3
votes
0
answers
388
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 (...
- 26.3k
3
votes
1
answer
377
views
Explicit formula for embedding Cayley graph of free group into hyperbolic space
The problem is to embed Cayley graph of free group with $n\geq2$ generators (the same as Bethe lattice with coordination number $2n$) into any model of $\mathbb{H}^2$ (we have no model preference, the ...
7
votes
1
answer
260
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 ...
- 2,079
1
vote
2
answers
124
views
Difference in chromatic number between Schreier coset graphs and Cayley graphs
Can the Schreier coset graphs can be seen as a subgraph of Cayley graph on the same groups(neglecting the loop edges) and, hence, have their chromatic numbers bounded by the chromatic numbers of the ...
- 2,079
2
votes
1
answer
95
views
Imposing reciprocity in the definition of vertex-transitivity
A simple, undirected graph is vertex-transitive if for any pair of vertices $x,y$, there exists an automorphism (adjacency-preserving self-bijection) $\phi$ such that $\phi(x)=y$.
What if, instead of ...
- 234
0
votes
1
answer
113
views
Bound on chromatic number of graphs on any finite $p$-group
Is the chromatic number of a Cayley graph on $p$-groups with any generating set bounded by the chromatic number of the maximal induced circulant subgraph?
I think yes. Because for one, the main ...
- 2,079
0
votes
1
answer
84
views
Extending the vertex coloring of circulant graph to graph on $p$-group
Let $G_1$ be a circulant graph of prime order $p$. This implies that $G_1$ is the Cayley graph on $\mathbb{Z}_p$ with some generating set $S_1$. I am interested in knowing the characterizations of the ...
- 2,079
1
vote
0
answers
50
views
Circulant graphs chromatically dominated by powers of cycles
Suppose we can color the vertices of powers of cycles $C_n^k$ using $c$ colors such that each of the color classes $c_i$ have $v_i$ number of vertices. Can we always color the circulant of degree $2k$ ...
- 2,079
1
vote
0
answers
125
views
halved and folded hypercube duality
Notation. Consider the group $\Gamma=\mathbb{Z}_2^n$. I will denote the group operation aditively and by $\epsilon_i=(0,\dots,0,1,0,\dots,0)$ I denote the canonical generators. Let's define also $\...
- 211
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) = \...
- 2,882
12
votes
2
answers
770
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,873
1
vote
0
answers
89
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
0
answers
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
3
votes
0
answers
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 ...
- 31
-1
votes
1
answer
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
1
answer
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
2
votes
0
answers
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
-1
votes
1
answer
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
1
answer
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
4
votes
2
answers
464
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,079
0
votes
1
answer
122
views
Recognizing perfect Cayley graphs as tensor products
It is known (and can easily be seen) that a unitary Cayley graph on $n=\prod_ip_i$, ($p_i$ distinct primes) vertices with $n$ square-free can be recognized as the tensor product of the graphs $K_{p_i}$...
- 2,079
5
votes
1
answer
356
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
1
vote
0
answers
111
views
Chromatic number of certain graphs with high maximum degree
Let $G$ be the graph of even order $n$ and size $\ge\frac{n^2}{4}$ which is a Cayley graph on a nilpotent group but not complete. Can the chromatic number of this graph be determined in polynomial ...
- 2,079
5
votes
1
answer
270
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$ ...
- 235
0
votes
1
answer
352
views
A vertex transitive graph has a near perfect/ matching missing an independent set of vertices
Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove ...
- 2,079
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
1
vote
0
answers
161
views
Are all even regular undirected Cayley graphs of Class 1?
Are even order Cayley graphs of Class 1, that is, can they be edge-colored with exactly $m$ colors, where $m$ is the degree of each vertex?
I think yes, because of the symmetry the Cayley graphs ...
- 2,079