A random graph is a graph 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$.

learn more… | top users | synonyms

0
votes
0answers
10 views

Asymptotic Density of threshold graphs

Someone said yesterday "threshold graphs are really scarce". Now, there are a lot of graph classes that occur with probability 0, in random graphs. How would someone make meaningful statements about ...
0
votes
1answer
27 views

Replacing initial probability in $G(n,\frac{1}{2})$ with $G(n,\frac{1}{3})$ for not appearance edges

I have a question; maybe so simple but practical: In Erdos-Renyi binomial random graph $G(n,p)$; set $p=\frac{1}{2}$. So with probability $1/2$ some edges will appear and some not. Now the question ...
0
votes
0answers
39 views

Probability of having at most a certain number of isolated vertices in random graph?

In Erdos-Renyi model of Binomial random graphs $G(n,p)$, if we have $np = \ln n - \ln \ln \ln n$, then what is the probability of having at most $a \ln n$ vertices be isolated. Having isolated ...
1
vote
0answers
26 views

Probability that a random bipartite graphs is the intersection of simple cycles

I have the following problem and honestly i don't know how to start working on it. Any clue will be appreciated. I need to calculate the probability that following the Erdos-Renyi model, a random ...
1
vote
0answers
41 views

Spencer and Shelah zero-one law for Erdos-Renyi random graph $G(n,p)$

In Erdos-Renyi random graph $G(n,p(n))$; set $p(n)= (\frac{ln n}{n})^2$. We know that already Spencer and Shelah have proved that zero-one law doesn't hold for $p(n)= \frac{ln n}{n}$. Now the question ...
1
vote
1answer
26 views

Chromatic number of Erdos-Renyi random graphs $G(n,m)$

In Erdos-Renyi random graphs $G(n,m)$, set $n=4$ and $m=5$. The question is as follows: What is the probability for to having Chromatic number exactly 2 in the case of $G(4,5)$; in other words what ...
-3
votes
0answers
37 views

Connectivety of the Erdős–Rényi random graph [closed]

Let G be a graph in G(n, p) (Erdős–Rényi model) I want to prove that that P( G(n, p) where p ≥ ( lnn/10n) and number of tree components on 11 vertices = 0 ) converges to 1 and lnn/n is a ...
3
votes
0answers
30 views

Expected number of cycles of length $k$ in a random graph. My simple (too simple?) solution

I attempted this on my own and got a fairly simple solution. However, after reading proofs here and here, I feel like I have massively over simplified the problem. I understand the other solutions, ...
0
votes
0answers
55 views

Zero-one law in binomial random graph model $G(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} ...
-4
votes
0answers
20 views

If G(n,n,p) is bipartite random graph, If X is number of cycles, whats is its variance and expectation? [closed]

If G(n,n,p) is random bipartite graph, and X = the number of cycles, then what is E(X) and V(X)?
-3
votes
0answers
31 views

In $G(n,2/n^{0.5})$, what is the limit probability of containing exactly two graphs from set $A$? [closed]

If we denote "$A$" as the set of two graphs. The first one is complete graph, $K_5$, and the second one is bipartite graph, $K_{4,4}$. In $G(n,2/n^{0.5})$, what is the limit probability of containing ...
-2
votes
0answers
19 views

Example of barabasi albert's preferential attachment model and generalized random graphs [closed]

I have a graph having some 10,000 nodes and 90,000 edges. Now i want to implement and generate random graphs as the same number of nodes and edges and want to compare my original graph with random ...
3
votes
1answer
45 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) ...
0
votes
0answers
28 views

What is the meaning of probability of an edge connected by two nodes in a graph

I am studying random graph models. While studying random graph models if we want to generate for instance erdos renyi's random graph model then we will have to place $n$ vertices and connect each pair ...
3
votes
1answer
59 views

Limit probability of a complete bipartite random graph $G(n,n,p)$ is connected

I need to calculate the following probability limit for a complete bipartite random graph $G(n,n,p)$ in the Erdos-Renyi model: \begin{equation} \lim_{n\rightarrow\infty}\mathbb{P}[G(n,n,p) \text{ is ...
4
votes
0answers
65 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 ...
1
vote
0answers
36 views

Number of complex components with l=1 in G(n,p)

I need to prove that the number of specific components with complexity one, that is, two cycles connected by a path or an edge and one cycle with an inner path, on the set of vertices $\{1\ldots k\}$ ...
2
votes
1answer
48 views

Existence of trees in Erdos–Renyi random graphs $G(n, p)$

In Erdos–Renyi random graphs $G(n, p)$; Can someone give me the idea on how to prove that if $p\times n^{\frac{k}{k-1}}= o(1),$ then there is no tree of order $k$? The only hint that I can suppose ...
1
vote
0answers
25 views

Limit of a certain sum

I need to show that $$\sum_{i=0}^{m} \binom{m}{m-i}\binom{m^2-m}{i} (1-p)^{\binom{i}{2} + i m} \bigg/ \binom{m^2}{m} (1-p)^{\binom{m}{2}} \to 0$$ as $m \to \infty$, where $p = \frac{1}{m}$, and the ...
0
votes
0answers
19 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 ...
1
vote
0answers
32 views

Is a “deterministic” subset of a random subset random?

Let $S$ be some set and consider $X \subseteq S$ of size $|X|=x$ u.a.r. (among all the subsets having this size). Now, use some properties of this set $X$ to find some subset $Y\subseteq X$ of some ...
-1
votes
0answers
23 views

Average number of connected triples in a random graph G(n,p)

I need to prove that the expected number of connected triples in a random graph $G(n,p)$ is $\frac{1}{2}nc^2$ when the average degree is $c$. I know that $c = (n-1) p$. I also figured out that if you ...
0
votes
0answers
16 views

Relation between Kolmogorov Zero-One Law and Random Graphs Zero-One Laws?

I know of Zero One laws for Random graphs (such as those concerning monotonic or first-order-logic properties). I also know about Kolmogorov's zero one law for tail sigma algebras. Apart from the ...
1
vote
2answers
57 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 ...
0
votes
0answers
46 views

Boolean function analysis on random graphs?

Random graphs have some properties that are determined in some random way such as edge probabilities in the interval $[0,1]$. Ryan O'Donnell's book "Analysis of Boolean Functions" (2014) has analysis ...
0
votes
0answers
27 views

Probability of a given deterministic graph containing a k-clique

I want to approximate the properties of a given, deterministic, undirected Graph $G$ without multiple edges. To be precise: I want to know the probability $P$ that $G$ with $n$ edges and $z$ ...
3
votes
0answers
83 views

Trace of power of random matrix / sum of random variables with semicircle distribution

I want to calculate the expectation value for the trace of the $m$-th power of the $n\times n$ adjacency matrix $A$ of a large Erdos-Renyi random graph (without self-coupling, i.e., all diagonal ...
0
votes
1answer
41 views

Probability of at least one triangle in Erdos-Renyi graph

Cross-posting here as I didn't get a satisfactory solution on cv. This is a well-known problem in random graph theory, where we show that if $X$ is the number of triangles in $G(V,E,p)$ with ...
2
votes
1answer
23 views

Random Geometric Graph in unit disk

According to the Wikipedia article, to define a random geometric graph, one needs a metric space. In the examples they give for 2D random geometric graphs, they say that "an RGG can be constructed ...
1
vote
1answer
68 views

What is the expected number of of $k$-tuples of vertices such that all edges between the vertices have the same colour?

Consider the complete graph $K_n$ and suppose we colour each edge of $K_n$ red or blue with equal probability. For every $k$, $1\leq k \leq n$, give a formula for the expected number of $k$-tuples ...
0
votes
1answer
28 views

What is the official name for the ratio of edges to nodes in a connected graph?

In my context, the nodes are code elements and the edges are "dependencies". So I am using the term "dependency density" to refer to the ratio of edges/nodes. Is there an official term for this ratio ...
3
votes
0answers
39 views

How to formalize this statement about $G_{n,p}$ and $G_{n,m}$?

I'm reading a proof of the following Thereom: If $m/n \to \infty$ then $G_{n,m}$ contains a triangle wit high probability. The first line of the proof states: Because having a triangle is ...
1
vote
2answers
45 views

Probability $u, v$ are connected in a random graph model

There is a random graph problem. Given an undirected graph $G(V,E)$ associated with $p_{uv}$ to denote the probability there is an edge between $u$ and $v$ ($p_{uv}$ are independent, maybe different ...
1
vote
0answers
20 views

Step in using Stirling's formula to get an upper bound

I'm having trouble seeing why the following holds. Given the conditions that $N=\binom{n}{2}$ and $m$ is a function of $n$ such that $N-m \to \infty$ as $n \to \infty$, why is it that $$(1+o(1)) ...
1
vote
0answers
18 views

Confused about this notation about random graphs in Bollobas' book

After Theorem 2.1 on page 26 (second edition) he states Note that the arugment above shows that if $Q$ is a nontrivial monotone increasing property then $$P_{p_2}(Q) \ge P_{p_1}(Q) + \{1 - ...
1
vote
1answer
32 views

Number of distinct vertices in a random walk on a graph

Let $G$ be a graph on $n$ vertices. Is it possible to calculate the expected number of distinct vertices seen in a simple random walk of length, say, $k < n$? Moreover, how is this affected when ...
1
vote
1answer
46 views

Probability of at least one isolated clique forming

Is there any "famous" random graph model in which the probability of at least one isolated clique forming is monotonic in the parameters? For instance, are any results known in this matter for the ...
-1
votes
1answer
38 views

Asymptotic enumeration of regular graphs

I have been following a few papers on the asymptotic enumeration of $r$-regular graphs of $n$ vertices, $L_r$. According to Random Graphs, $L_r = L_n \sim \sqrt{2} e^{- \frac{\left(r^2 - ...
0
votes
1answer
47 views

Random graph problem

I'm trying to analyze a network algorithm to get a latency probability distribution. One of the steps is to "calculate the probability distribution of the number of updated nodes in a single hop of a ...
1
vote
1answer
170 views

The expected number of triangles in Erdos-Renyi graph : why wrong derivation also works?

So I know how to correctly calculate the expected number of triangles in the Erdos-Renyi graph using linearity of the expectation value operator (See this for example). However, now consider a "wrong" ...
1
vote
1answer
20 views

Average node degree k in a geometric random graph is $\frac{\Pi r^2n}{l^2}$

The paper "Small-Worlds: Strong Clustering in Wireless Networks" (http://arxiv.org/pdf/0706.1063.pdf) is indicating empirically that the average node degree $<k>$ is (or can be approximated by) ...
1
vote
0answers
23 views

The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the ...
0
votes
0answers
26 views

Probability of maximum degree in On random graphs I by Erdos

In The Maximum Degree of a Random Graph by RIORDAN et al., the authors commented that the study of the distribution of the maximum degree $d^{max}(G)$ of a random graph $G$ was started by Erdos and ...
0
votes
1answer
32 views

Confused with the power set of an integer

I am going through The Maximum Degree of a Random Graph by RIORDAN et al. On the second page, the notation $\mathbb{P}(\mathcal{D})$ is used which I assume the power set of the set $\mathcal{D}$. ...
0
votes
0answers
12 views

The random graph quantity $S(n: K, L)$

I am going through Degree sequences of random graphs by Béla Bollobás. On page $3$ the author introduces the quantity $S(n: K, L)$ without any explanation. Could anyone please help me in ...
0
votes
1answer
25 views

Calculating the probability of a graph being Erdos-Renyi

Given an undirected, unweighted graph with |V| = 11 and |E|= 19 and given probability p=0.5 I have to calculate the probability of the graph being generated using the Erdos-Renyi Model. I applied the ...
0
votes
2answers
52 views

threshold for random 2-sat

I'm looking at notes on the threshold for random 2-sat which is given as $r_{2}^{*}=1$. In the first part of proving the threshold they claim that a 2-sat formula is satisfiable if and only if the ...
0
votes
0answers
38 views

Show With High Probability $G_{n, p}$ has an induced path of length $(\log(n))^{1/2}$

The problem on which I am working states: Let the probability $p = d/n$ where $d > 1$. Show that with high probability, $G_{n, p}$ contains an induced path of length $(\log(n))^{1/2}$. My ...
2
votes
3answers
56 views

Finding the limit of ${n-1 \choose k}p^k(1-p)^{n-1-k}$ as $n$ goes to infinity

On this Wikipedia page on random graphs, they compute this limit to be $$\lim_{n\to\infty}\binom{n-1}kp^k(1-p)^{n-1-k}=\frac{(np)^ke^{-np}}{k!}$$ with $np$ constant. Any hints on how to get that? ...
3
votes
2answers
128 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 ...