3
votes
0answers
118 views

What do we know about isospectral Cayley graphs?

Let $\Gamma_1=\Gamma_1(G_1,S_1)$ (respectively $\Gamma_2=\Gamma_2(G_2,S_2)$) be a Cayley graph for the group $G_1$ and the finite generating set $S_1$ (respectively $G_2$ and the finite generating set ...
5
votes
0answers
156 views

(Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples

Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...
1
vote
2answers
168 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
1answer
89 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 ...
5
votes
1answer
174 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
0answers
49 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
0answers
670 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 ...
7
votes
1answer
356 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
0answers
153 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
2answers
176 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
1answer
162 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
1answer
150 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
2answers
133 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
1answer
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
0answers
168 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
2answers
351 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
1answer
203 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
0answers
133 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
0answers
144 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
3answers
169 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
0answers
139 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
1answer
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
0answers
90 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
2answers
273 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
3answers
519 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
2answers
338 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
1answer
172 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
0answers
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 ...
15
votes
0answers
252 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
2answers
324 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
1answer
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
1answer
291 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
2answers
368 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
1answer
177 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
1answer
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
3answers
460 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
1answer
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
1answer
248 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
1answer
345 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
3answers
800 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
1answer
92 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
1answer
290 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
2answers
307 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
1answer
320 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
1answer
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
1answer
639 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
1answer
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
3answers
396 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
0answers
403 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
2answers
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, ...