close

Вход

Забыли?

вход по аккаунту

?

451

код для вставкиСкачать
Variants of the
Hajnal–Szemerédi
Theorem
Eldar Fischer*
DEPARTMENT OF MATHEMATICS
RAYMOND AND BEVERLY SACKLER FACULTY OF EXACT SCIENCES
TEL-AVIV UNIVERSITY
TEL-AVIV ISRAEL
Received December 30, 1996; revised December 23, 1998
Abstract: The Hajnal–Szemerédi Theorem [Hajnal & Szemerédi, Colloq Math
Soc J Bolyai, 1970] states that a graph with hk vertices and minimum degree at
least (h − 1)k contains k vertex disjoint copies of Kh . Its proof is not algorithmic.
Here, we present an algorithm that, for a fixed h, finds in such a graph k − C(h)
vertex disjoint copies of Kh in polynomial time in k, C(h) being a constant depending on h only. The proof suggests a variant of the theorem for h-partite graphs,
which is conjectured here and proven in a slightly weaker form in some special
c 1999 John Wiley & Sons, Inc. J Graph Theory 31: 275–282, 1999
cases. Keywords: graph embeddings, cliques, incremental approach
1. INTRODUCTION
All graphs considered here are finite and without loops or parallel edges. Given
a graph G with kh vertices, it is useful to formulate conditions on the minimum
*This article forms part of a Ph. D. thesis written by the author under the supervision
of Prof. N. Alon.
c
1999 John Wiley & Sons, Inc.
CCC 0364-9024/99/030275-08
276 JOURNAL OF GRAPH THEORY
degree of G that ensure that it contains k vertex disjoint copies of Kh , the complete
graph on h vertices.
By considering the complete h-partite graph with k−1 vertices in one color class,
k + 1 vertices in another, and k vertices in each of the remaining color classes, one
sees that a minimum degree of at least (h − 1)k must be required. It is seen from
Dirac’s Theorem that this is the exact case for h = 2, and the same for h = 3 was
proven by Corrádi and Hajnal [3]. All other cases were resolved by the following
classical result of Hajnal and Szemerédi.
Theorem 1.1 ([6]). If G is a graph with hk vertices and minimum degree at least
(h − 1)k, then G contains k vertex disjoint copies of Kh , the complete graph on h
vertices.
The proof of this theorem is quite involved, and does not yield an efficient
algorithm for finding explicitly the required vertex disjoint Kh copies.
We show here, for a graph G that satisfies the condition of Theorem 1.1, an
algorithm that finds k − C(h) disjoint Kh copies in O(f (h)k 2 ) time, with C and
f dependent only on h. We also state some related conjectures for which we prove
some partial results.
2. ALGORITHMIC APPROXIMATION OF THE
HAJNAL–SZEMERÉDI THEOREM
In this section we prove the following result, yielding the algorithm mentioned in
the introduction.
Theorem 2.1. There exists an algorithm that runs in time O((h + 5)!k 2 ), such
that, given h and a graph G with hk vertices and minimum degree at least (h − 1)k,
finds in G at least k − (h − 1)2 vertex disjoint copies of Kh .
We need the following simple lemma, whose proof is left to the reader.
Lemma 2.1. If a bipartite graph H with color classes A, B, |A| ≤ h, |B| = h,
contains at least (l − 1)h + 1 edges, then H contains a matching of size l.
Proof of Theorem 2.1. The algorithm keeps at each stage a partition of the
vertex set V of G into k sets of size h, V1 , . . . , Vk , together with a vertex maximal
complete graph Gi in each Vi . The algorithm begins with an arbitrary partition,
where some of the Gi ’s may be single vertices.
The algorithm terminates when there are less than h copies of Kj among
G1 , . . . , Gk for each 1 ≤ j < h. Otherwise, assume that G1 , . . . , Gh are copies of
Kj for some fixed 1 ≤ j < h, and perform the following procedure.
/ Gl
We define a connection to be a pair (v, l), v ∈ V, 1 ≤ l ≤ h, such that v ∈
and all vertices of Gl are neighbors of v . For 1 ≤ i ≤ k , denote by
c the number
P i
of connections (v, l) with v ∈ Vi . Counting arguments show that ki=1 ci ≥ (h −
j)hk , since each Kj copy has at least (h − j)k related connections.
If there exist i1 =
/ i2 satisfying 1 ≤ i1 , i2 ≤ h, such that all vertices of Gi1
are neighbors of a vertex in Vi2 , then, by modifying the partition V1 , . . . , Vk in the
HAJNAL-SZEMEREDI VARIANTS 277
obvious way, we get G1 , . . . , Gk in which Gi1 is of size j + 1, Gi2 is of size at least
j − 1, and all the other sizes remain as before.
Otherwise, there exists i > h such that ci > (h − j)h. In that case by Lemma
2.1 there exist v1 , . . . , vh−j+1 ∈ Vi and l1 , . . . , lh−j+1 ∈ {1, . . . , h}, all different,
such that all vertices of Gln are neighbors of vn for all 1 ≤ n ≤ h − j + 1. By
modifying the partition V1 , . . . , Vk and the graphs G1 , . . . , Gk , we can increase the
sizes of Gl1 , . . . , Glh−j+1 by one, decrease the size of Gi by at most h − j + 1, and
leave all the other sizes as before.
As the search for both cases is done in time O(h3 k), all that remains to be
proven is that this process terminates in a number of iterations, which is O((h +
2)!k). To prove this, we assign weights to G1 , . . . , Gk as follows. Denote by w :
{0, . . . , h} → R the function defined by w(1) = w(0) = 0, w(j + 1) − w(j) =
Pk
1− (h−j+1)!
i=1 wi .
(h+1)! for 1 ≤ j < h. Define wi = w(|Gi |) for 1 ≤ i ≤ k , and w =
It is clear that 0 ≤ w ≤ hk , and we now prove that w increases by a certain amount
in each stage of any of the cases described above.
In the first case, w gained 1 − (h−j+1)!
(h+1)! by the increase in Gi1 , and lost no more
(h−j+2)!
(h+1)! by the possible
(h−j+2)!
(h−j+1)!
1
(h+1)! − (h+1)! ≥ (h+1)! .
than 1 −
decrease in Gi2 . Thus, w is increased by at least
In the second case, w gained (h − j + 1)(1 −
(h−j+2)!−(h−j+1)!
(h+1)!
(h−j+1)!
(h+1)! )
= h−j +1−
by the increase in Gl1 , . . . , Glh−j+1 , and lost no more than
w(h) − w(j − 1) ≤ h − j + 1 − (h−j+2)!
(h+1)! by the decrease in Gi . Thus, w increased
1
by at least (h−j+1)!
(h+1)! ≥ (h+1)! .
This bounds the number of iterations by (h + 1)!hk = O((h + 2)!k), completing
the proof.
3. COLORED VERSION
When G is an h-partite graph with equal color classes, one might want to obtain a
partition of G into vertex disjoint Kh copies. This is a generalization of the perfect
matching problem in the case of bipartite graphs, solved in full by Hall’s Theorem
(see, e.g., [2]).
The following conjecture is a variant of the Hajnal–Szemerédi Theorem, with
constraints given by the coloring of G.
Conjecture 3.1. If G is an h-partite graph with color classes C1 , . . . , Ch of size
k, such that each vertex in any class has at least h−1
h k neighbors in each of the
other classes, then G contains k vertex disjoint copies of Kh .
For h = 2, this conjecture is an easy consequence of Hall’s Theorem. If true,
the condition on the number of neighbors of each vertex in each class is tight,
since for d < h−1
h k we can define G as the following counter example: Choose
a set A that consists of d vertices from each color class, and choose as edges all
278 JOURNAL OF GRAPH THEORY
possible edges across color classes that are incident with a vertex from A. Clearly,
every possible Kh copy in this G contains at least h − 1 vertices from A. Since
|A| = hd < (h − 1)k , there are no k vertex disjoint Kh copies.
By using the proof technique of the previous section, we can give the following
evidence for the correctness of the conjecture for higher values of h.
Proposition 3.1. If, for h = 3 or h = 4, G satisfies the conditions above, then
G contains k − C copies of Kh , C being a constant independent of k. These copies
can be found in time that is polynomial in k.
For proving this, we maintain a partition V1 , . . . , Vk of V , such that |Vi ∩Cj | = 1
for all 1 ≤ i ≤ k, 1 ≤ j ≤ h. We denote by vi,j the single vertex in Vi ∩ Cj . Again,
we maintain a list of known complete subgraphs G1 , . . . , Gk in V1 , . . . , Vk , but this
time, they are not necessarily vertex maximal. At the beginning, G1 , . . . , Gk are all
single vertices. We define each Gi to be colored by the color classes of the vertices
it contains. Proposition 3.1 for the case h = 3 follows almost immediately from
the following simple lemma, while the case h = 4 needs some extra work.
Lemma 3.1. For any partition as above, if Gi is only a single vertex, we can find a
new partition in which Gi will be an edge colored with x1 and x2 (1 ≤ x1 < x2 ≤ h
of our choice), and all other members of G1 , . . . , Gk will maintain their sizes and
colors.
Proof. We may assume i = 1 and x1 = 1, x2 = 2. If V1 already contains such
an edge, we are done by modifying G1 accordingly. Otherwise, for 1 < j ≤ k we
call Vj connected to v1,1 if vj,l for all 1 < l ≤ h are neighbors of v1,1 . A counting
argument shows that there is a Vj connected to v1,1 such that vj,1 is also a neighbor
of v1,2 . By swapping v1,1 and vj,1 , we arrive at the desired partition of V .
Proof of Proposition 3.1 for h = 3. We keep track only of triangles. As long
as there are less than k − 2 triangles among G1 , . . . , Gk , we may assume that
G1 , G2 , G3 are not triangles. Furthermore, by Lemma 3.1, we may assume that
G1 is an edge colored with 2 and 3, G2 an edge colored with 1 and 3, and G3 an
edge colored with 1 and 2. If there is a triangle within the vertices of V1 , V2 , V3 , we
modify the partition, if necessary, and add it. Otherwise, since for each 1 ≤ j ≤ 3
the graph Gj is connected to at least 13 k of the vertices vi,j , there exists 3 < i ≤ k
such that Vi contains two vertices connected to two distinct Gj ’s. By modifying the
partition V1 , . . . , Vk , we destroy Gi , which could be a triangle, but obtain two new
triangles instead.
Remark. In fact, by extending this proof a little we can obtain k triangles minus
one edge. This is done by allowing the edges appearing in the proof to be across
different Vi ’s in the final stages.
Proof of Proposition 3.1 for h = 4. We keep track of triangles and K4 copies.
To each triangle we assign a weight of 2, and to each K4 copy a weight of 5. We now
describe a procedure that increases the total weight at each stage, and terminates
HAJNAL-SZEMEREDI VARIANTS 279
only when G1 , . . . , Gk include less than 9 triangles and less than 4 smaller graphs,
and, in particular, all but at most 11 of them are K4 copies.
For 1 ≤ j ≤ 4, let tj denote the number of listed triangles that are colored with
all colors differing from j . At the beginning of this algorithm these are all 0, and
after each stage these numbers will remain between 0 and 3. Moreover, there will
be no possibility that at any stage three of them are 3 while the remaining one is 0.
At each stage, we execute one of the following procedures, depending on the
exact values of t1 , . . . , t4 .
• If t1 , . . . , t4 are all positive (but are not greater than 3), assume that Gj for
1 ≤ j ≤ 4 is a triangle colored with all colors differing from j . If one of these
triangles is connected to the remaining vertex in its appropriate Vj , say G1 is
connected to v1,1 , we complete it to a K4 and strike out from G1 , . . . , Gk also
one triangle colored differently from G1 . If one of G1 , . . . , G4 is connected
to a vertex in another one of these four triangles, we again complete a K4 and
strike out these two differently colored triangles.
Otherwise, a counting argument shows the existence of 4 < i ≤ k such that
Vi contains vertices connected to two distinct triangles among G1 , . . . , G4 ,
so we eliminate two triangles, and perhaps one more triangle or K4 copy, to
obtain two K4 ’s.
It is easily shown that the total weight increases this way, and at least two of
t1 , . . . , t4 will be less than 3 (in case one of them becomes 0).
• If one of t1 , . . . , t4 is 0 and another one not greater than 1, assume, without
loss of generality, that t1 = 0, t2 ≤ 1. Assume further that G1 , . . . , G4 are
neither triangles nor K4 copies. By Lemma 3.1, we may assume that G1 and
G2 are edges colored with 3 and 4, G3 an edge colored with 2 and 4, and G4
an edge colored with 1 and 3.
We want to find a vertex vi,1 connected to G1 , a vertex vi,2 connected to G2 , a
vertex vi,3 connected to G3 , and a vertex vi,4 connected to G4 . If any of these
is found within the vertices of V1 , . . . , V4 , we complete the stage by modifying
the partition (if necessary), and adding the new triangle to G1 , . . . , Gk . The
new triangle adds to t1 or t2 , but these remain less than 3 (in case there is still
a tj that is 0).
Otherwise, a counting argument shows the existence of an 4 < i ≤ k such
that Vi contains three of the required vertices. Modifying the partition, we
may destroy a K4 or an existing triangle that was Gi , but not a triangle colored
with 2, 3, 4 by the assumption t1 = 0. However, we obtain three new triangles.
t1 necessarily becomes 1 or 2, t2 may increase by no more than 2, t3 and t4
do not increase.
In any case, the total weight increases, and the rules regarding t1 , . . . , t4 in
the description of this algorithm are not violated.
• If one of t1 , . . . , t4 is 0 and all others are at least 2, then by the description of
this algorithm at least one of t1 , . . . , t4 is exactly 2. Assume, without loss of
generality, that t1 = 0, t2 = 2. Assume further that G1 , . . . , G4 are neither
280 JOURNAL OF GRAPH THEORY
triangles nor K4 copies. By Lemma 3.1, we may assume that G1 and G2 are
edges colored with 3 and 4, G3 an edge colored with 2 and 4, and G4 an edge
colored with 2 and 3.
We want to find a vertex vi,1 connected to G1 , a vertex vi,2 connected to G2 ,
a vertex vi,3 connected to G3 , and a vertex vi,4 connected to G4 . If any of
the last three mentioned vertices is found within V1 , . . . , V4 , we complete the
stage by modifying the partition (if necessary), and adding the new triangle
to G1 , . . . , Gk , setting t1 = 1.
Otherwise, counting arguments show the existence of 4 < i ≤ k and l, which
satisfies either l = i or l ≤ 4, such that three of the required four vertices
are within vl,1 , vi,2 , vi,3 , and vi,4 . Modifying the partition, we may destroy a
K4 or a triangle that was Gi (but not one colored with 2, 3, 4), and we obtain
three new triangles. This increases t1 , may increase t2 by at most one, and
does not increase t3 or t4 . Since all the ti ’s but t1 were at least 2, none of
them becomes 0.
In any case here the total weight increases, and t1 , . . . , t4 become positive
but do not exceed 3, so the rules regarding them are not violated.
All possible cases for the values t1 , . . . , t4 being covered, we note that this
procedure is applicable as long as G1 , . . . , Gk contain at least 9 triangles, or at least
4 smaller graphs. Since at each stage the weight increases (by at least 1), and the
maximal total weight is 5k , we conclude that the procedure terminates in O(k 2 )
running time. This completes the proof of the proposition for h = 4.
The following simple proposition shows that the conclusion of Conjecture 3.1
2h−3
holds, if we replace the function h−1
h k in its assumptions by 2h−2 k .
Proposition 3.2. If G is an h-partite graph with color classes C1 , . . . , Ch of size
k, such that each vertex in any class has at least 2h−3
2h−2 k neighbors in each of the
other classes, then G contains k vertex disjoint copies of Kh .
Proof. By induction on h. The case h = 2 is already known. For h > 2, we first
apply induction to find k vertex disjoint copies of Kh−1 occupying the first h − 1
color classes. Then we construct a bipartite graph H with color classes A, B as
follows: A consists of the Kh−1 copies found earlier, B is the remaining color class
of G. u ∈ A is connected to v ∈ B , if all vertices of the Kh−1 copy corresponding
to u are neighbors of v in G. A counting argument shows that the known case h = 2
of Conjecture 3.1 applies to H , thus yielding a perfect matching, which corresponds
to the required Kh copies in G.
4. CYCLES IN h-PARTITE GRAPHS
The proposed conjecture regarding the colored version of the Hajnal–Szemerédi
Theorem can be extended to the following problem.
Suppose that K is a fixed graph on the vertex set {v1 , . . . , vh }, and G is an
h-partite graph with k vertices in each color class. Formulate conditions on the
HAJNAL-SZEMEREDI VARIANTS 281
number of neighbors of a vertex from a color class of G in each of the other color
classes, such that the existence of k vertex disjoint copies of K in G, each with one
vertex from each color class in the manner corresponding to K , is ensured.
An instance of the general problem, other than Conjecture 3.1, is the following
conjecture.
Conjecture 4.1. If G is an h-partite graph with color classes C1 , . . . , Ch of size
k, such that for any 1 ≤ i ≤ h each vertex in Ci has at least h+1
2h k neighbors in
each of Ci+1 , Ci−1 (the indices are modulo h), then G contains k vertex disjoint
cycles, each consisting of one vertex from each class.
If true, the condition on the number of neighbors of each vertex in each class is
tight, since for d < h+1
2h k we can define as G the following counter example: Choose
sets A, B , such that A consists of d vertices from each color class, B consists of
max{d, k−d} vertices from each class, and A∩B consists of max{0, 2d−k} < h1 k
vertices of each class. Choose as edges all possible edges between Ci , Ci+1 for
1 ≤ i < h, which are incident with two vertices in A or two vertices in B , and all
possible edges between C1 , Ch , which are incident with one vertex in A and one
vertex in B .
It is easily shown that every possible cycle in this G contains at least one vertex
from A ∩ B , and since |A ∩ B| < k , there are no k vertex disjoint cycles.
If true, Conjecture 4.1 gives strong evidence in favor of El–Zahar’s conjecture
([4], see also [1] and [5]). For h = 3, the conjecture is identical to Conjecture 3.1,
and by a simple extension of the proof in the previous section we can arrive at the
following.
Proposition 4.1. If for a graph G as above each vertex has at least 23 k neighbors
in the next class and in the previous one, then G contains k−2 cycles as in Conjecture
4.1, found in polynomial time in k.
Sketch of proof. We maintain a partition as in the proof of Proposition 3.1,
keeping track of complete cycles only. Suppose that V1 , V2 , V3 do not contain such
cycles. By adding edges one by one, using each time the proof method of Lemma
3.1, we may assume that Vi contains a path from vi,i+1 to vi,i−1 in the right color
order for each 1 ≤ i ≤ 3.
If there is a cycle within V1 , V2 , V3 , we modify the partition, if necessary, and add
it to our list. Otherwise, a counting argument shows that by modifying the partition
we can complete two of these paths to cycles, with a possibility of destroying one
previously found cycle in the process.
ACKNOWLEDGMENTS
I would like to thank Professor Noga Alon for the helpful discussion and the continuing support. I would also like to thank an anonymous referee for his useful
comment.
282 JOURNAL OF GRAPH THEORY
References
[1] N. Alon and E. Fischer, 2-factors in dense graphs, Discrete Math 152 (1996),
13–23.
[2] B. Bollobás, Extremal graph theory, Academic, New York, 1978.
[3] K. Corrádi and A. Hajnal, On the maximal number of independent circuits in
a graph, Acta Math Acad Sci Hungar 14 (1963), 423–439.
[4] M. H. El–Zahar, On circuits in graphs, Discrete Math 50 (1984), 227–230.
[5] E. Fischer, Cycle factors in dense graphs, Discrete Math 197/198 (1999),
309–323.
[6] A. Hajnal and E. Szemerédi, ‘‘Proof of a conjecture of Erdös,’’ Combinatorial
Theory and its Applications, Vol. II, P. Erdös, A. Renyi, and V. T. Sös, (editors)
Colloq Math Soc J Bolyai. 4 (1970), 610–623.
Документ
Категория
Без категории
Просмотров
5
Размер файла
245 Кб
Теги
451
1/--страниц
Пожаловаться на содержимое документа