Welcome to our community

Be a part of something great, join today!

[SOLVED] Choosing Edges, Random Graph

joypav

Active member
Mar 21, 2017
151
Let $n$ be a positive integer, and let $G$ be a random graph from $G(n, 1/2)$. Let $e_1, . . . , e_{n \choose 2}$ be the
possible edges on the vertex set ${1, . . . , n}$, and for each $i$, let $A_i$ be the event that $e_i ∈ E(G)$.
Prove that the events $A_1, . . . , A_{n \choose 2}$ are independent.


Can I just have some help understanding what details I should be including here?
It's so trivial that I don't know how to write it down as a proof.
There is a probability of $\frac{1}{2}$ that any arbitrary possible edge will be an edge of the graph. And it just seems obvious that whether one edge is in the graph has nothing at all to do with if another edge is in the graph.

So then if we choose an arbitrary subset of $A_1, . . . , A_{n \choose 2}$, the probability of the events in the subset occurring will be the product of the individual probabilities of the events.
 

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
832
Let $n$ be a positive integer, and let $G$ be a random graph from $G(n, 1/2)$. Let $e_1, . . . , e_{n \choose 2}$ be the
possible edges on the vertex set ${1, . . . , n}$, and for each $i$, let $A_i$ be the event that $e_i ∈ E(G)$.
Prove that the events $A_1, . . . , A_{n \choose 2}$ are independent.


Can I just have some help understanding what details I should be including here?
It's so trivial that I don't know how to write it down as a proof.
There is a probability of $\frac{1}{2}$ that any arbitrary possible edge will be an edge of the graph. And it just seems obvious that whether one edge is in the graph has nothing at all to do with if another edge is in the graph.

So then if we choose an arbitrary subset of $A_1, . . . , A_{n \choose 2}$, the probability of the events in the subset occurring will be the product of the individual probabilities of the events.
In $G(n, p)$, the edges appear independently with probability $p$ (by definition of $G(n, p)$). So the question indeed is asking to prove something that is immediate from the definition.