# Tagged Questions

**19**

votes

**0**answers

646 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

347 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

143 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

171 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

151 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

147 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

125 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

161 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

332 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

195 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

140 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

162 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

116 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

63 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

87 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

504 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

321 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

157 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

228 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

315 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

143 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

273 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

346 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

170 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

457 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

240 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

342 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

781 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

274 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

298 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

305 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

248 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

625 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

385 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

378 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

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

**9**

votes

**2**answers

667 views

### Number of Geodesic Paths Passing Through a Vertex in an Expander Graph

Let $\{G_{n}\}$ be a sequence of $k$-regular expander graphs. For each $n$ assume that each pair of nodes in the graph is transmitting a unit load of traffic and the traffic goes through the minimum ...

**6**

votes

**3**answers

331 views

### Tutte polynomials of appropriate Cayley graphs

I was quite intrigued by Tutte polynomials in a recent talk I had been to. It was introduced as a polynomial associated to a undirected finite graph. For a graph $G=(V,E)$ we form the polynomial
...

**3**

votes

**2**answers

550 views

### Fixed points of a group-operation on a tree, Serre's book “Trees” 6.3.4. and Prop 27

Hello! I have a problem with the following Lemma, which is mentioned in Serre's book "Trees" on page 60. In the book it is the Example 6.3.4.:
Lemma: Let $G$ be a group acting (without inversion) on ...

**1**

vote

**2**answers

238 views

### How much local is the information encoded by the isoperimetric constant of a graph?

Upload: the general question has been answered in the negative. Now I am proposing a more specific question, which is actually the one that I am interested in.
I think that this is a quite natural ...