Skip to main content

# Section11.8Exercises¶ permalink

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