Stack Exchange Network

Stack Exchange network consists of 175 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]

A random graph is a graph - a set of vertices and edges - that is chosen according to some probability distribution. In the most common model, $G_{n, p}$, a graph has $n$ vertices, and edges are present independently with probability $p$. Use (graphing-functions) instead if your question is about graphing or plotting functions.

60
votes
3answers
2k views

How likely is it not to be anyone's best friend?

A teenage acquaintance of mine lamented: Every one of my friends is better friends with somebody else. Thanks to my knowledge of mathematics I could inform her that she's not alone and $e^{-1}\...
18
votes
1answer
251 views

Size of connected regions on a randomly-colored infinite chessboard

Consider an infinite chessboard where each square is colored white with probability $p$ and black with probability $1-p$. Suppose without loss of generality that the square at $(0,0)$ is white. We ...
15
votes
2answers
767 views

Why “One cannot construct more than countably many independent random variables”?

I'm reading the book "Large Networks and Graph Limits" by László Lovász. On the page 18 he said the following: One cannot construct more than countably many independent random variables (in a ...
12
votes
1answer
685 views

Probability that a random graph is planar

I've been attempting to solve the following challenge problem from a combinatorics class but am getting absolutely nowhere. Prove: For sufficiently large $n$, the probability a random graph $G=(V,E)...
12
votes
1answer
624 views

Random graph probability lemma

I'm trying to prove a fiddly lemma for homework, but getting absolutely nowhere with it. Here, $G_{n,p}$ and $G_{n,m}$ represent, respectively, random graphs on $n$ vertices where the number of edges ...
12
votes
1answer
209 views

Random walk on thin ice?

My Question: Is the stochastic process which is described below a (special case of a) well-studied model? What kind of properties are known under which assumptions? Let's think of a random walker on ...
12
votes
0answers
469 views

What is the Probability of Transmission Between Two Nodes in a Neural Network?

I have a network which is an Erdős–Rényi graph. It is a simple neural network with degree 0.7N where N is the number of nodes. Each weight between neurons is 1/N, meaning that if node n has fired ...
12
votes
0answers
500 views

Probability of the existence of a path of a specified length between any tw0 vertices in a random graph

Let $G$ be a graph with $n$ vertices, whose average degree is $k$. What is the probability that between any two vertices, there exists a path of length at most $l$? NOTE: For the above problem the ...
10
votes
2answers
731 views

Literature recommendation on random graphs

I'm looking for introductory references on random graphs (commonly mentioned as Erdős–Rényi graphs), having previous acquaintance with basic graph theory. I know that Bela Bollobas' book on random ...
10
votes
1answer
673 views

What is the probability that a random $n\times n$ bipartite graph has an isolated vertex?

By a random $n\times n$ bipartite graph, I mean a random bipartite graph on two vertex classes of size $n$, with the edges added independently, each with probability $p$. I want to find the ...
10
votes
0answers
767 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being present....
8
votes
2answers
970 views

What is the average weight of a minimal spanning tree of $n$ randomly selected points in the unit cube?

Suppose we pick $n$ random points in the unit cube in $\mathbb{R}_3$, $p_1=\left(x_1,y_1,z_1\right),$ $p_2=\left(x_2,y_2,z_2\right),$ etc. (So, $x_i,y_i,z_i$ are $3n$ uniformly distributed random ...
7
votes
5answers
259 views

asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one

A recent discussion, which may be found here, examined the problem of counting the number of acyclic digraphs on $n$ labelled nodes and having $k$ edges and indegree and outdegree at most one. It was ...
7
votes
1answer
515 views

The probability of having a perfect matching in a bipartite graph

Say we have a bipartite graph $G$ with two sets, $\{x_1,\dotsc,x_n\}$ and $\{y_1,\dotsc,y_n\}$. For each pair $xy$, there is an edge with probability $p$. Then, what is the probability of having a ...
7
votes
1answer
211 views

A graph theoretical/combinatorial problem

I'll try to describe a problem that I am currently working on, hoping to get some direction out of anyone possibly interested in the problem. Let $G_1=([n],E_1), G_2=([n],E_2)$, such that $E_1\...
7
votes
0answers
725 views

Generating a Random Connected Graph

Given a graph G(V, E), with |V | = n and |E| = 0 (that is, the graph is empty), and a static set F containing all the possible edges. Consider the following algorithm for generating a random graph. ...
7
votes
1answer
431 views

Probability of two vertices to be connected in G(n,p)

Let $G(n,p)$ be an Erdős–Rényi graph on $n$ vertices. Is there an explicit expression for the probability $P_{n,p}(u,v)$ that two fixed (distinct) vertices $u,v$ lie in the same connected component of ...
6
votes
3answers
196 views

Show $y = \sum_{k=1}^\infty \frac{k^{k-1}}{k!} x^k$ satisfies $ye^{-y} = x$.

My question is literally the title: Show $y = \sum_{k=1}^\infty \frac{k^{k-1}}{k!} x^k$ satisfies $ye^{-y} = x$. Here's a little motivation for the question. If you don't care about motivation, ...
6
votes
1answer
1k views

Expectation number of cycles in a Erdős–Rényi random directed graph $G(n,p)$

Let $G \sim G(n,p)$ be a directed Erdős–Rényi random graph with $n$ vertices and the probability $p$ that there is a directed edge between any two ordered pairs of vertices. What is the expected ...
6
votes
2answers
602 views

Probability that an undirected graph has cycles

If we know the probability $P$ that there exists an edge between two vertices of an undirected graph, let's say $P= 1/v$, where $v$ is the number of vertices in the graph, what is the probability ...
6
votes
1answer
88 views

Probability that a graph is bipartite

Given the empty graph on $n$ vertices, we add $m$ of the $\binom{n}{2}$ possible edges, uniformly at random. What is the probability that the resulting graph is bipartite (equivalently, contains no ...
6
votes
1answer
100 views

Prove that: Probability of connectivity of a random graph is increasing with the size of the graph

In a random graph $G(n, p)$, the exact probability of the graph being connected can be written as: $$ f(n) = 1-\sum\limits_{i=1}^{n-1}f(i){n-1 \choose i-1}(1-p)^{i(n-i)} $$ This probability is ...
6
votes
3answers
137 views

Probably of $A^k[i, j] \geq 1$ for a random matrix

Suppose there is a square matrix $A$, with random elements (say $A[i, j] \geq 1$ with probability $p$). This can be thought of as the adjacency matrix of a (directed) graph and $A^k[i, j]$ as the ...
6
votes
2answers
196 views

Graph theory and trees questions

(a) Is false. If $G$ is a tree then: $|E|=|V|-1$ So, $|E|=9-1=8$. But because the sum of the degrees of all vertices is equal to $2|E|$, we have $2|8|=16\neq18$ (b) Is true If $G$ is a graph then:...
6
votes
1answer
144 views

Assortativity (homophily) in random graphs

I am trying to come up with the solution to the following problem and would be grateful for any help. Consider a random undirected graph built using configuration model with degree distribution $\{...
6
votes
0answers
105 views

Central limit theorem for perfect matching counts

Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of of graph $G$ i.e. $N_G$ is very close to the ...
5
votes
1answer
860 views

Does an $n\times n$ adjacency matrix of a scale-free network graph have $n$ distinct eigenvalues?

Question updated Suppose that I have an $n\times n$ adjacency matrix $\mathbf{A}$ of a simple graph $G$ where the entry $(i,j)$ represent the number of edges between node $i$ and $j$ in $G$. Note ...
5
votes
1answer
701 views

Probability of a random graph being bipartite

We start from an "empty" graph with $n$ vertices standing alone. Each vertex has $s$ chances to choose one vertex each chance as its neighbor, uniformly and independently from the $n$ vertices, ...
5
votes
1answer
125 views

Random graphs with a hamiltonian path

Suppose we randomly choose a graph with $n$ vertices in the following manner: each edge is included with probability $\frac12$. Thus, each graph has the same probability of being chosen, and there are ...
5
votes
1answer
139 views

Expected steps to obtain a connected graph

We have a country containing $N$ cities with no road between any two cities (what a poor country). Each day we choose two cities such that there is no road between them and build a road between them. ...
5
votes
1answer
330 views

How many centers in a infinite connected graph?

I find a very interesting concept "center" while learning basic graph theory. A center of graph $G$ is a vertex with the minimal greatest distance (eccentricity) to other nodes in $G$. Now I’m curious ...
5
votes
1answer
833 views

Expected maximum degree Erdős–Rényi graph

Consider an Erdős–Rényi random graph $\mathrm{ER}(N,p)$, where $N$ is the number of nodes and $p$ the probability of placing an edge between each distinct pair of nodes. I'm interested in finding ...
5
votes
1answer
149 views

Almost every graph is asymmetric?

Here is a question: If i choose at random an isomorphism class of graph(no loops, undirected) on n vertices(with uniform probability on the set of such isomorphism classes), is the probability that ...
5
votes
1answer
302 views

Probability of finding a Hamilton circuit in a graph

In short, I would like to know either/both the probability that there exists a Hamiltonian circuit within a graph, or the number of circuits expected to exist. (Without actually finding all the ...
5
votes
1answer
269 views

Probability of cycles of length at most $g$ in a random graph

I am working on a homework problem. The essence of it is as follows: Fix some integer $g$, a probability $p\in [0,1]$, and a linear function $f(n)$, where $n$ is the number of vertices of a random ...
5
votes
0answers
111 views

A probability problem on randomly generated graph

The graph we discuss here is a directed pseudo-graph (two vertices can have multiple edges) with self-loops. The problem is to prove a very intuitively probability formula at the end. The background ...
5
votes
0answers
428 views

Minimal number of edges removed to make a graph triangle free

I'm interested in finding an upper bound on the expected value of the minimal number of edges one needs to remove from a random graph $G_{n,p}$ (where each edge appears with probability $p$) in order ...
5
votes
0answers
985 views

What can be said about the number of connected components of $G(n,p)$ random graphs?

By a $G(n,p)$ graph we mean a graph on $n$ vertices, all possible edges are independently included randomly with probability $p$. What can be said about the number of connected components? For ...
4
votes
2answers
149 views

Random Walk on graph with five vertices

Consider a random walk on the following graph: The random walk starts from the vertex $V_1$ and moves to one neighbouring vertex (each is reached with the same probability) in the next step. For ...
4
votes
3answers
2k views

Probability of a graph having at least 1 k-clique

I need to estimate the probability $P(\text{Graph G has at least 1 k-clique})$, any precision will do. I know the edge probability, say $p$, so the average number of the edges, $EK$, is $pm(m - 1)/2$, ...
4
votes
2answers
390 views

Random walk on a tree

Consider a Cayley tree with coordination number 3 (http://en.wikipedia.org/wiki/Bethe_lattice). Consider two sites, $x$ and $y$, having a distance $k$ one from another. What is the probability that ...
4
votes
1answer
1k views

Expected number of vertices a distance $k$ away in a random graph?

Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$. I ...
4
votes
2answers
218 views

Disjoint union of random graphs again a random graph?

Let $G_{n,p}, n\in \mathbb{N}, p\in(0,1)$ be the binomial random graph, i.e. a graph on $n$ vertices where an edge is in $G_{n,p}$ with probability $p$. Also, let $q\in (0,1)$. Can one regard $G_{n,q}...
4
votes
1answer
156 views

Mean cut size in generated graphs

Assume an undirected simple graph $G=(V,E)$ is created randomly: an edge $e=(u,v)$ is in $E$ with probability $p$, independent of other edges. Assume we select a random cut $(S,T = V\setminus S)$ in ...
4
votes
2answers
190 views

Show With High Probability, No Vertex Belongs to More than One Triangle

I am working on a random graphs problem, which is stated as follows: Suppose that $p = d/n$, where $d$ is constant. Prove that with high probability (w.h.p.), no vertex belongs to more than one ...
4
votes
1answer
266 views

Is the expected number of components in a random graph $G(n,p)$ a decreasing function of $p$?

Let $X$ be the number of connected components in $G(n,p)$. If we fix $n$ and vary $p$, is $E(X)$ a decreasing function of $p$? I "feel" that this should be right because as $p$ increases there are ...
4
votes
1answer
138 views

Threshold probabilities in Erdos-Renyi random graph model $G(n,p)$ and intermediate value theorem

In Erdos-Renyi random graph model $G(n,p)$, set $Q$ any graph property. Suppose there exist $p_1(n)$ and $p_2(n)$ in $(0,1)$ for $n \in \mathbb{N}$ such that $Pr(G(n,p_1)\ \text{has property}\ Q) =...
4
votes
2answers
885 views

Probability of a path of a given length between two vertices of a random graph

Suppose that in random graph $G$ on $n$ vertices any $2$ vertices can be connected by an edge with probability $\dfrac{1}{2}$, independently of all other edges. What is the probability $P_n(k)$ ...
4
votes
1answer
80 views

Clique numbers and Theorem 4.5.1 in “The Probabilistic Method” by Alon and Spencer

My question is "What is the precise formulation of the following theorem from Alon and Spencer's book The Probabilistic Method?" For context, Let $G(n,1/2)$ be the probability space of random graphs ...
4
votes
1answer
185 views

What is the expected total number of topological sorts in a Directed a cyclic graph with $n$ vertices?

I know that a DAG with $n$ vertices can have $O(n!)$ topological sorts. However, I am interested in knowing the expected number of topological sorts in a randomly generated DAG?