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

3
votes
1answer
50 views

Elementary proof for average number of tree components in a random forest of fixed size

In Flajolet's & Sedgewick's "Analytic Combinatorics" I found the statement that for a forest ("Catalan", i.e. collection of ordered trees) of size $n$, uniformly distributed, the number of tree ...
2
votes
1answer
69 views

Sequence of Erdos-Renyi random graphs convergent with probability 1

Definitions Let $H,G$ be finite simple graphs. Then the density of $H$ in $G$, denoted $d(H,G)$, is defined as the probability that a randomly chosen $|H|$-tuple of vertices of $G$ induce a graph ...
2
votes
0answers
22 views

Indicator function for a vertex-induced random subgraph of $G$?

I am trying to find polynomial, indicator function or sometimes called structure function to express whether a vertex-induced random subgraph $H$ of $G$ is connected or not. The polynomial $\phi(G')$ ...
0
votes
0answers
29 views

Which Random Graph model on Reliability network when vertices deleted?

The reliability network when edges deleted corresponds to binomial random graph model that is also called Bernoulli Model. The page 3 of Random Graphs book (2000) by Svante Janson, Tomasz Luczak and ...
1
vote
0answers
12 views

Eulerian Cycle in a Random Bipartite Graph

I want to know (or possibly a pointer to a relevant text) the probability of having an Eulerian cycle in a random bipartite graph. I assume an Erdos-Renyi model $G(n,m,p)$, where the number of nodes ...
1
vote
1answer
32 views

Probability that at least 2 edges of $\Gamma_{n,N}$ shall have a point in common

In the classic paper of Erdos,Renyi On the evolution of random graphs[page 7] ,it is argued that the probability that at least 2 edges of $\Gamma_{n,N}$ shall have a point in common is given by $1-\...
1
vote
1answer
29 views

Does the binomial random graph model $G(n, (\ln n)/n^2)$ obey zero-one law?

I want to know if the bionomial random graph model $G\left(n, \frac{\ln n}{n^2}\right)$ obeys Zero-one law or not? I know that $\frac{\ln n}{n}$ is a threshold function for connectivity and for $\...
1
vote
1answer
29 views

Probability of G(4, 1/2) random graph being connected

Suppose we have a random undirected graph G(4, 1/2), i.e. the probability of any two of the four total vertices being connected is 1/2. how to find the probability that Probability (G(4, 1/2) is ...
0
votes
0answers
19 views

Creating Barabási–Albert(BA) graph with spacific node and edgs

I am trying to construct a BA graph with 500 nodes and about 37000 edges. The number of edges to attach from a new node to existing nodes should be at least 91 to make enough number of edges. I ...
2
votes
1answer
67 views

Proving that a random graph is almost surely connected

So, I'm trying to show that a random graph is almost surely connected. I want to know if my intuition is correct, and if so, how to formalize that intuition into a proof. If a graph $G=(V,E)$ has $|V|...
0
votes
0answers
14 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
28 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 ...
1
vote
0answers
44 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 ...
2
votes
0answers
30 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
51 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
31 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 ...
4
votes
0answers
43 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
61 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} ...
3
votes
1answer
49 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
39 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
66 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
39 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
51 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
27 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
23 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 (...
0
votes
0answers
19 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 ...
2
votes
2answers
83 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
51 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
28 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
92 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
51 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 $p=\...
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
69 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
36 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
40 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
48 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
21 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
33 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
48 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
39 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 - 1\right)}{4}...
0
votes
1answer
52 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
190 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
22 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
27 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
28 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
34 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 ...