Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Note on Gy. Elekes’s conjectures concerning unavoidable patterns in proper colorings. | Note on Gy. Elekes s conjectures concerning unavoidable patterns in proper colorings Vera Rosta Webster University Geneva 1293 Bellevue Switzerland rosta@ 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 Erdos - Gyarfas and to Szemeredi 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 Kn 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 Kn are properly colored with cn colors where c 0 n n1 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 Szemeredi Theorem 1 6 Any set A a1 a2 . ang c N whith an cn and n n2 k c contains an arithmetic sequence of length k. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 N3 2 Szemeredi s theorem would follow easily from the last conjecture Let G A1 A2 be a complete bipartite graph where A1 A2 are identical copies of A and the color of the edge x y is x y where x 2 A1. Then the edges of G are properly colored with 2cn colors. If Conjecture 2 were true with n n1 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 2m-1 n 2m for some m. Label the .
