Note on Gy. Elekes’s conjectures concerning unavoidable patterns in proper colorings

Vera Rosta

Webster University Geneva 1293 Bellevue, Switzerland

                            rosta@masg22.epfl.ch

Submitted: March 19, 2000; Accepted: May 2, 2000. AMS Classification numbers: 05C15, 05C55, 05C38

Abstract

A counterexample is presented to Gy. Elekes’s conjecture concerning the existence of long 2-colored paths in properly colored graphs. A modified version of the conjecture is given and its connections to a problem of Erdős - Gyárfás and to Szemerédi’s theorem are examined.

The coloring of the edges of a simple undirected graph is considered proper if adjacent edges have different colors. To solve some combinatorial geometry questions, Elekes formulated the following conjectures:

Conjecture 1 [2] Let the edges of the complete graph K_{n} be properly colored with cn colors, c > 0. If n is sufficiently large then it must contain a six cycle with opposite edges having the same color.

Conjecture 2 [3] If the edges of the complete bipartite graph K(n, n) (or the edges of a complete graph K_{n}) are properly colored with cn colors where c > 0, n > n_{1}(k, c) then there exists an alternating 2-colored path of length k.

This last conjecture is closely related to the following well known theorem of Szemerédi:

Theorem 1 [6] Any set A = {a_{1}, a_{2}, …, a_{n}} ⊂ N whith a_{n} < cn, and n > n_{2}(k, c) contains an arithmetic sequence of length k.

Szemerédi’s theorem would follow easily from the last conjecture: Let G = (A_{1}, A_{2}) be a complete bipartite graph where A_{1}, A_{2} are identical copies of A and the color of the edge (x, y) is x − y where x ∈ A_{1}. Then the edges of G are properly colored with 2cn colors. If Conjecture 2 were true, with n > n_{1}(2k, 2c) an alternating 2 -colored path of length 2k would guarantee an arithmetic progression of size k.

Here we give a coloring disproving the complete graph version of Conjecture 2 for k > 3, which can be easily applied to the bipartite case.

Example 1 Let 2^{m−1} < n ≤ 2^{m} for some m. Label the vertices of the complete graph K_{2^{m}} by the 0-1 vectors of length m. Color the edges by 2^{m} − 1 colors as follows. The color of edge (x, y) is the 0-1 vector x + y (mod 2). Consider K_{n} as a subgraph of K_{2^{m}}.

It is easy to see that in the example the union of any t > 1 colors consists of disjoint components of at most 2^{t} vertices. Also no open path can consist of edges colored (in this order) a, b, c, …, x, a, b, c, …, x since such a sequence must always return to the starting point (i.e., it is a closed walk) by the mod 2 property . Therefore this example contradicts the second but not the first conjecture. In the special case of n = 2^{m} this example uses n−1 colors, proper coloring is a 1-factorization and if there is no 2-colored path with 4 edges then this coloring is unique up to isomorphism [4].

Closely related to the topic of this note is the following question raised by P. Erdős and A. Gyárfás [5] : Is it possible to have a proper edge coloring of K_{n} with cn colors so that the union of any two color classes has no paths or cycles with 4 edges? M. Axenovich [1] has an example showing that it is possible with 2n^{1+c/\sqrt{logn}} colors.

The above bipartite graph version of Szemerédi’s theorem has no 2-colored cycles at all. This suggests the following modification of Conjecture 2:

Conjecture 3 Let (A, B) be a complete bipartite graph with |A| = |B| = n, n > n_{3}(k, c) and the edges are properly colored with cn colors so that the union of any two color classes does not contain a cycle. Then there is an alternating 2-colored path of length k.

Conjecture 3 and the Erdős-Gyárfás problem are closely related. For k = 4 the two are equivalent. For k > 4 a positive answer to either of them would mean a negative answer for the other but a negative answer for either of them would not solve the other (where a positive answer for Conjecture 3 means that it is true).

Agknowledgment I am grateful to Gy. Elekes for telling me his interesting conjectures and to A. Gyárfás, Z. Füredi and A. Thomasson for helpful comments.

References

[1] M. Axenovich, A generalized Ramsey problem, Discrete Mathematics, to appear.

[2] Gy. Elekes, Recent trends in combinatorics, DIMANET Matrahaza workshop 22-28 Oct 1995, Combin. Probab. Comput (8) (1999), Cambridge University Press, Cambridge (1999), Ed. by E. Gyori and V.T. Sos, Problem collection, 185–192.

[3] Gy. Elekes, oral communication.

[4] P. Cameron, Parallelism and Complete Designs, London Math. Soc. Lecture Note. Ser. 23 Cambridge University Press (1976).

[5] P. Erdős and A. Gyárfás, A variant of the Classical Ramsey Problem, Combinatorica 17(4) (1997), 459–467.

[6] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arithmetika 27, 199–245.