\documentstyle
[12pt]
{article}

\def\e{\varepsilon} 
\def\ph{\varphi}
\def\ra{\rightarrow}
\def\Z{{\bf Z}}
\def\R{{\bf R}}
\def\Rplus{\R^+}
\def\RO{\R^{\geq 0}}
\def\mod{\;\mbox{\rm mod}}
\def\qed{$\Box$\par\bigskip\noindent}
\newtheorem{th}{THEOREM}

\title{Real-valued frequency assignment} 
\author{D.~G.~Fon-Der-Flaass
\thanks{Supported by the U.K. Radiocommunications Agency}
\\Centre for Discrete and Applied Mathematics
\\London School of Economics
\\Houghton St. London WC2A 2AE, U.K.}

\date{}

\begin{document}
\maketitle

\begin{abstract}
We consider the binary constraints formulation of the frequency assignment
problem in its most general form: for an arbitrary metric space, 
with frequencies taking arbitrary real
values, and with possibly infinitely many constraints. We obtain some 
necessary and sufficient conditions for the problem to have a solution 
with a finite span. When the metric space is the set of integers,
we give an exact criterion.

Also we demonstrate a connection of this problem in one-dimensional case
with one combinatorial question about finite permutations; and pose some
unsolved problems.
\end{abstract}

The practical problem of assigning frequencies to transmitters 
in a cellular network has been approximated by various combinatorial 
and/or geometrical formulations. Most often it is treated as a
problem of finding a colouring of a metric space (e.g. a graph). The required
colouring should satisfy a certain set of restrictions; usually each 
restriction involves two vertices, and the restrictions therefore are
called {\em binary constraints}.


In this note we consider a variant of the standard binary constraints
problem in which frequencies (or {\em colours}) can take on arbitrary 
real values. Apart from its theoretical significance, this problem can 
also have some practical importance; especially for the question
to what extent one can improve the performance by using more channels
within the same frequency interval.

\bigskip
Let $(M,d)$ be an arbitrary metric space. By a (real-valued) 
{\it colouring} of $M$ we mean any function $c:M\ra\R$; the {\it span}
of the colouring being $$sp(c)=\sup_{m\in M}c(m)-\inf_{m\in M}c(m).$$
By a {\it restriction function} we mean any non-increasing function 
$f:\Rplus\ra\RO$. A colouring $c$ of $M$ {\it satisfies} the restriction $f$
if for every two distinct elements $x,y$ of $M$ we have 
$$|c(x)-c(y)|\geq f(d(x,y)).$$

The real-valued frequency assignment problem in its most general form
can now be stated as follows: 

given a metric space $M$ and a restriction function $f$, find the value of
$\inf\;sp(c)$ for all colourings $c$ of $M$ satisfying the restriction $f$.

We shall denote this number by $sp(M,f)$.

First we shall study this problem for $M=\Z$, the set of integers, with
the natural metric $d(x,y)=|x-y|$.
The restriction function in this case is determined by a non-increasing
sequence $f=(f_n)_{n>0}$ of non-negative real numbers. The first question 
which arises in this situation is whether $sp(\Z,f)$ is finite or infinite.
We shall give the complete answer to this question, and also we'll find upper
bounds on the span when it is finite.

\begin{th}\label{th1}
For the restrictions sequence $f_n=1/n$, the span
$sp(\Z,f)$ is finite and does not exceed 
$$1+\ph=2.618\ldots,$$
where $\ph=(1+\sqrt{5})/2$
is the golden ratio. There exists a colouring $c$ of span $1+\ph$ 
satisfying $f$.
\end{th}

\begin{th}\label{th2}
For an arbitrary restrictions sequence $f=(f_n)$, 
the span $sp(\Z,f)$ is finite if and only if 
$C=\sup\{nf_n\mid n>0\}$ is finite; and the span does not exceed $C(1+\ph)$.
\end{th}

\begin{th}\label{th3}
If the sum $s=\sum_{n>0}f_n$ is finite then the span
$sp(\Z,f)$ is finite, and the span does not exceed $2s$.
\end{th}

First we shall derive Theorem \ref{th2} from Theorem \ref{th1}, 
and prove Theorem \ref{th3}; both
proofs are fairly easy. Then we'll give a proof of Theorem \ref{th1}.

\bigskip
PROOF OF THEOREM \ref{th2}. The ``if'' part immediately follows from Theorem 1.
Indeed, if the number $C$ is finite then for all $n$, $f_n\leq C/n$;
and we can take the colouring $c$ from Theorem 1 multiplied by $C$.

The ``only if'' part is just as easy. Given $L>0$, choose $n$ such that 
$nf_n>L$. As $f_i\geq f_n$ for $i<n$, all differences between colours of
elements $0,1,\ldots,n$ in a colouring satisfying $f$ are at least $f_n$;
and the span of these $n+1$ colours is at least $nf_n>L$. \qed

%\bigskip
PROOF OF THEOREM \ref{th3}. We shall assign colours to elements of $\Z$ 
one by one, 
in the following order: $0,1,{-1},2,{-2},\ldots$, choosing on each step
a value $c(k)\in [0,2s]$ which satisfies the colouring conditions. This
is always possible, since the measure of the set of values for
$c(k)$ which are forbidden by any of the previously chosen values of $c(i)$,
$i\leq|k|$,
is at most $2\sum_{i=1}^{2|k|} f_i$ and is less than $2s$. \qed

%\bigskip
PROOF OF THEOREM \ref{th1}.

Denote by $a\mod\;b$ with real $a,b$ the number
$q$ such that $0\leq q<b$, and $(a-q)/b\in\Z$.
Let also $\R_r$ mean the factorgroup $\R/r\Z$ of the additive group of reals.
The distance between elements of the group is naturally defined as
$d_r(a,b)=\min ((a-b)\mod\;r,(b-a)\mod\;r)$.

Let $X$ be the half-open interval $[-(\ph+1)/2,(\ph+1)/2)$.
Define a colouring $c:\Z\ra X$ by the formula:
$c(n)=((\ph+1)/2)+n\ph)\mod(\ph+1)-(\ph+1)/2$. 
If we consider elements of $X$ as representatives of the cosets 
$\R/(\ph+1)\Z$ then 
the colouring $c$ becomes a group homomorphism $c:\Z\ra\R_{\ph+1}$. 

Let us prove that this colouring satisfies the restriction $f$.
Since $c$ is a homomorphism, it is enough to show that for every $n>0$
the distance $d_{\ph+1}(c(0),c(n))\geq 1/n$.

Our colouring has the following easy properties:

$(i)$ \quad $c(0)=0$;

$(ii)$ \quad $c(n+1)-c(n)$ is equal to either $\ph$ or $-1$;

$(iii)$ \quad $d_{\ph+1}(0,c(n))=|c(n)|$.

The property $(ii)$ enables us to give an alternative description 
of the colouring by an easy inductive 
process: $c(0)=0$, and $c(n+1)$ is that one of the two numbers 
$c(n)+\ph$, $c(n)-1$ which belongs to $X$.

Properties $(i)$ and $(ii)$ imply that the number $c(n)$ 
is of the form $-a+b\ph$ for some natural numbers $a,b$ with $a+b=n$. 
Let $y=b+a\ph$; we have $y\leq n\ph$. Also, 
$$c(n)y=ab(\ph^2-1)+(b^2-a^2)\ph=(ab+b^2-a^2)\ph.$$
The number $ab+b^2-a^2$ is a non-zero integer; therefore
$|c(n)|\geq \ph/y\geq \ph/(n\ph)=1/n$, and by $(iii)$ we are done.
\qed

\medskip
Note that the colouring described above is a cyclic channel colouring 
(in the sense of \cite{HLS}) with the same constraints function; which is
a stronger property.

\bigskip
Our next theorem gives a sufficient and a necessary condition for finiteness
of the span for general discrete metric spaces. Though these conditions don't 
give a complete answer to the problem, they are rather close.

Let $M$ be a metric space, and sequences $(l_n)$, $(u_n)$ be such that
for every $n>0$, and for every $x\in M$, the following inequalities hold:
$$l_n\leq|\{y\in M\mid n-1<d(y,x)\leq n\}|\leq u_n.$$ 

Let $f$ be a restriction function; we extend its domain by setting 
$f(0)=\sup_{x>0} f(x)$, and assume that $f(0)$ is finite.
This assumption is very natural. Indeed, if there is a positive lower 
bound $\e$ on the distance between distinct elements of $M$ then we can
assume that $f(x)=f(\e)$ for all $0<x<\e$; on the other hand, if one can 
have arbitrarily small distances then this assumption is necessary for
the span to be finite.

\begin{th}\label{th4}
In the above notation, if $\sup f(n)\sum_{i=1}^n l_i=\infty$ then 
$sp(M,f)$ is infinite. If $\sum_{i=1}^\infty f(i-1)u_i<\infty$ then 
$sp(M,f)$ is finite.
\end{th}

PROOF.\quad The first assertion is proved exactly as the ``only if''
part of Theorem \ref{th2}; the second assertion --- as Theorem \ref{th3}.
\qed

For the $k$-dimensional rectangular grid $\Z^k$ we can take
$l_n=c_1n^{k-1}$ and $u_n=c_2n^{k-1}$ for suitable constants $0<c_1<c_2$.
As an immediate corollary, we get that $sp(\Z^k,(n^{-\alpha}))$ is finite
when $\alpha>k$, and infinite when $0<\alpha<k$; and this holds for every 
metrics on $\Z^k$ equivalent to the Euclidean one --- including the graph
distance metrics. 

The question whether $sp(\Z^k,(n^{-k}))$ is finite or 
infinite remains open for $k\geq 2$.

\bigskip
The result of Theorem \ref{th1} has an interesting application to 
monotone subsequences in permutations. 

The classical theorem of Erd\H os and Szekeres
\cite{Erd} states that every permutation of more than $n^2$ numbers has 
a monotonic (increasing or decreasing) subsequence of length more than $n$. 

Let $s\in S_n$ be a permutation of the set $\Omega=\{1,\ldots,n\}$, and 
$w=(i_0,\ldots,i_k)$ be an increasing sequence of elements of $\Omega$ 
such that the sequence $(s(i_0),\ldots,s(i_k))$ is monotonic
(to avoid trivialities, we assume that $k\geq 2$).
By the {\em density} of $w$ we mean the number $d(w)=k^2/(i_k-i_0)$.

The above-mentioned theorem implies that for $n>4$ there exists a lower bound
$b(n)>0$ such that every permutation in $S_n$ has a monotonic subsequence
of density at least $b(n)$; the bound $b(n)$ so obtained tends to 1 as $n$ 
tends to infinity. A question arises: can one find such a lower bound which
would tend to infinity with $n$? Theorem \ref{th1} gives a negative answer 
to this question.

Take the colouring $c$ as in this theorem. For every $n$ we define a 
permutation $f_n\in S_n$ as follows. The numbers $c(1),\ldots,c(n)$ are 
all distinct and linearly ordered; let $f_n(k)$ be the position of $c(k)$
in this ordering. We claim that every monotonic subsequence of any of the
permutations $f_n$ has density less than $1+\ph$. Indeed, let 
$i_0<i_1<\ldots<i_k$ be such that the sequence $(c(i_0),\ldots,c(i_k))$ 
is monotonic. We have:
\begin{eqnarray*}
i_k-i_0 &=& (i_k-i_{k-1})+\ldots+(i_1-i_0)\geq\\
     &\geq& |c(i_k)-c(i_{k-1})|^{-1}+\ldots+|c(i_1)-c(i_0)|^{-1}\geq\\
     &\geq& k\cdot(|c(i_k)-c(i_0)|/k)^{-1}>\\
        &>& k^2/(1+\ph);
\end{eqnarray*}
and the claim follows. 

\medskip
This leaves two related open questions: find the best possible value $b_1$
of the bound $b$ from the above problem; and find the exact value of
$b_0=sp(\Z,(1/n))$. The above considerations show that 
$$1\leq b_1\leq b_0\leq 1+\ph=2.618\ldots.$$ 
It is not difficult to show that $b_0\geq 2$
by considering all possible orderings of the five values $c(0),\ldots,c(4)$.

\begin{thebibliography}{9}
\bibitem{Erd} P.~Erd\H os, G.~Szekeres. A combinatorial problem in geometry.
{\em Compositio Math.} 2(1935), 463--470.

\bibitem{HLS} J.~van~den~Heuvel, R.A.~Leese, M.A.~Shepherd. Graph Labelling
and Radio Channel Assignment. {\em CDAM Research Report Series}, CDAM-96-23,
1996.

\end{thebibliography}
\end{document}