1
vote
0answers
96 views

random walk with reflecting barriers [closed]

Consider a random walk on the line 1,...,d. You start at point 1. At each step you flip a coin: heads means go left, tails means go right. If you're at 1 and get a heads, just stay where you are (same ...
1
vote
0answers
52 views

Asymptotic results in unbalanced left $d$-regular expander graphs

Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$. Call a graph $G = (U, ...
0
votes
1answer
55 views

mean length of the non-crossing graphs on n points

My original question is rather vague so I'll start with a precise example and then indicate possible generalisations. Given a n-tuple $x=(x_1,\dots,x_n)$ in, say, a square with side-length $1$ in the ...
7
votes
2answers
269 views

Wait time to grid network disconnection with failing edges

Let $G_n$ be an $n \times n$ planar toroidal grid graph, with each node connected to its four neighbors, with the top row connected to the bottom, and the right column connected to the left. Suppose ...
4
votes
2answers
618 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
0answers
141 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
1answer
129 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
0answers
139 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
1answer
158 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
1answer
315 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
3answers
515 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
3answers
164 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
0answers
117 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
1answer
490 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
0answers
127 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
1answer
433 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
1answer
275 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
2answers
267 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
0answers
93 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
1answer
243 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
1answer
166 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
0answers
86 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
1answer
283 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
0answers
151 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
2answers
251 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
1answer
238 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
2answers
309 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
1answer
233 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
1answer
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
3answers
458 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
2answers
280 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
1answer
337 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
1answer
193 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
1answer
358 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
0answers
101 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
0answers
210 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 ...
1
vote
2answers
159 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
1answer
145 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
1answer
282 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
1answer
336 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
1answer
198 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
3answers
703 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
1answer
215 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
1answer
366 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
1answer
595 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
0answers
71 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
0answers
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
4answers
690 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 ...
30
votes
1answer
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 ...
12
votes
5answers
921 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 ...