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

816 questions
Filter by
Sorted by
Tagged with
54 views

### Average Distance Between Two Nodes In An Unweighted Tree

Given a random unweighted tree with $n$ vertices, what would be an average minimal distance between two of its vertices? To put it in a more formal way, let's denote the set of all trees with $n$ ...
85 views

### Probability / Graph Theory / Optimization Problem

I have a problem involving a random graph $G$ with a set of nodes $n_1, n_2, ..., n_k$. A priori, we know approximately the probabilities $p_{ij} ( =p_{ji} )$ that an edge $e_{ij}$ exists between ...
• 21
1 vote
42 views

### Probability of number of $m$-walks in graph to be $l$

I'm considering this question: if a directed graph with adjacency matrix A satisfy that $P(a_{i,j}=1)=P(a_{i,j}=0)=0.5$ and $a_{i,i}=0$ for any i, j in ${1,...,n}$, where $n$ is the number of the ...
• 41
48 views

### Concentration inequality on graphs

Suppose we consider the graph $G_n$ with $n$ vertices and $nd$ edges, where we choose every edges $E_1,...,E_{dn}$ uniformly at random from the total set of $n \choose 2$ edges, independently for ...
• 629
1 vote
50 views

• 3,564
1 vote
21 views

• 3,635
1 vote
63 views

### High probability of $\sqrt{\log n}$ degree in random graph [duplicate]

I’m stuck on a problem I’ve found in a book on random graphs. Appreciate any help: Let $G_{n,p}$ be a random graph with $p=\frac{c}{n}$ for some positive $c$. Show that with high probability there is ...
8 views

### Trying to formally understand consistency of parameter estimation for random graph models?

Let $G$ be a set of graphs on $n$ nodes with an underlying probability distribution $P: G\rightarrow [0,1]$. The distribution is exchangeable i.e. isomorphic graphs have the same probability. I also ...
• 1,697
1 vote
75 views

• 934
1 vote
86 views

### One question about the proof of there is a graph $G$ with girth $g(G)>k$ (that is the length of the shortest cycle in graph $G$) and $\chi(G)>k$

In Diestel's Graph Theory, I try to figure out the proof of Theorem 11.2.2 on page 301: given any positive integer $k$, there is a graph $G$ with girth $g(G)>k$ (that is the length of the shortest ...
• 934
1 vote
30 views

### Connectivity of random regular multigraphs

For even integers $n$ and integers $3\le r < n$, is it true that a random $r$-regular multigraph on $n$ labelled vertices, obtained as the union of $r$ independent uniformly random perfect ...
32 views

### Connectivity of random collections of cubes

Imagine a cube $100\times100\times100$, a million little cubes. We randomly pick half of them to be red, half to be blue. Define "connected" to mean, two red cubes sharing a face. (You could ...
• 101
1 vote
91 views

### One question about the probabilistic method proof of the any large girth number and chromatic number on a graph.

In Diestel's Graph Theory, I try to figure out the proof of Theorem 11.2.2 on page 301: given any positive integer $k$, there is a graph $G$ with girth $g(G)>k$ (that is the length of the shortest ...
• 934
35 views

### Number of spanning trees in a random connected graph

Let us consider a graph $G$ with n nodes and m edges formed by Erdos Renyi random graph model $G(m,n)$. How do we find the number of spanning trees? Follow up question, how do we find the number of ...
• 73
16 views

### Recursive formula for estimating the mean number of second neighbors in a network reachable with two paths.

In the iLCD algorithm the EMSN (Estimation of the mean number of second neighbors) and the EMRSN (Estimation of the mean number of robust second neighbors) are approximated. These values represent, ...
1 vote
37 views

### equivalence of random hypergraph models

On Wikipedia it says that for any monotone graph property $P$, the two statements "$G(n,p)$ has property $P$ with high probability" and "$G(n, p\binom{n}{2})$ has Property $P$ with ...
• 13
1 vote