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.
335
questions
7
votes
2
answers
216
views
Evolution of the empirical mean of a list as we remove elements proportional to their value
Consider a list of $N$ integers $k_1,k_2,\dots k_N$, drawn independently from some distribution $P(k)$ with $k_i \geq 1$. We denote its mean with $\langle k\rangle=\sum_{k=1}kP(k)$. The first two ...
1
vote
0
answers
157
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 ...
0
votes
0
answers
45
views
Expected number of edges in the neighborhood of vertices in random graphs
Question:
given a vertex $v$ of a symmetric random graph $G$ without self loops and parallel edges, what is the expected number edges in the subgraph induced by the vertices $u\in G\setminus v:\ (u,v)...
3
votes
0
answers
136
views
Smallest dominating set
Given a graph $G$, we say $S$ is a dominating set if $S\cup \{N(x):x\in S\}=V(G)$. Let $d(n,k)$ be the smallest integer $s$ so that every $n$-vertex graph $G$ with minimum degree $k$ has some ...
1
vote
0
answers
77
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 ...
2
votes
0
answers
81
views
Do Fagin's zero-one laws hold on stochastic block model?
Let $n$ be a positive integer (the number of vertices), $k$ be a positive integer (the number of communities), $p = (p_1, . . . , p_k)$ be a probability vector on $[k] := \{1, . . . , k\}$ (the prior ...
7
votes
1
answer
135
views
Nearest neighbors on random complete graph
Consider the complete graph on $2n$ vertices, where the ${2n \choose 2}$ edges have distinct lengths in uniform random
order. So each vertex $v$ has a nearest neighbor $N(v)$, across the shortest ...
2
votes
2
answers
225
views
Finding an easy example applying the general Lovász local lemma
Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.
General Lovász local lemma: Consider a set $...
4
votes
1
answer
200
views
Erdős–Rényi random graphs — reproducing 2 inequalities
In Erdős and Renyi's 1959 paper On random graphs I
, I'm trying to reproduce, starting from Eq.\eqref{1} in their paper, the two inequalities that appear in Eq.\eqref{2}.
Eq.\eqref{1} is:
$$
P \le \...
0
votes
0
answers
55
views
Finding small connected subgraphs of a random regular graph
Fix parameters $m,f,b$. I do not believe it matters for the general form of the question, but in the problem I am examining $m,f,b$ are all powers of $2$ with $m \gg f > b$. For example $m=2^{25},f=...
1
vote
0
answers
51
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 ...
2
votes
2
answers
117
views
Example of random walk in a random environment (RWRE) saying things on the environment
I was wondering if anyone is aware of works/articles/examples where random walks in a random environment (RWRE) are actually used for obtaining information on the random environment.
To clarify a bit, ...
1
vote
0
answers
62
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 ...
0
votes
0
answers
44
views
A question related to contiguity of random regular graphs
I am looking for a reference for the following fact. Let $r\geq 3$ be constant, let $G(n,r-2)$ be a random (simple) $(r-2)$-regular graph and let $H(n)$ be an independent random Hamiltonian cycle (on ...
0
votes
0
answers
27
views
Do finite components get smaller as supercritical random graphs with an arbitrary degree sequence get denser?
I asked this question a few weeks ago on MSE but did not receive any responses so I am going to ask a related but more specific question here.
First some notation.
Let $\mathbb{G} = \mathbb{G}(n,\...
1
vote
0
answers
75
views
Graphon convergence of uniform weighted graphs
I have a question that I need at some point my research. Suppose that the upper-triangular entries of an $n\times n$ symmetric matrix $A$ are i.i.d. Uniform$(0,1)$. Does the weighted graph with ...
0
votes
0
answers
4
views
Statistics of connected-component sizes of minimum-weight $f$-factors in random planar geometric graphs
An $f$-factor is an $f$-regular subgraph with the same vertex set $V$ and a subset of the edges $E$ of some given undirected graph $G(V,E)$
Question:
what is known about the statistical properties of ...
0
votes
0
answers
96
views
Phase-transitions for a property of random bipartite graphs
Let $N_1$, $N_2$, and $k$ be positive integers. Let $V_1$ and $V_2$ be finite sets with $|V_i| = N_i \ge 1$. Consider a bipartite graph $G=(V_1,V_2,E)$ constructed as follows. For every $x \in V_1$, ...
1
vote
0
answers
52
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 ...
1
vote
0
answers
127
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$...
2
votes
1
answer
185
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
118
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
75
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 ...
0
votes
0
answers
42
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
279
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
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 ...
3
votes
0
answers
58
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
143
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
63
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 ...
7
votes
1
answer
365
views
What is this Ramsey problem?
Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
1
vote
1
answer
403
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
109
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
168
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
217
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
43
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
73
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
91
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!}
$$
...
2
votes
1
answer
94
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
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 ...
0
votes
0
answers
110
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
134
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
135
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
278
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 ...
6
votes
2
answers
605
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
334
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
138
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
181
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
465
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
160
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
498
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 ...