All Questions
Tagged with graph-theory geometric-group-theory
11 questions with no upvoted or accepted answers
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$), "...
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
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
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
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
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 ...
4
votes
0
answers
255
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
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
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
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