All Questions
11 questions
21
votes
6
answers
3k
views
"The" random tree
One time I heard a talk about "the" random tree. This tree has one vertex for each natural number, and the edges are constructed probabilistically. Connect vertex $2$ to vertex $1$. Connect vertex $3$ ...
- 68.9k
15
votes
4
answers
1k
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 non-...
- 4,705
12
votes
3
answers
552
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 ...
- 4,432
9
votes
1
answer
526
views
Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance
Problem: Consider a random walk on the lattice $\mathbb{Z}^2$ where on each iteration a particle either stays at its current location or moves to a neighboring vertex with probability 1/5. We start ...
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 ...
7
votes
3
answers
801
views
Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance Part II
For some context see Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance
As per Noah's answer and JBL's comment this was false as stated. However, I think the following ...
5
votes
3
answers
314
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 ...
- 15.5k
5
votes
1
answer
774
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 ...
- 4,432
3
votes
1
answer
693
views
Size of automorphism group of random regular graph
If I pick a random regular graph on $n$-vertices and degree $d$ from uniform distribution what is the probability that its automorphism group is of size at least $m$?
--
I want to know what is the ...
- 13.9k
2
votes
1
answer
141
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 $k$-...
- 4,432
1
vote
0
answers
340
views
Random walk on non-abelian free group
Let $F_2$ be the free non-abelian group with generators $a, b\in F_2$.
Has the "random walk" where we start with the identity and then multiply it by $a$ or $b$ or $a^{-1}$ or $b^{-1}$ ...
- 11