Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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