# Tagged Questions

**4**

votes

**2**answers

564 views

### Do Random Walks on the Hexagonal Lattice have a limit?

For every positive integer $n$, consider a regular hexagon $\mathrm{H}_n$ such that
the distance of each vertex from the center is $\frac{1}{\sqrt{n}}$. That in turn
induces a tiling of ...

**4**

votes

**0**answers

137 views

### Does the concept of connective constant make sense for any tiling of the plane?

First let me define what is the "connective constant" of a two dimensional lattice.
Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...

**4**

votes

**1**answer

117 views

### Epidemic threshold

Need some help / ideas to proceed. Stuck for a while on this.
In the literature of epidemic theory, it is found that the epidemic threshold is $1/\lambda_{max}(A)$ where $\lambda_{max}(A)$ is the ...

**6**

votes

**0**answers

135 views

### Uniformly sampling from the set of all simplicial maps

Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout.
How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial ...

**0**

votes

**1**answer

146 views

### Expected length of the shortest polygonal chain connecting N random points in the unit square

N points are selected uniformly at random in the unit square. Let L(N) be the expected length of the shortest (possibly self-intersecting) polygonal chain connecting all the points. It can be proved ...

**10**

votes

**1**answer

308 views

### Coloring $K_n$ via edge-weight sums

This is a question inspired by
and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly
much easier!
Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each
edge ...

**0**

votes

**3**answers

407 views

### Stationary distribution for bipartite graph

I was wondering if there is any stationary distribution for bipartite graph? Can we apply random walks on bipartite graph? since we know the stationary distribution can be found from Markov chain, but ...

**4**

votes

**3**answers

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

**3**

votes

**0**answers

108 views

### Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, ...

**0**

votes

**1**answer

361 views

### Calculate the probability of winning for a selected tic-tac-toe player

I am not a mathematician, I am a programmer. Sorry, if formulation of the problem is inexact.
I want to calculate the probability of winning for a selected tic-tac-toe player.
I have a directed graph ...

**1**

vote

**0**answers

114 views

### What is the expected Cheeger constant of a random graph?

Recall that the Cheeger constant (AKA isoperimetric constant) of a graph $G$ is the infimum of $\frac{\partial S}{vol S}$ over all subsets $S$ of $G$ with volume no larger than $vol(G)/2$. I would ...

**1**

vote

**1**answer

343 views

### Probability of two vertices being connected in a random graph

Consider a random directed graph with $N$ vertices where each vertex $v$ has exactly one link to some vertex (maybe to itself) $u$ with known probability $a_{vu}$. What is the probability of ...

**5**

votes

**1**answer

265 views

### Random path in a graph

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...

**1**

vote

**2**answers

230 views

### Probability distribution over cluster size in Erdős–Rényi random graph.

My question is about the probability distribution over the possible size of the containing cluster of a randomly chosen node in an Erdős–Rényi random graph.
Let G(n,p) be an Erdős–Rényi random graph ...

**4**

votes

**0**answers

92 views

### Metrized categories

Motivation: Let $\Gamma = (V,E)$ be a directed graph. To each edge $e \in E$, choose a value $\kappa^e \in \mathbb R$, representing the cost of transporting one unit of "stuff" through the edge. Let ...

**2**

votes

**1**answer

225 views

### Removing edges from Erdős–Rényi graph to make two nodes disconnected

Consider a Erdős–Rényi graph on $n$ nodes, say $1,2,\ldots,n$, ($n\geq 3$) such that the probability of edge between any two nodes is $c/n$. I wish to know if there is a result that says
"There ...

**4**

votes

**1**answer

158 views

### Random graphs nonisomorphic to unit distance graphs

I've encountered an interesting problem but can solve it only partially:
Prove that random graph $G\sim G\left(n,\frac cn\right)$, $c=const$, almost surely is isomorphic to some unit distance ...

**2**

votes

**0**answers

83 views

### Shortest loop containing 0 in continuum percolation

I am interersted in continuum percolation with intensity $\lambda>0$. Formally, let $X$ be a Poisson point process in $\mathbb{R}^d$ with intensity $\lambda$ and $G$ the graph obtained by ...

**4**

votes

**1**answer

257 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**

votes

**0**answers

140 views

### Graph distance of close points within the minimum spanning tree

My question is the following: Given $N$ uniform IID points $X=(X_1,...,X_N)$ on the unit cube of $\mathbb{R}^d$, take $X_1$ and another point, say $X_{(1)}$, "close" to $X_1$ (i.e. connected to $X_1$ ...

**2**

votes

**2**answers

225 views

### The probability distribution for vertex degree in a unit disc graph generated from random points on a plane

Imagine I cover an arbitrarily large plane with randomly placed points at some density $\rho$ s.t. the number of points in any randomly sampled area $A$ (of arbitrary shape and size) is $\approx ...

**0**

votes

**1**answer

221 views

### Two different definitions of Erdos-Rényi random graph

There are two or more ways to define an Erdos-Rényi random graph. Let consider the following two:
1) $G_n=(V_n,E_n)$ with vertex set $V_n=(1,\dots,n)$ and edge set $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ ...

**5**

votes

**2**answers

294 views

### Local concentration of measure on Erdos-Rényi graph

Let $G_n=(V_n,E_n)$ be an Erdos-Rényi random graph, precisely the vertex set is $V_n=(1,\dots,n)$ and the edge set is $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ \epsilon_{ij}=1)$ where $(\epsilon_{ij})_{ij}$ ...

**1**

vote

**1**answer

225 views

### Equivalent Markov Random Fields

Hi,
Is it possible to have topologically different Markov Random Fields (few different edges) and yet yielding the same inference results ?
Thanks!

**1**

vote

**1**answer

67 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

456 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

**2**answers

244 views

### expected number of cycles in a “random” bipartite directed graph

Consider a "random" bipartite directed graph where (1) on each side, the set of vertices has cardinality n and (2) for each vertex i, we add one (and only one) directed edge i->j at random (drawn ...

**3**

votes

**1**answer

323 views

### What is the expected value for this

If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...

**-2**

votes

**1**answer

190 views

### How to work with infinite random graph(s) ?

Hi,
In the case where we are dealing with an infinite random graph (RG with infinite nodes).
How do we model/work with notions like degrees, degree distribution ? How are they defined ?
Thanks!

**2**

votes

**1**answer

315 views

### “Nice” eigenvectors for (square of) adjacency matrix of a bipartite graph?

Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix.
I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be ...

**0**

votes

**0**answers

94 views

### Finding expectation of size of a subgraph.

I have been trying to implement a algorithm but got stuck in finding expectation of the size of the subgraph.
n - size of the network.
d - at most number of communities a node could participate ...

**4**

votes

**0**answers

192 views

### Expected number of components with multiple cycles in a subgraph of a square lattice

Short version
Is there an understanding of the emergence and subsequent disappearance of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the ...

**0**

votes

**2**answers

143 views

### Uniformly random planar map

Is there a way to sample a planar map uniformly at random? I am aware of the Cori-Vauquelin-Schaeffer bijection that can be used to sample and study uniformly random quadrangulations. There are other ...

**1**

vote

**1**answer

126 views

### The degrees in a random subgraph

Fix some positive integers $N$ and $d_k$, $k=1,2,\dots$ with $N=\sum_{k=1}^\infty d_k$.
Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ ...

**4**

votes

**1**answer

269 views

### Combinatorial descriptions of the stationary distribution of a Markov chain

When I say "Markov chain" I think of a directed positively weighted (finite) graph, such that the sum of all edges going out of a vertex equals 1. Also I assume that it is aperiodic and irreducible.
...

**0**

votes

**1**answer

299 views

### Probability of an edge appearing in a spanning tree

Hi guys, let's say I have a connected, undirected graph with many nodes. I am interested in finding the probability that an edge appears in any spanning tree of the graph. I could apply some of the ...

**3**

votes

**1**answer

196 views

### Probability that a randomly filled Go board has a set of white stones connected through their von Neumann neighborhoods

I have an $N$ by $M$ grid (a Go board for example), where for every square in the grid, I place a white stone with probability $p$ and a black stone with probability $(1-p)$. We call two white stones ...

**19**

votes

**3**answers

692 views

### Probability that random weights on $K_n$ satisfy triangle inequality

Given $K_n$, if a random real weight between $[0, 1]$ is chosen for every edge, what is the probability that the graph satisfies the triangle inequality? How about the discrete version, where the ...

**3**

votes

**1**answer

203 views

### Cover time and intersection time of random walks

Consider a simple lazy random walk on an $n$-vertex undirected, connected graph: this is the Markov chain which transitions from $i$ to $j$ with probability $p_{ij}=1/(2d(i))$ where $d(i)$ is the ...

**6**

votes

**1**answer

347 views

### Number of connected components in a graph from G(n,m)

Hello,
$G(n,m)$ is the family of all graphs with $n$ vertices and $m$ edges (I consider $m < n$).
Each graph in $G(n,m)$ is selected with uniform probability.
What is the probability that the ...

**8**

votes

**1**answer

571 views

### Correlation-Function for Random Graph Ising Model

For non-Ising'ers: Given a graph, we study the probability-distribution on the set of colorings ("Spin-up" and "-down") generated by a given correlation ("force to equality") between adjacient nodes ...

**2**

votes

**0**answers

69 views

### Subgraphs of bounded tree-width and preserving edges of original graph

Given a graph $G$, I would like to determine a method for randomly generating subgraphs $G'$ with the following properties:
Each edge of $G$ has at least some probability $p$ of going into $G'$
The ...

**3**

votes

**0**answers

128 views

### The mean number of vertices in small connected components of random geometric graphs

I place $N$ points on a circular plane of radius $R$, and draw edges to connect points that are less than or equal to some distance $D$ to form a set of graphs or cliques $G_i$. As a function of $N$, ...

**13**

votes

**4**answers

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

**29**

votes

**1**answer

1k views

### What is the sandpile torsor?

Let G be a finite undirected connected graph. A divisor on G is an element of the free abelian group Div(G) on the vertices of G (or an integer-valued function on the vertices.) Summing over all ...

**11**

votes

**5**answers

863 views

### Simple Random Walk on a Locally Finite Graph - when is it recurrent?

I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My ...

**9**

votes

**1**answer

296 views

### For what range of edge probability does the following property hold for random graphs?

Let $G(n,p)$ denote the Erdős–Rényi model of random graph. For a given function $p = p(n)$ we say that $G \in G(n,p)$ asymptotically almost surely has property $\mathcal{P}$ if
$$\mbox{Pr}[G \mbox{ ...

**8**

votes

**0**answers

364 views

### Abelian sandpile models

This question is about a popular probabilistic model on graphs studied in physics, mostly, for the standard lattice in ${\mathbb R}^n$ but also on other graphs (this model is of the same spirit as ...

**6**

votes

**3**answers

1k views

### Random bipartite graphs

Consider the following situation: I have a set $A$ of $n$ vertices and a set $B$ of $N = n^2$vertices. I consider the bipartite graph $(A, B)$ and put at random $M = n^{1 + \varepsilon}$ edges (or I ...

**5**

votes

**1**answer

361 views

### First Passage Percolation on Trees

Let $T$ be a rooted Galton-Watson random tree generated accordingly to a probability distribution $\mu$. Now assign to each edge $e$ a random non-negative weight $w_e$ distributed a accordingly to a ...