Minimum Degree of a Random Graph (Probabilistic Method)

In summary: Thus, for any fixed positive integer $k$, the random graph $G(n,p)$ has minimum degree at least $k$ almost surely as $n \rightarrow \infty$.In summary, we proved that under the assumption that $p >> n^{-1}ln(n)$, the random graph $G(n,p)$ has minimum degree at least $\frac{np}{2}$ almost surely as $n \rightarrow \infty$. This was done by using Chernoff's Inequality and the fact that edges are inserted independently with probability $p$. We then extended this result to show that for any fixed positive integer $k$, the random graph $G(n,p)$ has minimum degree at least $k$ almost surely as $n
  • #1
joypav
151
0
Problem:
Suppose that the function $p : N \rightarrow [0, 1]$ satisfies $p >> n^{-1}ln(n)$ (i.e. $n^{-1}ln(n) = o(p)$).

(a) Prove that as $n \rightarrow \infty$, the random graph $G(n, p)$ has minimum degree at least $\frac{np}{2}$ almost surely.
Idea: Look at the degree of each individual vertex $v \in V(G)$. Try to find a bound on the probability of this fixed vertex having a small degree (using Chernoff's Inequality?).

I am not getting to where I think I should with this idea.
Let $X_{u,v}$ be $1$ is $uv \in E(G)$ and $0$ if $uv \notin E(G)$.
Then, $X_v = \sum_{u \in V(G), u \neq v} X_{u,v}$ will give us the degree of $v$.
Also, the $X_{u,v}$'s are uniform/independent (as $G$ is a random graph and edges are picked independently with probability $p$).
Now we may use Chernoff's? How do I use the first thing we assumed... that $p >> n^-1ln(n)$?


(b)
Conclude that for any fixed positive integer k, the random graph $G(n, p)$ has minimum
degree at least k almost surely as $n \rightarrow \infty$.
 
Last edited:
Physics news on Phys.org
  • #2
For completeness, I will post a "proof" I came up with. As you can see, at the end I skipped over some much needed justification that I couldn't seem to figure out. Some help with this would be appreciated!

However, I do think that my general idea is correct.

Proof: (a) Let $G \sim G(n,p)$. Fix $v \in V(G)$. Let $A_{v,u}$ be the event that $vu \in E(G)$ and let $X_{v,u}$ be its indicator. Then, $X_{v,u}=1$ with probability $p$ and $X_{v,u}=0$ with probability $1-p$. Because each possible edge is inserted independently, the $X_{v,u}$'s are independent. Let $X_v = \sum_{u \in V(G), u \neq v} X_{u,v}$, (giving the degree of $v$). Now we may use Chernoff's Inequality with:
$$\sigma^2 = Var[X_v] = np(1-p)$$
$$E[X_v] = \sum_{u \in V(G), u \neq v} E[X_{u,v}]=p(n-1)$$
Then,
$P[$degree of v is less than $\frac{np}{2}] = P[X_v \leq E[X_v] - \frac{np-2p}{2}] = P[X_v \leq \frac{np}{2}]$
$$ \leq e^{\frac{-(\frac{np-2p}{2})^2}{2(np+\frac{\frac{np-2p}{2}}{3})}} = e^{-\frac{3n^2p-12np+12}{28n-8}}$$
Let $X$: existence of vertices with degree less than $\frac{np}{2}$. Then,
$$P[X]= \sum_{v \in V(G)}P[X_v \leq \frac{np}{2}] \leq n\cdot e^{-\frac{3n^2p-12np+12}{28n-8}} = e^{ln(n)-\frac{3n^2p-12np+12}{28n-8}}$$
By assumption $p > > n^{-1}ln(n)$.
$$\Rightarrow ln(n)-\frac{3n^2p-12np+12}{28n-8} \rightarrow -\infty $$
$$\Rightarrow P[X]\rightarrow 0$$
Then every vertex of G must have degree at least $\frac{np}{2}$.

(b) Apply part (a). So we have $\delta(G) \geq \frac{np}{2}$ a.s. as $n \rightarrow \infty$. As long as $n \geq \frac{2k}{p}$, $\delta(G) \geq k$.
 

Related to Minimum Degree of a Random Graph (Probabilistic Method)

What is the minimum degree of a random graph?

The minimum degree of a random graph refers to the minimum number of edges connected to each vertex in a randomly generated graph. It is an important measure in understanding the overall structure and connectivity of a graph.

How is the minimum degree of a random graph determined?

The minimum degree of a random graph is determined by the number of vertices and edges in the graph. It can also be calculated using the Erdős–Rényi model, which is a commonly used probabilistic method for generating random graphs.

What is the significance of the minimum degree in a random graph?

The minimum degree in a random graph is significant because it provides insights into the overall connectivity and robustness of the graph. A higher minimum degree indicates a more connected and resilient graph, while a lower minimum degree may indicate potential for isolated nodes or clusters.

Can the minimum degree of a random graph be controlled?

Yes, the minimum degree of a random graph can be controlled by adjusting the parameters used in the Erdős–Rényi model, such as the number of vertices and edges. This allows for the creation of graphs with specific minimum degrees to meet the desired connectivity requirements.

How is the probabilistic method used to determine the minimum degree of a random graph?

The probabilistic method involves using probability theory to prove the existence of a certain property in a random structure, such as a graph. In the case of the minimum degree of a random graph, the probabilistic method can be used to show that a graph with a certain minimum degree will exist with high probability when generated using the Erdős–Rényi model.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Replies
12
Views
792
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
2K
Back
Top