\documentclass{rae}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{epsf}

\firstpagenumber{616}
\received{September 30, 1993}

\Volume{19}
\IssueNumber{2}
\Year{1993/94}


\def\integer{\Bbb Z}
\def\natural{\Bbb N}
\def\rational{\Bbb Q}
\def\real{\Bbb R}

\newcommand{\supp}{\operatorname{supp}}

%% Theorems, etc.

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}{Problem}

\newcommand{\thm}[2]{\begin{theorem}\label{#1}#2\end{theorem}}
\newcommand{\cor}[2]{\begin{corollary}\label{#1}#2\end{corollary}}
\newcommand{\prop}[2]{\begin{proposition}\label{#1}#2\end{proposition}}
\newcommand{\lem}[2]{\begin{lemma}\label{#1}#2\end{lemma}}
\newcommand{\pr}[2]{\begin{problem}\label{#1}#2\end{problem}}
 
%%%%%%%%%%%%%%%%%%%%%   MISCELLANEOUS
 
\renewcommand{\P}{\mbox{$\cal P$}}
\newcommand{\B}{\mbox{$\cal B$}}
\newcommand{\e}{\mbox{$\varepsilon$}}

% characteristic function
     \newcommand{\charf}[1]{\mbox{\raise.48ex\hbox{$\chi$}$_{#1}$}}

%End of proof marker
\def\qed{\hfill$\Box$}
%Proof
\def\proof{\noindent{\sc Proof.} }



\title{ON RANGE OF UNIFORMLY ANTISYMMETRIC FUNCTIONS}
\author{Krzysztof Ciesielski,
Department of Mathematics,
West Virginia University,
Morgantown, WV 26506-6310,
(kcies@wvnvms.wvnet.edu)}

\date{}

\markboth{K.~Ciesielski}{On Range of Uniformly Antisymmetric Functions}

\keywords{uniformly antisymmetric functions, 
coloring of infinite graphs}
\MathReviews{26A15, 26A21}

\begin{document}\maketitle

\begin{abstract}
In this note it is proved that the range of uniformly 
antisymmetric function must have at least four elements. 
This generalizes the results from \cite{Kostyrko} and
\cite{CL:Unif} that the range of such function must
have at least three elements. The problem whether the range
of uniformly antisymmetric function can be finite remains open.
\end{abstract}

 
For a linear space $K\subset\real$ over $\rational$
a function $f\colon K\to\real$ is {\em uniformly antisymmetric}
if for every $x\in K$ 
there exists $g(x)\in (0,1)$ such that
\[
|f(x-h)-f(x+h)|\geq g(x)
\]
for every $0<h<g(x)$, $x\in K$. 
It is easy to see that 
$f\colon K\to\integer$ is uniformly antisymmetric
if there exists a function $g\colon K\to(0,1)$,
called a {\em gage function}, such that
\[
f(x-h)\neq f(x+h)
\]
for every $0<h<g(x)$, $h\in K$. 

Uniformly antisymmetric functions has been studied by
Kostyrko \cite{Kostyrko},
Cie\-sielski and Larson \cite{CL:Unif}, and
Komj\'ath and Shelah \cite{KomShel}.
In \cite{CL:Unif} it has been proved that
there exists an uniformly antisymmetric function 
$f\colon\real\to\natural$. 
It has been also shown there that
there is no uniformly antisymmetric function 
$f\colon K\to\{0,1\}$ for any uncountable linear space $K\subset\real$ 
over $\rational$, generalizing the result form \cite{Kostyrko}.
The main open problem from \cite[Problem 1]{CL:Unif} is whether 
there exists a uniformly antisymmetric function $f\colon\real\to\real$
with finite or bounded range.
In this note we will 
\pagebreak
reformulate this problem in terms of $n$-coloring of
some infinite graphs on $\real$ and
show that there is no 
uniformly antisymmetric function 
$f\colon K\to\{0,1,2\}$ for any uncountable linear space $K\subset\real$ 
over $\rational$. 


We need some definitions and facts. Let $K\subset\real$ be a linear
space over $\rational$. 
For a gage function $g\colon K\to(0,1)$
define a graph $G_g=(K,E_g)$ by considering $K$ as its set of vertices 
and defining the set $E_g$ of its edges as
the set of all unordered pairs $\{a,b\}$ from $K$ such that
$g(x)\geq |x-a|=|x-b|$ for $x=(a+b)/2$.
Notice that for $B\subset\integer$ there exists a uniformly 
antisymmetric function $f\colon K\to B$ with a gage function $g$
if and only if $f$ is a coloring of the graph $G_g$ such that
no two vertices connected by an edge have the same color.
In other words, there exists a uniformly antisymmetric function 
$f\colon K\to\{0,1,\ldots,n-1\}$ with gage $g$ if and only if
the graph $G_g$ is $n$-colorable. 

Since graph $G_g$ is $n$-colorable if and only if 
every its finite subgraph is $n$-colorable (see \cite{BruinErdos})
we conclude the following theorem. 

\thm{th1}{ For any linear space $K\subset\real$ 
over $\rational$ and any natural number $n$
there exists a
uniformly antisymmetric function 
$f\colon K\to\{1,2,\ldots,n\}$ if and only if there exists
a function $g\colon K\to(0,1)$ such that every finite subgraph of 
$G_g$ is $n$-colorable. 

In particular, there is no uniformly antisymmetric function 
$f\colon K\to\real$
with finite range if and only if for every 
$g\colon K\to(0,1)$ and every natural number
$n$ the graph $G_g$ contains a finite subgraph which is not 
$n$-colorable. \qed }

Now, we are ready to prove the following theorem.

\thm{thA}{ Let $K$ be an uncountable linear space over $\rational$.
If $f\colon K\to\{1,2,3\}$ then $f$ is not
uniformly antisymmetric function.}

Proof. Choose arbitrary $g\colon K\to(0,1)$. By Theorem \ref{th1}
it is enough to show that
$G_g$ contains finite subgraph which is not $3$-colorable. 
To this order we will show that $G_g$ contains $K_4$, i.e., graph
with $4$ vertices and all possible edges.

We denote vertices of $K_4$ by 
$A$, $B$, $C$ and $D$. We will think of this $K_4$ 
as on $3$-dimensional tetrahedron with base formed by vertices
$A$, $B$ and $C$. (See figure.)
Let $a$, $b$ and $c$ denote the mid points of intervals (edges) $BC$,
$AC$ and $AB$, respectively. (Thus, in triangle $ABC$, point
$a$ is a center of the side opposite to $A$, etc.)
Also, centers of sides $AD$, $BD$ and $CD$ are denoted by 
$a^\prime$, $b^\prime$ and $c^\prime$, respectively.

The algebraic relation between these points is given by
equations
\begin{equation}\label{eqBase}
A+B=2c,\ \ \ B+C=2a,\ \ \ A+C=2b,
\end{equation}
\begin{equation}\label{eqTop}
A+D=2a^\prime,\ \ \ B+D=2b^\prime,\ \ \ C+D=2c^\prime.
\end{equation}

Solving (\ref{eqBase}) we obtain
\begin{equation}\label{solBase}
A=-a+b+c,\ \ \ B=a-b+c,\ \ \ C=a+b-c.
\end{equation}
\protect\begin{center}\leavevmode\epsfbox{tetrahedron2.ps}\\
$K_4$ embedded into $G_g$.\end{center}
In particular, to insure that graph generated by triangle
$ABC$ is in $G_g$ it is enough to make sure that there 
 exists $\e>0$ such that
\begin{equation}\label{conBase1}
|a-B|=|b-c|<\e,\ |b-C|=|a-c|<\e,\ |c-A|=|a-b|<\e
\end{equation}
and
\begin{equation}\label{conBase2}
\e<g(a),\ \ \ \e<g(b),\ \ \ \e<g(c).
\end{equation}
Notice also, that adding each of the
equations (\ref{eqBase}) to an appropriate equation from
(\ref{eqTop}) we obtain 
\begin{equation}\label{conCenter1}
2(a+a^\prime)=2(b+b^\prime)=2(c+c^\prime)=A+B+C+D.
\end{equation}
So, intervals $[a,a^\prime]$, $[b,b^\prime]$
and $[c,c^\prime]$ have a common center. 
Denote this common center by $X$. Then, 
\begin{equation}\label{conCenter}
a^\prime=2X-a,\ \ \ b^\prime=2X-b,\ \ \ c^\prime=2X-c.
\end{equation}
Let $\delta$ denote the diameter of the set 
$\{a,b,c,a^\prime,b^\prime,c^\prime\}$
and notice that, by (\ref{eqTop}) and (\ref{solBase}),
\[
|a^\prime-D|=|A-a^\prime|=|-a+b+c-a^\prime|\leq |-a+b|+|c-a^\prime|\leq 2\delta.
\]
Similarly we can show that 
$|b^\prime-D|\leq 2\delta$ and $|c^\prime-D|\leq 2\delta$.
Thus, in order to insure that edges $AD$, $BD$ and $CD$ are in 
$G_g$ it is enough
to choose $ABCD$ such that
\begin{equation}\label{conCenter3}
g(a^\prime)>2\delta,\ \  g(b^\prime)>2\delta,\ \ g(c^\prime)>2\delta.
\end{equation}

Now, we are ready to make the choice of our $K_4$.
First, choose $d\in(0,1/4)$ and an uncountable $S\subset K$ such that
$g[S]\subset(4d,1)$. Pick $X\in K$ such that $S\cap(X - d,X + d)$
is uncountable and define 
$T=\{2X-s\colon s\in S\cap(X - d,X + d)\}$. 
Thus, $T\subset(X - d,X + d)$ is uncountable.
Choose uncountable subset $T_1\subset T$ and $\e>0$
such that $g[T_1]\subset(\e,1)$.
We can pick $a,b,c\in T_1$ such that $a<b<c<a+\e$.
Now, from points $a,b,c$ and $X$ we can reconstruct
$A,B,C,D,a^\prime,b^\prime,c^\prime$ as described above.

Edges $AB$, $BC$ and $AC$ are in $G_g$, since 
$a,b,c$ satisfy (\ref{conBase1}) and (\ref{conBase2}).

To see that edges $AD$, $BD$ and $CD$ are
in $G_g$ notice that
$a^\prime,b^\prime,c^\prime\in S$, i.e., 
$g(a^\prime)>4d$, $g(b^\prime)>4d$ and $g(c^\prime)>4d$.
To finish the proof it is enough to notice that
$a,b,c,a^\prime,b^\prime,c^\prime\in (X - d,X + d)$, i.e.,
that $\delta<2d$, since this implies (\ref{conCenter3}).
\qed 

The following questions seems to be intriguing in light of the previous theorem.

\pr{pr1}{ Can we embed $K_5$ into $G_g$ for every $g\colon\real\to\real$? }

\begin{thebibliography}{22}
\bibitem{BruinErdos} N.~G.~de~Bruin, P.~Erd\"{o}s, 
A colour problem for infinite graphs and a problem in the theory of relations,
{\sl Proceedings} 54 (1951), 371--373.
\bibitem{CL:Unif} K. Ciesielski, L. Larson, Uniformly antisymmetric functions,
{\sl Real Analysis Exchange} 19(1) (1993-94), this volume.
\bibitem{Kostyrko} P.~Kostyrko, There is no strongly locally antisymmetric set,
{\sl Real Analysis Exchange} 17 (1991-92), 423--425.
\bibitem{KomShel} P.~Komj\'ath and S.~Shelah, 
On uniformly antisymmetric functions, 
{\sl Real Analysis Exchange} 19(1) (1993-94), this volume.
\end{thebibliography}

\end{document}