## Exercises11.8Exercises

###### 1.

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{.}$$

1. Show that $$E(X+Y)\lt 1\text{,}$$ when $$n$$ is sufficiently large.

2. 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.