Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

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