Probability of a random graph being triangle-free 
Let $S$ be the set of all graphs with vertex set $\{1,2,\ldots,n\}$. A random graph $G\in S$ has probability $2^{-{n \choose 2}}$. Show that a random graph almost surely contains a triangle.

My attempt so far: we want to show that as $n$ goes to infinity, the probability of a triangle-free graph goes to zero. I tried to find a general formula for the probability of a triangle-free graph with $n$ vertices, but it seems impossible. I know that for any three vertices, the probability of not being a triangle is $\frac{7}{8}$, but I can't calculate the probability of the union of all such three vertices. Is there any other way to approach this problem?
 A: Let me preface this answer with the following: The overestimation of triangles is a much better argument for your particular problem as the probability of an edge appearing is fixed for all $n$. If you allow $p=p(n)$ then you have to be more careful. The technique that follows is technical, but it can be adapted very easily to show for any $p\ne o(\frac{\ln n}{n})$ that a.a.s. $G$ will have a triangle.

First observe that since the probability that any $G$ exists is $2^{-\binom{n}{2}}$ it is equivalent to consider each of the $\binom{n}{2}$ edges being chosen independently to appear in $G$ with probability $p=1/2$.
If we let $X$ be the discrete nonnegative random variable that counts the number of triangles in $G$, then we wish to show that $P(X=0)\to 0$ as $n\to\infty$. We will use the second moment method to get our result.
By Chebychev's inequality and the fact that $X$ is a nonnegative random variable, then we know that
$$
P(X=0)\le P(|X-E(X)|\ge E(X))\le \frac{Var(X)}{E(X)^2}=\frac{E(X^2)-E(X)^2}{E(X)^2}=\frac{E(X^2)}{E(X)^2}-1.
$$
So if we can show that $\frac{E(X^2)}{E(X)^2}\to 1$ as $n\to\infty$, then we are done.
Observe that $E(X)=\binom{n}{3}p^3\approx c_1n^3$ so that $E(X)^2\approx c_2n^6$. Suppose we enumerate all the $\binom{n}{3}$ possible triples and for $1\le i\le \binom{n}{3}$ we let
$$
T_i=\begin{cases}1, &\text{if the }i\text{th triple is a triangle}\\0, &\text{otherwise}\end{cases}.
$$
Then $X=\sum T_i$ so that 
$$
X^2=\left(\sum_{i=1}^{\binom{n}{3}} T_i\right)^2=\sum_{1\le i,j\le\binom{n}{3}} T_iT_j
$$
and
$$
E(X^2)=\sum_{1\le i,j\le\binom{n}{3}} P(T_iT_j=1).
$$
The RHS can be partitioned by the number of vertices that the $i$th and $j$th triangles can have in common: zero, one, two or three in common. Thus
$$
\begin{align*}
E(X^2)&=\sum_{1\le i,j\le\binom{n}{3}} P(T_iT_j=1)\\
&=\sum_{zero} P(T_iT_j=1)+\sum_{one} P(T_iT_j=1)+\sum_{two} P(T_iT_j=1)+\sum_{three} P(T_iT_j=1)\\
&=\binom{n}{3}\binom{n-3}{3}\frac{1}{2^6}+n\binom{n-1}{4}\frac{1}{2^6}+\binom{n}{2}\binom{n-2}{2}\frac{1}{2^5}+\binom{n}{3}\frac{1}{2^3}\\
&\approx c_3n^6+c_4n^5+c_5n^4+c_6n^3.
\end{align*}
$$
Thus 
$$
\frac{E(X^2)}{E(X)^2}\approx\frac{c_3n^6+c_4n^5+c_5n^4+c_6n^3}{c_2n^6}=\frac{c_3}{c_2}+\frac{c_4}{c_2n}+\frac{c_5}{c_2n^2}+\frac{c_6}{c_2n^3}.
$$
Observing that $c_2=c_3=\frac{1}{3^22^8}$ then as $n\to\infty$ we have
$$
\frac{E(X^2)}{E(X)^2}\approx\frac{c_3}{c_2}+\frac{c_4}{c_2n}+\frac{c_5}{c_2n^2}+\frac{c_6}{c_2n^3}\to 1
$$
and our conclusion follows.
A: In this situation, you can greatly overestimate the probability of no triangle and still get it to approach zero.  Divide your set of $n$ vertices into disjoint sets of size $3$ (with perhaps one or two vertices left over if $n$ isn't divisible by $3$). So you've got at least $(n-2)/3$ pairwise disjoint sets of size $3$. What's the probability that none of these sets forms a triangle? Well, each one of these sets fails to form a triangle with probability $7/8$ (as you said in the question). And, because the three-element sets under consideration are disjoint, these probabilities, for different $3$-element sets, are independent.  So the probability that none of these $(n-2)/3$ (or more) sets forms a triangle is $(7/8)^{(n-2)/3}$ (or less).  This approaches zero as $n\to\infty$.  
The probability that there are no triangles at all is, of course, $\leq$ the probability that none of our particular $3$-element sets forms a triangle, so it also approaches zero.
A: Consider a random graph on $3n$ vertices. Divide the vertices into $n$ triplets. The probability that a given triplet is not a triangle is $\frac78$, so the probability that no triplet is a triangle is $\left(\frac78\right)^n$. The probability that the graph is triangle-free is thus at most $\left(\frac78\right)^n$, which tends to $0$ as $n$ increases without bound.
