Induced complete h-partite graphs in dense clique-less graphs

Eldar Fischer ^{∗} Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel-Aviv University, Tel-Aviv, Israel.

                            eldar@math.tau.ac.il

Submitted: June 3, 1999; Accepted: September 16, 1999.

Abstract It is proven that for every fixed h, a and b, a graph with n vertices and minimum degree at least \frac{h−1}{h}n, which contains no copy of K_{b} (the complete graph with b vertices), contains at least (1 − o(1))\frac{n}{ha} vertex disjoint induced copies of the complete h-partite graph with a vertices in each color class. Mathematics subject classification numbers: 05C70, 05C55.

All graphs considered here are finite, undirected, and have neither loops nor parallel edges. The notation here follows the convention of [4] except where stated otherwise.

Many asymptotic embedding results have been proven by the Regularity Lemma of Szemerédi [6] over the years. See [5] for a survey. One of the results in this area, that of Alon and Yuster [2], has particular relevance to the following.

Theorem 1 ([2]) For every natural a, h and every ϵ > 0 there exists N = N(h, a, ϵ) such that if G is a graph with n > N vertices and minimum degree at least \frac{h−1}{h}n, then G contains at least (1 − ϵ)\frac{n}{ha} vertex disjoint copies of K(h, a), the complete h-partite graph with a vertices in each color class.

∗Research supported by the Fritz Brann Doctoral Fellowship in Engineering and Exact Sciences.

The following result, proven below, is an analogue of Theorem 1 for the context of induced subgraphs.

Theorem 2 For every h, a, b and ϵ > 0 there exists N′ = N′(h, a, b, ϵ), such that if G is a graph with n > N′ vertices, minimum degree at least \frac{h−1}{h}n, and no copy of K_{b} (the complete graph with b vertices), then G contains at least (1 − ϵ)\frac{n}{ha} vertex disjoint induced copies of K(h, a), the complete h-partite graph with a vertices in each color class.

In [1] a variant of the Regularity Lemma which is suitable for dealing with induced subgraphs in very general circumstances is presented and proven. The proof of Theorem 2, however, is immediate from Theorem 1 by use of the following well known Ramsey’s Theorem.

Theorem 3 (Ramsey’s Theorem, see e.g. [4]) For every two positive integers a and b there exists R = R(a, b), such that every graph with R vertices contains either a set with a vertices and no edges between them, or a clique with b vertices.

Proof of Theorem 2: We choose N′ = N(h, c, \frac{1}{2}ϵ) where N is the function defined in Theorem 1, and c = ⌈2R(a, b)ϵ^{−1}⌉ where R is the function defined in Theorem 3.

Given a graph G with n > N′ vertices which satisfies the conditions in the formulation of Theorem 2, we first apply Theorem 1 to find in G at least (1 − \frac{1}{2}ϵ)\frac{n}{hc} vertex disjoint copies of K(h, c). For each such copy we apply the following procedure.

Let us denote by U_{1}, …, U_{h} the color classes of such a (not necessarily induced) copy. For every 1 ≤ i ≤ h, Theorem 3 guarantees the existence of a set W_{i} ⊂ U_{i} with a vertices and no edges of G between them, since no copies of K_{b} are present in G. Thus, the set ⋃_{i=1}^{h} W_{i} spans an induced copy of K(h, a) in G. We set this copy aside, and apply the same procedure again to the sets of vertices which are in U_{1}, …, U_{h} but not in this copy.

As long as at least R(a, b) vertices remain in each U_{i} this procedure can be applied repeatedly, thus finding at least (1 − \frac{1}{2}ϵ)\frac{c}{a} vertex disjoint induced copies of K(h, a) in each copy of K(h, c). Since there are at the beginning at least (1 − \frac{1}{2}ϵ)\frac{n}{hc} vertex disjoint copies of K(h, c), this makes a total of at least (1−ϵ)\frac{n}{ha} vertex disjoint induced copies of K(h, a) in G. □

Concluding remarks: One may ask if a minimum degree at least (\frac{h−1}{h} + o(1))n of a graph G with n = hal vertices and without a K_{b}-copy guarantees that G contains l vertex disjoint copies of K(h, a), in analogy to the main result of [3]. This is however far from being true even for the first nontrivial cases of h = a = 2. In fact, given b > 3, the complete (b−1)-partite graph with 4k−1 vertices in one color class, 4k+1 vertices in another, and 4k vertices in each of the other classes (setting n = 4(b − 1)k and l = (b − 1)k) is a graph without l vertex disjoint induced copies of K(2, 2) although it has no K_{b}-copy and its minimum degree is (\frac{b−2}{b−1} − o(1))n, which is much larger than (\frac{1}{2} + o(1))n.

One may also ask if a graph satisfying the conditions of Theorem 2 contains \frac{n}{ha} −C vertex disjoint induced K(h, a)-copies for some C = C(h, a, b) independent of n. This could be true.

Acknowledgment: I would like to thank Professor Noga Alon for the helpful discussion, leading to a dramatic simplification of the proof, and the continuing support.

References

[1] N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Proceedings of the 40^{th} IEEE FOCS (1999), to appear.

[2] N. Alon and R. Yuster, Almost H-factors in dense graphs, Graphs and Combinatorics 8 (1992), 95–102.

[3] N. Alon and R. Yuster, H-factors in dense graphs, J. of Combinatorial Theory Ser. B 66 (1996), 269–282.

[4] B. Bollobás, Extremal Graph Theory, Academic Press, New York (1978).

[5] J. Komlós and M. Simonovits, Szemerédi’s Regularity Lemma and its applications in graph theory, In: Combinatorics, Paul Erdös is Eighty, Vol II (D. Miklós, V. T. Sós, T. Szönyi eds.), János Bolyai Math. Soc., Budapest (1996), 295–352.

[6] E. Szemerédi, Regular partitions of graphs, In: Proc. Colloque Intern. CNRS No. 260 (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau eds.), 1978, 399–401.