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.
319
questions
2
votes
1
answer
63
views
Connected components in random regular graphs
Suppose we take a random regular graph $G_{2n, r}$, where $n$ is large. Let us also assume that $r$ is fixed, (not dependent on $n$). Let's say that half of the vertices of the graph are colored black ...
- 1,223
1
vote
1
answer
83
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 $...
- 59
2
votes
0
answers
53
views
Random walks on randomly evolving graphs
I am interested in analyzing a random walk on a growing tree with vertices labelled on a tree with following properties.
The number of nodes at depth $k$ is a an exponential function of $k$. One can ...
- 121
1
vote
0
answers
109
views
Size of the maximum matching in random graph $G(n,p)$
a.a.s. Is there a lower bound of maximum matching size in random graph $G(n,p)$?
For example:
Theorem(Bollobas and Thomason). Let $y_n=2 n p-\log n-2 \log \log n$. Then
$$
\mathbb{P}(\mathbb{G}(n, p) \...
- 59
0
votes
0
answers
25
views
Asymmetric strictly balanced graphs
I am interested in the existence of strictly balanced, asymmetric graph with given number of vertices and edges.
A known result of Rucinski and Vince shows that for every $(v,e)$ with $1\leq v-1 \leq ...
- 123
5
votes
1
answer
192
views
Probability of the random graph on $2n$ vertices having exactly $n$ vertices with degree $\ge n$
Let $G = (V, E)$ be a uniform random graph on $2n$ labeled vertices and let $S \subseteq {V}$ be the set of vertices with degree $\ge n$. Then what happens to $\mathbf{P}(|S|=n)$ as $n \to \infty$?
...
1
vote
0
answers
39
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
48
views
What is the average degree of a node in a Barabasi-Albert network?
Consider a random network that is generated following the Barabasi-Albert model, i.e., the degree distribution of a node follows the distribution:
$$ p(k)=\frac{4}{k(k+1)(k+2)}.$$
For network of size $...
- 187
3
votes
0
answers
51
views
Minimum induced subtree cover number of a graph
For an arbitrary simple finite graph $G$, without multiple edges between any two nodes and without any loop, the minimum induced subtree cover number, which is denoted by $stc(G)$, is defined to be ...
- 4,688
2
votes
0
answers
132
views
Union of two copies of uniform spanning forest on $\mathbb{Z}^3$ is transient? [closed]
Let $G$ be the (random) graph which is the union of two independent copies of the uniform spanning forest on $\mathbb{Z}^3$.
Question: Is (the simple random walk on) $G$ transient almost surely?
- 41
1
vote
1
answer
53
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 ...
- 115
0
votes
0
answers
92
views
An unnamed (perhaps?) graph theory problem
We create a graph weighted $G_0$ given a set of nodes and a function $f(v_x, v_y, G_i) $ that calculates the edge weight between the nodes within $G_0$ that's dependent on the global graph structure. ...
0
votes
1
answer
217
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 ...
- 11
1
vote
0
answers
81
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
4
votes
1
answer
91
views
Quasi-random vs pseudo-random graphs
My question is somehow concerning terminology on extremal graph theory.
Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that ...
- 1,453
6
votes
1
answer
154
views
Expected doubling constant of a random Erdős–Rényi graph
Consider the $G(n,p)$ random graph model where $n$ is a ``large'' positive integer and $p\in (0,1)$. We may equip every realized random graph $G$ with its shortest path distance, making it into a (...
- 4,881
0
votes
0
answers
38
views
Hyperbolic random geometric graphs with less clustering
The hyperbolic random geometric graph $G_{\mathbb{H}}$ consists of a $N$ uniformly random points (within a disk of radius $R$ centred at the origin) of the hyperbolic plane $\mathbb{H}$, connected ...
- 532
1
vote
0
answers
57
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
85
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!}
$$
...
- 532
0
votes
0
answers
69
views
Reference request: Spectral gap for cubic random graphs
I gather the following is well known:
Fact: There exists some $\epsilon>0$ such that with probability approaching $1$ as $n\to\infty$, a random cubic (i.e. $3$-regular) graph on $n$ vertices has ...
- 51
2
votes
1
answer
84
views
Lower bound on the number of balanced graphs
Let $\alpha>1$ be a constant and define $B_n$ as the number of (labeled) balanced graphs with $n$ vertices and $\left\lceil \alpha n\right\rceil $ edges. The paper Strongly Balanced Graphs
and ...
- 123
0
votes
0
answers
66
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 ...
- 259
0
votes
0
answers
88
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,\...
- 532
6
votes
0
answers
99
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 ...
- 5,507
1
vote
0
answers
101
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 "...
- 532
1
vote
1
answer
214
views
What is the exact definition of a sharp transition?
In "Sharp threshold phenomena in statistical physics", H. Duminil-Copin, Japanese J. of Math. 14, 2019, a sharp transition of a boolean function is defined as follows:
A sequence of ...
- 532
0
votes
0
answers
65
views
Vertex percolation on bipartite graphs
This is essentially a repost of this math overflow post since it didn't get any reception.
Let $G = (V \cup C, \mathcal{E})$ be $(\gamma_V, \delta_A, \gamma_B, \delta_B)$-left-right-expanding with ...
- 1
6
votes
2
answers
495
views
Threshold function for a graph not being planar
A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property.
It is well-known that every ...
- 493
8
votes
2
answers
267
views
Selection of an n-vertex graph at random
Let's say I want to select, at random, an $n$-vertex graph $G=(V,E)$ from the set of all $n$-vertex graphs.
One way to do this would be to take the empty graph on $n$ vertices and then add each ...
- 151
1
vote
1
answer
122
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$ ...
- 2,382
3
votes
1
answer
164
views
Discrepancy of random bipartite graphs
This is a crosspost from MathStackExchange (original question).
Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$).
Define a ...
- 2,382
10
votes
1
answer
417
views
(Asymmetric) matrix power series in closed form: $\sum_{i=0}^{\infty} A^i \left(A^i\right)^{\top}={?}$
Let $A\in \mathbb{S}^{N\times N}$ be a symmetric, real and stable matrix, i.e., $\rho(A)<1$, where $\rho(A)$ stands for the spectral radius of $A$. Then, $$\sum\limits_{i=0}^{\infty} A^{2i}=\left( ...
- 555
2
votes
2
answers
124
views
Which infinite random graphs with percolation threshold $p_c=0$ are transient?
I am interested in long-range percolation models with heavy-tailed degree distributions such as DHH13, GLM21, Y6. The simplest example is scale-free percolation in which vertices are elements $\mathbb{...
1
vote
1
answer
249
views
Hammersley-Clifford theorem
The paper spatial interaction and the statistical analysis of lattice systems by Besag (1974) presents an alternative proof for the Hammersley-Clifford theorem.
In order to prove the HM theorem, Besag ...
- 113
1
vote
0
answers
54
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 ...
- 532
5
votes
3
answers
453
views
Probability of an edge in a random graph
Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence.
...
- 1,345
3
votes
1
answer
139
views
The most pseudorandom subgraph of a dense graph
A bipartite graph $(A,B)$ is $(p, \beta)$-jumbled if for all subsets $A'\subseteq A$ and $B'\subseteq B$ we have that $\left|\mathrm{E}(A',B')-p|A'||B'|\right|\leq \beta \sqrt{|A'||B'|}$. A easy ...
- 785
2
votes
1
answer
142
views
Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?
A uniformly random $r$-regular bipartite graph on $n$ vertices is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular ...
- 153
2
votes
1
answer
79
views
Are the eigenvalues of the 1D lattice with random weights known?
Consider the adjacency matrix $\mathbf{A}$ of a one dimensional lattice of size $N$. That is, $A$ is a $N\times N$ matrix with $A_{ij}=1$ if vertex $i$ adjacent to vertex $j$ (there exists an edge ...
- 187
1
vote
1
answer
117
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
0
votes
0
answers
139
views
Expected chromatic number of random subgraph
Let $G$ be a fixed graph and let $G_p$ be a random subgraph of $G$ where every edge is kept independently with probability $p$. According to [1] and [2] the paper [3] proves
$$
\mathbb{E}[\chi(G_p)] \...
1
vote
0
answers
19
views
Is homomorphism density of partially labeled graph continuous with respect to cut metric
Let $F=(V, E)$ be a finite simple graph on $n$ vertices with two labelled vertices, say $x, y$. Let $W:[0, 1]^2\to [-1, 1]$ be symmetric function. Lov'asz's book (Large Networks and Graph Limits) ...
- 351
1
vote
0
answers
65
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} ...
- 893
4
votes
0
answers
278
views
Research on graph theory
I am interested in graph theory. My background is mainly algebraic. I have been researching algebraic geometry for five years so I assume that the transition to the graph theory realm shouldn't be so ...
- 439
1
vote
1
answer
91
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$, ...
- 587
6
votes
1
answer
429
views
Graphs resembling the math genealogy graph must have concentration in a small number of families?
I was talking with a non-mathematician the other week at a workshop about the fact that many mathematicians, like myself, are indexed in the math genealogy database. We talked a little about how many ...
- 3,152
1
vote
0
answers
84
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 ...
- 2,770
3
votes
0
answers
111
views
Random graph - probability threshold for any linear size set to contain a fixed clique
Let $t\geq 3$ and $0<\varepsilon<1$ be fixed. Denote by $K_t$ the clique on $t$ vertices, and by $G_{n,p}$ the binomial random graph.
Question:
Is the threshold for the probability that "...
1
vote
0
answers
83
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,058
0
votes
0
answers
71
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. (...
- 9