# 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
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 $...

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 ...

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) \...

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 ...

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 ...

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 $...

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 ...

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?

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 ...

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 ...

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 ...

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 ...

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 (...

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 ...

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 ...

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!}
$$
...

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 ...

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 ...

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 ...

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,\...

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 ...

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 "...

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 ...

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 ...

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 ...

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 ...

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$ ...

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 ...

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( ...

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 ...

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 ...

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.
...

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 ...

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 ...

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 ...

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....

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) ...

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} ...

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 ...

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$, ...

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 ...

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 ...

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....

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. (...