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

29 questions
514 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 ...
197 views

### Are the vertices of a Voronoi diagram obtained from a Sierpinski attractor also a kind of attractor?

Trying to understand how the Voronoi Diagrams work I did a test generating the Voronoi diagram of the points obtained from The Chaos Game algorithm when it is applied to a $3$-gon. The result is a set ...
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 ...
7k views

### Expected number of triangles in a random graph of size $n$

Consider the set $V = \{1,2,\ldots,n\}$ and let $p$ be a real number with $0<p<1$. We construct a graph $G=(V,E)$ with vertex set $V$, whose edge set $E$ is determined by the following random ...
132 views

### Probability spaces over graphs: which area has focus on them?

Suppose a simple graph $G$. Now consider probability space $G(v;p)$ where $0\leq p\leq 1$ and $v$ vertices. I want to calculate globally-determined properties of $G(v;p)$ such as connectivity and ...
158 views

### Probability of having a girlfriend in a school with groups

A school has $r$ groups. Each group has $n$ girls and $n$ boys. Any boy and girl know each other with probability $p$ if they belong to the same group, and with probability $q$ if they belong to ...
210 views

### Expected number of edges: does $\sum\limits_{k=1}^m k \binom{m}{k} p^k (1-p)^{m-k} = mp$

Find the expected number of edges in $G \in \mathcal G(n,p)$. Method $1$: Let $\binom{n}{2} = m$. The probability that any set of edges $|X| = k$ is the set of edges in $G$ is $p^k (1-p)^{m-k}$. So ...
232 views

### How many paths of length 2 in a general random graph?

Suppose you have several random graphs. Each one has $n$ nodes, connected among them with probability $p$. There are $r$ random graphs. Now, each node is connected to nodes of another random graph ...
684 views

280 views

### does a power law degree distribution imply graphs are sparse?

Lets say I have a random variable with values in the space of square binary matrices from which I can sample (adjacency matrices of) graphs, and lets say that the resulting graphs have a power law ...
691 views

### estimate value of maximum cut in graph by random sampling

I have an unweighted, undirected graph G=(V,E) from which I am sampling a set S of $\frac{kn}{ε^2}$ edges uniformly at random, where k is constant and ε is a variable parameter. From this set S I want ...
1k views

### Cover Time for Random Walk on a cycle

I'm trying to find the expected time to cover all $N$ nodes on an undirected cycle graph, starting from a given node $k$. The probabilities of moving clockwise and anticlockwise are $\frac{1}{2}$ each....
319 views

### Sample Code to Generate Points on the Rim of a Randomly Rotated Cone : What's Going On Here?

Related to this question: https://math.stackexchange.com/questions/407897/randomly-generate-point-on-shell-from-3-points-2-angles-with-uniform-angle-dis I'm trying to reverse engineer the math-...
77 views

### Arbitrary vs. random subsets: computing probabilities

Let $G=([n],E)$ be a graph having minimum degree $\delta(G) \geq (1-\delta) n$. For some $q=q(n)$, let $G_q=([n], E_q)$ be the random subgraph of $G$ obtained by deleting each edge independently with ...
I read this: estimate value of maximum cut in graph by random sampling but I didn't understand how to solve my problem that is very similar. My problem is let $G(V, E)$ be an unweighted and ...