All Questions
Tagged with random-graphs pr.probability
42 questions with no upvoted or accepted answers
13
votes
0
answers
509
views
First passage percolation on a random geometric graph in the large connectivity limit
Let $V_\rho\subset\mathbb{R}^2$ be a point set in the plane obtained from a Poisson process of density $\rho$. The random geometric graph $G_\rho$ is obtained from $V_\rho$ by connecting points that ...
- 3,927
8
votes
0
answers
240
views
Stepanov phase transition in random graph
Consider the classical random graph model G(n,p), with p=c/n, as proposed by Erd\"os and R\'enyi.
At this scaling, the most prominent feature is arguably the abrupt change of the topology that the ...
- 468
6
votes
0
answers
164
views
Hamilton cycles in random graphs with just enough connectivity
What is the asymptotic probability that $G$ has a Hamilton cycle if $G$ is a random $n$ vertex $\frac{4}{3}n$ edge graph, with minimum degree 2 and without degree 2 vertices at distance 1 or 2 to each ...
- 7,545
6
votes
0
answers
301
views
Probability that a random multigraph is simple
Question.
Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...
- 1,444
6
votes
0
answers
105
views
Long loops in critical random graphs
A simple calculation seems to show that the expected number $X_k$ of loops of length $k$ in a critical Erdös-Renyi random graph $G(n,n^{-1})$ is approximately given by
$$ \mathbb{E} X_k=\frac1{2k}{e^...
6
votes
0
answers
149
views
Does squaring a directed random graph more than double its out-degree?
As far as I know, it is an unsolved question
whether or not this is true:
If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least
double that of its ...
- 151k
5
votes
0
answers
66
views
Full distribution of FPTs in random walks on graphs
There is a lot of published research on the mean passage passage time (FPT) for random walks on various types of graphs. How about the variance of the FPT and higher momenta? In fact, I would be ...
4
votes
0
answers
220
views
Navigation in a graph
The problem
Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$.
Assumptions about the graph: You may ...
- 323
4
votes
0
answers
158
views
Using Crump-Mode-Jagers processes to get logarithmic bound on a random tree height
I am currently pursuing my PhD degree and in my research I came across a family of random trees. I need to prove a logarithmic asymptotic bound for the heights of such trees as their size grows. I ...
- 41
4
votes
0
answers
183
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$, i....
- 163
4
votes
0
answers
617
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 edge-...
- 1,414
3
votes
0
answers
81
views
Can we remove the restriction on a parameter in Talagrand concentration inequality?
Recently I am trying to use Talagrand concentration inequality to do something on graphs. I find a version from the book of Molloy and Reed ''Graph Colouring and Probabilistics Method''. I attached a ...
- 1,190
3
votes
0
answers
87
views
Is the probability distribution of a graphon given as a graph limit computable?
Let $G_i$ be a sequence of finite graphs that is Cauchy in the space of graphons. That is, for every $\epsilon \in \mathbb Q_+$ there is a $N \in \mathbb N$ such that $$\forall n, m > N. \delta_\...
- 6,353
3
votes
0
answers
151
views
Largest eigenvalue divided by $n$
Let $X$ be an $n\times n$ symmetric random matrix whose diagonal is fixed as $1$, and every element in the upper triangle (excluding the diagonal) is drawn from Bernoulli($p$). The elements in the ...
- 272
3
votes
0
answers
151
views
Sequential generation of any random graph
The high-level question is: can we generate any random graph with size $d$ using a Markov chain?
For example, let $X^{(0)} = (1,0,\ldots,0) \in R^d$ be the initial state, and $X^{(t+1)} = f^{(t)}(X^{...
- 1,127
2
votes
0
answers
51
views
Subgraphs of random graphs with a given degree sequence
Let $\mathbf{d}=(d_1,\dots, d_n)$ be a given degree sequence with $3\leq d_i\leq \Delta$ for every $i$, where $\Delta$ is constant. Let $G(n,\mathbf{d})$ denote the random graph uniformly distributed ...
- 143
2
votes
0
answers
74
views
Cycle statistics of random endomorphism
Let $S$ be a set with $n$ elements and let $f:S\to S$ be a random function, chosen uniformly among the $n^n$ possibilities. Considering $f$ as a directed graph of constant outdegree $1$, i. e. with ...
- 3,017
2
votes
0
answers
83
views
Zero-One law for Hamiltonian path subgraphs of Hamming Distance Graphs?
$(\alpha,\beta,d)$-Hamming Distance Graph $G_d(\alpha,\beta)$ for $\alpha,\beta\in(0,1]$ is a graph on $2^d$ vertices $v_0,\dots,v_{2^d-1}$ with edges $(v_i,v_j)\in\mathcal E(G_d)$ iff $0<\sum_{t=1}...
- 13.9k
2
votes
0
answers
64
views
Transversal deviation in first passage percolation
Take the lattice $\mathbb{L}^{2}=(\mathbb{Z}^{2},\mathbb{E}^{2})$ with i.i.d. $\text{U}[0,1]$ weights on the edges, and the random variable $D$ giving the maximal transversal deviation of the geodesic ...
- 640
2
votes
0
answers
64
views
Largest eigenvalue of two types of slightly different random matrices
Consider two types of slightly different $n \times n$ symmetric random matrices $X$. The diagonal elements of $X$ are fixed as $1$. Suppose $\frac{k}{n} \to \alpha$ for some constant $\alpha\in(0,1)$.
...
- 272
2
votes
0
answers
93
views
Erdös-Renyi Model with prescribed subgraph
In the Erdös-Rényi model for random graphs there is a lot of results stating sharp phase transitions for the probability of a random graph to contain a fixed prescribed ...
- 2,630
2
votes
0
answers
69
views
What is the gap between the two defined distances from node to node in a random graph?
Give a sparse random graph $G=(V,E)$, every edge $(u,v)\in E$ is associated with a weight $w(u,v)$. We assume each $w(u,v)$ is geometrically distributed with parameter $p_{u,v}$. The weight of a path ...
- 321
1
vote
0
answers
68
views
A one-sided/monotone version of min/max-stable distributions -- does this have a name?
In a couple of papers I am working on (in random graph theory) I have encountered the following property of certain probability distributions, which I will describe shortly, and I am wondering if this ...
- 111
1
vote
0
answers
46
views
Diameter of component graph of uniform spanning forests on the amenable transitive graph with super polynomial growth
According to the paper Benjamini, Kesten, Peres, and Schramm - Geometry of the uniform spanning forest: transitions in dimensions 4, 8, 12 (Annals, 2004), the diameter of the component graph of the ...
- 41
1
vote
0
answers
82
views
Concavity of expected size of a maximum matching (in a bipartite graph) w.r.t. edge probability
Given a n*n bipartite graph where each edge (between any two nodes on the opposite side) is formed i.i.d. with probability $p$, can we show a concavity result on the expected size of a maximum ...
- 53
1
vote
0
answers
96
views
Limit of alternating sum of factorial moments which diverge
Consider the non-negative, integer valued random variable $X$, and its $i^{\text{th}}$ factorial moment $E_{i}[X]$. Then we have that
$$
P(X=0) = \sum _{i=0}^{\infty} \frac{(-1)^i E_{r}[X]}{ i!}
$$
...
- 640
1
vote
0
answers
167
views
Width of the critical window in a random graph
In an Erdős–Rényi random graph $G(n,p)$, the giant component emerges with thresholding function $p(n) = c/n$, where $c>1$.
When $c=1$, and $\lambda \in \mathbb{R}$, we can write or "...
- 640
1
vote
0
answers
78
views
Canonical representation of the a probability distribution for Hammersley Clifford Theorem
I'm reading the following paper
http://www2.stat.duke.edu/~scs/Courses/Stat376/Papers/GibbsFieldEst/BesagJRSSB1974.pdf
On page 7 they give the result that
$$Q(\textbf{x}) = \sum_{1 \leq i \leq n} ...
- 903
1
vote
0
answers
97
views
Longest close common subsequence but for continuous random variables
We have two copied sequences of correlated continuous positive random variables that are independent of each other $(X_{n})\perp(Y_{n})$ and equal in distribution $X_{n}\stackrel{dis}{=}Y_{n}$ for ...
- 5,474
1
vote
0
answers
87
views
Contiguity of uniform random regular graphs and uniform random regular graphs which have a perfect matching
Let us consider $\cal{G}_{_{n,d}}$ as the uniform probability space of d-regular graphs
on the n vertices $\{1, \ldots, n \}$ (where $dn$ is even). We say that an event $H_{_{n}}$ occurs a.a.s. (...
- 19
1
vote
0
answers
140
views
Count shortest path with different lengths in random graph
Let $G(n,p)$ be an Erdos-Renyi random graph on $n$ vertices with probability $p$, i.e. for each pair of vertices, they are connected directly by an undirected edge with probability $p$. Suppose we are ...
- 1,495
1
vote
0
answers
43
views
In weighed random graph where the edge weight is restricted to $[0,1]$, what are the usual assumptions of edge weight distribution?
In classic ER random graph, the edge distribution is Bernoulli. Given a weighted random graph where the edge weight is restricted in $[0,1]$, is there a canonical assumption of the weight distribution ...
- 272
1
vote
0
answers
109
views
Number of $H$-free graphs
Sorry if this is basic for MO. But the people at SE couldn't help me.
I'd like to get an estimate on the number of (labeled) $H$-free graphs on $n$ vertices, i.e. graphs in which no set of $|V(H)|$ ...
- 11
1
vote
0
answers
255
views
Multiple Bipartite graphs and matchings
I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...
- 903
1
vote
0
answers
188
views
Generating Conditional Random Graphs
Let $G(n,p)$ be the usual random graph on $n$ vertices with each edge existing independently with probability $p$ (no self loops , or double edges not are allowed). I would like to simulate the ...
- 4,952
0
votes
0
answers
69
views
Likelihood ratio of non-trivial cycles in an inhomogeneous random square lattice graph embedded on a toroidal surface
Consider a square lattice (random) graph $G$ embedded on a toroidal surface. Each edge $(i, j)$ of the graph has an associated likelihood probability $p_{ij}$. The probabilities $p_{ij}$ come from a ...
- 269
0
votes
0
answers
181
views
What to do when the second moment method does not provide a sufficient bound for $P(X=0)$
We have that for a real valued random variable $X$,
$$
P(X=0) \leq \frac{\text{Var}(X)}{\left(\mathbb{E}(X)\right)^2}
$$
known as Chebyshev's inequality. Consider a random variable $X \in \{0,1,2,\...
- 640
0
votes
0
answers
80
views
Not exactly directed percolation
Is the following problem known/well-studies? I'm looking for references or a name that I can look up.
I start with $N$ cell, each one divides into two cells, each one of the new cells either dies ...
- 371
0
votes
0
answers
69
views
Quasi-stationary measure on a finite graph equals stationary measure?
Assume the simple random walk $X$ on the graph $G(V,E)$, s.t. $G$ is simple, undirected, finite, connected and let $B \subset V$, s.t. $V\setminus B$ is connected. Let $\sigma_B$ be the quasi-...
- 71
0
votes
0
answers
320
views
Gromov-Hausdorff distance measure between minimum spanning trees
I am trying to compare minimum spanning trees through time. I have two questions:
1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...
- 1
0
votes
0
answers
216
views
Computation on Random Bipartite graphs
I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability ...
- 903
0
votes
0
answers
161
views
T. Lyons Criterion
Hello all,
I want to prove that any flow on the following tree must have an infinite energy.
The structure of the graph is (taken from R.Lyons and Y.Peres book)
"We’ll construct a tree $T$ embedded ...
- 1