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.
124 questions with no upvoted or accepted answers
2
votes
0
answers
69
views
Are two degree sequences compatible, for random simple graph generation?
Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...
- 1,444
2
votes
0
answers
212
views
Expansion of random subgraphs of a bi-regular bipartite graph
Let $G = (L, R, E)$ be a bi-regular bipartite graph, with $|L|=n$ and $|R| = C \cdot n$, where $C$ is a large constant. Let $d$ be its (constant) right-degree.
We know $G$ is a good spectral expander. ...
- 225
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
28
views
Edgeweight-Conditions for "Statistically Self-similar" Complete Weighted Graphs
Given a complete symmetric weighted graph with $n$ vertices, for such a graph there always exists a minimum spanning tree and, under the assumption of the uniqueness of that tree, the vertex degrees ...
- 13.2k
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
49
views
Size of the last non-empty $k$-core of a random graph
Given $n$ and $p$ for $G(n,p)$, how to find the distribution of the size of the non-empty $k$-core with largest $k$?
In particular, what is the probability (for any $n$ and $p$) that only $c$ ...
- 21
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
220
views
mixing time of random walks on dense Erdos Renyi graphs
Is there anything known about the mixing time of a simple random walk on an Erdos-Renyi graph with parameter $\langle n,d \rangle$ where $d=n^a (0<a<1 )$. I know about Reed et al and Benjamini ...
2
votes
0
answers
228
views
expected number of edges for fixed min cut
It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges.
Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ ...
- 21
2
votes
0
answers
76
views
How are Polynomials of Toric ideals Studied with Exponents as ST-cuts?
Topic: Toric ideals on Expected value of Structure Functions in Random Graphs
Goal: to understand the toric ideal where the exponents $h_i$ and $s_j$ are st-vertex-cuts of a digraph
\begin{equation}
...
- 143
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
2
votes
0
answers
67
views
"drift" of a random graph $G(n,p)$ with $p=\alpha\ln{n}/n$
Suppose $G\sim G(n,p)$ with $p=\alpha\ln{n}/n$ for some large constant $\alpha$. I wish to show a certain "drift" property of $G$, which can roughly be phrased as follows: if $u$ is "not that far" ...
- 221
2
votes
0
answers
163
views
Reachability in dynamic random graphs
There has been some advice on how to ask questions. So I reask my question.I have a problem related to graph theory, random graphs or random geometric graphs in special that really confuses me. ...
- 35
2
votes
0
answers
83
views
Can this application of the moment closure method to epidemics on networks be made rigorous?
Short version: Consider the SI model of infectious disease spread on a random graph $G$ with a given degree sequence. Let $j$ be a vertex and let $i$ and $k$ be two of its neighbors. If $G$ ...
- 462
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
101
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
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
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
1
vote
0
answers
75
views
Weak law for component count of Erdos-Renyi random graphs
Penrose and Yukich derive a weak law for functionals of binomial point processes, which implies a law of large numbers for the component count of random geometric graphs. Do similar results exist for ...
- 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
152
views
Matchings in random bipartite graphs
I was wondering if anyone could point me in the direction of a text or paper which would help deal with the following problem
Suppose i am given a $K_{\mathrm{log}(n)} \times K_{\mathrm{log}(n)}$ ...
- 903
1
vote
0
answers
82
views
Simulation of disassortative random graphs
Recently I have been trying to find a succinct algorithm for generation of disassortative networks. The best I have found is the algorithm by Newman described in his paper "Mixing patterns in networks"...
1
vote
0
answers
372
views
counting k-cliques not also (k+1) on random graphs
consider the set of graphs with $n$ vertices and exactly half of all $\binom n 2$ possible edges.
looking for a formula that counts the number of these graphs that have a $k$-clique but not a $(k+...
- 529