All Questions
Tagged with graph-theory geometric-group-theory
37 questions
7
votes
0
answers
220
views
Is there a Cayley graph with end space infinite and discrete?
A Cayley graph of a finitely generated group must be locally finite, and we know end spaces of locally finite graphs must be compact - so we can't have an infinite and discrete end space in this ...
- 407
0
votes
1
answer
198
views
Finding automorphism groups of regular graphs [closed]
Can some body help me with some source code for finding automorphism groups of regular maps?. For example: the type of graph is denoted as $\{p, q\}$, which means that they are tessellations of the ...
23
votes
1
answer
1k
views
Universal graph
A connected (and infinite) graph $U$ will be called $n$-universal if any connected graph with degree $\leqslant n$ admits an embedding in $U$.
Is there a 3-universal graph with bounded degree?
- 45k
2
votes
1
answer
292
views
Do balls in expander graphs have small expansion?
Consider a $d$-regular infinite transitive expander graph $G$, and let $B_r$ be a ball of radius $r$ in $G$. Can one place any upper bounds on the expansion of $B_r$?
My intuition is that $B_r$ will ...
- 31
16
votes
0
answers
362
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,926
3
votes
1
answer
348
views
Can graphs of groups be thought of as "graph objects" in the category of groupoids?
An undirected graph is sometimes defined as a pair of sets $V$ and $E$ (vertices and oriented edges), together with two maps $i,f: E\to V$ (sending a directed edge its initial/final vertex) and a map $...
- 3,446
1
vote
1
answer
80
views
Deduce unsolvability of $\operatorname{IP}(G_0)$ from the Adian–Rabin Theorem
$\operatorname{IP}(G_0)$: the special isomorphism problem for $G_0$, i.e., given $G_0$, determine if $G$ is isomorphic to $G_0$. My question is that how can we deduce from the Adian–Rabin theorem that ...
- 51
4
votes
0
answers
254
views
Graphs with high girth and low diameter
As the title says, I'm interested in graphs with high girth and low diameter.
Given a class $\Gamma$ of finite $k$-regular graphs, call a $\Gamma$-graph GD-extremal if every $\Gamma$-graph either has ...
- 3,612
4
votes
1
answer
102
views
Shortcutting quasigeodesics
Let $\Gamma$ be a connected graph, let $\lambda \ge 1$ and $c \ge 0$ be some constants. Recall that a combinatorial path $p$ in $\Gamma$ is said to be $(\lambda,c)$-quasigeodesic if for every ...
- 3,181
7
votes
1
answer
283
views
Are two quasi-isometric, isomorphic on large enough balls, transitive graphs isomorphic?
Take two transitive graphs $X,Y$ (potentially directed and edge-labelled, e.g. Cayley graphs).
Assume $X,Y$ are quasi-isometric with constant $K$, i.e. there exists a function $f:VX \to VY$ ($VX,\,VY$ ...
- 887
31
votes
0
answers
919
views
Is this representation of Go (game) irreducible?
This post is freely inspired by the basic rules of Go (game), usually played on a $19 \times 19$ grid graph.
Consider the $\mathbb{Z}^2$ grid. We can assign to each vertex a state "black" ($b$), "...
7
votes
1
answer
319
views
Which groups contain a comb?
The comb is the undirected simple graph with nodes
$\mathbb{N} \times \mathbb{N}$
where $\mathbb{N} \ni 0$ and edges
$$ \{\{(m,n), (m,n+1)\}, \{(m,0), (m+1,0)\} \;|\; m \in \mathbb{N}, n \in \mathbb{N}...
- 6,652
7
votes
1
answer
247
views
Going up of an amalgamated decomposition of a subgroup of finite index
Let $G$ be a finitely presented group and H a subgroup of index $n$ in $G$. Suppose that H has a non-trivial decomposition as amalgamated product, say $H = A \ast_U B$. I am wondering about the ...
5
votes
1
answer
407
views
Cayley graph properties
Consider an infinite graph that satisfies the following property: if any finite set of vertices is removed (and all the adjacent edges), then the resulting graph has only one infinite connected ...
4
votes
0
answers
215
views
Words Growth in Finite Groups
Let $G$ be a finite group with a set of generators and let $\Gamma$ be its Cayley Graph. Let $b_k$ be the number of elements in the ball of radius $k$. I am interested in what is known about the ...
- 5,450
5
votes
0
answers
169
views
In the literature on infinite graphs, are there results on "periodizable" graphs?
Let $G=(V,E)$ be a connected countably infinite $k$-regular simple graph (no loops or multiple edges). For $A$ a finite subset of $V$, let me denote by $G_A=(A,E_A)$ the induced subgraph with vertex ...
8
votes
2
answers
343
views
Cubic almost-vertex-transitive graphs with given spanning tree
Consider the infinite 3-regular tree. Pick a vertex $C$, the "center".
For any integer $L\ge 1$ consider the closed ball, in the graph distance, of radius $L$ around $C$. Let $T_L$ be the induced ...
3
votes
0
answers
285
views
Cayley Graphs and Cyclically reduced words [closed]
Let $G$ be a finite group and $S$ be a symmetric generating set for $G$. (EDIT: Assume $S$ does not contain involutions!) Cyclically reduced words can be thought of as minimal length representatives ...
- 949
2
votes
1
answer
222
views
Mapping $\Delta(2,2,2)\mapsto \Delta(4,4,2)$
Looking at the images below, you recognize that the adjacency matrix of the graph $A_G$ splits up into three different colored submatrices, with $A_G=A_r+A_b+A_d$ (where $d$ is dark, damn...).
It's ...
- 457
4
votes
2
answers
312
views
Non-Cayley expander graphs
When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. Now my questions are as follows:
Are all expander regular graphs are Cayley, or there is a special ...
2
votes
0
answers
135
views
Extending continuous functions from $\partial X$ to $X\cup \partial X$
Consider a proper geodesic hyperbolic space $X$ (in the sense of Gromov). Let $\partial X$ be its Gromov boundary. Consider a complex-valued continuous function on the boundary $f\colon\partial X\to\...
- 329
4
votes
2
answers
871
views
Detecting HNN-Extension and free products with amalgamation
This question is partly connected with the following Connection between Stalling's end theorem and Seifert-van Kampen Theorem.
By Stalling's Theorem a group with more than one end splits over a ...
- 721
4
votes
1
answer
323
views
Obtaining a quasi-isometry of the 'boundary'
It is well-known that a quasi-isometry induces a homeomorphism on the space of ends of say a locally finite graph for simplicity. Clearly the converse is not true. In other words the concept of ends ...
- 721
10
votes
2
answers
677
views
Is every metric space quasi-isometric to a graph?
I've proved that if $(X, d)$ is a geodesic metric space then there exists a graph which is quasi-isometric to $X$...during this proof I've precisely used the fact that given two point in $X$ there ...
- 3,751
19
votes
0
answers
782
views
Reference request: Parallel processor theorem of William Thurston
Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...
- 15.4k
5
votes
2
answers
805
views
A generously vertex transitive graph which is not Cayley?
A graph is vertex transitive if $x \mapsto y$ by an automorphism.
A graph is generously vertex transitive if $x \mapsto y \mapsto x$ by an automorphism.
Simple facts:
GVT $\rightarrow$ unimodular. ...
- 153
2
votes
1
answer
346
views
Limit Group decomposition
I would need a clarification about a statement in the article Limit groups and groups acting freely on $\mathbb{R}^n$-trees by Vincent Guirardel.
First recall that a limit group is a finitely ...
- 41
13
votes
1
answer
887
views
Isometries of some simple Cayley graphs
Consider a Cayley graph of a group $G$ with respect to a symmetric finite generating set $S$.
There are some obvious candidates to isometries of this graph - for example, translation by elements of $G$...
- 689
13
votes
1
answer
393
views
Is the Cayley graph of Thompson's group isolated in the space of vertex-transitive graphs?
Consider Thompson's group (the one commonly referred to as $T$), which is finitely presentable. Consider the Cayley graph, but then forget the coloring and direction on edges. So now we just have an ...
- 3,073
17
votes
0
answers
255
views
Approximation of the effective resistance on Cayley graph
Let $\Gamma$ be a finitely generated group, and denote by $G$ the Cayley graph of $\Gamma$. Denote by $d_R$ the resistance distance metric on this graph. The resistance distance metric between the ...
- 395
4
votes
0
answers
137
views
Actions of amenable groups on graphs with uncountably many ends
Let $G$ be a finitely generated amenable group acting transitively on an amenable Schreier graph $S$. Is it possible for $S$ to have uncountably many ends? An amenable graph with uncountably many ends ...
- 2,449
3
votes
0
answers
311
views
Induced graphs of Cayley graph
I have a Cayley graph $\mathrm{Cay}(G,S)$, its group presentation $G=\langle S | R \rangle$, and it becomes a metric graph by assigning a length equal to $1$ to each edge. I also have an induced ...
- 31
11
votes
2
answers
659
views
Quantum Cellular Automata on Riemannian manifolds and geometric group theory
We try to motivate our question. We have a certain logical/operational structure that has an
emergent physical interpretation. We are giving this structure a geometric setting via
quasi-isometries. ...
- 153
4
votes
1
answer
375
views
Cayley graphs of finitely generated infinite groups quasi-isometrically embeddable in R^3
Dear friends,
I am only a theoretical physicist. However, the answer to this question is relevant for emergence of space-time from a quantum cellular automaton (in the future I will pose a much more ...
- 153
7
votes
1
answer
299
views
How large is this "algebra" of defining graphs for Right-angled Artin groups?
As part of my research, I have been trying to construct a spherical space at infinity for every right-angled artin group. I've been able to work it out for a certain class of defining graphs. I'd like ...
- 3,359
4
votes
2
answers
809
views
hyperbolic amenable graph
Is there an infinite (finite degree) transitive amenable hyperbolic graph ?
- 43
4
votes
2
answers
1k
views
Hausdorff Dimension of Cayley Graphs of Groups
I was wondering what has been done concerning the Hausdorff measure of the Cayley graphs of finitely generated countable groups. There are number of issues that would need to be dealt with:
1.) By ...
- 2,441