Questions tagged [random-graphs]
The study of probability distributions over graphs. For example, the Erdős–Rényi model where each edge occurs independently with equal probability.
346 questions
1
vote
1
answer
128
views
Random graph uniformly sample from the special graphs
We know two basic random graph models:$G(n,p)$ and $G(n,m)$. $G(n,m)$ consists of all graphs with $n$ vertices and $m$ edges, in which the graphs have the same probability. We know that $G(n,p)$ and $...
- 91
1
vote
1
answer
85
views
Probability of randomly finding a loop in a (directed) Bernoulli random graph
This problem is inspired by an activity at work, where each person was tasked with introducing another person in the onboarding class, sequentially.
Problem Statement
Given $N$ people. For each pair ...
- 257
1
vote
1
answer
545
views
Vertex degree on random graphs
Let $p = d/n$ with $d$ constant. How do I prove that, with high probability, $G_{n,p}$ contains a vertex of degree at least $(\log n)^{1/2}$,
where $G_{n,p}$ is a graph with $n$ vertices and the ...
- 21
1
vote
1
answer
152
views
Discrepancy of random bipartite graphs (2)
This question is a modification of the one asked here, which turned out to ask for something too strong to be true.
Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ ...
- 3,446
1
vote
1
answer
132
views
how to compute the probability that a random graph has two components? [closed]
This question is an example in the book Introduction to Probability Models 11th edition (Sheldon M.Ross). 3.6.2 A random graph:
A graph has $V$ nodes and a set $A$ of pairs of nodes in $V$ called arcs....
- 113
1
vote
1
answer
124
views
Empirical degree distribution of random $n$ vertices labeled rooted tree converges to Poisson distribution
I am reading Louigi's lecture note on random trees and graphs here. I get stuck on part (b), Exercise 1.2.3 on page 19, which says the following:
Let $T_n$ be uniformly drawn from $\mathcal{T}_n$, ...
- 715
1
vote
1
answer
192
views
Survey/references on random geometric $K$-NN – $K$-nearest-neighbour graphs?
[Edit:] Some related info on number of connected components of NN-graphs can be found here: https://cstheory.stackexchange.com/a/47037/2408
Sample $N$ points in $\mathbb{R}^d$ from some distribution $...
- 24.9k
1
vote
1
answer
436
views
Size of minimum cut in random graph
Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) The score of each ...
- 1,209
1
vote
1
answer
104
views
Limit of normalized sum of Dirac measures at first $\lfloor p/2\rfloor$ eigenvalues of the sample covariance matrix, with Marcenko-Pastur assumptions?
Let $\lfloor{*}\rfloor$ denotes the nearest integer $\le *$. I'm asking myself the question what's the limit of the part of the empirical spectral distribution corresponding to the first $\lfloor{p/2}...
- 1,465
1
vote
1
answer
265
views
Continuum percolation in 1d
What is known about continuum percolation in 1d?
By this, I mean, for $d \in \mathbb{N}$, the Poisson-Boolean model of disks of radius $r_0 \in \mathbb{R}$ with centres arranged randomly in $[0,1]^{d}...
- 640
1
vote
1
answer
94
views
What is the expected distance between the sides of a random subgraph of the grid?
Let $G$ be the $n \times n$ grid, in which each vertex is connected to the vertices above it, below it and on either side. Let $G_p$ be the random subgraph of $G$ obtained by keeping each edge with ...
- 1,633
1
vote
1
answer
188
views
KPZ relation $\chi = 2 \xi -1$ in a random geometric graph
If I have $n$ points uniformly distributed on the surface of a torus, and form a graph by adding an edge between pairs whenever they are within a unit distance (induced by the Euclidean metric), I ...
- 640
1
vote
1
answer
1k
views
An explicit formula for the number of different (non isomorphic) simple graphs with $p$ vertices and $q$ edges
I would like to know if there is an explicit formula for the number of different (non isomorphic) simple graphs with a given number of vertices $p$ and edges $q$, and if yes what is it.
Trying to ...
- 29
1
vote
1
answer
168
views
Vertex reachability in random graph
Given $n$ vertices, one of which is $z$. Consider a uniform random tournament: Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $...
- 1,209
1
vote
2
answers
2k
views
Expected matching in a bipartite graph
Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
- 903
1
vote
1
answer
420
views
Poisson approximation of random sub-graphs
I add the edges of $G(n)$ the complete graph on $n$ vertices one by one, at random and without replacement, and denote by $G(n,m)$ the resulting Erdos Renyi random graph process. At step $m$ in the ...
- 468
1
vote
1
answer
223
views
PR[$\lambda_2 > x$] in $G_{np}$ model
Hi!
Does anyone know of any statement relating the probability that the second largest eigenvalue of a random graph is bigger than $x$ to the parameter $p$ in the $G_{np}$ model?
- 239
1
vote
0
answers
24
views
Vertex coloring of the Rado graph
Is there a reference for the following fact about the Rado graph (the random countable graph) which came up in an answer to this question?
If the vertices of the Rado graph $G=(V,E)$ are colored with ...
- 13.4k
1
vote
0
answers
149
views
Inequalities in the classic proof of perfect matching in Erdős–Rényi graph
I am checking the classic paper by Erdős and Rényi, "On the existence of a factor of degree one of a connected random graph" with the link here. I am curious about the computation of the ...
- 97
1
vote
0
answers
89
views
Gamma and Poisson distributions and their relations to the randomness
I'm reading the following paper:
https://academic.oup.com/bioinformatics/article/32/1/122/1743683
and in Figure 3 (Section 4.4) the authors have shown some vertex degree distributions:
enter image ...
1
vote
0
answers
99
views
Szemeredi Regularity Lemma - Reasonable Bounds
Recently, I came across the wonderful Szemeredi regularity lemma and I was wondering. Are these "natural/reasonable/standard" examples of random graphs families, for which the number of $\...
- 5,405
1
vote
0
answers
164
views
Locally "unshortable" paths in graphs
Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
- 24.9k
1
vote
0
answers
92
views
Diameters of random bipartite graphs
Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
- 11
1
vote
0
answers
54
views
Controlling quantity related to Laplacian pseudo-inverse of Erdős–Rényi graph
Consider an $n$-node undirected graph $G = (V, E)$ equipped with weights $W$. Let $L$ be the weighted graph Laplacian matrix, i.e. $L_{ij} = -W_{(i,j)}$ for $(i,j)\in E$ and $L_{ii} = \sum_{j:(i,j)\in ...
- 11
1
vote
0
answers
104
views
Benjamini-Schramm convergence: convergence on metric balls implies weak convergence?
In the famous paper by Benjamini-Schramm 2001, they consider the space of rooted graphs with uniformly bounded degrees, this space modulo rooted graph isomorphism is denoted by $\mathcal X$.
This ...
- 502
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
132
views
Random graphs constructed by many large matchings
Let $G_{n,d}$ be $d$-regular random graph. We know that for $d \geq 3$, $G \in G_{n,d}$ a.a.s. has a $1$-factorisation when $n$ is even.
So, the resulting graph that obtained from randomly choosing $d$...
- 91
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
115
views
Probability of (single) connecting paths in Erdos-Renyi graphs
In an Erdos-Renyi graph with labeled vertices in $(1, ..., N)$, and for any pair of vertices $(r, s)$ with $r < s$ and a length $l$ in $(1, ..., s-r)$, I am looking for the probability of
there ...
- 129
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
64
views
Angles between edges of a geometric graph and graph invariants
Are there any clever ways in which the angles between edges in a geometric graph are encoded in the graph spectrum, or another object associated with the graph?
I'm interested to see what else is ...
- 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
88
views
In percolation on a lattice, how is "infected" status correlated for points in a region around the origin?
Consider independent bond percolation on $\mathbb{Z}^2$, with $p>p_c$ so that the process is supercritical. For any site $x$ let $Y_x$ be the indicator of $x$ belonging to the infinite open cluster....
- 1,068
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
105
views
Understanding the finale of the proof of Komlós' and Szemerédi's limit distribution of Hamiltonian random graphs
My question is about the end of the proof of Theorem 1 in [Komlós, Szemerédi (1983)], more precisely the arguments in Subsection 2.3. Let me state the beautiful theorem I am trying to understand in my ...
- 71
1
vote
1
answer
286
views
Bound on $i$th largest eigenvalue in a large Erdos-Renyi graphs
Typical magnitude of $i$th largest eigenvalue of an Erdos-Renyi random graph seems to decay at least exponentially with $i$. Is there an analytic expression for the constant in the exponent, or a nice ...
- 2,442
1
vote
0
answers
72
views
Another betweenness centrality measure: neighbourhood centrality
Among the many centrality measures that I have heard of, I miss the following (but maybe I'm just blind).
Consider a graph $G$ with $k$ connected components $G_i$ of size $|G_i|$. The number of node ...
- 9,720
1
vote
0
answers
40
views
Eigenvalue bounds of a random graph with a clique
I'm looking into this paper and having some problems proving (ii) of proposition 2.1. I don't quite understand how the lemma is proved. I also read the original paper where the lemma comes from but ...
- 11
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
29
views
Bound on the number of bridges between vertices in a sampled subgraph
I am researching connectivity in sampled subgraphs and have come across the following problem.
A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ ...
- 175
1
vote
0
answers
61
views
$\exp(-Cn^{\epsilon})$ estimate for probability of Brouwer-Haemers condition in Erdos-Renyi-like random graph
For any $n$-vertex graph $G$, we have the inequality $\lambda_i^{L_G}\geq D_i-i+2,$ where $L_G$ denotes the Laplacian of $G$ and $\lambda_i^{L_G}$ denotes the $i^\text{th}$ largest eigenvalue and $D_i$...
- 276
1
vote
0
answers
209
views
Characterization of k-walk-equivalent graphs
Let $G=(V,E)$ be an undirected graph. A walk of length $k$ in $G$ is a sequence of vertices $v_1,v_2,\ldots,v_{k+1}$ in $V$ such that $(v_i,v_{i+1})\in E$ for each $i=1,2,\ldots,k$.
Call two graphs $...
- 493
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
79
views
Generation of randomly looking graph coordinates
Let $G$ be some connected graph. We pick randomly $k$ distinct vertices $l_1, l_2, \cdots l_k \in V(G)$. We call them the landmarks.
We define $d(u,v)$ to be the length of the shortest path between ...
- 323
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
68
views
Almost all graphs have an induced path on four vertices [closed]
Is this statement true? If yes, I would like to be pointed to references containing its proof.
- 327
1
vote
0
answers
166
views
Expected number of perfect matchings in bounded degree bipartite graphs
Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$.
What is the expected number of perfect matching a graph in $\mathcal C_{n,n,\...
- 13.9k