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.
0
votes
0answers
39 views
The fraction of vertices in the giant component as a function of $\lambda$
In the Erdos-Renyi random graph $G_{n,p}$ the fraction of vertices in the giant component, $v$, and the parameter $\lambda$, where $p = \lambda / n$, are well known to be related by $1-v = \exp(-\...
1
vote
1answer
66 views
Random Optimization on Graphs: Minimum Cut
Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...
6
votes
0answers
100 views
Collecting proofs of the birth of the giant component
I want to collect different proofs of Erdös-Rényi result on the double jump of the largest connected component on $G(n,p)$ (or in $G(n,M)$.
I know the original proof of Erdös-Rényi, the proof that ...
2
votes
1answer
132 views
non-backtracking random walk in regular (finite) graphs
I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a ...
4
votes
1answer
143 views
Component properties in Euclidean graphs with distance threshold
In the context of Euclidean graphs with vertices randomly embedded in either a 2D plane (for instance square with length $L$) or in 3D (similarly, cube of side $L$), where an edge between two given ...
12
votes
3answers
498 views
A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?
In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...
0
votes
0answers
45 views
Component size distribution in small Erdos-Renyi networks
I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10.
I would like to know the probability a random node is in a component of size $m$.
It's ...
0
votes
1answer
90 views
The expected value of common neighbors on a random regular graph
Given a random $d$-regular graph on $n$ nodes, what is the expected number of common neighbors between two nodes?
I don't know if it is as simple as just assuming that each neighbor of the first node ...
3
votes
1answer
122 views
What is the Essential Difference Between Random Matrices and Random Graphs?
I have the impression, that random graphs and random matrices seem to be perceived and treated as separate areas of interest; I'm not an expert in either of the subjects, so maybe my impression is ...
1
vote
0answers
39 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$...
1
vote
0answers
103 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 $...
2
votes
0answers
42 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$ ...
2
votes
1answer
65 views
References on the structure of bond percolation on the (finite) 2D-grid in the sub-critical regime (e.g p=1/10)
Would appreciate references to the most up-to-date results for the structure of bond percolation on the (finite) 2D-grid in the sub-critical regime (e.g, $p=1/10$).
Thank you.
5
votes
2answers
174 views
expected length of a largest cycle in regular graph
Consider a simple random regular graph $G_d(n)$ with $d=2$ (that is, I select a $2-$regular graph from the set of all $2-$regular graphs on $n$ vertices, uniformly at random).
It is clear that this ...
1
vote
1answer
106 views
Uniform sampling of random connected graph with given number of vertices/edges
I am looking for algorithms for the exact uniform sampling of connected labelled graphs with $n$ vertices and $m$ edges. By "exact" I mean that every such graph should be generated with precisely (not ...
0
votes
0answers
16 views
Distribution of maximum-weight matching in a random graph
Consider the $k$-th power of a non-directed cycle graph with $n$ vertices $C_n^k$. In other words vertex $i \in \{1, ..., n\}$ is connected to vertices $i-k$ to $i+k$ (modulo $n$). Here is an Example ...
4
votes
2answers
326 views
Expected global clustering coefficient for Erdős–Rényi graph
What is the expected global clustering coefficient $\mathbb{E}[C_{GC}]$ for the Erdős–Rényi random graph (ER-graph) $\mathcal{G}(n,p)$ (expectation is over the ensemble of all ER-graphs) as $n \...
0
votes
1answer
88 views
KPZ relation $\chi = 2 \xi -1$ in a random geometric graph
If I have $n$ points uniformly distributed on the surface of a torus, and form a graph by adding an edge between pairs whenever they are within a unit distance (induced by the Euclidean metric), I ...
1
vote
1answer
179 views
Bounds on degrees of minors obtained by edge contractions of regular graphs
Given a connected $d$-regular graph $G=(V,E)$, generate a sequence of minors by performing only edge contractions and loop deletions (as, e.g., in Karger's algorithm) until the graph collapses to a ...
0
votes
0answers
63 views
Not exactly directed percolation
Is the following problem known/well-studies? I'm looking for references or a name that I can look up.
I start with $N$ cell, each one divides into two cells, each one of the new cells either dies ...
2
votes
1answer
206 views
Longest Path in a Directed Graph with Specified Number of Edges
Let $G$ be a directed graph that has $n$ nodes and is strongly connected. Define a random path as the following: Pick two vertices uniformly at random and find the shortest path going from one vertex ...
2
votes
0answers
49 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)$.
...
4
votes
1answer
110 views
Distribution of eigenvectors and eigenvalues for random, symmetric matrix
Consider two simple, undirected graphs with adjacency matrices ${\bf A}$ and ${\bf A'}$. Let ${\bf P} = {\bf A'} - {\bf A}$. Thus, ${\bf P}$ is symmetric and always 0 along the diagonal.
Let $f({\bf ...
1
vote
0answers
39 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 ...
3
votes
2answers
162 views
Largest eigenvalue of the adjacency matrix of weighted random graph
I find the theorem for largest eigenvalue of the adjacency matrix of ER random graph in here https://arxiv.org/pdf/math/0106066.pdf. The adjacency matrix is a symmetric random matrix s.t. diagonal ...
3
votes
0answers
82 views
Largest eigenvalue divided by $n$
Let $X$ be an $n\times n$ symmetric random matrix whose diagonal is fixed as $1$, and every element in the upper triangle (excluding the diagonal) is drawn from Bernoulli($p$). The elements in the ...
1
vote
0answers
29 views
Sampling non-isomorphic Moore automata
Consider the set of Moore machines with input alphabet $A$, output alphabet $B$, and state set $S$. Let $\langle f, g \rangle$ be a machine with transition function $f : A \rightarrow S \rightarrow S$ ...
5
votes
1answer
298 views
What is the chromatic number of the Erdős–Rényi graph G(n,d/n) when d < 1?
What is the chromatic number of the ER graph $G(n,d/n)$, when $d < 1$ (there exist expressions for $d > 1$, but what if the graph is super sparse?). Here $n$ is the number of vertices and $d/n$ ...
1
vote
1answer
263 views
An explicit formula for the number of different (non isomorphic) simple graphs with $p$ vertices and $q$ edges
I would like to know if there is an explicit formula for the number of different (non isomorphic) simple graphs with a given number of vertices $p$ and edges $q$, and if yes what is it.
Trying to ...
2
votes
1answer
113 views
Minimum dominating sets in tournaments
It is known that in any tournament with $n$ vertices, there is a dominating set of size no more than $\lceil \log_2 n\rceil$. (See Fact 2.5 here.)
What about when the tournament is chosen ...
5
votes
0answers
82 views
Long loops in critical random graphs
A simple calculation seems to show that the expected number $X_k$ of loops of length $k$ in a critical Erdös-Renyi random graph $G(n,n^{-1})$ is approximately given by
$$ \mathbb{E} X_k=\frac1{2k}{e^...
13
votes
1answer
334 views
When is the union of a graph and a random permutation thereof connected?
First things first: in what follows, a "random permutation" of a set $\Omega$ with $n$ elements does not necessarily mean an element chosen uniformly at random from $\textrm{Sym}(\Omega)$. Rather, and ...
3
votes
2answers
187 views
Conditional probability that a random spanning tree contains the edge e
Let $G$ be a connected simple graph with two distinct edges $e,f \in E(G)$. Choose a random spanning tree $T\subseteq G$, my question is whether there are any known upper bound for the following
\...
20
votes
2answers
421 views
Do these polynomials have alternating coefficients?
In answering another MathOverflow question, I stumbled across the sequence of polynomials $Q_n(p)$ defined by the recurrence
$$Q_n(p) = 1-\sum_{k=2}^{n-1} \binom{n-2}{k-2}(1-p)^{k(n-k)}Q_k(p).$$
Thus:
...
7
votes
2answers
411 views
Edge probability for connected Erdős–Rényi model
Consider the Erdős–Rényi model $G_{n,p}$ with corresponding probability measure $\mathbb{P}_{n,p}$. For any two vertices $x,y$, $\mathbb{P}_{n,p}[E_{x,y}]=p$, where $E_{x,y}$ is the event that there ...
1
vote
1answer
86 views
Vertex reachability in random graph
Given $n$ vertices, one of which is $z$. Consider a uniform random tournament: Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $...
2
votes
1answer
102 views
Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$
Let $G=(V,E)$ be a simple undirected graph. Define an mmd$k$s in $G$ (for 'maximal minimum degree $k$ subset') to be any subset $S$ of $V$ such that
the subgraph induced by $S$ in $G$ has minimum ...
1
vote
0answers
63 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 ...
1
vote
0answers
60 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 ...
3
votes
1answer
96 views
Threshold for appearance of a cycle
I am interested in a random graph $G\sim G(n,p)$. I know that if $p<<1/n$, then $G$ will be a forest. I happen to be interested in the boundary case where $p=c/n$, where $c<1$ is a constant....
8
votes
0answers
182 views
Stepanov phase transition in random graph
Consider the classical random graph model G(n,p), with p=c/n, as proposed by Erd\"os and R\'enyi.
At this scaling, the most prominent feature is arguably the abrupt change of the topology that the ...
2
votes
1answer
86 views
zero-one law in bipartite random model $G(n,n,p)$
Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has
$$\lim\limits_{n \rightarrow \infty}...
0
votes
1answer
285 views
Random graphs- Erdos and Renyi 1959 paper
Please refer to this link. It is Erdos and Renyi's first paper on Random Graphs (1959). I am trying to work through it.
I'm struggling with equations (16), (17) and (21).
(16)
I'm not sure why ...
3
votes
0answers
48 views
Eigenvalue Spectrum density for a simple non-iid matrices
As a part of research, I am studying the eigenvalues spectrum of adjacency matrices. My adjacency matrices are symmetrical. However, their elements are following multivariate gaussian distribution. ...
2
votes
0answers
94 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 ...
0
votes
0answers
37 views
Equivalence between spanning trees in random graphs
First process: Suppose you have a connected random graph, obtained using the Erdős-Rényi model. Then you take a random spanning tree.
Second process: Suppose in the graph above you assign a random ...
4
votes
2answers
120 views
Colorability of random regular graphs?
I have the following experimental results on random regular graphs. I would like to know current theory on colorability of random regular graphs.
Almost all 5 regular graphs are 3 colorable.
Almost ...
2
votes
2answers
84 views
Volume doubling implies that the degree is uniformly bounded above?
Let $G=(V,E)$ be a connected graph. Here $V$ is the set of all vertices of $G$, and $E$ is the set of all edges of $G$. Suppose that $G$ is locally finite, i.e., $\sharp\{y\sim x:y \in V \}$ is finite ...
0
votes
1answer
292 views
How to compute the clustering coefficient of a random graph?
How is the clustering coefficient defined for random graphs? For example, a first definition could be calling clustering coefficient of a random graph the expected value of the clustering coefficient ...
0
votes
0answers
55 views
Quasi-stationary measure on a finite graph equals stationary measure?
Assume the simple random walk $X$ on the graph $G(V,E)$, s.t. $G$ is simple, undirected, finite, connected and let $B \subset V$, s.t. $V\setminus B$ is connected. Let $\sigma_B$ be the quasi-...
