On the problems of edge disjoint cliques in graphs

Thesis

Nguyen Huu Hoi

Supervisor: Győri Ervin

2005

Eötvös Loránd University, Mathematics Department

Table of contents

Preface. 2

Chapter 1.  Estimates on general graphs.  4
Chapter 2.  Estimates on graphs of small size.  15
Chapter 3.  Other methods and relating problems.  24

References. 33

Preface

Many results have been published in extremal graph theory on the number of given size cliques in graphs. To some extent, there are three main topics:

• on the maximal number of cliques.

• on the maximal number of vertex disjoint cliques.

• on the maximal number of edge disjoint ones.

For the first topic, Moon and Moser [11] proved that a graph of order n and size e (i.e it has n vertices and e edges) contains at least (e/3n)(4e−n^{2}) triangles, the analogous results can be proved for the general case. If e is bounded from above then better lower bounds can be proved, say for the number of triangles, Bollobás [2] proved that if n^{2}/4 ≤ e ≤ n^{2}/3 then the graph contains at least (n/9)(4e − n^{2}) triangles.

From another viewpoint, Erdős conjectured that if G is a graph of order n and size ⌊n^{2}/4⌋ + m (m < n/2) then G has at least m⌊n/2⌋ triangles. Lovász and Simonovits [12] proved this conjecture whenever n is sufficiently large. More results can be found in [3],

[4] and [14].

Dealing with the second one, Hajnal and Szemerédi [1] showed that if the minimum degree δ(G) ≥ (1 − 1/r)n then G contains ⌊n/r⌋ vertex-disjoint copies of K_{r}. One can replace K_{r} by a H graph of order r, and the extended version of the Hajnal-Szemerédi becomes a theorem of Alon and Yuster [15] concerning the vertex disjoint copies of H when δ(G) is greater than (1 − 1/χ(H))n. These problems are studied in a large number of papers by E. Szemerédi, J. Komlós, M. Simonovits, R. Yuster.

The thesis concentrates on the third topic, studying on the number of edge disjoint cliques. For a graph G of order n and size m (which are given), let edk_{k}(G) denote the maximum number of edge disjoint K_{k}’s in G. Let edk_{k}(n, m) denote the minimum of edk_{k}(G) for all graphs G of order n and size m.

In the first chapter, generally speaking, we will prove edk_{3}(n, \frac{n^{2}}{4} + m) ≥ \frac{5}{9}m − O(n), edk_{4}(G) ≥ \frac{5}{18}m − o(n^{2}) and edk_{k}(n, t_{k−1,n} + m) ≥ _{\frac{1}{\binom{k}{2}−(k−2)}}m for k ≥ 5. The latter could

be refined by method applied in the first two, however the result would not be much better and still far from the possibly best edk_{k}(G) ≥ \frac{2}{k}m − o(n^{2}).

The second chapter discusses the case the graph contains t_{r−1}(n) + m edges, where m = o(n^{2}). There are almost m cliques can be found. Generally,

edk_{k}(n, t_{k−1}(n) + m) = m − O(\frac{m^{2}}{n^{2}} )

and

edk_{k}(n, t_{k−1}(n) + m) = m

if m is ”linear”.

The last chapter is miscellaneous and contains three small topics. The first two deal a bit with fractional method. On the third we are likely to have some notes upon the relation between edk_{k}(G) and other structures of the graph.

Thanks I am very grateful to my advisor Győri Ervin for giving me this pretty topic. Without his help and encouragement I could not have finished the work.

Chapter 1

For n = t(k − 1) + r, 0 ≤ r ≤ k − 2, let T_{k−1,n} denote the complete (k-1)-partite graph of n vertices such that r color classes contain t + 1 vertices and k − r − 1 color classes contain t vertices. Then T_{k−1,n}, which has t_{k−1,n} := |E(T_{k−1,n})| = [n(n − t) − r(t + 1)]/2 edges, does not contain any complete subgraph K_{k} of k vertices. Turán proved that any other graph of n vertices with at least t_{k−1,n} edges contains K_{k} as a subgraph. T_{k−1,n} is called the (k − 1)−partite Turán graph. Results of Erdős, Goodman and Pósa [16] (k = 3) and Bollobás [2] (k ≥ 4) imply that

T 1. The edge set of every graph of n vertices can be decomposed into at most t_{k−1,n} edge disjoint K_{k}’s and edges. If k ≥ 3 then T_{k−1,n} is the only extremal graph. For k = 3, the complete graph K_{4}, K_{5} and the graphs T_{2,n}(n = 1, 2, ..) are the extremal graphs.

The results can be formulated in the following form

edk_{k}(n, t_{k−1,n} + m) ≥ _{\frac{1}{\binom{k}{2}−1}}m if k ≥ 3.

In a paper by Győri and Tuza [6], the result was improved (k ≥ 4). Let p_{k}(G) =min{∑_{1}^{m} |V (G_{i})| : G_{i}’s are K_{k} and edges,∪_{i}^{m}E(G_{i}) = E(G)}. If G is K_{k}−free then p_{k}(G) = 2|E(G)| and, in particular, p_{k}(T_{k−1,n}) = 2t_{k−1,n}. The authors stated that

T 2. If k ≥ 4 and G is an arbitrary graph of n vertices then p_{k}(G) ≤ 2t_{k−1,n} and equality holds only for T_{k−1,n}.

Which means

edk_{k}(n, t_{k−1,n} + m) ≥ _{\frac{1}{\binom{k}{2}− \frac{k}{2}}} m if k ≥ 4

equality holds only for Turán graphs. (k ≥ 4 is supposed because p_{3}(G) is not always smaller than 2t_{2}(n). If we cover the complete graph K_{6m−2} by edge disjoint triangles and edges, the number of edges used in the cover is at least 3m, so, p_{3}(K_{6m−2}) ≥ |E(K_{6m−2})| + 3m = 2t_{2,6m−2} + 1) By using the same method, the result can be improved a bit.

Theorem 1.1. (n ≥ k ≥ 3)

edk_{k}(n, t_{k−1,n} + m) ≥ \frac{1}{\binom{k}{2} − (k − 2)}m

and only T_{k−1,n}, for k = 3, K_{4},K_{5}, T_{2,n} are the extremal examples.

To prove this, we need the a result of Hajnal and Szemerédi[1] which has been noticed in the preface.

T 3. Let G be a graph of n vertices such that the degree of every vertex in G is at least d. Then there exist vertex disjoint complete subgraphs G_{1},...,G_{n−d} of G such that ∪_{1}^{n−d}V (G_{i}) = V (G) and the numbers of the vertices of the subgraphs G_{i} differ from each other at most one, i.e,|V (G_{i})| is ⌊\frac{n}{n−d}⌋ or ⌈\frac{n}{n−d}⌉ for 1 ≤ i ≤ n − d.

Proof of Theorem 1.1. The case k = 3 was settled. We prove for k ≥ 4 by induction on n. If n = k the statement holds obviously. Suppose that it holds for graphs of at most n − 1 vertices. Let

n − 1 = t(k − 1) + r, 0 ≤ r ≤ k − 2, t ≥ 1.

Then

t_{k−1,n} − t_{k−1,n−1} = n − t − 1 = t(k − 2) + r.

Consider an arbitrary graph G of n vertices and t_{k−1}(n) + m edges. Let x be a vertex of G with minimum degree, d := d_{G}(x). If d ≤ n − 1 − t, then

edk_{k}(G) ≥ edk_{k}(G − x) ≥ \frac{1}{\binom{k}{2} − (k − 2)}(t_{k−1,n} + m − d − t_{k−1,n−1})

≥ \frac{1}{\binom{k}{2} − (k − 2)}m.

Equality holds iff d = n − t − 1, G − x = T_{k−1,n−1}, and m = 0, so G = T_{k−1,n} (otherwise Turán’s theorem implies edk_{k}(G) ≥ 1) From now on, suppose

d ≥ n − t = t(k − 2) + r + 1.

In this case we will prove the strict inequality. Because of the minimality of d(x), the degree of every vertex in G(N(x))(the induced graph by neighbors of x) is at least 2d − n. Applying T 3 to G(N(x)), we obtain that there exist vertex disjoint complete subgraphs G_{1},..,G_{n−d} of order ⌊\frac{d}{n−d}⌋ or ⌈\frac{d}{n−d}⌉ and ∪_{1}^{n−d}V (G_{i}) = V (N(x)). Since

\frac{d}{n − d} ≥ \frac{t(k − 2) + r + 1}{t} > k − 2

There are two cases to be considered:

Case 1. There exists G_{i} with |V (G_{i})| = k − 2. Suppose |V (G_{i})| = k − 1 for i = 1, ..., p and |V (G_{i})| = k − 2 for i = p + 1, ..., n − d where p ≤ n − d − 1.

d = p(k − 1) + (n − p − d)(k − 2)

implies that

p = d(k − 1) − n(k − 2).  (1.1)

Note that p ≥ 1 (otherwise, d = \frac{n(k−2)}{k−1} and thus \frac{d}{n−d} = k − 2, contradiction.)

The graph H := (V (G) − x, E(G)\ ∪_{1}^{p} E(G_{i})) has t_{k−1,n} + m − d − p\binom{k−1}{2} edges. By the induction hypothesis,

edk_{k}(G) ≥ p + edk_{k}(H) ≥ p + \frac{1}{\binom{k}{2} − (k − 2)}(t_{k−1,n} + m − d − p\binom{k − 1}{2} − t_{k−1,n−1})

= \frac{1}{\binom{k}{2} − (k − 2)}m + \frac{1}{\binom{k}{2} − (k − 2)}(p + t(k − 2) + r − d) > \frac{1}{\binom{k}{2} − (k − 2)}m

Because p + t(k − 2) + r − d = p − 1 + t(k − 2) + r + 1 − d

= p − 1 + \frac{n(k − 2)}{k − 1} + \frac{r + 1}{k − 1} − d = p − 1 − \frac{p}{k − 1} + \frac{r + 1}{k − 1}

• If p ≥ 2, then p − 1 − \frac{p}{k−1} ≥ p − 1 − \frac{p}{2} = \frac{p−2}{2} ≥ 0, the sum is positive.

• If p = 1, then the sum above may be 0 when r = 0 and H = T_{k−1,n−1}, leading to n = t(k − 1) + 1 and d = \frac{n(k−2)+1}{k−1} = t(k − 2) + 1. Since n > k we see that t ≥ 2 and so d < n − 1.

In H every color is of t vertices and every vertex is of t(k − 2) degree. After adding x and restoring the deleted edges to make G, there is still at least one vertex of that degree, which is smaller than that of x, contradicts the supposition about x. Case 2. |V (G_{i})| ≥ k − 1 for i = 1, ..., n − d. So, d ≥ (k − 1)(n − d) Let

d = s(k − 1) + q, 0 ≤ q ≤ k − 2.  (1.2)

Then 1 ≤ n − d ≤ s ≤ t by 1.2. The minimum degree in G(N(x)) is at least

d − (n − d) ≥ d − s

and so, according to T 3, there exist vertex disjoint complete subgraphs G_{1}, G_{2}, ..., G_{s} of k − 1 vertices in G(N(x)) so that ∪_{1}^{s}V (G_{i}) ⊆ V (N(x)). Again, using the induction hypothesis for the graph

H := (V (G) − x, E(G)\ ∪_{1}^{s} E(G_{i}) ∪ E(x))

of t_{k−1,n} + m − d − s\binom{k−1}{2} edges, we have

edk_{k}(G) ≥ s + edk_{k}(H)

≥ s + \frac{1}{\binom{k}{2} − (k − 2)}(t_{k−1,n} + m − d − s\binom{k − 1}{2}) = \frac{1}{\binom{k}{2} − (k − 2)}m

+\frac{1}{\binom{k}{2} − (k − 2)}(s + t(k − 2) + r − d) > \frac{1}{\binom{k}{2} − (k − 2)}m.

Here

s + t(k − 2) + r − d = s + t(k − 2) + r − s(k − 1) − q
= t(k − 2) − s(k − 2) + r − q = (t − s)(k − 2) − q + r > 0

Let’s explain why this happens.

• if t = s, then the sum is not negative, and could be zero if q = r, that is d = n − 1, and H = T_{k−1,n−1}. However, in H, each color does not contain edges because we have deleted from them, but we only deleted edges that form edge disjoint K_{k−1} in G−x. So each color is of k − 1 size, it means n = (k − 1)^{2} + 1. It is easy to verify that in this graph, a copy of K_{(k−1)^{2}+1}) where k ≥ 4, there are at least k, and then more than k − 1 = _{\frac{1}{\binom{k}{2}−(k−2)}}m

edge disjoint K′_{k}s.

• if t > s then q ≤ k−2, the sum is not negative. It would be 0 if t = s+1, q = k−2, r = 0, and H = T_{k−1,n−1}, so d = (t − 1)(k − 1) + k − 2 = t(k − 1) − 1 = n − 2. But the in H, again, every vertex is of t(k − 2) degree. After adding x and the deleted edges to make G, since there is one vertex is not x′s neighbor, its degree remains unchanged, in addition, t(k − 1) − 1 > t(k − 2), so x could not be a vertex of minimum degree in G

The result of Győri and Tuza is proved for k ≥ 4 already. As we have noticed, the K_{6m−2} example disproves the similar assertion for k = 3: p_{3}(G) ≤ 2t_{2,n}. However, it might be possible that:

Conjecture. For every graph of n vertices, p_{3}(n) ≤ \frac{1}{2}n^{2} + o(n^{2}). (⇔ edk_{3}(t_{2}(n) + m) ≥ \frac{2}{3}m − o(n^{2})).

Győri and Tuza [6] proved

T 4. p_{3}(n) ≤ \frac{9}{16}n^{2}.

We prove the following improvement

Theorem 1.2. edk_{3}(n, t_{2}(n) + m) ≥ \frac{5}{9}m − O(n).

Before proving the theorem, we need

T 5. Let k_{3}(G) denote the number of triangles in an arbitrary graph G of n vertices. Then G contains at least \frac{k_{3}(G)}{n−2} − O(n) edge disjoint triangles.

Proof of T 5. It has been shown proven by Spencer [10] that in the complete graph K_{n} of n vertices there can be found a (partial) Steiner system S_{n} of s_{n} = \frac{1}{3} \binom{n}{2} − O(n) edge disjoint triangles. Let G be a graph of n vertices and denote by T the set of triangles of G(then|T| = k_{3}(G)). For an arbitrary permutation π of V (G), put t_{π} = |T ∩ π(S_{n})| where π(S_{n}) is the image of S_{n} after applying π. For each pair T, T′ of triangles satisfying T ∈ T and T′ ⊂ K_{n} there are exactly 6(n − 3)! permutations such that T = π(T′). On the other hand, S_{n} contains s_{n} of the triangles of K_{n}, therefore the average value of t_{π} is k_{3}(G)s_{n}/\binom{n}{3}. Consequently, there exists a π for which π(S_{n}) contains at least k_{3}(G)s_{n}/\binom{n}{3} triangles of G.

T 6. Every graph of n vertices and e edges contains at least \frac{e}{3n}(4e − n^{2})(\frac{1}{n−2}) − O(n) edge disjoint triangles.

Proof of T 6. Without loss of generality, we replace t_{2}(n) by \frac{n^{2}}{4} . If e ≤ \frac{n^{2}}{4} , there is nothing to prove. Otherwise, if \frac{n^{2}}{4} < e ≤ \binom{n}{2}, the result of Moon and Moser [11] states that G contains at least

k_{3} ≥ \frac{e}{3n}(4e − n^{2})

triangles, therefore T 5 implies the validity of our theorem.

Proof of Theorem 1.2. Induction on n. The statement is obvious for n ≤ 5. Assume that Theorem 1.2 holds for graphs of at most n − 1 vertices. Let G be an arbitrary graph of order n and size e = \frac{n^{2}}{4} + m Case 1. e ≥ \frac{5n^{2}}{12} then T 6 implies

edk_{3}(G) ≥ \frac{e}{3n^{2}} (4e − n^{2}) − O(n)

≥ \frac{\frac{5}{12}n^{2}}{3n^{2}} 4m − O(n) = \frac{5}{9}m − O(n)

Case 2. e < \frac{5n^{2}}{12} . Denote by d the minimum degree, then d < \frac{5}{6}n. Let x be a vertex of G with this minimum degree, N(x) be the graph induced by x′s neighbors. We distinguish two subcases.

Subcase 2.1 If d ≤ \frac{n}{2} then

edk_{3}(G) ≥ edk_{3}(G − x) ≥ \frac{5}{9}(e − d − \frac{(n − 1)^{2}}{4} ) − O(n − 1)

= \frac{5}{9}(e − \frac{n^{2}}{4} ) + \frac{5}{18}(n − 2d) − O(n) ≥ \frac{5}{9}m − O(n).

Subcase 2.2 If d > \frac{n}{2}, in N(x) there exist vertex disjoint complete subgraphs G_{1},...,G_{n−d} of order ⌊\frac{d}{n−d}⌋ or ⌈\frac{d}{n−d}⌉ satysfying ∪_{1}^{n−d}V (G_{i}) = V (N(x)). Suppose that |V (G_{i})| = ⌈\frac{d}{n−d}⌉ for i = 1,..,p and |V (G_{i})| = ⌊\frac{d}{n−d}⌋ for i = p + 1, ..., n − d where p ≤ n − d − 1 If ⌊\frac{d}{n−d}⌋ = 1, then \frac{n}{2} < d < \frac{2n}{3} and p = 2d − n. We see that

edk_{3}(G) ≥ p + edk_{3}(G − x, e − d − p) ≥ p + \frac{5}{9}(e − d − p − \frac{(n − 1)^{2}}{4} ) − O(n − 1)

= \frac{5}{9}(e − \frac{n^{2}}{4} ) + p + \frac{5}{18}n − \frac{5}{9}(d + p) − O(n)

= \frac{5}{9}m − O(n) + \frac{6d − 3n}{18} ≥ \frac{5}{9}m − O(n).

If ⌊\frac{d}{n−d}⌋ ≥ 2 then let

d := 2s + q(q = 0, 1),  (1.3)

In G(N(x)) every degree is at least d−s(2d−n ≥ d−s), so there exist s endpoint disjoint edges. Therefore

edk_{3}(G) ≥ s + edk_{3}(n − 1, e − d − s)

≥ s + \frac{5}{9}(e − 3s − q − \frac{(n − 1)^{2}}{4} ) − O(n − 1)

= \frac{5}{9}(e − \frac{n^{2}}{4} ) − O(n) + \frac{5}{18}n − \frac{2}{3}s

≥ \frac{5}{9}m − O(n)

since 2s ≤ d < \frac{5}{6}n. We are done.

Corollary. p_{3}(n) ≤ \frac{5}{9}n^{2} + O(n).

Proof of corollary. Obviously, p_{3}(G) = 2e − 3edk_{3}(G). Using both

edk_{3}(G) ≥ \frac{4m(m − \frac{n^{2}}{4} )}{3n^{2}}

and

edk_{3}(G) ≥ \frac{5}{9}m − O(n)

for every graph G of size e more than \frac{n^{2}}{4} we obtain

p_{3}(G) ≤ n^{2} \frac{m}{n^{2}} (3 − 4\frac{m}{n^{2}} )

and also

≤ \frac{m}{3} + \frac{5}{12}n^{2} + O(n)

either. The maximum point of the smaller value between them does not exceed \frac{5}{9}n^{2}+O(n), being when \frac{m}{n^{2}} is about \frac{3}{8}

I believe that by induction, as well as by combination of estimates of edk_{3}(G) depending on the magnitude of e and δ(G), we might work out better results.

For k = 4, Theorem 1.1 gives us edk_{4}(n, t_{3}(n)+m) ≥ \frac{1}{4}m. Using the analogous technique, this result can be refined.

Theorem 1.3.

edk_{4}(n, m + t_{3}(n)) ≥ \frac{5}{18}m − o(n^{2}).

To settle this theorem, a general result of Moon and Moser dealing the number of cliques is needful. Let t(K_{r}, G) = \frac{hom(K_{r},G)}{n^{r}} where hom(K_{r}, G) denote the number of homomorphism of K_{r} to G, that is t(K_{r}, G) = \frac{r!k_{r}(G)}{n^{r}}.

T 7. r\frac{t(K_{r},G)}{t(K_{r−1},G)} ≤ (r − 1)\frac{t(K_{r+1},G)}{t(K_{r},G)} + 1.

Proof of T 7. H_{r+1}^{i} denotes the graph remaining after deleting i edges sharing a common vertex in K_{r+1}. It can be shown that t(K_{r−1}, G)t(H_{r+1}^{1}, G) ≥ t(K_{r}, G)^{2} (from the positive semidefinite property of a matrix, [13]) Consequently,

r\frac{t(K_{r}, G)}{t(K_{r−1}, G)} ≤ r\frac{t(H_{r+1}, G)}{t(K_{r}, H)}.

Applying the super-modular property(i.e t(F +e, G)+t(F +f, G) ≤ t(F, G)+t(F +e+f, G)) r − 1-times, we obtain that rt(H_{r+1}^{1}) ≤ (r − 1)t(K_{r+1}) + t(K_{r}).

Corollary. for k ≥ 2

k_{k}(G) ≥ \frac{1}{k!} ∏_{1}^{k−1}(1 − i(1 − 2q))n^{k} where q = \frac{e}{n^{2}} .  (1.4)

Proof of corollary. There is nothing to prove if e < \frac{1}{2}(1 − \frac{1}{k−1})n^{2}. Suppose that e ≥ \frac{1}{2}(1 − \frac{1}{k−1})n^{2}. Let b_{i+1} := \frac{t_{i+1}(G)}{t_{i}(G)}, i = 1, .., k − 1, b_{1} := 1. Note that b_{i} ≤ 1(i = 1, .., k) and t_{k}(G) = ∏_{1}^{k} b_{i}. The inequality 1.4 implies

rb_{r} ≤ (r − 1)b_{r+1} + 1, so r(1 − b_{r}) ≥ (r − 1)(1 − b_{r+1}).

therefore

1 − b_{i} ≤ ∏_{1}^{i−2} \frac{r+1}{r}(1 − b_{2}) = (i − 1)(1 − \frac{2e}{n^{2}} ) = (i − 1)(1 − 2q), b_{i} ≥ 1 − (i − 1)(1 − 2q).

Corollary.

k_{4}(G) ≥ \frac{1}{6}q(3q − 1)(4q − 1)n^{4} where q = \frac{e}{n^{2}} ≥ \frac{1}{3}.  (1.5)

We still need the general form of the T 5

T 8. G contains at least \frac{(r−2)!k_{r}(G)}{n^{r−2}} − o(n^{2}) edge disjoint K_{r}.

Proof of this theorem. According to a result of V. Rödl [18], There is a system of edge disjoint K′_{r}s which covers almost all the edges of the complete graph K_{n} but o(n^{2}). Denote this system by S_{n}, the left steps are quite similar to what we have done in T 5

Proof of Theorem 2.2. We will use the same technique as before. For convenience, let t_{3}(n) be \frac{n^{2}}{3} . To explain why the constant is \frac{5}{18}, let us replace it by α and try to find the possibly largest value of α. For small n, clearly edk_{4}(G) ≥ αm − o(n^{2}). Suppose that it holds for every graph of at most n − 1 vertices. Consider an arbitrary graph G of n vertices and let x be a vertex of G with minimum degree, d(x) = d. If d is relatively small then the induction step can be done easily as follows. In case of d < \frac{2n}{3}, we have

edk_{4}(G) ≥ edk_{4}(G − x) ≥ α(e − d − \frac{(n − 1)^{2}}{3} ) − o((n − 1)^{2})

≥ αm − o(n^{2}).

It is still easy when \frac{2n}{3} ≤ d < \frac{3n}{4} because applying the T 3 to G(N(x)), there exist vertex disjoint subgraphs G_{1},...,G_{n−d} of order 2 or 3 which cover the vertices of G(N(x)). The number of K′_{3}s in {G_{1},...,G_{n−d}} is 3d − 2n, therefore

edk_{4}(G) ≥ p + edk_{4}(G − x) ≥ p + α(e − d − 3p − \frac{(n − 1)^{2}}{3} ) − o(n^{2})

= α(e − \frac{n^{2}}{3} ) + (3 − 10α)(d − \frac{2n}{3}) − o(n^{2}) ≥ αm

Providing that

α ≤ \frac{3}{10}.

So by this way we can’t hope to find α larger than \frac{3}{10} From now on let d ≥ \frac{3n}{4}. Set d = 3s + q, where 0 ≤ q ≤ 2. Again, since every vertex in G(N(x)) has a degree at least d − s, there exist s vertex disjoint K_{3} in G(N(x)), as a consequence

edk_{4}(G) ≥ s + edk_{4}(n − 1, e − d − 3s))

≥ s + α(e − d − 3s − \frac{(n − 1)^{2}}{3} )) − o((n − 1)^{2})

≥ αm − o(n^{2}) + \frac{2α}{3}(n − \frac{d(6α − 1)}{2α}).

Thus if e ≤ \frac{α}{6α−1}n^{2} then we accept this induction step. Otherwise the formula stated in T 8 for r = 4 gives,

edk_{4}(G) ≥ \frac{1}{3}q(3q − 1)(4q − 1)n^{2} − o(n^{2}),

here q = \frac{e}{n^{2}} ≥ \frac{α}{6α−1} and q ≥ \frac{1}{3} also. Under these conditions, the inequality

\frac{1}{3}q(3q − 1)(4q − 1) ≥ α(q − \frac{1}{3}) holds when α ≤ \frac{5}{18}.

A possible generalization of these theorems is

Conjecture. edk_{k}(n, t_{k−1}(n) + m) ≥ \frac{2}{k}m − o(n^{2}).

Remarks. Let p(G) denote the minimum of ∑ |V (G_{i})| over all decompositions of G into edge disjoint cliques G_{1}, G_{2}, .. (i.e. the subgraphs G_{i}’s are pairwise edge disjoint cliques such that E(G) = ∪E(G_{i}) and they are not of given sizes). It was conjectured by G.O.H. Katona and T. Tarján and was proven by F.R.K. Chung, E. Győri and A.V. Kostochka that T 9.

p(G) ≤ 2t_{2}(n)

equality holds if and only if G ≃ T_{2}(n).

The proof is now simple. So if G is K_{4} free then edk_{3}(G) ≥ \frac{2}{3}m, It is still easy to show that in this case edk_{3}(G) ≥ \frac{3}{4}m P. Erdős suggested to study a similar weigh-function. For any graph G, let p^{∗}(G) denote the minimum of ∑(|V (G_{i})| − 1) over all decompositions of G into pairwise edge disjoint cliques G_{1}, G_{2}, .... A maybe too optimistic conjecture is:

Conjecture. For every graph G of n vertices,

p^{∗}(G) ≤ t_{2}(n).

This conjecture seems to be just a bit stronger than the T 9, but it is not the case. A special case of it is still open, as well.

Conjecture. Every K_{4}-free graph of n vertices and t_{2}(n) + m edges contains m edge disjoint triangles.

Only the following even weaker special case is settled by Győri.

T 10. Every 3-colorable graph of n vertices and t_{2}(n) + m edges contains m edge disjoint triangles.

Proof of T 10. Suppose A, B, C with cardinals a ≥ b ≥ c be the three color parts of V (G). For M is an arbitrary subset of A with cardinals b let edk_{3}(M, B, C) denote the maximum edge disjoint triangles of G restricted on M, B, C. Then edk_{3}(M, B, C) ≥ bc − n_{BC} − n_{BM} − n_{CM} where n_{XY} := |X||Y | − e_{G}(X, Y)(the number of not-G graph edges between X and Y) So the average

\frac{∑_{M⊂A} edk_{3}(M, B, C)}{\binom{a}{b}} ≥ bc − n_{BC} − \frac{n_{AC} \binom{a−1}{b−1} + n_{AB}\binom{a−1}{b−1}}{\binom{a}{b}}

= bc − n_{BC} − \frac{b}{a}(n_{AC} + n_{AB}) ≥ bc − (n_{BC} + n_{AC} + n_{AB})

= bc − (ab + bc + ca − m − t_{2}(n)) = m + t_{2}(n) − a(b + c) ≥ m.

To end up the chapter, we examine the graph G of order n, formed by adding m edges to the T_{2,n}. Let m_{1}, m_{2} be the number of added edges in the red, as well as in the blue color of G, let c_{i} = \frac{m_{i}}{n^{2}} , c := c_{1} + c_{2} = \frac{m}{n^{2}} . We estimate the number of edge disjoint triangles as follows. Suppose there are m_{1} not monochromatic edge disjoint triangles that cover the m_{1} red edges and m_{2} not monochromatic edge disjoint triangles that cover the m_{2} blue edges. By permuting the vertices in each color we receive many such covering by triangles. Let us choose one of those examples randomly and consider the triangles as vertices, adjancency means that the triangles share some edge. We are finding maximal independent set of vertices. Note that a graph of n edges and e edges have at least n − e independent set of vertices. By counting the expectation of the size of the independent set, since each pair of red-blue edges add 4 to the amount, it is at least

m_{1} + m_{2} − \frac{4m_{1}m_{2}}{\frac{n}{2} 2} ≥ m − 4\frac{m^{2}}{n^{2}}

As we can see, when m = o(n^{2}), the estimate works and almost the best, results in about m. However, when m = O(n^{2}) it is unusable because we just used the not monochromatic triangles, for example if m ≥ \frac{1}{8}n^{2} then we win not more than \frac{m}{2} triangles. It is likely that there are at least \frac{2}{3}m edge disjoint triangles in G(would be a corollary of the first conjecture.) However I have no idea to verify this fact. A special case, when the m edges form a triangle-free subgraph in the two colors (therefore only not-monochromatic triangles exist) might be examined by using the fractional results discussed in Chapter 3.

Similarly, the result can be verified for k ≥ 3, that is there exists a constant c_{k} such that after adding m edges to T_{k−1,n} we must have m − c_{k} \frac{m^{2}}{n^{2}} edge disjoint K′_{k}s.

If we add m edges to the Turán graph T_{k−1}(n) arbitrarily then the resulting graph contains at most m edge disjoint cliques of k vertices because each clique must contain at least one new edge. that is,

edk_{k}(n, t_{k−1}(n) + m) ≤ m

If m is large enough, it may occur that we can’t find m or asymptotically m edge disjoint cliques of k vertices. To examine the case when m is small, first we need the following([12])

Let k be an integer ≥ 3, and G be a graph of order n so that t_{k−1}(n) ≤ |E(G)|. We write |E(G)| in the form

|E(G)| = (1 − \frac{1}{t})\frac{n^{2}}{2}

Let d be ⌊t⌋, set m = |E(G)| − t_{d}(n) then

T 11. (“stability theorem”) For C be an arbitrary constant there exist positive constants Δ = Δ(C) and D = D(C) such that if 0 < m < Δn^{2} and

k_{k}(G) ≤ \binom{t}{k}(\frac{n}{t})^{k} + Cmn^{k−2}

then there exists a K_{d}(n_{1}, .., n_{d}) such that ∑ n_{i} = n, |n_{i} − \frac{n}{d}| < D\sqrt{m}, and G can be obtained by adding to and deleting from this K_{d}(n_{1}, n_{2}, .., n_{d}) less than Dm edges.

Especially, for k = d + 1, suppose that m = E(G) − t_{k−1}(n) is much smaller than n^{2}, the theorem becomes

Corollary If k_{k}(G) ≤ Cmn^{k−2} then there exists a K_{k−1}(n_{1}, .., n_{k−1}) such that ∑ n_{i} = n, |n_{i} − \frac{n}{k−1}| < D\sqrt{m} and G can be obtained by adding to and deleting from it less than Dm edges.

Now we are ready to prove Theorem 2.1. edk_{k}(n, t_{k−1}(n) + m) = m − O(\frac{m^{\frac{3}{2}}}{n}) if m = o(n^{2}).

Proof of theorem 2.1. Set C be any constant larger than 1. If

k_{k}(G) ≥ Cmn^{k−2}

then by the proof used in T.8, G contains

\frac{k_{k}(G)k!(n − k)!(\begin{matrix}( & {n \atop 2} & ) \\ ( & {k \atop 2} & ) \end{matrix} − o(n^{2}))}{n!} ≥ \frac{k_{k}(G)n^{2}(k − 2)!(1 − o(1))}{n^{k}}

= Cm(k − 2)!(1 − o(1))

edge disjoint copies of K_{k}, which is more than m provided that n is sufficiently large, and we are done. Otherwise, by the corollary,

k_{k}(G) ≤ Cmn^{k−2}

implies there exists K_{k−1}(n_{1}, .., n_{k−1}) such that ∑ n_{i} = n, |n_{i} − \frac{n}{k−1}| < D\sqrt{m} and G can be obtained by adding to and deleting from it less than Dm edges. Suppose that the number of deleted edges is m_{del}. Let m_{nom} be the number of monochromatic G-edges, then

O(m) = m_{nom} ≥ m_{del} + m.  (2.1)

Set m_{i} be the number of monochromatic edges in i-th color. In each color we choose \frac{n}{k−1} − D\sqrt{m} vertices such that the number of monochromatic edges in it maximum, that is it contains at least

( \frac{\frac{n}{k−1} − D\sqrt{m}}{\frac{n}{k−1} + D\sqrt{m}})^{2}m_{i}

chromatic edges. Therefore the chosen vertices form a Turán graph(with colors’ of size \frac{n}{k−1} − D\sqrt{m}) but at most m_{del} edges have been deleted and the number of the remaining monochromatic edges, m′_{nom}, is obviously

≥ ( \frac{\frac{n}{k−1} − D\sqrt{m}}{\frac{n}{k−1} + D\sqrt{m}})^{2}m_{nom} = m_{nom} − O(\frac{m\frac{3}{2}}{n}).  (2.2)

According to the result noted at the end of the previous chapter, there are at least

m′_{nom} − O( \frac{m′_{nom}}{\frac{n}{k−1} − D\sqrt{m}})^{2} − m_{del}

edge disjoint copies of K_{k}, Taking account into 2.1, 2.2 we see that

edk_{k}(G) ≥ m − O(\frac{m^{\frac{3}{2}}}{n})

For the triangle-case(and similarly for k ≥ 4), let us produce a direct proof of

edk_{3}(n, t_{2}(n) + m) = m − O(\frac{m^{\frac{3}{2}}}{n})

if m = o(n^{2}).

Proof of . Roughly speaking, we will prove that either we can find m edge disjoint triangles or the graph is similar to a graph obtained from T_{2}(n) by adding m edges to it. Delete the edges of edge disjoint triangles of maximum number and let G^{∗} denote the resulting triangle-free graph. If we found m edge disjoint triangles then we are done. So we assume that

|E(G^{∗})| > t_{2}(n) − 2m

Choose a maximum size spanning bipartite graph G_{0} of G^{∗}(with two coloring A, B), let G_{1} = (V, E(G^{∗}) − E(G_{0})), i.e the spanning subgraph of the monochromatic edges. Note that d_{G_{0}}(v) ≥ d_{G_{1}}(v) ( otherwise by changing the color of v we would obtain a greater size spanning bipartite subgraph) Proposition

E(G_{1}) = O(\frac{m^{\frac{3}{2}}}{n})

Proof Since

\frac{1}{|E(G^{∗})|} ∑_{uv∈E(G^{∗})}(d_{G}^{∗}(u) + d_{G}^{∗}(v)) = \frac{1}{|E(G^{∗})|} ∑_{v∈V}(d_{G}^{∗}(v))^{2}

≥ \frac{n}{|E(G^{∗})|}(\frac{∑_{v∈V} d_{G}^{∗}(v)}{n})^{2}

= \frac{4|E(G^{∗})|}{n} ≥ n − \frac{8m}{n}.

There is an edge uv ∈ E(G^{∗}) such that d_{G}^{∗}(u) + d_{G}^{∗}(v) ≥ n − \frac{8m}{n}. Let H_{0} be a spanning bipartite graph of G^{∗} which

i) contains the edges incident to u or v. ii) d_{H_{0}}(w) ≥ d_{H_{1}}(w) if w is not u nor v neighbor, H_{1} = (V, E(G^{∗}) − E(H_{0})). There exists such H_{0}, for example a maximum size spanning bipartite subgraph satisfying i). We have

E(H_{1}) ≤ d\frac{8m}{n}

Where d is the maximum degree in H_{1} because the vertices that are not adjacent to u or v represent all the edges of H_{1}.

If x is a vertex that d_{H_{1}}(x) = d then the graph G^{∗} does not contain any edge joining N_{H_{0}}(x) and N_{H_{1}}(x), so

t_{2}(n) − 2m ≤ |E(G^{∗})| = |E(H_{0})| + |E(H_{1})|

≤ t_{2}(n) − dH_{1}(x)dH_{0}(x) + d\frac{8m}{n}

≤ t_{2}(n) − d^{2} + d\frac{8m}{n}

Thus,

d ≤ \frac{4m}{n} + \sqrt{\frac{16m^{2}}{n^{2}} + 2m} ≤ (\sqrt{2} + o(1))\sqrt{(}m)

and

|E(H_{1}) = O(\frac{m^{\frac{3}{2}}}{n}).

which implies that E(G_{1}) = O(\frac{m^{\frac{3}{2}}}{n}) by the choice of G_{0}. The proposition implies that

|E(G_{0})| ≥ t_{2}(n) − 2m − O(\frac{m^{\frac{3}{2}}}{n}) = t_{2}(n) − (2 + o(1))m

and

|A|, |B| ≥ \frac{n}{2} − O(\sqrt{m}).

From here we may proceed as above.

However, by more careful techniques, we can also prove that

Theorem 2.2. If m = |E(G)| − t_{k−1}(n) = o(n^{2}) then either G contains m edge disjoint K′_{k}s or there is an (k − 1)-coloring {V_{1}, ..V_{k−1}} of V (G) such that the number of monochromatic edges is t_{k−1}(n) − O(1)\frac{m^{2}}{n^{2}} and so |V_{i}| = \frac{n}{r−1} + O(1)\frac{m}{n} for i = 1, .., k − 1.

Using this theorem, it is easy to prove that

Theorem 2.3. (Győri [8])

edk_{k}(n, t_{k−1}(n) + m) = m − O(\frac{m^{2}}{n^{2}} ) if m = o(n^{2})

Corollary. There is a function f(c)(= c_{0}c^{2}) such that every graph of n vertices and t_{k−1}(n) + cn edges contains cn − f(c) edge disjoint K′_{k}s.

It can be proved that for a given order n and size t_{k−1}(n) + m (m = o(n^{2})), edk_{k}(G) is minimum if G is obtained from T_{k−1}(n) by adding edges so that ⌊\frac{m}{n}⌋ vertices of each color join to all vertices. It implies T 12. There is a constant c that edk_{3}(t_{2}(n) + m) ≤ m − c\frac{m^{2}}{n^{2}} if 2n ≤ m = o(n^{2}).(and we can do also for k ≥ 4, so the O(\frac{m^{2}}{n^{2}} ) factor is tight in the 2.3.) Proof. It is enough to estimate the edk_{3}(G) where G is obtained from T_{2}(2k) by adding m = an − a(a + 1), 2 ≤ a = o(n) edges so that a vertices of each color should be joined to all other vertices. Let the two colors be U, V and A_{U}, A_{V} be the two set of a vertices. For a set S of edge disjoint triangles let G_{0} be the graph containing monochromatic edges that belong to the not chromatic triangles of the set. Let m_{0}, m_{1} be the number of not chromatic and chromatic triangles of the set. The chromatic triangles contain 3, the not chromatic ones contain 1 new edges, so

m_{0} + 3m_{1} ≤ m

It implies that

|S| = m_{0} + m_{1} ≤ \frac{m}{3} + \frac{2m_{0}}{3}

Obviously

m_{0} = ∑_{u_{i}∈A_{U}} d_{G_{0}}(u_{i}) + ∑_{v_{i}∈A_{V}} d_{G_{0}}(v_{i}) − |G_{0}-edges having both endpoints in A_{U} or A_{V} |

For u ∈ A_{U} we have taken at least 2(d_{G_{0}}(u) + a − k) not monochromatic edges that have an endpoint in A_{V} to cover d_{G_{0}}(u) not monochromatic triangles at u, the sum using to cover all can be at least(each edge can be counted twice)

∑_{u_{i}∈A_{U}}(d_{G_{0}}(u_{i}) + a − k) = ∑_{u_{i}∈A_{U}} d_{G_{0}}(u_{i}) + a^{2} − ak

On the other hand we have to use at least ∑_{v_{i}∈A_{V}} d_{G_{0}}(v_{i}) not monochromatic edges to cover A_{V} −vertices, hence

∑_{v_{i}∈A_{V}} d_{G_{0}}(v_{i}) ≤ ak − ( ∑_{u_{i}∈A_{U}} d_{G_{0}}(u_{i}) + a^{2} − ak)

that is

∑_{u_{i}∈A_{U}} d_{G_{0}}(u_{i}) + ∑_{v_{i}∈A_{V}} d_{G_{0}}(v_{i}) ≤ 2ak − a^{2} = m + a

Therefore if the number of |G_{0}-edges having both endpoints in A_{U} or A_{V} is at least \frac{a^{2}}{2} then m_{0} ≤ m + a − \frac{a^{2}}{2} . Otherwise, of less than \frac{a^{2}}{2} edges in A_{U} and A_{V} are used in the not monochromatic triangles. Thus m_{0} ≤ m − \frac{a^{2}}{2} . So

edk_{3}(G) ≤ m − \frac{a^{2}}{3} + O(a) = m − O(\frac{m^{2}}{n^{2}} ).□

Another relating problem, questioned by P.Erdős, is

Problem. Determine the maximum m such that every graph of n vertices and t_{2}(n) + m edges has m edge disjoint triagles. The answer follows

Theorem 2.4. (Győri [7])

edk_{3}(n, t_{2}(n) + m) = m \begin{matrix}if m ≤ 2n − 10 for odd n \\ if m ≤ \frac{3}{2}n − 5 for even n \end{matrix}

providing that n is sufficiently large.

Examples show that the upper bounds for m in Theorem 2.4 are sharp.

Example 1. n = 2k Add 3k − 4 edges to T_{2}(n) so that two vertices of color class A and one vertex of color class B should be joined to all vertices. If the k − 1 edges in B are covered by k − 1 edge disjoint triangles then deleting these 3k − 3 edges, every vertex in A has k − 2 neighbors in B except one which has k ones. Since two vertices in A have k − 1 neighbors in A, we can’t find 2k − 3 edges disjoint triangles covering the 2k − 3 edges incident to these two vertices. This is the unique extremal example.

Example 2. n = 2k + 1 Take the Turán graph T_{2}(n) with color classes V_{1} and V_{2} of k and k + 1 vertices, respectively. Take one vertex in V_{1} and join it to all vertices in V_{1}. Then, take three vertices, say x_{1},x_{2},x_{3} in V_{2}, and join them to each other and to k − 3(except one) other vertices in V_{2}.(The set of k − 3 vertices do not have to be the same for the vertices x_{1}, x_{2}, x_{3}) It is easy to see that the resulting graph G of n vertices and t_{2}(n) + 2n − 9 edges does not contain 2n − 9 edge disjoint triangles. We have only three extremal examples.

The continuing of 2.4 follows Theorem 2.5. (Győri [8])

edk_{k}(n, t_{k−1}(n) + m) = m if m ≤ ⌊3\frac{n + 1}{r − 1}⌋ − 5 for r ≥ 4

provided that n is sufficently large.

The following example shows that the upper bound for m in Theorem 2.5 is sharp.

Example 3. Consider two color classes V_{i} and V_{j} of T_{(}k − 1)(n) of ⌊\frac{n+1}{r−1}⌋ vertices. Add 3⌊\frac{n+1}{r−1}⌋ - 4 edges to T_{(}k − 1)(n) so that two elements of V_{i} and one element of V_{j} should be joined to all vertices. If the ⌊\frac{n+1}{r−1}⌋ − 1 edges in V_{j} are covered by ⌊\frac{n+1}{r−1}⌋ − 1 edge disjoint K′_{k}s then deleting these (⌊\frac{n+1}{r−1}⌋ − 1)\binom{n}{2} edges, every vertex in V_{i} has ⌊\frac{n+1}{r−1}⌋ − 2 neighbors in V_{j} except one which has ⌊\frac{n+1}{r−1}⌋ neighbors. Since two elements of V_{i} have ⌊\frac{n+1}{r−1}⌋ − 1 neighbors in V_{i}, we cannot find 2⌊\frac{n+1}{r−1}⌋ − 3 edge disjoint K′_{k}s covering the 2⌊\frac{n+1}{r−1}⌋ − 3 edges incident to these two vertices. This is the only extremal graph.

Remarks Another important characterization of the Turán graphs is Let G_{k−1,m}(n) denote a graph obtained from T_{k−1}(n) by adding m edges so that the new edges belong to the same class having maximum number of vertices(i.e. ⌈\frac{n}{k−1}⌉) and the new edges do not form triangles, if this is possible. Then there exist a constant c_{k} > 0 such that for m < c_{k}n, if G is a graph of order n and size t_{k−1}(n) + m then

k_{k}(G) ≥ k_{k}(G_{k−1,m}(n)) = m ∏_{0≤i≤k−3}⌊\frac{n + i}{k − 1}⌋  (2.3)

Problem Determine the constant c_{k} in the theorem above.

If we add p + 1 or more edges to the first class of K_{k−1}(p + 1, p, .., p, p − 1), then each new edge will be contained only in (p − 1)p^{k−3} K′_{k}s, and we can verify that 2.3 does not hold. So c_{k} ≤ \frac{1}{k−1}

Theorem 2.6. [12] If e(G) = t_{k−1}(n) + m, where m < ⌊\frac{n}{k−1}⌋, then

k_{k}(G) ≥ m ∏_{0≤i≤k−3}⌊\frac{n + i}{k − 1}⌋

For example, k = 3 gives

If e(G) = t_{2}(n) + l, 0 < l ≤ \frac{n}{2}, then G contains at least l⌊\frac{n}{2}⌋ triangles.

Here we reproduce a simple fact proving for the case l ≤ \frac{n}{4}, as follows[3]

We assume that n is even(similar of the case n odd) Let t^{k} (k=1,2,3) be the number of triangles in K_{n} that contain exactly k edges of \overline{G}. Thus t^{0} = k_{3}(G). Let λ_{v} be the number of edges between N(v) and V (G − N(v). For uv edge, denote by t_{uv}^{k} the number of triangles in K_{n} that contain uv and k edges of \overline{G}. By definitions, it is obviously that

∑_{v} λ_{v} = 2t^{2},  (2.4)
∑_{uv∈E(G)} t_{uv}^{0} = 3t^{0},  (2.5)

∑_{uv∈E(G)} t_{uv}^{2} = t^{2},  (2.6)
n = d(u) + d(v) − t_{uv}^{0} + t_{uv}^{2},  (2.7)

provided that uv ∈ E(G). Summing the last equality over all edges uv, and by 2.5, 2.6, we have

nm = ∑_{u} d(u)^{2} − 3t^{0} + t^{2},  (2.8)

Since

∑_{uv∈E(G)}(d(u) + d(v)) = ∑_{u} d(u)^{2}.

By putting p(u) = d(u) − \frac{n}{2} we obtain that

∑_{u} d(u)^{2} = ∑_{u} p(u)^{2}+n ∑_{u} p(u)+\frac{n^{3}}{4} = ∑_{u} p(u)^{2}+sn(m−\frac{n^{2}}{4} )+\frac{n^{3}}{4} = ∑_{u} p(u)^{2}+2ln+\frac{n^{3}}{4} .

Together with 2.4 and 2.8, it gives

3t^{0} = ∑_{u}(p(u)^{2} + \frac{λ(u)}{2}) + ln.

This relation gives the assertion of the theorem unless

∑_{u}(p(u)^{2}) + \frac{λ(u)}{2} ≤ \frac{ln}{2}.  (2.9)

Thus, we may assume 2.9 holds. Then for some vertex u

p(u)^{2} + \frac{λ(u)}{2} ≤ \frac{l}{2}.  (2.10)

The number of edges in G with both end vertices in N(u) or V (G) − N(u) is

\frac{n^{2}}{4} + l − (\frac{n^{2}}{4} − p(u)^{2} − λ(u)) = l + p(u)^{2} + λ(u).

Each such edge belongs to at least

\frac{n}{2} − |p(u)| − λ(u) ≥ \frac{n}{2} − p(u)^{2} − λ(u)

G-triangles (which have the third vertex in the other color). Therefore

k_{3}(G) > ((l + p(u)^{2}) + λ(u))(\frac{n}{2} − p(u)^{2} − λ(u)) =

l\frac{n}{2} + (p(u)^{2} + λ(u))(\frac{n}{2} − l − p(u)^{2} − λ(u))

≥ l\frac{n}{2} + (p(u)^{2} + λ(u))(\frac{n}{2} − 2l) > \frac{ln}{2}□

Part 1.

In the beginning of Chapter 1 we have defined:

p_{k}(G) =min{∑_{1}^{m} |V (G_{i})| : G_{i}’s are K_{k} and edges,∪_{i}^{m}E(G_{i}) = E(G)}.

The weight of each K′_{k}s copies is k and 2 is that of edges. We also proved that

p_{k}(G) ≤ 2t_{k−1,n}

for k ≥ 4. In the first part of this chapter, we use the fractional method from [5]. We will study the problem when the weight of K′_{k}s copies is a given integer s less than k(k − 1). Let’s start with some definitions. For G is a graph of n vertices, a ψ^{∗} function on subgraphs H of G where H ≃ K_{k} or an edge to [0, 1] is called fractional full-packing if

∑_{e∈H} ψ^{∗}(H) = 1

for every edge e.

Definition. |ψ_{s}^{∗}| := ∑_{H≃K_{k}} sψ^{∗}(H) + ∑_{H≃K_{2}} 2ψ^{∗}(H).

Definition. ψ_{s}^{∗}(G) := min{|ψ_{s}^{∗}|, ψ^{∗} is fractional full-packing of G}.

A ψ fractional full-packing to {0, 1} is called integer full-packing. ψ_{s}(G) := min{|ψ_{s}|, ψ is an integer full-packing of G}. It is obvious that ψ_{s}(G) ≥ ψ_{s}^{∗}(G), the following shows that the difference is small

Theorem 3.1.

ψ_{s}(G) − ψ_{s}^{∗}(G) = o(n^{2})

for all graphs G.

The theorem in fact is a direct corollary of a deep application of the Szemerédi regularity lemma [19], as follows Let H_{0} be any fixed graph, let ν_{H_{0}}(G) denote the maximum size of a set of pairwise edge disjoint copies of H_{0} in G and ν_{H_{0}}^{−}(G) denote the maximum value of ∑_{H∈G,H≃H_{0}} ψ(H), where ψ runs over all functions on copies of H satisfying ∑_{e∈H} ψ(H) ≤ 1 for every edge e of G(i.e fractional packing). Then

ν_{H_{0}}^{−}(G) − ν_{H_{0}}(G) = o(|V (G)|^{2})

for all graphs G. This theorem makes it easier to study the edk_{H_{0}}(G) when the structure of the graph is regular.

Proof of Theorem 3.1. We see that ψ_{s}^{∗}(G) = min{∑_{H≃K_{k}} sψ^{∗}(H) + 2 ∑_{H≃K_{2}} ψ^{∗}(H) : ψ^{∗} is a fractional full-packing of G}= min{2 ∑_{e} ∑_{H≃K_{k} or edge,e∈H} ψ^{∗}(H) − (k(k − 1) − s) ∑_{H≃K_{k}} ψ^{∗}(H) : ψ^{∗} is a fractional full-packing of G} = 2e−(k(k−1)−s)ν_{K_{k}}^{−}(G), since max ∑_{H≃K_{k}} ψ^{∗}(H) = ν_{K_{k}}^{−}(G). Similarly, ψ_{s}(G) = min{∑_{H≃K_{k}} sψ(H) + 2 ∑_{H≃K_{2}} ψ(H) : ψ is an integer full-packing of G}= min{2 ∑_{e} ∑_{H≃K_{k} or edge,e∈H} ψ(H) − (k(k − 1) − s) ∑_{H≃K_{k}} ψ(H) : ψ is an integer full-packing of G} = 2e − (k(k − 1) − s)ν_{K_{k}}(G) due to max ∑_{H≃K_{k}} ψ(H) = ν_{K_{k}}(G).

Definition. p_{s}^{∗}(n) := max{|ψ_{s}^{∗}(G)|, G is of order n}, p_{s}(n) := max{|ψ_{s}(G)|, G is of order n}. Corollary. p_{s}(n) − p_{s}^{∗}(n) = o(n^{2}) The p_{k}(n) has been investigated. By the corollary we can study p_{s}^{∗}(n) instead of p_{s}(n). The p_{s}^{∗}(n) can be studied easily.

Theorem 3.2. The \frac{p_{s}^{∗}(n)}{n(n−1)} sequence is monotone decreasing.

Proof of Theorem 3.2. Let G be a graph of order n + 1 where |ψ_{s}^{∗}(G)| = p_{s}^{∗}(n + 1). For every vertex v of G let G_{v} is the G − v graph, and ψ_{G_{v}}^{∗} is its optimal fractional fullpacking. Then, the ξ^{∗} := \frac{1}{n−1} ∑_{v} ψ_{G_{v}}^{∗} is also a fractional full-packing inG. Obviously,

|ξ_{s}^{∗}| = \frac{1}{n − 1} ∑_{v} |ψ_{G_{v}}^{∗}| ≤ \frac{n + 1}{n − 1}p_{s}^{∗}(n)

and |ξ_{s}^{∗}| ≥ min{|ψ^{∗}|, ψ^{∗} is a fractional full-packing of G} = ψ_{s}^{∗}(G) = p_{s}^{∗}(n + 1).

Corollary. The limit of \frac{p_{s}^{∗}(n)}{n^{2}}, and also, of \frac{p_{s}(n)}{n^{2}} exists when n ⟶ ∞, they are equal.

We have another relation

Theorem 3.3. p_{s}^{∗}(kn) ≤ k^{2}p_{s}^{∗}(n) + sn + ⌊\frac{R(k,k)−1}{k}⌋(k^{2} − k − 2 − s)^{+} where R(k, k) is the appropriate Ramsey number.

Proof of Theorem 3.3. Let G_{kn} be a graph of order kn where |ψ_{s}^{∗}(G_{kn})| = p_{s}^{∗}(kn). We can divide the graph into n groups G_{1}, G_{2}, .., G_{n} of k vertices so that each of the first n − ⌊\frac{R(k,k)−1}{k}⌋ groups is K_{k} or its complement. For each v_{1}, v_{2}, .., v_{n} vertices from each group, define ψ_{v_{1},v_{2},..v_{n}}^{∗} be an optimal fractional full-packing of the graph formed by v_{1}, v_{2}, ..v_{n}. Let ψ_{i}^{∗} be an optimal fractional full-packing of the i − th group(graph formed by the vertices in group). Clearly,

ξ^{∗} := \frac{1}{k^{n−2}} ∑_{v_{i}∈G_{i}} ψ_{v_{1},v_{2},..v_{n}}^{∗} + ∑_{i} ψ_{i}^{∗}

is a fractional full-packing in G_{kn}, therefore |ξ_{s}^{∗}| ≥ p_{s}^{∗}(kn) On the other hand,

|ξ_{s}^{∗}| ≤ \frac{1}{k^{n−2}} k^{n}p_{s}^{∗}(n) + (n − ⌊\frac{R(k, k) − 1}{k}⌋)s + ⌊\frac{R(k, k) − 1}{k}⌋max\{s, k(k − 1) − 2\}

= k^{2}p_{s}^{∗}(n) + sn + ⌊\frac{R(k, k) − 1}{k}⌋(k^{2} − k − 2 − s)^{∗},

and we are done.

Let c_{s}^{k} be the limit in Theorem 3.2. In Chapter one we have shown some lower bounds of c_{k}^{k}, not knowing there exist or not. As k = 3 and s = 3, since R(3, 3) = 6, the Theorem 3.4 shows:

p_{3}^{∗}(3n) ≤ 9p_{3}^{∗}(n) + 3n + 1.  (3.1)

The c_{3}^{3} ≤ \frac{5}{9} is a result in chapter one.

Theorem 3.4. c_{3}^{3} ≤ \frac{p_{3}^{∗}(n)}{n^{2}} + \frac{1}{2n} + \frac{1}{8n^{2}} , and hence c_{3}^{3} ≤ \frac{p_{3}(n)}{n^{2}} + \frac{1}{2n} + \frac{1}{8n^{2}} too

Proof of Theorem 3.4. From 3.1,

p_{3}^{∗}(3^{k+1}n) ≤ 9^{k+1}p_{3}^{∗}(n) + ∑_{i=0}^{k} 9^{k−i}(3^{i+1}n + 1).

This implies

c_{3}^{3} ≤ \frac{p_{3}^{∗}(3^{k+1}n)}{3^{k+1}n(3^{k+1}n − 1)} = \frac{3^{k+1}n}{3^{k+1}n − 1} \frac{p_{3}^{∗}(3^{k+1}n)}{9^{k+1}n^{2}}

≤ \frac{3^{k+1}n}{3^{k+1}n − 1}(\frac{p_{3}^{∗}(n)}{n^{2}} + \frac{1}{3n} ∑_{i=0}^{k} 3^{−i} + \frac{1}{n^{2}} ∑_{i=0}^{k} 9^{−i−1}).

Also the limit of the latter term is \frac{p_{3}^{∗}(n)}{n^{2}} + \frac{1}{2n} + \frac{1}{8n^{2}} when k tends to infinity

Similarly, the k = 4, s = 4 case(R(4, 4) = 18):

p_{4}^{∗}(4n) ≤ 16p_{4}^{∗}(n) + 4n + 24.  (3.2)

and we have

Theorem 3.5. c_{4}^{4} ≤ \frac{p_{4}^{∗}(n)}{n^{2}} + \frac{1}{3n} + \frac{1}{10n^{2}} . Consequently, c_{4}^{4} ≤ \frac{p_{4}(n)}{n^{2}} + \frac{1}{3n} + \frac{1}{10n^{2}} too.

Proof of theorem 3.5. From 3.2

p_{4}^{∗}(4^{k+1}n) ≤ 16^{k+1}p_{4}^{∗}(n) + ∑_{i=0}^{k} 16^{k−i}(4^{i+1}n + 24)

Which leads to

c_{4}^{4} ≤ \frac{p_{4}^{∗}(4^{k+1}n)}{4^{k+1}n(4^{k+1}n − 1)} = \frac{4^{k+1}n}{4^{k+1}n − 1} \frac{p_{4}^{∗}(4^{k+1}n)}{16^{k+1}n^{2}}

≤ \frac{4^{k+1}n}{4^{k+1}n − 1}(\frac{p_{4}^{∗}(n)}{n^{2}} + \frac{1}{16n} ∑_{i=0}^{k} 4^{1−i} + \frac{24}{16n^{2}} ∑_{i=0}^{k} 16^{−i−1}).

The limit of the latter term is \frac{p_{4}^{∗}(n)}{n^{2}} + \frac{1}{3n} + \frac{1}{10n^{2}} when k tends to infinity

By help of such computation we can determine the value of \frac{p_{3}(n)}{n^{2}},\frac{p_{4}(n)}{n^{2}}...when n is large enough, I think the constants \frac{5}{9}, \frac{5}{18}... can be improved this way.

Remarks. Let k be unchanged. For x ∈ [0, k(k − 1)], and n is given, let G_{x} be an optimal graph(or one of),i.e |ψ_{G_{x}}| = p_{x}(n). We set m_{x} := E(G_{x}), T_{x}:= maximal number of edge disjoint K′_{k}s in G_{x} (in fact m_{x}, T_{x} depend on G_{x}), then for any r ≤ s in the [0, k(k − 1)] interval the followings hold

(a) T_{s} ≥ T_{r},m_{s} ≥ m_{r} and

(k(k − 1) − r)(T_{s} − T_{r}) ≥ 2(m_{s} − m_{r}) ≥ (k(k − 1) − s)(T_{s} − T_{r})

(b) c_{x} is a continuously monotone, convex function. (c)

(s − r)T_{s} ≥ p_{s}(n) − p_{r}(n) ≥ (s − r)T_{r}.

Proof of (a). By the maximality of p_{s}(n) p_{s}(n) ≥ |ψ_{s}(G_{r})| = 2m_{r} − (k(k − 1) − s)T_{r}, but p_{s}(n) = 2m_{s} − (k(k − 1) − s)T_{s}, So

2(m_{s} − m_{r}) ≥ (k(k − 1) − s)(T_{s} − T_{r})

By the maximality of p_{r}(n) p_{r}(n) ≥ |ψ_{r}(G_{s})| = 2m_{s} − (k(k − 1) − r)T_{s}, but p_{r}(n) = 2m_{r} − (k(k − 1) − r)T_{r}, So

2(m_{s} − m_{r}) ≤ (k(k − 1) − r)(T_{s} − T_{r})

(b) p_{r}(n) ≥ |ψ_{r}(G_{s})| ≥ \frac{r}{s}|ψ_{s}(G_{s})| = \frac{r}{s}p_{s}(n), thus c_{s} ≥ c_{r} ≥ \frac{r}{s}c_{s}, and therefore it is continuous. If t = αr + (1 − α)s, we see that

p_{t}(n) = |ψ_{t}(G_{t})| = 2m_{t} − (k(k − 1) − t)T_{t} =

α(2m_{t} − (k(k − 1) − r)T_{t}) + (1 − α)2m_{t} − (k(k − 1) − s)T_{t} ≤ αp_{r}(n) + (1 − α)p_{s}(n).

(c) p_{s}(n) − p_{r}(n) = 2m_{s} − (k(k − 1) − s)T_{s} − 2m_{r} + (k(k − 1) − r)T_{r}, and we are done by (b).

Clearly c_{0} = 1 − \frac{1}{k−1}, c_{k(k−1)} = 1

Corollary.

\frac{c_{s} − c_{r}}{s − r} ≤ \frac{1}{k(k − 1)}.

If the conjecture edk_{k}(G) ≥ \frac{2}{k}m − o(n^{2}) is true, then c_{k(k−2)} = 1 − \frac{1}{k−1}(equivalent), which means the function c_{x} is constant in [0, k(k − 2)] and linear in [k(k − 2), k(k − 1)].

Part 2.

In any 2-coloring of K_{n}, where n > R(k, k), there are monochromatic K′_{k}s. We can ask about the minimum number of such monochromatic K′_{k}s. Here we will consider the number of edge disjoint monochromatic K′_{k}s. Definition. Let N(n, k) be the minimum number of pairwise edge disjoint monochromatic complete subgraphs K_{k} in any 2-coloring of the edges of K_{n}.

Theorem 3.6. lim_{n→∞} \frac{N(n,k)}{n(n−1)} exists .

Proof of theorem 3.6.

1. If c_{k} = sup_{n} \frac{N(n,k)}{n(n−1)}, then for any given small ϵ > 0, there is an m = m(ϵ) such that

\frac{N(m, k)}{m(m − 1)} ≥ (1 − ϵ)c_{k}m(m − 1).

Then for n sufficiently large, the edges of K_{n} can be packed with (1 − ϵ)\begin{matrix}( & {n \atop 2} & ) \\ ( & {m \atop 2} & ) \end{matrix} edge disjoint

K′_{m}s by [18]. As a consequence, for n large

N(n, k) ≥ (1 − ϵ)\begin{matrix}( & {n \atop 2} & ) \\ ( & {m \atop 2} & ) \end{matrix}(1 − ϵ)c_{k}m(m − 1) ≥ (1 − ϵ)^{2}c_{k}n(n − 1).

Therefore we are done, and the limit equals sup_{n} \frac{N(n,k)}{n(n−1)}

2. Let N^{−}(n, k) be the minimum possible value of ν_{K_{k}}^{−}(G) + ν_{K_{k}}^{−}(\overline{G}) over all 2-colorings G ∪ \overline{G} of the edges of K_{n}. According to a result in Part 1.,

N^{−}(n, k) − N(n, k) = o(n^{2}).

The N^{−}(n, k)′s have the following property

The sequence \frac{N^{−}(n,k)}{n(n−1)} is increasing in n.

Because considering 2-coloring the edges of complete graph K_{n+1}, for every 1 ≤ i ≤ n + 1 we can find a fractional packing w_{i} of monochromatic K_{k} of the complete graph received from K_{n+1} after deleting it’s i-th vertex; the total value of w_{i} is at least N^{−}(n, k) by definition. Each edge of K_{n+1} belongs to n − 1 such complete subgraphs, so the w := \frac{1}{n−1} ∑_{i} w_{i} is also a fractional packing for K_{n+1}. But its total value is at least \frac{n+1}{n−1}N^{−}(n, k). Therefore

N^{−}(n + 1, k) ≥ \frac{n + 1}{n − 1}N^{−}(n, k).

The \frac{N^{−}(n,k)}{n(n−1)} is bounded by \frac{2}{k(k−1)} for every n. Therefore by the above, this sequence converges.

Let c_{k} be this constant; The main problems are to estimate c_{k} for every k. For the case k = 3, if we consider the 2-coloring of K_{n} determined by T_{2}(n) and its complement(two monochromatic cliques) then there are approximately

2\frac{\binom{n/2}{2}}{3} = \frac{n^{2}}{12} + o(n^{2})

edge disjoint monochromatic triangles, thus c_{3} ≤ \frac{1}{12}. This example led to a conjecture of P. Erdős. Conjecture:

c_{3} = \frac{1}{12}.

The value of N(11, 3) is 6. Therefore, by the first method above,

c_{3} = sup_{n} \frac{N(n, 3)}{n(n − 1)} ≥ \frac{N(11, 3)}{11.10} = \frac{3}{55}.

Another way to find estimate for c_{3} is by second method and techniques used in the first part.

Theorem 3.7. ([5]) N^{−}(3n, 3) ≥ 9N^{−}(n, 3) + n − 1.

Proof of theorem 3.7. Consider such a 2-coloring of K_{3n} that the total value of its maximal packing is N^{−}(3n, 3). Since 6 vertices contain a monochromatic triangle we can find n−1 vertex disjoint monochromatic triangles. Let T_{1}, T_{2}, .., T_{n−1} denote these triples and T_{n} be the remaining three vertices. For any 3^{n} distinct copies of K_{n}(from each set each vertex) there is a fractional packing w_{i}, and because each edge connecting different T′_{j}s is covered exactly 3^{n−2} times by such w′_{i}s, the w := 3^{−(n−2)}σ_{i}w_{i} is a fractional packing of the connecting edges. By adding T′_{i}s to this packing, we receive a packing of K_{3n}, whose value is at least

3^{−(n−2)}.3^{n}N^{−}(n, 3) + (n − 1) = 9N^{−}(n, 3) + n − 1

Iterating this result will lead to Corollary

c_{3} ≥ \frac{N^{−}(n, 3)}{n^{2}} + \frac{1}{6n} − \frac{1}{8n^{2}}

for every n ≥ 1 The corollary provides that, with the easy fact N^{−}(7, 3) ≥ N(7, 3) = 2,

c_{3} ≥ \frac{N^{−}(7, 3)}{7^{2}} + \frac{1}{6.7} − \frac{1}{8.7^{2}} = \frac{73}{1176} > \frac{1}{16.11} > \frac{3}{55}

The up-to-now best result of c_{3} is due to Sudakov and Keevash: c_{3} > \frac{1}{12.88} Similarly, we might study the case k ≥ 4. It seems that these bounds will depend on the Ramsey numbers R(k, k)′s.

Remark The conjecture may be weakened by asking whether there are approximately \frac{1}{12}n^{2} triangles in the G graph whose complement is triangle-free. We may ask the related question, let N′(n, k) be the minimum of the maximum of the two monochromatic edge disjoint K′_{k}s number in any 2-coloring of the edges of K_{n}. The construction based on the blowup of C_{5} shows that the number of monochromatic edge disjoint triangles in either of the colors is about \frac{n^{2}}{20} , and this led to the conjecture of Jacobson Conjecture If n is sufficiently large, then

N′(n, 3) = \frac{n^{2}}{20} + o(n^{2}).

Obviously, N′(n, k) ≥ \frac{1}{2}N(n, k).

Part 3.

In this part, we are discussing on the relations between the graph’s structures. For F is a fixed graph, let Δ_{F} (G) be the minimum number of copies of F and edges which fully pack E(G), Δ_{F}^{+}(G) be the minimum number of copies of F and edges which cover E(G) and finally, μ_{F} (G) be the maximum number of edges in the F -free subgraphs of G. Clearly,

Δ_{F} (G) ≥ Δ_{F}^{+}(G)

According to [16], Δ_{K_{k}}(G) ≤ t_{k−1,n} for any graph G of order n

for F = K_{3}, we have

Theorem 3.8. ([9]) Δ_{K_{3}}^{+}(G) ≤ μ_{K_{3}}(G)

Shortly, for every e edge ∈ E − M(M is a maximal triangle free subgraph) we find an f edge ∈ M so that e and f are edges of a triangle, and no e′s have the same f. The Hall condition can be verified by using the maximality of M and the fact that every graph contains a triangle free subgraph of size at least it’s one half. More generally, the theorem is true for all F has the chromatic number not less than 3(one can check that for some bipartite F′s the theorem does not stand, on the other hand, for these F the size of a F -free subgraph always be o(n^{2})), and the proof of this is quite similar to the triangle case,

Theorem 3.9. Δ_{F}^{+}(G) ≤ μ_{F} (G) with χ(F) ≥ 3 and equality holds iff G is F −free.

For the case F = K_{k}(k ≥ 3) and G contains a k−clique, the equality does not hold, indeed on these conditions

Theorem 3.10. Δ_{F}^{+}(G) ≤ μ_{F} (G) − \binom{k}{2} + 2

The following conjectures [9] fit to our topic

Conjecture

Δ_{K_{3}}(G) ≤ μ_{K_{3}}(G)

This result would be a generalization of [16] stating that the edges of a graph on n vertices can be covered by at most ⌊\frac{n^{2}}{4} ⌋ pairwise disjoint edges and triangles. Conjecture

Δ_{F} (G) ≤ μ_{F} (G)

if χ(F) ≥ 3?

32

Bibliography

[1] A. Hajnal and E. Szemerédi, Proof of a conjecture of Erdős, Combinatorial theory and its applications, Coll. Math. Soc. J. Bolyai 4, North-Holland, Amsterdam(1970), 601-623

[2] B. Bollobás, On complete subgraphs of different orders, Math. Proc. Cambridge Philos Soc., 79(1976), 19-24.

[3] B. Bollobás, Extremal graph theory, Academic Press, 1978.

[4] B. Bollobás, Modern graph theory, Graduate texts in mathematics, vol 184, Springer, New York, 2002

[5] B. Sudakov and P. Keevash, Packing triangles in a Graph and its complement, J. Graph Theory 47 (2004), 203-216.

[6] E. Győri and Zs.Tuza, decompositions of graphs into complete subgraphs of given order, Studia Scientiarum Mathematicarum Hungarica 22(1987), 315-320.

[7] E. Győri, On the number of edge disjoint triangles in graphs of given size, Colloquia Mathematica Societatis János Bolyai, 52(1987).

[8] E. Győri, On the number of edge disjoint cliques in graphs of given size, Combinatorica 11(1991), 231-243.

[9] J. Lehel and Zs. Tuza, Triangle-free graphs and edge covering theorems, Discrete Mathematics 39(1982), 59-65.

[10] J. Spencer, Maximal consistent families of triplets, J. Combinatorial Theory 5(1968), 1-8.

[11] J. W. Moon and L.Moser, On a problem of Turán, Publ. Math. Inst. Hungar. Acad. Sci, 7(1962), 283-286.

[12] L. Lovász and M. Simonovits, On the number of complete subgraphs of a graph II, Studies in Pure Mathematics, to the memory of P. Turán, 1983, 459-495.

[13] L. Lovász The rank of connection matrices and the dimension of graph algebras, Technical report.

[14] M. Simonovits and J. Komlós, Szemerédi’s regularity lemma and its applications in graph theory. Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 295– 352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.

[15] N. Alon and R. Yuster, h-factors in dense graphs, J. Combin. Theory B 66(1996), 269-282.

[16] P. Erdős, A. Goodman and L. Pósa, The representation of graphs by set intersections, Canad. J. Math. 18(1966), 106-112.

[17] P. Erdős, R.J. Faudree, R.J. Gould, M.S. Jacobson, J. Lehel, Edge disjoint monochromatic triangles in 2-colored graphs. Discrete Mathematics 231(2001), 135-141.

[18] V. Rödl, On a packing and covering problem, Europ. J. Combinatorics 5(1985), 69-78.

[19] V. Rödl and P. Haxell, Integer and fractional packings in dense graphs, Combinatorica 21(2001), 13-38.