%A LaTeX file for a 3 page document
\documentclass[12pt]{article}
%\usepackage[textures]{graphics} % mac textures
%\usepackage[dvips]{graphics} % unix tex
%\usepackage{epsfig,amsmath}
\usepackage{amsmath}
\renewcommand{\baselinestretch}{1.0}
\setlength{\oddsidemargin}{0mm}
\setlength{\evensidemargin}{0mm}
\setlength{\textwidth}{152mm}
\setlength{\topmargin}{0mm}
\setlength{\textheight}{217mm}
%\setlength{\headsep}{0in}
%\setlength{\headheight}{0pt}
\def\theequation{\arabic{equation}}
\def\thefigure{\arabic{figure}}
\def\thetable{\arabic{table}}
\def\thetheorem{\arabic{theorem}}
\newtheorem{theorem}{Theorem}
\newtheorem{conjecture}{Conjecture} % the same numbering as theorem
\newtheorem{example}{Example} % the same numbering as theorem
\newenvironment{PROOF}[1]
{\medskip\noindent{\bf #1}\quad}{\QED \bigskip}
\newenvironment{proof}
{\begin{rm}\par\smallskip\noindent{\bf Proof.}\quad}{\QED\end{rm}}
\def\BBox{\rule{2mm}{3mm}}
\def\QED{\hfill$\BBox$}
\title{Note on Gy. Elekes's conjectures concerning unavoidable patterns in proper colorings}
\author{
Vera Rosta\\
\small{Webster University Geneva}\\
\small{1293 Bellevue, Switzerland}\\
\small\texttt{rosta@masg22.epfl.ch}}
\date{\small{Submitted: March 19, 2000; Accepted: May 2, 2000.\\
AMS Classification numbers: 05C15, 05C55, 05C38}}
\begin{document}
\pagestyle{myheadings}
\markright{\sc the electronic journal of
combinatorics \textbf{7} (2000), \#N3\hfill}
\thispagestyle{empty}
\maketitle
\begin{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\H os - Gy\'arf\'as and to Szemer\'edi's theorem are examined.
\end{abstract}
%\section{Note}
\bigskip\noindent
The coloring of the edges of a simple undirected graph is considered $\it proper$ if adjacent
edges have different colors.
To solve some combinatorial geometry questions, Elekes formulated the following conjectures:
\begin{conjecture}\label{C1} \cite{E1}
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.
\end{conjecture}
\begin{conjecture}\label{C2} \cite{E2}
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$.
\end{conjecture}
This last conjecture is closely related to the following well known theorem of Szemer\'edi:
\begin{theorem}\cite{Sz}\label{THM}
Any set $A=\{a_1,a_2,\ldots,a_n\}\subset N$ whith $a_nn_2(k,c)$ contains an
arithmetic sequence of length $k$.
\end{theorem}
Szemer\'edi'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\in A_1$. Then the edges of $G$ are properly colored
with $2cn$ colors. If Conjecture~\ref{C2} were true, with $n>n_1(2k,2c)$ an alternating $2$ -colored path of length $2k$ would guarantee an arithmetic progression of size $k$.
\bigskip
Here we give a coloring disproving the complete graph version of Conjecture~\ref{C2} for $k>3$, which can be easily applied to the bipartite case.
\begin {example}
Let $2^{m-1}< n\leq 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 \pmod{2}$. Consider $K_n$ as a subgraph of $K_{2^m}$.
\end{example}
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,\ldots,x,a,b,c,\ldots,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 \cite{C}.
\bigskip
Closely related to the topic of this note is the following question raised by P. Erd\H os and A. Gy\'arf\'as \cite{EGy} : 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 \cite{A} has an example showing that
it is possible with $2n^{1+c/\sqrt{logn}}$ colors.
\bigskip
The above bipartite graph version of Szemer\'edi's theorem has no $2$-colored cycles at all. This
suggests the following modification of Conjecture~\ref{C2}:
\begin{conjecture}\label{C3}
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$.
\end{conjecture}
Conjecture~\ref{C3} and the Erd\H os-Gy\'arf\'as 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~\ref{C3} means that it is true).
\bigskip\noindent
{\bf Agknowledgment} I am grateful to Gy. Elekes for telling me his interesting conjectures and to A. Gy\'arf\'as, Z. F\"uredi and A. Thomasson for helpful comments.
\bigskip\noindent
\begin{thebibliography}{99}
\bibitem{A} M. Axenovich, A generalized Ramsey problem, {\em Discrete Mathematics}, to appear.
\bibitem{E1} Gy. Elekes, Recent trends in combinatorics, DIMANET Matrahaza workshop 22-28 Oct 1995, {\em Combin. Probab. Comput}
{\bf (8)} (1999), Cambridge University Press, Cambridge (1999), Ed.~by E. Gyori and V.T. Sos, Problem collection, 185--192.
\bibitem{E2} Gy. Elekes, oral communication.
\bibitem{C} P. Cameron, Parallelism and Complete Designs, {\em London Math. Soc. Lecture Note.} {\bf Ser.~23} Cambridge University Press (1976).
\bibitem{EGy} P. Erd\H os and A. Gy\'arf\'as, A variant of the Classical Ramsey Problem, {\em Combinatorica} {\bf 17(4)} (1997), 459--467.
\bibitem {Sz} E. Szemer\'edi, On sets of integers containing no $k$ elements in arithmetic progression, {\em Acta Arithmetika} {\bf 27}, 199--245.
\end{thebibliography}
\end{document}