# Tagged Questions

**1**

vote

**2**answers

150 views

### Cubic Cayley (undirected) graphs

The generators of a cubic Cayley graph always include at least one involution, since 3 is odd. There are then two possibilties for the other two generators: either (A) they are also (distinct) ...

**2**

votes

**1**answer

77 views

### What is the minimal girth of a cayley graph for Alt(n) in which the girth relator is not a proper power?

First, a definition: a girth relator for a Cayley graph is a word that you get by reading the edge labels along a shortest loop. The girth relator is not usually unique, though it is often unique up ...

**6**

votes

**1**answer

158 views

### Duration and critical groups order in sandpile models and chip firing games

The famous chip firing game (which is closely related to sandpile models) goes like this:
Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of
degree $d_{v}$ has at least ...

**2**

votes

**0**answers

47 views

### When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...

**19**

votes

**0**answers

660 views

### Non-linear expanders?

Recall that a family of graphs (indexed by an infinite set, such as the primes, say) is called an expander family if there is a $\delta>0$ such that, on every graph in the family, the discrete ...

**6**

votes

**1**answer

351 views

### Paths in groups

Given a finite group $G$, write $K(G)$ for the complete digraph on the elements of $G$. Label the edge from $g$ to $h$ by element $g^{-1}h$.
Question: For what groups does there exist a Hamiltonian ...

**0**

votes

**0**answers

146 views

### Induced graphs of cayley graph

I have a Cayley graph $Cay(G,S)$, its group presentation $G=< S | R >$ and it is a metric graph by assigning a length equal to 1 to each edge. I also have an induced subgraph of that Cayley ...

**4**

votes

**2**answers

173 views

### Are the following Cayley digraphs Hamiltonian?

Consider the Cayley graphs $A'G_n$ on the alternating group $A_n$ with generating set $S = \{(1i2) : 3 \leq i \leq n\}$, for $n \geq 4$.
See the following page on Alternating Group Graphs for ...

**2**

votes

**1**answer

154 views

### Does index 2 subgroup imply bipartite Cayley graph?

Let $G$ be a finitely generated group and let $\Gamma=Cay(G, S)$ be the Cayley graph of $G$ with respect to some generating set $S$.
If there exists $S$ such that $\Gamma$ is bipartite, then $G$ has ...

**4**

votes

**1**answer

148 views

### Which hyperbolic tilings are Cayley graphs?

I realise the question is easy but after asking to a few people (and never getting a clear answer), I thought it could be instructive to ask it here:
Given a regular tiling of the hyperbolic plane is ...

**2**

votes

**2**answers

128 views

### Normal subgroups of automorphism group of infinite cubic tree

Let $T$ denote the unique (countably infinite) tree in which every vertex has degree $3$ and let $G=Aut(T)$ be the group of graph automorphisms of $T$.
I'm interested in the properties of this ...

**2**

votes

**1**answer

130 views

### Non-exchangeable unimodular graph

Let $G=(V,E)$ be an countably infinite, locally finite transitive graph. Say that $G$ is exchangeable if for every two vertices $v,w \in V$ there exists a graph homomorphism that maps $v$ to $w$ and ...

**3**

votes

**0**answers

162 views

### vertex transitive and Cayley graphs

(all the graphs alluded to below are finite).
Suppose I gave you a graph, and asked you whether it was vertex-transitive. How hard is that algorithmically?
The second question is: suppose I gave you ...

**3**

votes

**2**answers

336 views

### A structure of the group of automorphisms of an infinite binary tree

My friend asked me to ask his question here. Where he can find (a paper or a book) containing a complete description (with the proof) of a structure of the group of automorphisms of an infinite binary ...

**2**

votes

**1**answer

198 views

### Upper bound on the number of vertex transitive graphs

Is there a known upper bound on the number of vertex transitive graphs on $n$ vertices?

**1**

vote

**0**answers

132 views

### A connection between nonplanar complete graphs and the alternating group?

I didn't get any response on MSE so I though I'd give this a try here (my question on MSE).
I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...

**1**

vote

**0**answers

142 views

### Can assigment of Cayley graphs be functorial?

Let $G$ and $G'$ be finitely generated groups and $f:G\to G'$ a homomorphism. First question: for a given $f:G\to G'$ it possible to select generating sets $S\in G, S'\in G'$ so that their would be a ...

**4**

votes

**3**answers

164 views

### Tracking automorphism groups of graph processes

Start with an edgeless graph on $n$ labeled vertices, and note that the automorphism group is $\Sigma_n$, the symmetric group on $n$ elements. Now imagine that we randomly start throwing in all of the ...

**1**

vote

**0**answers

126 views

### Is the automorphism group of a homogeneous (locally finite) tree unimodular?

I have seen somewhere (that I don't remember now) that the (full) automorphism group of a k-regular tree is unimodular. I assume a k-regular tree is the same thing as the homogeneous tree of degree k ...

**2**

votes

**1**answer

65 views

### Commensurability of 2-colorings of finite 4-valent graphs

It is quite easy to show that given two finite 4-valent graphs $X,X'$ (I will take the convention that there is at most one edge between two vertices, but allow loops) there is a third such graph ...

**2**

votes

**0**answers

89 views

### Groups acting on non-locally-finite trees with independence and specified local actions

Suppose I have a biregular tree $T_{m, n}$ (not necessarily locally finite), with distinct cardinal numbers $m, n$, so Aut$(T_{m, n})$ acts on $T_{m, n}$ without inversion. Let $V_m$ be those vertices ...

**6**

votes

**2**answers

271 views

### Embedding of a “quotient graph”

Consider the simple undirected graph $G$ with natural equivalence relation $\sim$ on $V(G)$:
$u\sim v$ iff they are similar, i.e. iff there exists $\phi\in Aut(G)$ with $\phi(u)=v$.
Define a ...

**7**

votes

**3**answers

509 views

### Is there a Cayley graph of a non-abelian 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 ...

**2**

votes

**2**answers

329 views

### Automorphism group action leads to a “quotient graph”

Let $G$ be a simple (finite) graph. Consider the next natural equivalence relation $\sim$ on $V(G)$:
$u\sim v$ iff there exists and automorphism $\phi\in Aut(G)$, such that $\phi(u)=v$.
Define a new ...

**2**

votes

**1**answer

171 views

### Commuting graph automorphisms for Schreier graphs

Let $G=\langle g_1,g_2\rangle$ denote the free group of rank 2. For a subgroup $H$ of $G$ consider the quotient graph with vertex set $H\setminus G$ of right cosets, where $Hg$ and $Hg'$ are connected ...

**4**

votes

**0**answers

160 views

### Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...

**14**

votes

**0**answers

240 views

### Maximum automorphism group for a 3-connected cubic graph

The following arose as a side issue in a project on graph reconstruction.
Problem: Let $a(n)$ be the greatest order of the automorphism group of a 3-connected cubic graph with $n$ vertices. Find a ...

**1**

vote

**2**answers

319 views

### The generators of special linear groups

Let $x$ and $y$ be two element of general linear group $SL(n,q)$, such that the orders of $x$ and $y$ be some primitive prime divisor of $q^n-1$. Is it true that if $xy\not=yx$, then $x$ and $y$ ...

**-2**

votes

**1**answer

144 views

### Maximal torus and application in prime graph [closed]

I am studying papers about " Prime graph" , for example "Prime graph components of finite groups" [ williams], " Groups with complete prime graph connected components" [ Lucido and moghaddanfar]. ...

**4**

votes

**1**answer

280 views

### Probabilities of a random walk exiting a set

Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as ...

**11**

votes

**2**answers

350 views

### Finite vertex-transitive graphs that look like infinite vertex-transitive graphs

For a vertex-transitive graph $G$ and a positive integer $d$, and let $G(d)$ be the subgraph induced by all vertices of $G$ within distance $d$ of some given vertex $v$ (since $G$ is ...

**3**

votes

**1**answer

171 views

### Planar Cayley graphs/complexes for coxeter groups

Consider a Coxeter group presentation $< s_1, \ldots s_n \mid (s_i s_j)^{m_{ij}}>$ with $m_{ii}=1$ for all $i$. I can prove (using http://arxiv.org/abs/1011.4255) that if for each $i$ there are ...

**1**

vote

**1**answer

69 views

### Spanning subgaph with trivial Poisson boundaries

Assume $\Gamma$ is the Cayley graph of an amenable$^{*}$ group and that the simple random walk has non-trivial Poisson boundary$^{**}$. Is there a spanning connected subgraph $\Gamma'$ of some ...

**12**

votes

**3**answers

458 views

### Estimate on currents in Cayley graphs

Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...

**2**

votes

**1**answer

117 views

### Can the isoperimetric dimension of a d-generated group attain any value?

Background
The isoperimetric dimension of a finitely generated group $G$, which we denote by $\dim(G)$, is the largest number $d$ such that any Cayley graph $\Gamma$ of $G$ (constructed with respect ...

**4**

votes

**1**answer

243 views

### polycirculant conjecture

By the polycirculant conjecture, every vertex-transitive graph is a polycirculant graph (D. Marusic 1981 and D. Jordan 1988).
There are two papers that claim to prove this conjecture:
1. A. Golubchik, ...

**8**

votes

**1**answer

344 views

### When does a `distinguished matching' exist?

Suppose I have a bipartite graph on a pair of vertex sets $X$ and $Y$.
Definition: A distinguished matching is a subset $DX\subseteq X$ and a subset $DY\subseteq Y$ such that:
For all $y\in Y$, ...

**7**

votes

**3**answers

785 views

### Showing non-expansion for $x\rightarrow x+1, x\rightarrow 2x.$

Construct a graph having $V=\mathbb{Z}/p\mathbb{Z}$ as its set of vertices and $\{\{x,x+1\}: x \in V\}\cup \{\{x,2x\}: x \in V\}$ as its set of edges. This graph is not an expander - quite ...

**1**

vote

**1**answer

90 views

### Artin groups whose graphs differ by one edge and coverings

Every right-angled Artin group and Coxeter group has a graph $\Gamma$ associated to it. The vertices of the graph stayfor the generators of the group and the edges correspond to the relations of the ...

**2**

votes

**1**answer

278 views

### article by Jacques Tits about automorphism group of a locally finite tree

I believe that there might be an article by Jacques Tits somewhere in which he shows that a locally finite tree can be recovered from the topological group structure on its automorphism group (with ...

**3**

votes

**2**answers

300 views

### Configuration of the branch locus of a branched covering of an elliptic curve

Let $C$ be a curve of genus 3 and suppose that it admits a branched cover $\varphi:C\rightarrow E$ with $E$ elliptic and such that $\varphi$ does not factor through any \' etale cover. Then the degree ...

**7**

votes

**1**answer

310 views

### Maximal subgroups of a certain finite 2-group

The following came up in a problem on reconstruction of digraphs. I determined enough about the answer to satisfy the application completely, but still I am curious to know what the complete solution ...

**4**

votes

**1**answer

249 views

### Representing groups with two generators as graph automorphisms

Suppose we have a group $G$ which can be generated by two elements $x$, $y$. Call $H$, $K$, $L$ the subgroups of $G$ generated by $x$, $y$ and $y^{-1}x^{-1}$, respectively.
With these data, we can ...

**3**

votes

**1**answer

631 views

### Algebraic structure generated by primitive graph operations

Let $M$ be a finite set, and
$S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}$.
Each element of $S(M)$ can be considered as a finite directed graph with the set of nodes $M$, which has exactly two arrows ...

**3**

votes

**1**answer

123 views

### Counting connected fundamental domains of actions on Cayley graphs

The following question arises, for me, from mathematical music theory:
Write $({\Bbb Z}^n,E_n)$ for the Cayley graph of ${\Bbb Z}^n$
relative to standard free generators.
Given a subgroup $L$ of ...

**9**

votes

**3**answers

390 views

### Are there Hamilton paths in Cayley graphs of Coxeter groups?

Hi everyone.
I want to optimize certain computation on finite Coxeter groups $(W,S)$. Basically I compute the matrices $\rho(T_w)$ for all $w\in W$ of a matrix representation $H\to K^{d\times d}$ of ...

**8**

votes

**0**answers

383 views

### Shortest path in Cayley graphs

The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set ...

**12**

votes

**2**answers

1k views

### Non-isomorphic groups with the same oriented Cayley graph

There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, ...

**13**

votes

**4**answers

684 views

### The critical value of percolation on Cayley graphs.

Let $\Gamma$ be a discrete group with a generating set $S$. Let $p_c(\Gamma,S)$ be the critical probability for percolation of the Cayley graph of $\Gamma$. Is it known that if $\Gamma$ is ...

**7**

votes

**4**answers

1k views

### Cayley graphs and its subgraphs

I have two questions about Cayley graphs. Any answers will be appreciate.
1) Do we have any Cayley graph that has Petersen graph as its induced subgraph?
2) Suppose $Cay(G,S)$ be a Cayley graph that ...