EDGE-DISJOINT CLIQUES IN GRAPHS WITH HIGH MINIMUM DEGREE

For a graph G and a fixed integer k >= 3, let nu(k) (G) denote the maximum number of pairwise edge-disjoint copies of K-k in G. For a constant c, let.(k, c) be the infimum over all constants gamma such that any graph G of order n and minimum degree at least cn has nu(k) (G) >= gamma n(2)(1 -o(n)(1)). By Turan's theorem, eta(k, c) = 0 if c <= 1 -1/(k -1) and by Wilson's theorem, eta(k, c) -> 1/(k(2) - k) as c -> 1. We prove that for any 1 > c > 1-1/(k-1), eta(k, c) >= c/2 - ((k 2)-1)c(k-1)/2 Pi(k-2)(i=1) ((i+1)c-i)+2((k 2)-1c(k-2), while it is conjectured that eta (k, c) = c/(k(2) - k) if c >= k/(k + 1) and eta(k, c) = c/2 -(k - 2)/(2k - 2) if k/(k + 1) > c > 1 - 1/(k - 1). The case k = 3 is of particular interest. In this case the bound states that for any 1 > c > 1/2, eta(3, c) >= c/2 -c(2)/4c-1. By further analyzing the case k = 3 we obtain the improved lower bound eta(3, c) >= (12 c(2)-5 c+2-root 240 c(4)-216 c(3)+73c(2)-20 c+4)(2 c-1)/32(1-c) c. This bound is always at most within a fraction of (20 - root 238)/6 > 0.762 of the conjectured value, which is eta(3, c) = c/6 for c >= 3/4 and eta(3, c) = c/2 - 1/4 if 3/4 > c > 1/2. Our main tool is an analysis of the value of a natural fractional relaxation of the problem.