Consider a random graph with vertex set \(\{1,2,\dot,n\}\text{.}\) If the edge probability is \(p=1/2\text{,}\) then let \(X\) denote the number of complete subgraphs of size \(t=2\log n\) and let \(Y\) denote the number of independent sets of size \(t=2\log n\text{.}\)
Show that \(E(X+Y)\lt 1\text{,}\) when \(n\) is sufficiently large.
Use the result from part a to show that \(\omega(G)\) is less than \(2\log n\text{,}\) while the chromatic number of \(G\) is at least \(n/(2\log n)\) (both statements holding with high probability). As a result, the basic inequality \(\chi(G)\ge\omega(G)\) is far from being tight for a random graph.
2.
We form a random tournament as follows. Start with a complete graph with vertex set \(\{1,2,\dots,n\}\text{.}\) For each distinct pair \(i\text{,}\)\(j\) with \(1\le i\lt j\le n\text{,}\) flip a fair coin. If the result is heads, orient the edge from \(i\) to \(j\text{,}\) which we denote by \((x,y)\text{.}\) If the toss is tails, then the edge is oriented from \(j\) to \(i\text{,}\) denoted \((y,x)\text{.}\) Show that when \(n\) is large, with high probability, the following statement is true: For every set \(S\) of size \(\log n/10\text{,}\) there is a vertex \(x\) so that \((x,y)\) in \(T\) for every \(y\in S\text{.}\)
3.
Let \(T\) be a random tournament on \(n\) vertices. Show that with high probability, the following statement is true: For every pair \(x\text{,}\)\(y\) of distinct vertices, either (1) \((x,y)\) in \(T\text{,}\) or (2) there is a vertex \(z\) for which both \((x,z)\) and \((z,y)\) are in \(T\text{.}\)
4.
Many statements for random graphs exhibit a threshold behavior. Show that a random graph with edge probability \(p=10\log n/n\) almost certainly has no isolated vertices, while a random graph with edge probability \(p=\log n/(10 n)\) almost certainly has at least one isolated vertices.
5.
In the sense of the preceding problem, determine the threshold probability for a graph to be connected.
