# 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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**0**answers

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