The k-representation number of the random graph

The k-representation number of a graph G is the minimum cardinality of the system of vertex subsets with the property that every edge of G is covered at least k times while every non-edge is covered at most $(k-1)$ times. In particular, for $k=1$ this notion is equivalent to the clique number of a graph G. Extending results of Frieze and Reed, and Eaton and Grable, we study the k-representation number of $G(n,1/2)$. As a tool, we will prove a sharp concentration result counting the number of induced subgraphs of $G(n,1/2)$ with density (1/2+α). In Lemma 3.7, we will show that the number of such subgraphs is close to its expected value with probability 1-exp(-nC).