\documentclass{rae}
\usepackage{amstex}
%\input StandardMacros
\firstpagenumber{147}
\received{July 26, 1994}
\MathReviews{Primary 26A16; Secondary 03E50, 04A20.}
%\coverauthor{K. Ciesielski}
%\covertitle{Uniformly antisymmetric functions and $K_5$}
\date{}

\keywords{uniformly antisymmetric functions,
uniformly anti-Schwartz functions,
the Continuum Hypothesis, coloring of infinite graphs.}

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

\def\qed{\hfill$\Box$}

\def\natural{\mathbb N}
\def\N{\natural}
\def\rational{\mathbb Q}
\def\Z{\mathbb Z}
\def\Q{\rational}
\def\real{\mathbb R}
\def\R{\real}
\def\pf{{\sc Proof.\ }}


%%%%%%%% END FOR AMS LATEX

%% Theorems, etc.
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}{Problem}
\newtheorem{remark}{Remark}

\newtheorem{FACT}{Fact}

\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}}
\newcommand{\fact}[2]{\begin{FACT}\label{#1}#2\end{FACT}}
\newcommand{\rem}[2]{\begin{remark}\label{#1}#2\end{remark}}

%%%%%%%%%%%%%%%%%%%%%   MISCELLANEOUS

\renewcommand{\P}{\mbox{$\cal P$}}
\newcommand{\B}{\mbox{$\cal B$}}
%\renewcommand{\G}{\mbox{$\cal G$}}
\newcommand{\G}{\mbox{$\cal G$}}
\newcommand{\F}{\mbox{$\cal F$}}
\newcommand{\e}{\mbox{$\varepsilon$}}
%\renewcommand{\e}{\mbox{$\varepsilon$}}

\title{UNIFORMLY ANTISYMMETRIC FUNCTIONS AND $K_5$}
\author{Krzysztof Ciesielski,\thanks{The results
presented in this paper were
in part obtained
during the Joint US--Polish Workshop in Real Analysis,
{\L}{\'o}d{\'z}, Poland, July 1994.
The Workshop was partially
supported by the NSF grant INT--9401673.}\ \
Department of Mathematics,
West Virginia University,
Morgantown, WV 26506-6310,
(kcies@@wvnvms.wvnet.edu)}

\date{}

\markboth{K.~Ciesielski}{Uniformly antisymmetric functions and $K_5$}

\begin{document}\maketitle

\begin{abstract}
In \cite[Thm 2.5]{CL:Unif} and \cite[Thm 2]{CL:Unif2}
it was proved that there is no uniformly antisymmetric
function with two- and three-element range
by showing that $K_3$ and $K_4$ can be embedded into a
graph $G(h)$ (defined below)
for all appropriate $h$. In this note we will
answer Problem 1 from \cite{CL:Unif2} by showing that
under the continuum hypothesis there exists $h$ for which
$K_5$ cannot be embedded into $G(h)$. In particular, the
technic used in the proof that there is no uniformly antisymmetric
function with three-element range cannot be
used for the four-element range proof.
Whether there exists a uniformly antisymmetric
function with a finite range remains an open problem.

The notion of a uniformly anti-Schwartz function is also defined
and it is proved that there exists a
uniformly anti-Schwartz function $f\colon\R\to\N$.
\end{abstract}


For $S\subset\R$ and $h\colon S\to(0,\infty]$ let
\[
E(h)=\left\{\{a,b\}\in[\R]^2\colon\frac{a+b}{2}\in S\ \&\
\frac{|a-b|}{2}<h\left(\frac{a+b}{2}\right)\right\}.
\]
The graph $G(h)=(\R,E(h))$ is an infinite graph with
vertices $\R$ and edges $E(h)$. We will answer the problem
from \cite{CL:Unif2} by showing that
under the continuum hypothesis there exists
a function $h\colon\R\to(0,1)$ such that the
graph $G(h)$ does not contain $K_5$,
the complete graph on 5 vertices, as a subgraph.

The motivation for this question lies in
the study the uniformly antisymmetric functions, i.e.,
functions $f\colon\R\to\R$ for which there exists
$h\colon\R\to(0,1)$ such that
\[
|f(x-h)-f(x+h)|\geq h(x)
\]
for every $x\in\R$ and $0<h<h(x)$.
(See \cite{Kostyrko}, \cite{CL:Unif}, \cite{KomShel} and \cite{CL:Unif2}.)
It is known \cite{CL:Unif} that
there exists a uniformly antisymmetric function $f\colon\R\to\N$,
while it is unknown whether such function can have a finite range
\cite[Problem 1(a)]{CL:Unif}.

It is not difficult to show
\cite[Theorem 1]{CL:Unif2} that there exists
a uniformly antisymmetric function with
$n$-element range if and only if there exists
$h\colon\R\to(0,1)$ such that
$G(h)$ is $n$-colorable. In \cite{CL:Unif2}
it was proved that the range of every
uniformly antisymmetric function must have at least
four elements by showing that $G(h)$ contains $K_4$
for every $h\colon\R\to(0,1)$. We will show here
that this result cannot be extended to $K_5$.

\thm{main}{Let $M$ be a subfield of $\R$ of cardinality $\omega_1$.
Then there exists $h\colon M\to(0,1)$ such that
$G(h)$ does not contain $K_5$.

In particular, if the continuum hypothesis holds, then
there exists $h\colon\R\to(0,1)$ such that
$G(h)$ does not contain $K_5$.
}

\pf
Let $\{M_\xi\colon\xi<\omega_1\}$ be an increasing tower of countable
subfields of $M$ such that
$M=\bigcup_{\xi<\omega_1}M_\xi$ and
$M_\lambda=\bigcup_{\xi<\lambda}M_\xi$
for every limit ordinal $\lambda<\omega_1$. We will construct,
by transfinite induction on $\xi<\omega_1$, an increasing sequence
$\{h_\xi\colon M_\xi\to(0,1)\colon\xi<\omega_1\}$ such that
the following inductive conditions are satisfied
for every $\xi<\omega_1$:
\begin{description}

\item[($A_\xi$)] $G(h_\xi)$ does not contain $K_5$, i.e.,
$[A]^2\not\subset E(h_\xi)$ for every $A\in[\R]^5$;

\item[($B_\xi$)] for every $\zeta\leq\xi$ and $B\in[M_\zeta]^3$
if
\[
S_\xi(B)=\{B+t\in[\R]^3\colon [B+t]^2\subset E(h_\xi)\},
\]
then $S_\xi(B)$ is a finite subset of $[M_\zeta]^3$.
\end{description}

The existence of such a sequence immediately implies Theorem \ref{main}
if we take $h=\bigcup_{\xi<\omega_1}h_\xi$.

To construct the sequence assume that
$\{h_\xi\colon M_\xi\to(0,1)\colon\xi<\eta\}$
is already constructed for some $\eta<\omega_1$.
If $\eta$ is a limit ordinal, then
it is easy to see that $h_\eta=\bigcup_{\xi<\eta}h_\xi$
satisfies the inductive hypothesis.
So, assume that $\eta$ is a successor ordinal, say $\eta=\xi+1$.

Let $\{x_n\colon n<\omega\}$ be an enumeration,
without repetitions, of
$M_{\xi+1}\setminus M_\xi$. Since $h_{\xi+1}$ is already
defined on $M_\xi$, it is enough to define
$h_{\xi+1}(x_n)$ for every $n<\omega$.

Before we define it, let us choose $g_\xi\colon M_{\xi+1}\to(0,1)$
such that $G(g_\xi)$ does not contain any odd cycle.
Such a function exists
since for every countable field $M\subset\R$ there exists
a uniformly antisymmetric function $f\colon M\to\{0,1\}$.
(See \cite[Theorem 1]{KomShel}.)

Now, choose $n<\omega$. For each $i<j<n$ consider
the family $S_{ij}^n$ of all sets $B=\{a,b,c\}\subset M_\xi$ such that
$[B]^2\subset E(h_\xi)$ and that
there exists $d\in\R$ with $a+d=2x_i$, $b+d=2x_j$ and $c+d=2x_n$.
Notice that for every
$B^\prime,B\in S_{ij}^n$ there exists $t$ such that $B^\prime=B+t$.
Thus, by ($B_\xi$), the set $S_{ij}^n$ is finite.
In particular, the number
\[
\e_n=\frac{1}{2}\min\{|p-x_n|>0\colon p\in B\
\text{ for some $B\in S_{ij}^n$ and $i<j<n$}\}
\]
is well defined and positive. Define
\[
h_{\xi+1}(x_n)=\min\left\{g_\xi(x_n),\e_n,\frac{1}{n}\right\}.
\]

To finish the proof it is enough to show that
the conditions ($A_{\xi+1}$) and ($B_{\xi+1}$) are satisfied.

We will start with showing ($B_{\xi+1}$). So,
choose $\zeta\leq\xi+1$, let
$B=\{a,b,c\}\in[M_\zeta]^3$
and let
$x=(a+b)/2$, $y=(b+c)/2$ and $z=(a+c)/2$. Then
\begin{equation}\label{eq}
a=x-y+z,\ \ \ b=x+y-z,\ \ \ c=-x+y+z.
\end{equation}
First notice that $S_{\xi+1}(B)\subset [M_{\xi+1}]^3$.
This is the case since
$B+t\in S_{\xi+1}(B)$ implies $t\in M_{\xi+1}$, as
for every $t\in\R\setminus M_{\xi+1}$ we have
$x+t= t + (a+b)/2\not\in M_{\xi+1}$ and so,
$\{a+t,b+t\}\not\in E(h_{\xi+1})$.

If $\zeta<\xi+1$, then
$S_\xi(B)$ is a finite subset of $[M_\zeta]^3$ by ($B_\xi$).
It is enough to show that $S_{\xi+1}(B)=S_\xi(B)$.
But if $B+t\in S_{\xi+1}(B)\setminus S_\xi(B)$, then
$t\in M_{\xi+1}\setminus M_\xi$. In particular,
$\{x+t,y+t,z+t\}\subset M_{\xi+1}\setminus M_\xi$.
But this would imply that $[B+t]^2\subset E(g_\xi)$,
contradicting the fact that $G(g_\xi)$ does not contain any odd cycle.

So, assume that $\zeta=\xi+1$.
If there exists a number
$t\in\R$ such that $\{x+t,y+t,z+t\}\subset M_\xi$, then
$B+t\in[M_\xi]^3$ and $S_{\xi+1}(B+t)=S_{\xi+1}(B)=S_\xi(B)$
is finite subset of
$[M_\xi]^3\subset[M_\zeta]^3$ by the above.

So, assume that $\{x+t,y+t,z+t\}\not\subset M_\xi$ for every
$t\in\R$ and choose
$B+t\in S_{\xi+1}(B)\subset [M_{\xi+1}]^3$. Then
there exist $k<\omega$ such that
$x_k\in\{x+t,y+t,z+t\}$.
But if $n<\omega$ is such that $1/n<\min\{|a-x|,|b-y|,|c-z|\}$,
then $k<n$, since otherwise
$[B+t]^2\not\subset E(h_{\xi+1})$. Therefore, there is at most
$3n$ numbers $t\in\R$ such that $[B+t]^2\subset E(h_{\xi+1})$.
Thus, the set $S_{\xi+1}(B)$ is a finite subset of
$[M_{\xi+1}]^3=[M_\zeta]^3$.

\newpage

To prove ($A_{\xi+1}$) assume, by way of contradiction, that
$G(h_{\xi+1})$ contains $K_5$; i.e., that there is
$A=\{a,b,c,d,e\}\in[\R]^5$ such that
$[A]^2\subset E(h_{\xi+1})$.
Let us identify the edges of $G=(A,[A]^2)$ with their centers.
Then all edges are in $M_{\xi+1}$.
Let $E_0$ ($E_1$) be all edges of $G$ that belong (do not belong)
to $M_\xi$ and let
$G_i=(A,E_i)$ for $i<2$.

Notice that $G_1$ does not contain any odd cycle, since
it is a subgraph of $G(g_\xi)$. Hence,
it is bipartite. As it has $5$ vertices,
some of the bipartition classes must have at least $3$ elements,
say $a,b,c$. This is a triangle in $G_0$.
In particular, by (\ref{eq}), $a,b,c\in M_\xi$.

At least one of the remaining two vertices, say $d$, is in
$M_{\xi+1}\setminus M_\xi$. Then so are $(a+d)/2$, $(b+d)/2$ and
$(c+d)/2$, i.e., they are equal to
$x_i$, $x_j$ and $x_n$,
respectively, for some distinct $i,j,n\in\omega$.
Assume that $i<j<n$. Then, $\{a,b,c\}\in S_{ij}^n$ and
$h_{\xi+1}(x_n)\leq\e_n<|c-x_n|$. Therefore,
$\{c,d\}\not\in E(h_{\xi+1})$ contradicting our assumption.

Theorem \ref{main} has been proved. \qed

The above argument, as well as a technique used in \cite{CL:Unif2}
and \cite{CL:Unif} suggest that the problem of existence of
uniformly antisymmetric function with finite range has a considerably
algebraic content. The next theorem shows that this is indeed the case.
That is, in the absence of linear dependency, the problem becomes
trivial.

\thm{independent}{ If $B\subset\R$ is linearly independent
over $\Q$
and $h\colon B\to(0,\infty]$ is such that $h(x)=\infty$ for every
$x\in B$, then
$G(h)$ is $3$-colorable. }

\pf Let $\G$ be the family of all components of $G(h)$, i.e., of
all maximal connected subgraphs of $G(h)$.
It is enough to show that every $G\in\G$ is $3$-colorable.

Let $\G_0$ be the family of all $G\in\G$ that contain an odd cycle.
Evidently every $G\in\G\setminus\G_0$ is $2$-colorable. Thus, it is enough
to show that the graph $G_0=\bigcup\G_0$ is $3$-colorable.

Define
\[
\F=\{w\colon B\to\Z\colon 1<|\{b\in B\colon w(b)\neq 0\}|<\omega\ \&\
\Sigma_{b\in B}w(b)=1\}
\]
and put $\supp(w)=\{b\in B\colon w(b)\neq 0\}$ for $w\in\F$. Moreover,
let $V(G_0)$ denote the set of all vertices of $G_0$ and define
\[
V=\{x\in\R\colon (\exists w_x\in\F)
(x=\Sigma_{b\in B}w_x(b)\,b\}.
\]
We will show first that
\begin{equation}\label{vertices}
V(G_0)\subset V.
\end{equation}

To see this first notice that if $a_0,\ldots,a_{2n}$ are the vertices of
an odd cycle in $G_0$ and $b_i=(a_i+a_{i+1})/2$ for all $i\leq 2n$ (where
$a_{2n+1}=a_0$), then $a_0=\Sigma_{i=0}^{2n}(-1)^i\,b_i$. It is easy to see
that $a_0\in V$. The proof of (\ref{vertices}) is then completed
by induction
on the distance from an odd cycle if we notice that for every
$x=\Sigma_{b\in B}w_x(b)\,b\in V$ and $y\in\R$
connected with $x$; i.e., such that $b_0=(x+y)/2\in B$, we have
$y=2b_0 - x = 2b_0 - (\Sigma_{b\in B}w_x(b)\,b)\in V$.

Now let $G_1$ be the subgraph of $G(h)$ generated by the vertices of $V$.
Since $G_0$ is a subgraph of $G_1$, it is enough to show that
$G_1$ is $3$-colorable.
To see it first notice that, by linear independence of
$B$ over $\Q$, for every $x\in V$ there exists precisely one
$w_x\in\F$ such that $x=\Sigma_{b\in B}w_x(b)\,b$.
Moreover, the vertices $x,y\in V$ are connected, if and only if
$b_0=(x+y)/2$ belong to $B$. This is equivalent to saying that
there is an edge between $x,y\in V$ if and only if
there is $b_0\in B$ such that $w_x(b_0)+w_y(b_0)=2$ and
$w_x(b)+w_y(b)=0$ for all $b\in B$, $b\neq b_0$.

Define the $3$-coloring $c\colon V\to\{0,1,2\}$ of $V$ the following way.
For $x\in V$ let
$\supp(w_x)=\{b_0,\ldots,b_n\}$, where $b_0<\cdots<b_n$.
Notice that $n>0$. Then put
\[
c(x)= \left\{
\begin{array}{ll}
0      & w_x(0)<0\\
1      & w_x(0)>0\ \&\ w_x(n)<0\\
2      & w_x(0)>0\ \&\ w_x(n)>0.\\
\end{array}\right.
\]
It is easy to see that this function is indeed a $3$ coloring of $G_1$.

This finishes the proof of Theorem \ref{independent}. \qed

The definition of uniformly antisymmetric function was motivated by
the study of the paradoxical behavior of real functions from
the point of view of their symmetric continuity. The natural counterpart
of the symmetric continuous functions, i.e., functions $f$ for which
$\lim_{h\to 0} f(x-h) - f(x+h) =0$, are Schwartz continuous functions, i.e.,
functions for which $\lim_{h\to 0} f(x-h) + f(x+h) - 2 f(x) =0$ for all
$x\in\R$.
(See \cite{thomson}.%
\footnote{ Thomson uses terms ``nowhere weakly symmetrically
continuous function'' for uniformly antisymmetric function and
``symmetric continuous function'' for Schwartz continuous
function.}%
)
Thus, the following seems to be a natural
counterpart for uniformly antisymmetric functions:
a function $f\colon\R\to\R$ is
said to be {\em uniformly
anti-Schwartz} provided for every $x\in\R$ there exists
$g(x)>0$ such that for every $0<h<g(x)$
\[
|f(x-h) + f(x+h) - 2 f(x)|\geq g(x).
\]

Hajrudin Fejzi\'{c} asked the author, whether there exist a uniformly
anti-Schwartz function. The following theorem gives
a positive answer to this question.



\thm{Schwartz}{ There exists a function $f\colon\R\to\N$ which is
uniformly anti-Schwartz. Moreover,
\[
|f(x+h)+f(x-h)-2f(x)|\geq 1\ \
\text{ for {\bf all} $x\in\R$ and $h> 0.$}
\]
}

\pf
Let $S\subset\N$ be infinite and
such that it does not contain any arithmetic progression
of length 3.
Let $\{P_n: n\in S\}$ be a partition of $\R$ such that
no $P_n$ contains an arithmetic progression of length 3.
(The existence of such partition is well known. For example, the
partition from \cite[Thm 1.1]{CL:Unif}
has this property.)

Define
\[
f(x)=n\  \text{ if and only if }\   x\in P_n.
\]

Now if $|f(x+h)+f(x-h)-2f(x)| < 1$,
then $f(x+h)+f(x-h)-2f(x) = 0$.
Thus, the numbers $f(x-h)$, $f(x)$ and $f(x+h)$
form an arithmetic progression.
But the assumption on $S$ implies that
$f(x-h)=f(x)=f(x+h)=n$  for some  $n$  from $S$.

So $x-h$, $x$ and $x+h$ belong to the same  $P_n$.
However since  $P_n$
is 3-arithmetic progression free, we conclude that $h=0$.

This completes the proof. \qed

The referee and Miroslav Chleb{\'\i}c noticed that%
\footnote{During the Joint US--Polish Workshop in Real Analysis,
{\L}{\'o}d{\'z}, Poland, July 1994.}
that if in the above prove we take $S=\N$,
choose a quickly decreasing sequence $\{a_n\}_{n\in\N}$
like $a_n=3^{-n}$ and define
\[
f(x)=a_n\  \text{ if and only if }\   x\in P_n,
\]
then we obtain a uniformly anti-Schwartz function
with bounded range. The problem of finding uniformly antisymmetric
function with bounded range (\cite[Prob. 1(b)]{CL:Unif},
\cite[Prob. 25]{thomson})
remains open.



\pr{prSch}{ Does there exist a
uniformly anti-Schwartz
function $f\colon\R\to\R$ with two element range?}

This problem seems to be particularly interesting in light
of the fact, that it is known that there is no
uniformly antisymmetric function with two element range
\cite[Thm 2.1]{CL:Unif}.



\begin{thebibliography}{22}
\bibitem{CL:Unif2} K. Ciesielski,
On range of uniformly antisymmetric functions,
{\sl Real Analysis Exchange} 19(2) (1993--94), 616--619.
\bibitem{CL:Unif} K. Ciesielski, L. Larson,
Uniformly antisymmetric functions,
{\sl Real Analysis Exchange} 19(1) (1993--94), 226--235.
\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), 218--225.

\bibitem{thomson} Brian Thomson,
{\sl Symmetric Properties of Real Functions},
Marcel Dekker, 1994.

\end{thebibliography}

\end{document}