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 (12+). In Lemma 3. 7, we will show that the number of such subgraphs is close to its expected value with probability 1- (-nC).