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.
354 questions
1 vote
1 answer
103 views
Intersection of a set and a sphere on a Ramanujan graph
Let $G$ be a $d$-regular Ramanujan graph on $n$ vertices. Fix a subset of vertices $S \subseteq V(G)$, and let $v_0$ be a uniformly random vertex in $G$. I'm interested in the expected number of ...
- 377
4 votes
0 answers
208 views
Query in application of Russo's formula in a paper by H.Duminil-Copin and Tassion
I was reading H.Duminil-Copin's and Tassion's famous paper A New Proof of the Sharpness of the Phase Transition for Bernoulli Percolation and the Ising Model and I had a query about the application of ...
9 votes
1 answer
727 views
How random are Fraïssé limits really?
Up until now, I had just had the intuition that Fraïssé limits were in some sense "random" probabilistic objects in the same manner as the Rado graph. I was told recently that this intuition ...
- 563
2 votes
0 answers
132 views
Captured Killer numbers of a graph
I thought of a fun class of problems in graph theory which I'll call "captured killer" problems. Apologies if this concept already exists under another name! I started thinking about this ...
- 211
1 vote
0 answers
59 views
Expectation of a functional in a canonical ensemble of weighted bipartite graphs
Let $Q=(Q_{ij})_{1\le i,j\le N}$ be a nonnegative $N\times N$ matrix (investor $i$ investing a dollar amount in asset $j$). From a given matrix $Q^\star$ (from a financial dataset), let $$ r_i^\star=\...
- 670
0 votes
0 answers
116 views
A question on the expander graphs claims by Kolmogorov-Bardzin
According to Gromov-Guth (Generalizations of the Kolmogorov-Barzdin embedding estimates), Kolmogorov-Bardzin proved ''essentially'' the following theorems: Theorem 1. If $\Gamma$ is a graph of degree ...
- 1
1 vote
1 answer
75 views
Uniqueness and constancy of infinite black components in i.i.d. vertex percolation on infinite graphs
I'm studying i.i.d. vertex percolation on infinite graphs. Specifically, let $G = (V, E)$ be an infinite connected graph of bounded (finite) degree, where each vertex is independently colored black ...
5 votes
0 answers
123 views
second largest eigenvalue and phase transition of graphs
I study (several) families of finite, directed graphs $(G_n)_{n\ge 0}$, where $G_0$ is "very complicated" and $G_n$ has no edges at all for $n$ large enough; in between, there appears to be ...
- 2,359
2 votes
1 answer
142 views
Distribution of the maximum degree in a Barabási–Albert Random Graph?
The Barabási–Albert model has a degree distribution \begin{equation} P(k) = \frac{4}{k(k+1)(k+2)}, \end{equation} whose tail approximately scales as $k^{-3}$, and for finite size networks the largest ...
- 304
5 votes
2 answers
296 views
Extremal combinatorics results matched closely by probabilistic constructions
There are numerous examples of extremal* results in combinatorics that are matched asymptotically by some probabilistic construction, but with some gap, often quite substantial. Think for example of ...
- 284
2 votes
0 answers
141 views
Expected size of Nearest Neighbor Cliques in Random Point Sets
If we are given a random i.i.d. finite pointset in some metric space we can define a graph $G(V,E,k)$ whose vertices represent the points and whose edges are adjacent to a pair of vertices $u$ and $v$ ...
- 13.9k
0 votes
0 answers
57 views
Scaling in unbalanced gale–shapley proposals
Let $G = (A, B, E)$ be a bipartite graph representing a matching market with $|A| = n+1$ and $|B| = n$. Each vertex $a \in A$ has a preference list that is a uniformly random permutation of $B$, and ...
user551082
2 votes
0 answers
75 views
Threshold for generic universal rigidity of Erdős–Rényi random graphs?
Let $G(n,p)$ denote the Erdős–Rényi random graph model, with $n$ vertices and edge probability $p \in (0,1)$. (Q1) Is there a threshold $p_c$ such that $G \sim G(n,p)$ with $p > p_c$ is ...
- 893
2 votes
1 answer
85 views
Randomising weighted bipartite networks
Squartini et al. have shown how to randomise weighted networks while preserving the expected value of local properties (i.e. sampling from the canonical ensemble preserving e.g. the strength sequence, ...
- 670
1 vote
0 answers
82 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 ...
- 15.1k
2 votes
0 answers
207 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 ...
- 107
2 votes
0 answers
95 views
Subgraphs of random graphs with a given degree sequence
Let $\mathbf{d}=(d_1,\dots, d_n)$ be a given degree sequence with $3\leq d_i\leq \Delta$ for every $i$, where $\Delta$ is constant. Let $G(n,\mathbf{d})$ denote the random graph uniformly distributed ...
- 235
0 votes
0 answers
41 views
Chaining random graph thresholds
I've found myself needing to prove a certain graph theoretic property has a probabilistic threshold in the Erdos-Renyi model. The problem is that this property is not edge monotone in general. It is, ...
3 votes
0 answers
114 views
Can we remove the restriction on a parameter in Talagrand concentration inequality?
Recently I am trying to use Talagrand concentration inequality to do something on graphs. I find a version from the book of Molloy and Reed ''Graph Colouring and Probabilistics Method''. I attached a ...
- 1,210
2 votes
0 answers
172 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 ...
5 votes
1 answer
475 views
Are directed graphs with out-degree exactly 2 strongly connected with probability 1?
Consider a directed graph with out-degree exactly two with $n$ vertices $v_1, v_2 \cdots v_n$ that is constructed as follows: For each vertex $v_i$, one chooses uniformly at random two (not ...
- 8,395
2 votes
1 answer
122 views
Positive-semidefiniteness of Laplacian of signed graph
Consider a signed complete graph $G(E,V)$ with adjacency $A_{ij}\in\{-1,+1\}$. Define the Laplacian matrix as $L:=D-A$ where $D$ is the degree matrix, $D_{ii}=\sum_{j\neq 1}A_{ij}$. my question. If $\...
- 405
2 votes
0 answers
707 views
Average number of cycles in a directed regular graph?
A directed random regular graph is a graph where all vertices have exactly $d_{\rm in}$ edges going in and $d_{\rm out}$ going out. If the graph is undirected, i.e. all vertices have degree $d$, then ...
- 311
4 votes
0 answers
120 views
Is the probability distribution of a graphon given as a graph limit computable?
Let $G_i$ be a sequence of finite graphs that is Cauchy in the space of graphons. That is, for every $\epsilon \in \mathbb Q_+$ there is a $N \in \mathbb N$ such that $$\forall n, m > N. \delta_\...
- 7,138
1 vote
0 answers
143 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 $\...
- 4,942
7 votes
2 answers
305 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 ...
- 304
1 vote
0 answers
197 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 ...
- 26.3k
0 votes
0 answers
89 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)...
- 13.9k
3 votes
0 answers
190 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 ...
- 3,509
1 vote
0 answers
141 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
2 votes
0 answers
115 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 ...
- 131
7 votes
1 answer
224 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 ...
- 486
2 votes
2 answers
515 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 $...
- 1,210
4 votes
1 answer
270 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 \...
- 43
1 vote
0 answers
91 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
2 votes
2 answers
271 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, ...
- 59
1 vote
1 answer
485 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 ...
- 564
0 votes
0 answers
100 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 ...
- 235
2 votes
0 answers
145 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 ...
- 273
1 vote
0 answers
109 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
181 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$...
- 111
2 votes
1 answer
392 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,417
1 vote
1 answer
174 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 $...
- 111
5 votes
1 answer
388 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$? ...
- 798
1 vote
0 answers
65 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
3 votes
0 answers
87 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,796
2 votes
0 answers
172 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
126 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 ...
- 277
8 votes
1 answer
478 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$ ...
- 3,509
1 vote
1 answer
663 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