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

493 questions
2k views

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

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 ...
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 ...
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, ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$, ...
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 ...
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 ...
218 views

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)$ ...
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 ...
### 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?