11.8: Exercises

1. Consider a random graph with vertex set \(\{1,2,;n\}\). If the edge probability is \(p=1/2\), 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\).

a. Show that \(E(X+Y)<1\), when \(n\) is sufficiently large.

b. Use the result from part a to show that \(ω(G)\) is less than \(2 \log ⁡n\), 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)≥ω(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,…,n\}\). For each distinct pair \(i, j\) with \(1≤i<j≤n\), flip a fair coin. If the result is heads, orient the edge from \(i\) to \(j\), which we denote by \((x,y)\). If the toss is tails, then the edge is oriented from \(j\) to \(i\), denoted \((y,x)\). Show that when \(n\) is large, with high probability, the following statement is true: For every set \(S\) of size \(\log ⁡n/10\), there is a vertex \(x\) so that \((x,y)\) in \(T\) for every \(y \in S\).

3. Let \(T\) be a random tournament on \(n\) vertices. Show that with high probability, the following statement is true: For every pair \(x, y\) of distinct vertices, either (1) \((x,y)\) in \(T\), or (2) there is a vertex \(z\) for which both \((x,z)\) and \((z,y)\) are in \(T\).

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/(10n)\) 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.