\documentstyle[12pt,leqno]{article}
\topmargin -0.6in
\textheight 9.5in
\oddsidemargin -0.2in
\textwidth 6.8in
\parindent 0in
\parskip 1em
\def\LIMBO#1{}
\def\mb#1{\hbox{\kern0.25ex}\( #1 \)\hbox{\kern0.25ex}}
\def\ml#1{\hbox{\kern0.25ex}\( #1 \)\hbox{\kern0.01ex}}
\def\mr#1{\hbox{\kern0.01ex}\( #1 \)\hbox{\kern0.25ex}}
\def\Spoint{\hskip -1em.~ }
\def\sec#1{\section{\Spoint #1}}
\def\susec#1{\subsection{\Spoint #1}}
\def\sususec#1{\subsubsection{\Spoint #1}}
\def\Tpoint{\sf\hskip -0.4em. }
\newtheorem{Definition}{Definition}
\def\DEFINITION#1{\begin{Definition}\Tpoint #1\end{Definition}}
\newtheorem{Theorem}{Theorem}
\def\THEOREM#1{\begin{Theorem}\Tpoint #1\end{Theorem}}
\newtheorem{Lemma}{Lemma}
\def\LEMMA#1{\begin{Lemma}\Tpoint #1\end{Lemma}}
\newtheorem{Note}{Note}
\def\NOTE#1{\begin{Note}\Tpoint #1\end{Note}}
\def\FORM#1{\begin{equation}#1\end{equation}}
\def\BR{\char'051~}
\newcounter{NASS}
\newenvironment{ASSERT}{\begin{list}%
{\hbox{\kern5ex}\arabic{NASS}\BR\hbox{\kern0.5ex}}%
{\usecounter{NASS}\labelwidth=7ex%
\topsep=0.5em\parskip=0.2em\parsep=1.0em\itemsep=0.0em}}%
{\end{list}}
\newenvironment{ASS}{\begin{list}%
{\hbox{\kern5ex}\arabic{NASS}\BR\hbox{\kern0.5ex}}%
{\usecounter{NASS}\labelwidth=7ex%
\topsep=0.0em\parskip=0.0em\parsep=0.0em\itemsep=0.0em}}%
{\end{list}}
\newenvironment{LIST}[1]{\begin{list}%
{\hbox{\kern5ex}{\bf (#1\arabic{NASS})}\hbox{\kern0.5ex}}%
{\usecounter{NASS}\labelwidth=7ex\topsep=0em\parsep=0em\itemsep=0em}\sf}%
{\end{list}}
\newenvironment{LISTI}[1]{\begin{list}%
{\hbox{\kern5ex}{\bf (#1\arabic{NASS}\(_{i}\))}\hbox{\kern0.5ex}}%
{\usecounter{NASS}\labelwidth=7ex\topsep=0em\parsep=0em\itemsep=0em}\sf}%
{\end{list}}
\def\LL#1{\label{#1}\hfill\quad\fbox{\fbox{\normalsize\bf#1}}
}
\def\RF#1{\ref{#1}~\fbox{\small\bf#1}~
}
\def\RFBF#1#2{{\bf (#1\ref{#2})}}
\def\refI#1{{\bf (I\ref{#1}\(_{i}\))}}
\def\refIplus#1{{\bf (I\ref{#1}\(_{i+1}\))}}
\def\BRACK#1{
\[ \left\{
\parbox{6.2in}{
\begin{itemize}
#1
\end{itemize}
}
\right. \]
}
\def\BRACKET#1{
\begin{equation}
\quad\left\{
\parbox{6.2in}{
\begin{itemize}
#1
\end{itemize}
}\right.
\end{equation}
}
\def\R{{\bf R}}
\def\Z{{\bf Z}}
\def\EX{{\bf E}}
\def\term#1{{\sc #1}}
\def\HB#1{\hbox{\quad#1\quad}}
\def\SET#1{\{#1\}}
\def\proof{\par{\bf Proof: }}
\def\implies{~\Longrightarrow~}
\def\origin{{\cal O}}
\def\OK{{OK}}
\def\DOK{\Delta\OK}
\def\ML{{\cal L}}
\def\ALL{{all}}
\def\END{{end}}
\def\nn{n}
\def\nl{r}
\def\SL{{R}}
\def\mem{m}
\def\const{\hbox{const}}
\def\size{M}
\def\median{\hbox{\sf median}}
\def\dist{\hbox{\sf dist}}
\def\norm{\hbox{\sf norm}}
\def\diam{\hbox{\sf diam}}
\def\span{\hbox{\sf span}}
\def\ersatz{\hbox{\sf ersatz}}
\def\hub{\hbox{\sl hub}}
\def\rub{\hbox{\sl rub}}
\def\lowest{\hbox{\sl pit}}
\def\alfa{\alpha}
\def\epsi{\varepsilon}
\def\delt{\delta}
\def\barnabla{\bar{\nabla}}
\def\fin{\hbox{\sf fin}}
\def\inf{\hbox{\sf inf}}
\def\INF{\hbox{\sf INF}}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\D{{\cal D}}
\def\F{{\cal F}}
\def\M{{\cal M}}
\def\T{{\cal T}}
\def\U{{\cal U}}
\def\V{{\cal V}}
\def\qed{~~\raisebox{-0.3ex}{$\Box$}~~}
\def\empset{\hskip -0.1em \raisebox{-0.3ex}{
\begin{picture}(10,10)(0,0)
\put(0, 0){\line(1, 1){10}}
\put(5, 5){\circle{8}}
\end{picture}~}}
\begin{document}%\baselineskip=2.5em
\begin{center}
\vskip 1em
{\LARGE A Critical Phenomenon in Growth Systems}
\vskip 1em
{\Large Andrei Toom\\
Mathematics Department, University of Texas at Austin}%
\footnote{Author's present address:
{\sl Incarnate Word College. 4301 Broadway. San Antonio, Texas 78209.}}
\vskip 1em
\end{center}
\begin{abstract}
The paper treats of interacting infinite or finite systems
whose components' states are in the set \mb{\SET{0,1,2,3,\ldots}}.
All components' initial states are zeroes.
Components interact with each other in a local deterministic way,
in addition to which every component's state grows by one
with a constant probability \mb{\theta} at every moment of the discrete time.
Our main question about infinite systems is whether the average value
of components tends to infinity or remains bounded as \mb{t\to\infty}.
The analogous question about finite systems is how long the system's
average remains less than a constant: this time may be bounded or
tend to infinity as the system' size tends to infinity.
Both in the infinite and finite cases sufficient conditions for
both ways of behavior are given here. It is shown that the different
ways of behavior may occur with one and the same deterministic
interaction depending on the value of \mb{\theta}.
\end{abstract}
The combinatorial method applied here to growth systems, was developed
\cite{Toom-80,Toom-82,Discrete-90}
for systems with a finite set of states of every point.
Our introductory examples (\RF{median-NEC}) and (\RF{median-line}) are
growing analogues of Votings which were first proposed in \cite{VPP}.
The first of these Votings is now known as the NEC-system \cite{BG-85}.
The techniques used here is similar to that of \cite{Toom-80},
explained for the case of the NEC-system in \cite{LMS}
(where it is called the Toom model). The finite case
(of the NEC-system) was first treated of in \cite{Berman-Simon}.
The importance of non-symmetry was pointed at in \cite{Pippenger}.
An alternative method was proposed in \cite{Bramson-Gray}.
\sec{Introductory Examples}
Throughout the paper
\mb{\R} stands for the set of real numbers,
\mb{\R_+} is the set of non-negative real numbers,
\mb{\Z} is the set of integers,
\mb{\Z_+} is the set of non-negative integers.
\mb{\EX (\cdot)} means expectation.
Let us compare random processes with the state space \ml{\R_+^{\Z^2}}.
To specify a state means to assign a real number
\mb{x(i,j) \geq 0} to every \ml{(i,j) \in \Z^2}.
Take the initial state `all zeroes' and assume that at every moment
of the discrete time every \mb{x(i,j)} undergoes the following two steps:
\begin{description}
\item[Step 1 : ] \mb{x(i,j)} takes the value of some deterministic
function \mb{d(\cdot)} of its and its neighbors' previous states.
\item[Step 2 : ] \mb{x(i,j)} is incremented by 1 with probability \mb{\theta}
independently of the others' increments and of the prehistory.
\end{description}
The only difference between processes in question is in
the \term{transition function} \mb{d(\cdot)} used in Step 1.
Let \mb{\EX_\theta(i,j,t)} stand for the
expectation of \mb{x(i,j)} at time \ml{t}.
These expectations are the same for all \mb{(i,j) \in \Z^2} if the
initial condition and the transition rule are uniform,
and in these cases we call them \ml{\EX_\theta(t)}.
We are interested in the behavior of \mb{\EX_\theta(t)} as \ml{t\to\infty}.
The introductory Theorem 1 shows that in a fairly general case
\mb{\EX_\theta(t)} tends to infinity provided \mb{\theta} is close enough to 1.
It is very easy to present transition functions for which
\mb{\EX_\theta(t)} tends to infinity with any \ml{\theta>0},
for example if Step 1 does not change the value of \ml{x(i,j)} at all,
or \mb{d(\cdot)} equals the arithmetical mean of its arguments.
By definition, \median ~of \mb{2k-1} arguments equals the \ml{k}-th
number among them if they are ordered in the increasing order.
Note that median does not favor greater or smaller values, i.e.
$$
\median(-x_1,\ldots,-x_{2k-1})=-\median(x_1,\ldots,x_{2k-1}).
$$
However, in the process in which
\FORM{
d(\cdot)=\median(x(i,j),x(i+1,j),x(i,j+1)), \LL{median-NEC}
}
\mb{\EX_\theta(t)} remains bounded by a constant,
provided \mb{\theta} is small enough. This follows from our Theorem 2.
(In fact, this process takes values in \ml{\Z_+^{\Z^2}}.)
Thus, for some functions \mb{d(\cdot)}, including (\RF{median-NEC}),
there is a critical value of \mb{\theta}, which separates
two modes of behavior -- with bounded and growing \ml{\EX_\theta(t)}.
Theorem 3 proves the analogous phenomenon for finite systems
in the same assumptions about the deterministic interaction.
Of course, in finite systems \mb{\EX_\theta(t)} can not remain
bounded forever: it remains bounded during time which grows
exponentially in the system's size.
Geometrical positions of neighbors are essential. For example,
it is fairly evident that the process with
\FORM{
d(\cdot)=\median(x(i,j),x(i+1,j),x(i-1,j)) \LL{median-line}
}
has \mb{\EX_\theta(t)\to\infty} for any \ml{\theta >0}.
Theorem 4 generalizes this fact and states the class of transition
functions with which the condition of Theorems 2 and 3 is not only sufficient,
but also necessary for the statements of these theorems to be true.
Theorem 5 applies Theorem 4 to the special case when \mb{d(\cdot)} is a median.
\sec{Definitions and Formulations}
\mb{\Z^{\dim}} is the \ml{\dim}-dimensional discrete space.
\mb{\Z_\size} stands for the ring of residues modulo \mb{\size}
and \mb{\Z_\size^{\dim}} is the \ml{\dim}-dimensional torus.
\mb{Space} stands for \mb{\Z^{\dim}} if it infinite
and for \mb{\Z_\size^{\dim}} if it is finite.
\mr{|S|} stands for the cardinality of any finite set \ml{S}.
A family means a set whose elements are sets.
For any functions \mb{F \prec G} means \ml{F \leq\const\cdot G}.
A natural \mb{\mem} is fixed and called \term{memory}.
The set \mb{\SET{-\mem,\ldots,-1,0,1,\ldots}} is called \ml{Time}, and
$$
V=Volume=Space \times Time=\SET{(s,t): s \in Space,~ t \in Time}.
$$
Elements of \mb{V} are called \term{points} and
subsets of \mb{V} are called \term{point-sets}.
If \ml{v=(s,t)}, then \mb{s(v)} means \mb{s} and \mb{t(v)} means \ml{t}.
Points with \mb{t < 0} are called \term{initial},
those with \mb{t \geq 0} are called \term{inner}.
Every inner point \mb{(s,t)} has \mb{\nn} \term{neighbors}
\FORM{
N_i(s,t)=(s,t)+(\Delta s_i, \Delta t_i),~~i=1,\ldots,\nn, \LL{neighbors}
}
where the sequence of \term{neighbor vectors}
\FORM{
\Delta=((\Delta s_1,\Delta t_1),\ldots,(\Delta s_\nn,\Delta t_\nn))
\LL{vectors}
}
is one and the same for all inner points and
$$
\forall i=1,\ldots,\nn~:~-\mem \leq \Delta t_i \leq -1.
$$
For every inner point \mb{v} its neighborhood \mb{N(v)} is the set of its
neighbors. Initial points have empty neighborhoods.
To represent the system of neighborhoods, we shall use the
directed graph \mb{\nabla} which has \mb{V} as its set of vertices,
and edges that go to every inner point \mb{(s,t)}
from \ml{(s,t)+(\Delta s_i,\Delta t_i),~i=1,\ldots,\nn}.
Every point \mb{v} has one and the same set \mb{X_v \equiv X_0=\Z_+}
of its possible states and every inner point
has one and the same transition function
\FORM{
d~:~X_{N(v)} \mapsto X_v,\HB{where}X_{N(v)}=X_0^\nn\HB{and}X_v=X_0. \LL{d}
}
To every point \mb{(s,t) \in V} there corresponds a variable
\mb{x(s,t)\in X_0} which represent the state of this point,
that is the state of component \mb{s} at time \ml{t}.
The set \mb{X=X_0^V} is the configuration space
whose elements \mb{x} are called \term{configurations}.
Generally, to any subvolume \mb{W \subset V} there corresponds
its configuration space \mb{X_W=X_0^W} whose elements \mb{x(W)}
are called configurations on \mb{W}.
For any measure \mb{P} on \mb{X}, any \mb{W \subset V} and any \mb{v \in V},
\mb{P|_W} stands for the projection of \mb{P} to \mb{X_W} and
\mb{P|_v} stands for the projection of \mb{P} to \mb{X_v}.
We shall define \term{random processes}, i.e. normed measures on \mb{X}
using (every time the same) mutually independent \term{hidden variables}
\mb{h(v)} for all inner points \ml{v}, everyone of which equals 1
with probability \mb{\theta} and 0 with probability \ml{1-\theta}.
Thus we have the hidden product-measure \mb{\eta} on the
configuration space \mb{H=\SET{0,1}^V} of the hidden variables.
To any sequence \mb{\Delta} (\RF{vectors}) of neighbor vectors,
any function \mb{d(\cdot)} (\RF{d}) and any value of \mb{\theta}
there corresponds the process, i.e. the normed measure on \mb{X}
induced by \mb{\eta} with the map \mb{D~:~H \mapsto X}
defined in the following inductive way:
\FORM{
x(v)=\cases{0 &if $t(v)<0$, \cr
d(x(N(v)))+h(v) &if $t(v) \geq 0$.} \LL{D}
}
Denote the expectation of \mb{x(s,t)} in this process by
\mb{\EX_\theta^\size(t)}. In all our theorems the system's size \mb{\size}
is any natural or substituted by \mb{\infty} in the infinite case.
\THEOREM{
If \ml{d(x_1,\ldots,x_\nn) \geq \min(x_1,\ldots,x_\nn)}, then
$$
\forall~t,~\size \in \Z_+ \cup \{\infty\}~:~
\EX_\theta^\size(t) \geq C(\theta) \cdot t
$$
for \mb{\theta} large enough, where \ml{C(\theta) \to 1/\mem}
when \ml{\theta\to 1}. \LL{unbounded-T}
}
Theorems 2 and 3, which constitute the main result of our paper,
give a sufficient condition for \mb{\EX_\theta^\size(v)}
to be uniformly bounded during an exponential or infinite time.
Since our systems are uniform (i.e. neighbor vectors and the
transition function are the same for all inner points), it is
sufficient to speak about the neighborhood and transition function
of the origin \mb{\origin}.
\DEFINITION{
A subset \mb{S \subset N(\origin)} is called
a \term{veto-set} if the value of \mb{d(x(N(\origin)))}
can not be greater than \ml{\max\{x(w),~w \in S\}}.
}
Let us consider the infinite volume \mb{V=\Z^{\dim} \cdot Time} as a subset
of the continuous space \ml{R^{\dim+1}} with the same origin \ml{\origin}.
Let \mb{conv(S)} stand for the convex hull of any \ml{S \subset R^{\dim+1}}.
For any set \mb{S \subset R^{\dim+1}} and any number \mb{k} we define:
$$
kS=\{ks:s\in S\},~~~ray(S)=\bigcup\{kS:~k \geq 0\}.
$$
We call \mb{ray(S)} \term{ray} of \ml{S}.
A \term{ray} means a closed half-line emanating from the \ml{\origin}.
\DEFINITION{
$$
\sigma(\Delta,d)= \cap \{ ray(conv(S))~:~S \HB{is a veto-set} \}. \LL{sigma}
$$
}
The following condition plays important role in this paper:
\FORM{
\sigma(\Delta,d)=\{ \origin \}. \LL{sigma=O}
}
\THEOREM{
Given condition (\RF{sigma=O}). Then for \mb{Space=\Z^{\dim}} and for
\mb{\theta} small enough, \LL{bounded-inf-T}
\FORM{
\forall~t~:~\EX_\theta^\infty(t) \leq \theta+O(\theta^2). \LL{bounded-inf-F}
}
More exactly, there is such a function \mb{f(\theta)=\theta + O(\theta^2)} that
$$
\forall~s,~t,~k \in Z_+~:~Prob(x(s,t) \geq k) \leq f^k(\theta).
$$
}
\THEOREM{
Given condition (\RF{sigma=O}). Then for \mb{Space=\Z_\size^{\dim}}
with \mb{\size} large enough and for\mb{\theta} small enough,
there is such \mb{C>1} that \LL{bounded-fin-T}
\FORM{
\forall~t \leq C^\size~:~\EX_\theta^\size(t) \leq \theta+O(\theta^2).
\LL{bounded-fin-F}
}
More exactly, there is such a function \mb{f(\theta)=\theta + O(\theta^2)} that
$$
\forall~s,~t \leq C^\size,~k \in Z_+~:~Prob(x(s,t) \geq k) \leq f^k(\theta).
$$
}
\DEFINITION{
Call a function \term{minimax} if it can be expressed through
minima and maxima. \LL{minimax-D}
}
\THEOREM{
If the function \mb{d(\cdot)} is minimax,
then the condition (\RF{sigma=O}) is not only sufficient,
but also necessary for the statements of Theorems 2 and 3 to be true.
More exactly, if condition (\RF{sigma=O}) is wrong, then \LL{minimax-T}
$$
\forall~t,~\size\in \Z_+\cup\{\infty\}~:~
\EX_\theta^\size(t) \geq C(\theta) \cdot t
$$
where \mb{C(\theta)>0} for all \ml{\theta>0}.
}
\THEOREM{
If the function \mb{d(\cdot)} is a median, then the set
\mb{\sigma(\Delta,d)} either equals \mb{\{ \origin \}}, or is a ray.
The latter case takes place iff there exists such a ray
\mb{\rho \subset R^{\dim+1}} that for any hyperplane \mb{\Pi}
which contains this ray, \LL{plane-T}
$$
BEL > DIF_{out} + DIF_{in}.
$$
Here \mb{BEL} is the number of neighbor vectors that belong to \ml{\rho},~~
\mb{DIF_{out} > 0} is the difference between
the number of neighbor vectors on one side of \mb{\Pi} and
the number of neighbor vectors on the other side of \mb{\Pi},~~
\mb{DIF_{in } > 0} is the difference between
the number of neighbor vectors that belong to \mb{\Pi}
and are on one side of \mb{\rho} and
the number of neighbor vectors that belong to \mb{\Pi}
and are on the other side of \mb{\rho}.
}
\NOTE{
Let all the neighbor vectors be mutually non-collinear. Then the latter
case of Theorem 5 takes place iff there is such a neighbor vector
\mb{\delta \in R^{\dim+1}} that all the other neighbor vectors form pairs,
the two vectors of each pair having the opposite
\ml{\delta}-direction projections to $Space$.\\
\hbox{\kern1em} This statement can be applied to our examples
(\RF{median-NEC}) and (\RF{median-line}).
In our first example (\RF{median-NEC}) such a neighbor
vector \mb{\delta} evidently does not exist.
In our second example (\RF{median-line}) such a neighbor
vector exists and equals \ml{\delta=(0,0,-1)}.
}
Now to prove our theorems. Sign\qed marks ends of proofs.
\sec{Proof of Theorem 1}
It is sufficient to prove Theorem 1 for the case
\FORM{
d(x_1,\ldots,x_\nn)=\min(x_1,\ldots,x_\nn). \LL{d=min}
}
Reconstruct the directed graph \mb{\nabla} into another directed
graph \mb{\barnabla} by stretching every its vertex \mb{v}
into a directed edge and assign to this edge \mb{v}
a random time delay that equals \ml{h(v)}.
Old edges, that come from \mb{\nabla}, have zero delay.
Define the time delay of a path in \mb{\barnabla}
as the sum of delays along it.
Define the time delay of an inner point as the minimum
of delays of paths that lead to it from initial points.
\NOTE{
For any point \ml{v} and any realization of hidden variables,
\ml{x(v)=Delay(v)}. \LL{x=Delay}
}
Thus, \mb{x(v)} equals the minimum of delays \mb{Delay(\Pi)}
that pertain to directed paths \mb{\Pi} from initial points to \ml{v}.
For every path \mb{\Pi} its length \mb{l(\Pi)} is no less than \ml{t(v)/m}.
The number of these paths is no more than \mb{\nn^{t(v)}}.
Delay of every path \mb{\Pi} is the sum of delays along this path, that is
the sum of \mb{l(\Pi)} independent random variables, everyone of which equals
\mb{1} with probability \mb{\theta} and
\mb{0} with probability \ml{1-\theta}.
This reduces the proof of Theorem 1 to an easy calculation
that pertains to sums of independent random variables \qed
\LIMBO{
It is known that for every \mb{k \in (0,1)} we can choose
\mb{\theta <1} such that for every path \mb{\Pi}
$$
Prob(Delay(\Pi) < 2k \cdot t(v)/m ) \prec (2\nn)^{-t(v)}.
$$
Then
$$
Prob(Delay(v) < 2k \cdot t(v)/m) \prec 2^{-t(v)},
$$
whence
$$
\EX_\theta^\size(t)=\EX(Delay(v)) \geq k \cdot t(v)/m
$$
for \ml{t \geq C=\const}. Now choose another \mb{\theta <1} to take care
of \mb{t < C}, and then take the maximum of these values of \mb{\theta} \qed
}
\NOTE{
For the particular case (\RF{d=min}),
this first passage percolation representation allows to prove
assertions of our Theorems 2 and 3 in a more simple way.
}
\sec{Proof of Theorem 2}
\susec{Outline}
We shall present a function
\FORM{
f(\theta)=\theta + O(\theta^2) \LL{f}
}
and for every inner point \mb{v} we shall define
a finite family \mb{\F(v)} of point-sets such that
\FORM{
\forall v~:~\sum\{\theta^{|S|},~~S \in \F(v)\} \leq f(\theta) \LL{sum}
}
and if \ml{x(v) \geq k>0}, there are \mb{k} disjoint
point-sets \mb{S_1,\ldots,S_k \in \F(v)} such that
\FORM{
h_w=1 \HB{for all} w \in S_1 \cup\ldots\cup S_k. \LL{h=1}
}
\LEMMA{
If there is a function \mb{f(x)} and for every inner point \mb{v}
there is a finite family \mb{\F(v)} for which (\RF{f}), (\RF{sum})
and (\RF{h=1}) hold, then Theorem 2 holds. \LL{function+family}
}
\proof From (\RF{h=1}), then (\RF{sum}):
\begin{eqnarray*}
\lefteqn{Prob(x(s,t) \geq k) \leq}\\
&&\sum \{Prob(h_w=1 \hbox{~~for~all~~} w \in S_1 \cup\cdots\cup S_k),
&&\sum \{ \theta^{|S_1 \cup\ldots\cup S_k|},
&&\sum \{ \theta^{|S_1| + \ldots +|S_k|},~~S_1,\ldots,S_k \in \F \}=\\
&&(\sum \{ \theta^{|S|},~S \in \F \})^k \leq f^k(\theta) \qed
\end{eqnarray*}
\LIMBO{
Therefore (using (\RF{f})),
$$
\EX_\theta(s,t)=\sum_{k=1}^\infty Prob(x(s,t) \geq k) \leq
\sum_{k=1}^\infty f^k(\theta)=f(\theta)/(1-f(\theta))=\theta + O(\theta^2),
$$
which may be taken for the right part of (\RF{bounded-inf-F}) \qed
}
\susec{Preliminaries}
\sususec{Graphs}
When treating of graphs, we assume that they have no loops and
every two vertices \mb{a} and \mb{b} are connected with at most one edge,
which is denoted by \mb{a-b} if it is non-directed,
and by \mb{a \to b} if it is directed from \mb{a} to \ml{b}.
\mb{G' \subseteq G} means that \mb{G'} is a subgraph of \ml{G}.
\sususec{Sets}
Any two elements of a set are \term{connected} by this set.
For any family \ml{F} of sets, \mb{Union(F)}
stands for the union of its elements.
For any family \mb{F} of sets, \mb{Graph(F)} is the non-directed
graph whose set of vertices is \mb{Union(F)} and two vertices are
connected with an edge iff they are connected by some element of \ml{F}.
Call a family \mb{F} of sets \term{connected} iff \mb{Graph(F)} is connected.
Two families \mb{F^1} and \mb{F^2} given, \mb{Graph(F^1/F^2)} is the
non-directed graph whose set of vertices is \mb{Union(F^1)} and two vertices
are connected with an edge iff they are connected by some element of
\ml{F^1 \cup F^2}. Family \mb{F^1} is called \term{\ml{F^2}-connected}
iff \mb{Graph(F^1/F^2)} is connected.
\LEMMA{
Families \mb{F^1,~F^2,~F^3} are given. Assume
\begin{ASS}
\item \mb{F^1} is \ml{(F^2 \cup F^3)}-connected, \LL{F1}
\item \mb{F^2} is \ml{F^3}-connected, and \LL{F2}
\item \ml{Union(F^1) \cap Union(F^2) \ne\empset}. \LL{FU}
\end{ASS}
Then \mb{F^1 \cup F^2} is \ml{F^3}-connected. \LL{F-F-F}
}
\proof From ~\RF{FU}\BR, there is some \ml{z \in Union(F^1) \cap Union(F^2)}.
Let us prove that all elements of \mb{Union(F^1 \cup F^2)}
are \ml{(F^1 \cup F^2 \cup F^3)}-connected by some paths with \ml{z}.
For elements of \mb{Union(F^2)} it follows from ~\RF{F2}\BR.
For elements of \mb{Union(F^1)} it follows from ~\RF{F1}\BR \qed
\sususec{Neighborhoods}
Given any directed graph \ml{G}, those vertices whence edges go to a vertex,
are called \ml{G}-\term{neighbors} or just \term{neighbors} of this vertex.
(In all notations that pertain to any graph \mb{G} we may
omit the index \mb{G} if there is no danger of confusion.)
The set of neighbors of a vertex \mb{v} is called
its \term{neighborhood} and denoted \ml{N_G(v)}.
Two different \ml{G}-neighbors of one vertex are called \term{\ml{G}-peers}.
For example, neighborhoods \mb{N(\cdot)} which we defined in Section 2
for all points in \ml{V}, are \ml{\nabla}-neighborhoods now,
where the graph \mb{\nabla} was also defined in Section 2.
Neighborhood of a set \mb{S} of vertices is the
union of neighborhoods of elements of \ml{S}.
Further, \mb{N^k(S)} is defined for every \mb{k=0,1,2,\ldots}
and every set \mb{S} by the inductive rule:
$$
N^0(S)=S, \qquad N^{k+1}(S)=N(N^k(S)),
$$
and
$$
N^\ALL(S) =\bigcup_{k=0}^\infty N^k(S), \qquad
N^+(S) =\bigcup_{k=1}^\infty N^k(S),
$$
$$
N^\END(S)=\{A \in N^\ALL(S)~:~N(A)=\empset \}.
$$
Call \mb{N^\ALL(S)} extended neighborhood of \mb{S}
and call its elements extended neighbors of \mb{S}.
\sususec{Linear Functions and Polars}
\LEMMA{
The condition (\RF{sigma=O}) is equivalent to the following:
There is such a natural \mb{\nl \leq \dim+1} and such \mb{\nl} homogeneous
linear functions \mb{L_1,\ldots,L_\nl} on \mb{R^{\dim+1}} that \LL{linear}
\FORM{
L_1 + \ldots + L_\nl \equiv 0,\HB{and} \LL{sum=0}
}
\FORM{
\HB{For all} i=1,\ldots,\nl \HB{the set} \SET{w\in N(\origin)~:~L_i(w)\geq 1}
\HB{is a veto-set.} \LL{veto-set}
}
}
\proof
First, assume that there are such homogeneous lineat functions
\mb{L_1,\ldots,L_\nl} on \mb{R^{\dim+1}}
that (\RF{sum=0}) and (\RF{veto-set}) are true.
Assume that there is some non-zero point \ml{v \in \sigma(\Delta,d)}
and come to a contradiction. For \mb{i=1,\ldots,\nn} denote
$$
S_i=\{ w \in N(\origin)~:~L_i(w) \geq 1 \}.
$$
>From (\RF{veto-set}), \ml{S_i} is a veto-set,
whence \ml{v \in ray(conv(S_i))},
which means that there is \mb{k >0} for which \ml{kv \in conv(S_i)}.
Since values of \mb{L_i} on all elements of \mb{S_i} are not less
than \ml{1}, its value on \mb{kv} also is not less than \mb{1}.
Therefore, the value of \mb{L_i} on \mb{v} is positive.
Thus, the values of all our functions \mb{L_1,\ldots,L_\nl} on
\mb{v} are positive, which contradicts (\RF{sum=0}).
Now assume that \mb{\rho} is empty and
prove existence of functions \mb{L_i} in question.
For any finite \mb{S\subset R^{\dim+1}}, the set \mb{ray(conv(S))}
can be represented as an intersection of several halfspaces.
(A halfspace is a set in \ml{R^{\dim+1}}, where some
homogeneous linear function is non-negative.)
Apply this to veto-sets, and you have several
veto-halfspaces whose intersection is \ml{ \{ \origin \} }.
(A veto-halfspace is a halfspace whose
intersection with \mb{N(\origin)} is a veto-set.)
For everyone of these veto-halfspaces we introduce a homogeneous
linear function \mb{f_i} which is non-positive on it and only on it.
We know that the origin is the only point in
\mb{R^{\dim+1}} where all $f_i$ are non-positive.
This allows us to apply Theorem 21.3 of \cite{Rockafellar}
(a variant of Helly's theorem) to the hyperplane \mb{\Pi=\{(s,t)~:~t=-1\}},
restrictions \mb{f_i|_\Pi} of our functions to it and
any non-empty closed convex set \ml{C \subseteq \Pi}. We take \ml{C=\Pi}.
Then, according to Theorem 21.3 of \cite{Rockafellar},
there exist such non-negative real numbers \ml{\lambda_i},
at most \mb{\dim+1} of which are positive, that for some \mb{\epsi>0}
$$
\forall w\in C : \sum_i \lambda_i f_i (w)\geq\epsi.
$$
Since the left part is linear and bounded from below by a
positive constant on \ml{C}, it has to be a positive constant on \ml{C}:
$$
\forall w\in C : \sum_i \lambda_i f_i (w)=\delt=\const\geq\epsi.
$$
Hence
$$
\forall w\in R^{\dim+1} : \sum_i \lambda_i f_i (w)=-\delt t.
$$
Then the functions \mb{L_i=-(t+\nn \lambda_i f_i /\delta)}
fit (\RF{sum=0}) and (\RF{veto-set}) \qed
We denote \mb{\SL=\SET{1,\ldots,\nl}} where \mb{\nl} is the number of
functions \mb{L_1,\ldots,L_\nl} and
term any map \mb{\pi : \SL \mapsto S} a \term{polar} on a set \ml{S}.
The image \mb{\pi(k)} of a number \mb{k \in \SL}
is called the \ml{k}-th pole of \ml{\pi}.
Similarly \mb{\pi(S)=\SET{\pi(i),~i \in S}} for any \ml{S \subseteq \SL}.
In particular, \mb{\pi(\SL)=Range(\pi)} is the range of \mb{\pi}.
We say that \mb{a,b \in Range(\pi)} are \term{connected} by \ml{\pi}.
\sususec{Trusses}
Let us claim two sequences of polars equivalent if one
turns into the other by some permutation, and call
the resulting classes of equivalence \term{trusses}.
We designate a truss by any sequence of its polars:
\ml{\T=(\pi_1,\ldots,\pi_k)}.
There is the empty truss which corresponds to the empty sequence of polars.
\mb{|\T|} stands for the number of polars in the truss \ml{\T}.
For any truss \mb{\T} its range \mb{Range(\T)} is
defined as the union of ranges of its polars.
For any two trusses \mb{\A} and \mb{\B} their concatenation
\mb{\A \ast \B} results from writing one sequence after the other.
\mb{\U(v)} stands for the truss that consists of one polar,
whose all poles coincide with \ml{v}.
Given a truss \mb{(\pi_1,\ldots,\pi_k)} on any set \ml{S}, we term it
\term{\ml{p}-even} or just \term{even} on a subset \mb{Q \subseteq S}
if for any \mb{i=1,\ldots,\nl} the sequence \mb{\pi_1(i),\ldots,\pi_k(i)}
has exactly \mb{p} members belonging to \ml{Q}. We term a truss on \mb{S}
\term{overall-even} on \mb{Q} if it is even on all elements of \mb{Q} and
\term{overall-even} if it is even on all elements of \mb{S}.
For any truss \mb{\T},~~~\mb{Graph(\T)} stands for the non-directed graph
whose set of vertices is \ml{Range(\T)}, two vertices being
connected iff they are connected by some polar in \ml{\T}.
Call \mb{\T} connected if \mb{Graph(\T)} is connected.
Given a truss \mb{\T} and a family \mb{F} of sets,
\mb{Graph(\T/F)} stands for the graph whose set of
vertices is \ml{Range(\T)}, and two vertices are connected
iff they are connected by some polar in \mb{\T} or
by some set which belongs to \ml{F}.
Say that \mb{\T} is \term{\ml{F}-connected}
if \mb{Graph(\T/F)} is connected.
\NOTE{
If a truss \mb{\T} is \ml{F}-connected and every element of \mb{F}
consists of one element, then \mb{\T} is connected. \LL{one}
}
A truss \mb{\T} given,
\mb{Family(\T)} stands for the family of ranges of polars in \ml{\T}.
\LEMMA{
Given trusses \mb{\T^1} and \mb{\T^2} and a family \ml{F}. Assume
\begin{ASS}
\item \mb{\T^1} is \ml{(Family(T^2) \cup F)}-connected,
\item \mb{\T^2} is \ml{F}-connected, and
\item \mb{Range(\T^1) \cap Range(\T^2) \ne\empset}.
\end{ASS}
Then \mb{\T^1 \ast \T^2} is \ml{F}-connected. \LL{T-T-F}
}
\proof It follows from Lemma \RF{F-F-F} \qed
\sususec{Polars and Trusses on Graphs}
A polar on a graph \mb{G} means a polar on the set of vertices of \ml{G}.
A polar \mb{\pi} on a graph \mb{G} is called an \term{edger} on \mb{G}
if \mb{Range(\pi)} consists of two vertices connected with an edge,
and we say that this edge corresponds to \ml{\pi}.
\LEMMA{
For any polar \mb{\pi_0} on a connected non-directed graph \ml{G},
there is a tree \mb{\gamma \subseteq G},
and a connected truss \mb{\T} on \mb{\gamma},
which consists of edgers, such that: \LL{polar-truss}
\begin{ASS}
\item the truss \mb{(\pi_0) \ast \T} is connected,\\
\item the truss \mb{(\pi_0) \ast \T} is 0-even or 1-even
on every vertex of \ml{G}, and
\item \ml{|Range((\pi_0) \ast \T)|=|Range(\T)|=|\T|+1}.
\end{ASS}
}
\proof Let \mb{\gamma} be a minimal connected subgraph of \ml{G},
whose set of vertices contains \ml{Range(\pi_0)}.
Then \mb{\gamma} is a tree and every edge of it is a bridge.
Based on this, for every edge \mb{a-b} of \mb{\gamma} let us form an edger
\mb{\pi_{a-b}} on \mb{\gamma} whose \ml{k}-th pole for all \mb{k} coincides
with \mb{a} or \ml{b}, namely with that one of the two, which needs
the edge \mb{a-b} to be connected with the \ml{k}-th pole of \ml{\pi_0}.
The truss \mb{\T} that consists of these edgers, is the one sought.
The last assertion of our lemma is true because
\mb{|\T|} equals the number of edges of \mb{\gamma},
ranges of \mb{\T} and \mb{((\pi_0) \ast \T)}
coincide with the set of vertices of \mb{\gamma} and
because in \mb{\gamma} (like in any tree)
the number of vertices is one more than the number of edges \qed
\sususec{Polars and Trusses on $V$. Arrows and Bows.}
For any polar \mb{\pi} on \ml{V}, the value
$$
L_1(\pi(1))+\ldots +L_\nl(\pi(\nl))
$$
is termed the \term{stretch} of \ml{\pi}.
\NOTE{
If a truss on \mb{V} is overall-even on \ml{V},
then the sum of stretches of its polars equals zero. \LL{zero}
}
The following two kinds of polars on \mb{V} are important for us:
A polar \mb{\alfa} on \mb{V} is called a \term{\ml{k}-arrow}
or just an \term{arrow} if \ml{Range(\alfa)=\SET{u,v}},
where \mb{u \in N_\nabla(v)}, and \ml{\alfa(k)=u}, and all the other
poles of \mb{\alfa} coincide with \ml{v}, and \ml{L_k(u)-L_k(v) \geq 1}.
Call \mb{u} the \term{head} and \mb{v} the \term{tail} of this arrow.
A polar \mb{\beta} on \mb{V} is called a \term{bow} if
\mb{Range(\beta)=\SET{u,v}} where \mb{u} and \mb{v} are \ml{\nabla}-peers.
\LEMMA{
Given an overall-even truss \ml{\A \ast \B} on \ml{V},
where \mb{\A} consists of arrows and \mb{\B} consists of bows.
Then \ml{|\A| \leq |\B| \cdot\const}. \LL{arrows-bows}
}
\proof Denote
$$
\ML=\max \{ L_i ( \Delta s_j,~\Delta t_j)~:~i=1,\ldots,\nl,~~j=1,\ldots,\nn \}.
$$
>From (\RF{sum=0}) the stretch of any bow is no more than
\mb{2 \nl \ML} by modulo, hence no less than \ml{-2 \nl \ML}.
Also from (\RF{sum=0}), the stretch of any arrow is no less than \ml{1}.
Thus, the sum of stretches of polars in our truss
(which equals zero from Note \RF{zero}), is no less than
$$
0 \geq |\A| - 2 \nl \ML \cdot |\B|,
$$
whence
$$
|\A| \leq |\B|\cdot 2 \nl \ML \qed
$$
\LEMMA{
Consider all pairs of trusses \mb{\A,~ \B} such that: \LL{Euler}
\begin{ASS}
\item \mb{\A} consists of arrows
\item \mb{\B} consists of bows
\item \mb{ \A \ast \B } is connected
\item \mb{Range(\A \ast \B)} contains a given point
\item \mb{|\A \ast \B|=k}
\end{ASS}
The number of these pairs does not exceed \ml{\const^k}.
}
\proof Introduce the non-directed graph \mb{\nabla'} with \mb{V} as
its set of vertices, in which two vertices are connected
if one is the the other's \ml{\nabla}-neighbor or they are \ml{\nabla}-peers.
The degree of any vertex of \mb{\nabla'} does nor exceed \ml{\nn^2+2\nn}.
Note that all arrows and bows are edgers on \ml{\nabla'}.
To every pair of trusses in question there corresponds a circuit on
\mb{\nabla'} which starts and ends at the given point and makes \mb{2k} steps,
every edger represented by two steps in the two
opposite directions along the corresponding edge.
At every step we must choose the edge, distribute the poles between its
two ends and decide whether the edger belongs to \mb{\A} or to \ml{\B}.
Therefore the number of trusses in question
does not exceed \mb{(2^{\nl+1}(\nn^2+2\nn))^{2k}} \qed
\susec{Description of the family $\F(\cdot)$}
Now for any given inner point \mb{v} we can
describe the family \mb{\F(v)} as follows:
A point-set \mb{S} belongs to \mb{\F(v)} if there are such trusses
\mb{\A} and \mb{\B} that the following {\bf Conditions F} are fulfilled:
{\bf Conditions F:}
\begin{LIST}{F}
\item \mb{\A} consists of arrows. \LL{arrows-F}
\item \mb{\B} consists of bows. \LL{bows-F}\\
\item The truss \mb{\A \ast \B} is overall-even. \LL{overall-even-F}\\
\item The truss \mb{\T=\U(v) \ast \A \ast \B} is connected. \LL{connected-F}
\item \mb{S} consists of those points in \mb{Range(\T)}
which are not tails of arrows in \ml{\A}. \LL{tails-F}
\item \ml{|S|=|\B|+1}. \LL{+1-F}
\end{LIST}
\LEMMA{
{\bf Conditions F} given, there is \mb{f(\theta)}
for which (\RF{f}) and (\RF{sum}) hold.\\ \LL{F-f}
}
\proof Let us evaluate the cardinalities of sets
\ml{ \F_k(v)=\{ S \in \F(v)~:~ |S|=k \} }.
\mb{|\F_0(v)|=0}, because
the empty set does not belong to \ml{\F(v)}, due to \RFBF{F}{+1-F}.
\mb{|\F_1(v)|=1} because \mb{\{v\}} is the only element of \mb{\F(v)} whose
cardinality equals 1. To prove it, assume \mb{S \in \F(v)} and \ml{|S|=1}.
Then \RFBF{F}{+1-F} \mb{\B} is empty, whence (Lemma \RF{arrows-bows})
\mb{\A} is empty also, and \ml{\T=\U(v)}, and \RFBF{F}{tails-F} \ml{S=\{v\}}.
Now evaluate \mb{|\F_k(v)|} for \ml{k \geq 2}.
>From \RFBF{F}{tails-F}, \mb{S} is uniquely determined by \mb{\A} and \ml{\B}.
Therefore \mb{|\F_k(v)|} is no more than the number of different corresponding
pairs of trusses. If \mb{S \in \F(v)} and \ml{|S|=k}, then the corresponding
trusses have (\RFBF{F}{+1-F}, then \RFBF{F}{arrows-F}, \RFBF{F}{bows-F}
and \RFBF{F}{overall-even-F} allow to apply Lemma \RF{arrows-bows})
$$
|\B|=k-1 \implies |\A| \leq\const\cdot(k-1) \implies
k-1 \leq |\A \ast \B| \leq\const\cdot (k-1).
$$
Due to \RFBF{F}{arrows-F}, \RFBF{F}{bows-F} and \RFBF{F}{connected-F} we can
apply Lemma \RF{Euler} to obtain
$$
|\F_k(v)| \leq \sum_{i=k-1}^{\const\cdot(k-1)} \const^{i} \leq\const^{k-1}.
$$
Thus,
$$
\sum \{\theta^{|S|},~~S \in \F(v)\}=
\sum_{k=0}^\infty |\F_k(v)|\cdot \theta^k \leq
\theta + \sum_{k=2}^\infty \const^{k-1}\cdot\theta^k
= \theta + O(\theta^2),
$$
which may be taken for \mb{f(\theta)} \qed
\susec{Inquest} \LL{Inquest}
Inquest\footnote{Constructions of this sort are so awful that
Janos Simon proposed to add some detective fun into them.
Imagine that it is a crime that \mb{x(\hub)>0}, and we look into its causes.}
is the central part of the proof. Its purpose is to present sets
\mb{S_1,\ldots,S_k \in \F(\hub)} which satisfy (\RF{h=1}) for any inner point
\mb{\hub} and any configuration \mb{x} such that \ml{x(\hub) \geq k}.
These sets will be obtained as
$$
S(\hub,~x,~\rub),~~~\rub=1,~\ldots,~k.
$$
Throughout Inquest, \mb{\hub,~x,~\rub} are fixed.
Call a point \mb{v} a \term{\ml{\rub}-upstart} if
$$
x(w) \geq \rub \HB{and} d(x(N_\nabla(v))) \leq \rub-1.
$$
\NOTE{
If \mb{v} is a \ml{\rub}-upstart, then \mb{x(v)=\rub}
and \mb{d(x(N_\nabla(v)))=\rub-1} and \ml{h(v)=1}. \LL{upstart}
}
\sususec{Graph $G$}
To obtain a directed graph \ml{G}, we construct inductively a sequence
of graphs \mb{G_0,~G_1,~G_2,~\ldots} and at some step we stop.
Some vertices of these graphs belong to \ml{V}, others will be newly
introduced. At every step we prove that \mb{x(\cdot) \geq \rub}
for all those vertices of \mb{G_i} which belong to \ml{V}.
{\bf Initial condition:}
We start with a graph \mb{G_0} which has one vertex \mb{\hub} and no edges.
Note that \ml{x(\hub) \geq \rub}.
{\bf When the induction process stops:}
When every vertex of \mb{G_i} either has a non-empty \ml{G_i}-neighborhood or
is a \ml{\rub}-upstart. As soon as this happens, we stop and define \ml{G=G_i}.
{\bf Induction step:}
Suppose that the graph \mb{G_i} has a vertex \mb{v} which
has no \ml{G_i}-neighbors and is not an \ml{\rub}-upstart.
Denote \mb{d(x(N_\nabla(v)))=e} and prove that \ml{e \geq \rub}.
By our assumption, \ml{x(v) \geq \rub}.
If \mb{x(v)>\rub} then \mb{e>\rub-1} whence \ml{e \geq \rub}.
If \mb{x(v)=\rub} then \mb{e \geq \rub} because
otherwise \mb{v} would be a \ml{\rub}-upstart.
Thus, we have proved that \ml{d(x(N_\nabla(v)))=e \geq \rub}.
Hence, every veto-set for \mb{v} contains
a point where \ml{x(\cdot) \geq \rub}.
Thus, from (\RF{veto-set}) for every \mb{j=1,\ldots,\nl}
there exists \mb{n_j \in N_\nabla(v)} where
\FORM{
x(n_j) \geq \rub \HB{and} L_j(n_j)-L_j(v) \geq 1. \LL{n-j}
}
Let this \mb{n_j} be chosen in some standard way,
say the first in the numeration (\RF{neighbors}) of those
which fit the conditions (\RF{n-j}).
For every \mb{j=1,\ldots,\nl} we call \mb{\tau_j=t(v)-t(n_j)-1 \geq 0}
and define a `chain'.
If \mb{\tau_j=0}, the `chain' is \mb{n_j \to v}.
Otherwise we introduce
\mb{\tau_j} intermediate vertices \mb{u_1,\ldots,u_{\tau_j}} and
\mb{\tau_j+1} intermediate edges connected in the form of a `chain':
$$
n_j \to u_1 \to u_2 \to \cdots \to u_{\tau_j} \to v.
$$
We define the time function on the newly introduced vertices by the rule
$$
t(u_k)=t(n_j)+k,~~~k=1,\ldots,\tau_j.
$$
The newly defined graph \mb{G_{i+1}} results from \mb{G_i} by
including these `chains' for all \mb{j=1,\ldots,\nl} into it.
\LIMBO{
\NOTE{
A vertex of \mb{G} is a \ml{\rub}-upstart
iff its \ml{G}-neighborhood is empty. \LL{vertex-upstart}
}
}
\sususec{Tree $T$}
Now classify the vertices of \mb{G} into equivalence classes
called \term{branches} as follows:
\BRACK{
\item If \mb{t(a)=t(b)} and \mb{N_G^\ALL(a)\cap N_G^\ALL(b)\neq\empset}
then \mb{a} and \mb{b} are equivalent.
\item Only those vertices of \mb{G} are equivalent for which
it follows from the previous rule and transitivity.
}
For any branch \mb{A} define \ml{t(A)=t(a)}, \ml{a \in A}.
Now define a directed graph \ml{T} as follows:
\BRACK{
\item The set of vertices of \mb{T} is the set of branches.
\item An edge \mb{A \to B} is present in \mb{T} iff
\ml{\exists~ a \in A,~b \in B~:~a \in N(b)}.
}
\LIMBO{
\NOTE{
If \mb{a \in N_G^{end}(\hub)} then \mb{a} is equivalent
to nothing else and forms a branch \ml{\SET{a}}. \LL{end}
}
\NOTE{
The set of branches coinsides with \mb{N_T^\ALL(\{\hub\})}.\\
For any branch \mb{A}, \ml{N_G^\ALL(A)=Union(N_T^\ALL(A))}. \LL{G=T}
}
}
\NOTE{
The point \mb{\hub} is equivalent to nothing else,
and forms a branch \ml{\SET{\hub}}.
\mb{T} is a tree in which all edges are directed
towards the vertex \ml{\SET{\hub}}. \LL{tree}
}
\sususec{Graphs $\Gamma(\cdot)$}
For any branch \mb{A} for which \mb{N_T(A)} is non-empty, define
a non-directed graph \mb{\Gamma(A)} as follows:
\BRACK{
\item The set of vertices of \mb{\Gamma(A)} is \ml{N_T(A)}.
\item Vertices \mb{B^1} and \mb{B^2} are connected with an edge
in \mb{\Gamma(A)} iff they are different and\\
\ml{\exists~~a \in A,~~~b^1 \in N_G^\ALL(B^1) \cap N_G(a),
~~~b^2 \in N_G^\ALL(B^2) \cap N_G(a)}.
}
\LEMMA{
Every \mb{\Gamma(A)} is connected. \LL{Gamma}
}
\proof Take any different vertices \mb{B^1} and \mb{B^2} of
\mb{\Gamma(A)} and prove that they are connected with a path.
By definitions,
$$
\exists~ a^1,~a^2 \in A,~~~b^1 \in B^1 \cap N_G(a^1),
~~~b^2 \in B^2 \cap N_G(a^2).
$$
If \mb{a^1=a^2} then \mb{B^1} and \mb{B^2} are connected with an edge.
Now let \ml{a^1 \neq a^2}.
Since \mb{a^1} and \mb{a^2} belong to one branch \ml{A}, they are equivalent,
which means that there is such a sequence \mb{c_0=a^1,~c_1,~\ldots,~c_l=a^2}
of different elements of \mb{A} that
$$
\forall i=1,\ldots,l~:~ N_G^\ALL(c_{i-1}) \cup
N_G^\ALL(c_{i }) \neq\empset.
$$
This means that for every \mb{i=1,\ldots,l} there are such
$$
e_{i-1} \in N_G(c_{i-1}) \HB{and}
e_{i-1}'\in N_G(c_{i })
$$
that
$$
N_G^\ALL(e_{i-1}) \cap N_G^\ALL(e_i')\neq\empset.
$$
Besides that, \ml{t(e_{i-1})=t(e_i')}.
Therefore \mb{e_{i-1}} and \mb{e_i'} are equivalent;
let \mb{E_i} stand for the branch to which they belong.
Now, every two next terms of the sequence \mb{B^1,~E_1,~\ldots,~E_l,~B^2}
either coincide or are connected with an edge \qed
\sususec{Two Trusses and a Set}
Now \mb{i} is an integer parameter which
grows from \mb{0} to some maximal value.
For every value of \mb{i} we shall form two trusses \mb{\A_i} and \mb{\B_i}
on \mb{N^\ALL(\hub)} and a set \mb{\sigma_i} of branches.
Thereby we shall also define a truss
$$
\T_i=\U(\hub) \ast \A_i \ast \B_i,
$$
a family
$$
\Sigma_i= \{ N_G^\ALL(B),~B \in \sigma_i \}
$$
and a set of branches
$$
\OK_i=N_T^\ALL({\hub}) - N_T^\ALL(\sigma_i).
$$
(On branches that belong to \mb{\OK_i} our construction is OK,
that is need no more amendment.)
We shall construct \ml{\A_i,~\B_i,~\sigma_i}, and thereby
\ml{\T_i}, \mb{\Sigma_i} and \ml{\OK_i}, inductively,
the parameter \mb{i} increasing from zero.
Along with constructing them, we shall prove by induction
that they satisfy the following {\bf Conditions I$_i$}:
{\bf Conditions I$_i$:}
\begin{LISTI}{I}
\item \mb{\A_i} consists of arrows. \LL{arrows-I}
\item \mb{\B_i} consists of bows. \LL{bows-I}
\item \mb{\T_i} is overall-even on \mb{\OK_i}. \LL{overall-even-I}
\item \mb{\T_i} is \mb{\Sigma_i}-connected. \LL{connected-I}
\item \mb{Union(\OK_i) \cap Range(\T_i)}
equals the set of tails of arrows of \ml{\A_i}. \LL{tails-I}
\item \ml{|\sigma_i| = |\Sigma_i| = |\B_i| + 1}. \LL{+1-I}
\item \mb{\T_i} is 1-even on every element of \ml{\Sigma_i}. \LL{1-even-I}
\item \mb{Range(\T_i) \subseteq N_G^\ALL(\hub)}. \LL{Range-I}\\
\item If \mb{A,B \in \Sigma_i} and \mb{A \neq B} then
\mb{A \notin N_T^\ALL(B)} and \ml{B \notin N_T^\ALL(A)}. \LL{uncomparable-I}
\end{LISTI}
{\bf The initial case \mb{i=0}:}
\mb{\A_0} and \mb{\B_0} are empty.
\mb{\sigma_0} consists of one branch \ml{\SET{\hub}}.
It is evident that all the eight properties hold in this case.
{\bf When the induction process ends:}
As soon as \ml{\forall A \in \sigma_i ~:~ N_T(A)=\empset}, we stop.
{\bf The induction step:}
Assume that \mb{\A_i,~\B_i,~\sigma_i}
(and thereby \mb{\T_i}, \mb{\Sigma_i} and \mb{\OK_i})
have been constructed and {\bf Conditions I$_i$} are proved.
Choose a branch \mb{\DOK_i \in \sigma_i}
for which \ml{N_T(\DOK_i) \neq\empset}.
The two trusses to construct are
$$
\A_{i+1}=\A_i \ast \Delta\A_i, \qquad
\B_{i+1}=\B_i \ast \Delta\B_i
$$
where it remains to define \ml{\Delta\A_i} and \ml{\Delta\B_i}.
{\bf To define \mb{\Delta\A_i} : }
If \mb{\DOK_i \cap Range(\T_i) =\empset} then \mb{\Delta\A_i} is empty also.
Now let \mb{\DOK_i \cap Range(\T_i)} be non-empty.
\refI{1-even-I} implies that for every \mb{j=1,\ldots,\nl} there is
at most one polar in \mb{\T_i} whose \ml{j}-th pole belongs to \ml{\DOK_i}.
Let \mb{S_i} be the set of those values of \mb{j} for which \mb{\DOK_i}
contains the \ml{j}-th pole of some polar in \ml{\T_i}.
Denote this pole \mb{a_j} and form a \ml{j}-arrow \mb{\pi_j}
whose head is \mb{n_j(a_j)} and whose tail is \ml{a_j}.
The truss \mb{\Delta\A_i} consists of these arrows \ml{\pi_j,~~~j \in S_i}.
\NOTE{
\ml{Range(\Delta\A_i) \subset N_G^\ALL(\DOK_i)}. \LL{Range-DA}
}
\NOTE{
Truss \mb{\T_i \ast \Delta\A_i} is overall-even on \ml{\OK_i \cup \DOK_i}.
\LL{T+DA-OK}
}
\NOTE{
Truss \mb{\T_i \ast \Delta\A_i} is 1-even on \ml{N_G^+(\DOK_i)}.
\LL{T+DA-1-even}
}
{\bf To define \mb{\Delta\B_i} : }
Note \RF{T+DA-1-even} allows us to define a polar \mb{\pi_0} on
\mb{N_T(\DOK_i)} by the following rule applied to all \mb{j=1,\ldots,\nl}:~~
\mb{\pi_0(j)} is that element of \mb{N_T(\DOK_i)} whose \mb{N_G^\ALL}
contains the \ml{j}-th pole of some polar in \ml{\T_i \ast \Delta\A_i}.
>From Lemma \RF{Gamma},~~ \mb{\Gamma(\DOK_i)} is connected.
Then Lemma \RF{polar-truss} provides us with a truss of edgers
on a tree \mb{\gamma(\DOK_i) \subseteq \Gamma(\DOK_i)}
which satisfy assertions of that lemma.
For everyone \mb{\epsi} of these edgers, we form a bow \mb{\beta} as follows.
Denote
$$
Range(\epsi)=\SET{B,B'} \subset N_T(\DOK_i).
$$
Since branches \mb{B} and \mb{B'} are connected with an edge
in \ml{\Gamma(\DOK_i)}, there are points
$$
a \in V,~~~ b \in N_G^\ALL(B ) \cap N_G(a),
~~~ b' \in N_G^\ALL(B') \cap N_G(a).
$$
Now define \mb{\beta} :
\FORM{
\forall~ j=1,\ldots,\nl~:~\beta(j)=\cases{b &if $\epsi(j)=B $,\cr
b' &if $\epsi(j)=B'$.} \LL{beta}
}
The truss \mb{\Delta\B_i} consists of these bows.
\NOTE{
\ml{Range(\Delta\B_i) \subset N_G^+(\DOK_i)}. \LL{Range-DB}
}
Denote \mb{\Delta\T_i=\Delta\A_i \ast \Delta\B_i} and \mb{\Delta\sigma_i=
\{ S \in N_T(\DOK_i)~:~N_G^\ALL(S) \cap Range(\Delta\T_i)\ne\empset\}}.
{\bf To define \mb{\sigma_{i+1}} : } it results from \mb{\sigma_i} by
excluding \mb{\DOK_i} and including all the elements of \ml{\Delta\sigma_i}.
The induction step is described.
\NOTE{
\mb{\T_{i+1} = \T_i \ast \Delta\T_i}. \LL{T=T+DT}
}
\LEMMA{
\mb{Range(\Delta\T_i) \subset N_G^\ALL(\DOK_i)}. \LL{Range-DT}
}
\proof It follows form Notes \RF{Range-DA} and \RF{Range-DB} \qed
\NOTE{
\mb{\T_{i+1}} is overall-even on \ml{\DOK_i}. \LL{T+-DOK}
}
\NOTE{
\mb{\Delta\T_i} is 1-even on \mb{N_G^\ALL(A)}
for every \ml{A \in \Delta\sigma_i}. \LL{DT-1-even}
}
\NOTE{
\mb{\Delta\T_i} is 0-even on \mb{N_G^\ALL(A)} for every
\ml{A \in N_T(\DOK_i)-\Delta\sigma_i}. \LL{DT-0-even}
}
Denote \mb{ \Delta\Sigma_i=\{ N_G^\ALL(B),~B \in \Delta\sigma_i \} }.
\LEMMA{
\mb{\Delta\T_i} is \ml{\Delta\Sigma_i}-connected. \LL{DT-connected}
}
\proof
First, prove that \mb{\Delta\B_i} is \ml{\Delta\Sigma_i}-connected.
Take any \ml{a^1,~a^2 \in Range(\Delta\B_i)}.
They belong to some branches \mb{A^1,~A^2 \in N_T(\DOK_i)}
Remember that \mb{A^1,~A^2} are vertices of the tree \mb{\gamma(\DOK_i)}.
Let \mb{E_0=A^1,~E^1,\ldots,~E_l=A^2} be the
path in this tree from \ml{A^1} to \ml{A^2}.
According to (\RF{beta}), every next terms \mb{E_{j-1}} and \mb{E_j} in
this sequence are connected with an edger \mb{\epsi_j} to which
there corresponds a bow \mb{\beta_j} which connects
the point \mb{b_j} with the point \ml{b'_j}.
Thus, in the sequence \mb{b_1,~b'_1,\ldots,b_l,~b'_l} every two
next terms are connected either with a bow or with a set.
The statement of the lemma follows from the proven one and the fact
that every arrow in \mb{\Delta\A_i} connects its tail with head,
and has a head in \ml{Range(\Delta\B_i)}. \qed
\NOTE{
\mb{Range(\T_i) \cap Range(\Delta\T_i) \ne\empset}. \LL{T-DT}
}
\NOTE{
\mb{\Delta\Sigma_i \subseteq \Sigma_{i+1}}. \LL{DSigma}
}
\LEMMA{
\mb{\Delta\T_i} is \ml{\Sigma_{i+1}}-connected. \LL{DT-S}
}
\proof It follows from Lemma \RF{DT-connected} and Note \RF{DSigma} \qed
\LEMMA{
\mb{\T_i} is \ml{(Family(\Delta\T_i) \cup \Sigma_{i+1})}-connected.
\LL{T-connected}
}
\proof From \refI{connected-I}, \mb{\T_i} is \ml{\Sigma_i}-connected.
Note that all the branches of \mb{\Sigma_i} belong to
\mb{\Sigma_{i+1}} also, with the only exception of \ml{\DOK_i}.
Thus, the only chance of our lemma's statement to be false
is where connection was provided by \ml{\DOK_i}.
But all the elements of \mb{Range(\T_i) \cap \DOK_i}
are tails of arrows in \ml{\Delta\A_i}, all of which are
\mb{\Sigma_{i+1}}-connected together from Lemma \RF{DT-S} \qed
Now let us prove {\bf Conditions I$_{i+1}$}.
%==========================================================
Proofs of \refIplus{arrows-I} and \refIplus{bows-I} are evident.
%::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Proof of \refIplus{overall-even-I}:
Note that \mb{\OK_{i+1}} consists of \mb{\OK_i}, \mb{\DOK_i} and
extended \ml{G}-neighborhoods of those \ml{T}-neighbors of \mb{\DOK_i}
where there are no poles of our polars at all (Note \RF{DT-0-even}).
Hence our statement follows from \refI{overall-even-I}
and Notes \RF{T+DA-OK}, \RF{Range-DT} and \RF{T+-DOK} \qed
%::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Proof of \refIplus{connected-I}: It follows from
Notes \RF{T=T+DT} and \RF{T-DT} and Lemmas \RF{T-T-F} and \RF{T-connected} \qed
%::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Proof of \refIplus{tails-I}:
The set of tails of arrows in \mb{\Delta\A_i} coincides
with \mb{Range(\T_i) \cap \DOK_i} \qed
%:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Proof of \refIplus{+1-I}: This is because
$$
|\sigma_{i+1}|-|\sigma_i|=|\B_{i+1}|-|\B_i|.
$$
Let us prove it.
The right part equals the number of bows (\RF{beta}).
The left part is one less than the number of those branches
in \mb{N_T(\DOK_i)} whose \mb{N_G^\ALL} intersects \ml{Range(\T_{i+1})}.
The number of these branches (see definition of \mb{\Delta\B_i})
equals range of the truss provided by Lemma \RF{polar-truss} which is
one more than the number of bows, from the last statement of that lemma \qed
%:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Proof of \refIplus{1-even-I}:
Take any \mb{A \in \sigma_i} and prove that
\mb{\T_i} is 1-even on \ml{N_G^\ALL(A)}.
If \ml{A \notin N_T(\DOK_i)}, this just follows from \refI{1-even-I},
because in this case \ml{A \in \sigma_i}.
If \mb{A \in N_T(\DOK_i)} then all the poles of \mb{\T_{i+1}}
in \mb{N_G^\ALL(A)} are those of \ml{\Delta\T_i}.
According to its construction (see Notes \RF{DT-1-even} and \RF{DT-0-even}),
\mb{\Delta\T_i} is 0-even or 1-even
on \mb{N_G^\ALL(A)} for every \ml{A \in N_T(\DOK_i)},
but only the latter are included into \mb{\sigma_{i+1}} \qed
%::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Proof of \refIplus{Range-I} is evident.
%:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Proof of \refIplus{uncomparable-I}:
Take any two different branches \mb{A} and \mb{B} in \mb{\sigma_{i+1}} and
prove that each of them does not belong to \mb{N_T^\ALL} of the other.
Consider three cases:
\begin{ASSERT}
\item \ml{A,~B \in \Sigma_i}.
In this case our statement follows from \refI{uncomparable-I}.
\item \ml{A,~B \in N_T(\DOK_i)}.
In this case \mb{t(A)=t(B)} which makes it impossible for
one of them to belong to \mb{N_T^\ALL} of the other.
\item \mb{A \in \Sigma_i} and \ml{B \in N_T(\DOK_i)}.
If \mb{A \in N_T^\ALL(B)} then \mb{A \in N_T^\ALL(\DOK_i)}
which contradicts \refI{uncomparable-I}.
If \mb{B \in N_T^\ALL(A)} then
\mb{N_T^\ALL(A) \cap N_T^\ALL(\DOK_i) \neq \empset}
which contradicts Note \RF{tree} \qed
\end{ASSERT}
%======================================================================
\sususec{Result of Induction}
The induction process certainly will have an end,
because \mb{|\OK_i|} increases at every step.
When it is over, we obtain the trusses
\mb{\A_{i}} and \mb{\B_{i}}
and the set \mb{\Sigma_{i}}
for which {\bf Conditions I$_i$} are true
and such that every element of \mb{\sigma_i} has empty \ml{T}-neighborhood.
Then we denote \ml{\A=\A_i,~~\B=\B_i,~~\sigma=\sigma_i}.
\LIMBO{
\NOTE{
\ml{Range(\T) \subseteq N_G^\ALL(\hub)}. \LL{Range-T}
}
}
\NOTE{
\mb{N_T(A)=\empset} for every \ml{A \in \sigma}. \LL{empty-T}
}
\NOTE{
Every element of \mb{\sigma} consists of one point. \LL{in-Sigma}
}
Note \RF{in-Sigma} allows us to introduce a point-set
\ml{S=\{v~:~\{v\}\in \sigma\}}.
\NOTE{
\ml{|S|=|\sigma|}. \LL{S=Sigma}
}
\NOTE{
\ml{S \subseteq N_G^\END(\hub) \subseteq N_G^\ALL(\hub)}. \LL{S-belongs}
}
\NOTE{
All the elements of \mb{S} are \ml{\rub}-upstarts. \LL{S-upstarts}
}
Now let us prove {\bf Conditions F} for \mb{\A,~\B} and \mb{S} thus obtained.
\RFBF{F}{arrows-F} follows from \refI{arrows-I}.
\RFBF{F}{bows-F} follows from \refI{bows-I}.
Proof of \RFBF{F}{overall-even-F}:
Outside \mb{S} our truss is overall-even from \refI{overall-even-I}.
On every element of \mb{S} our truss is 1-even from \refI{1-even-I}
and Notes \RF{empty-T} and \RF{in-Sigma} \qed
Proof of \RFBF{F}{connected-F}: this follows from \refI{connected-I} and
Notes \RF{one} and \RF{in-Sigma} \qed
Proof of \RFBF{F}{tails-F}: It is evident that \ml{S \subset Range(\T)}.
Elements of \mb{S} can not be tails of arrows of \mb{\A}
because \ml{N_G(S)=\empset}.
It remains to prove that all the other points
in \mb{N_G^\ALL(\hub)} are some arrows' tails.
This follows from \refI{tails-I} and definitions of \mb{\OK_i} and \ml{S} \qed
Proof of \RFBF{F}{+1-F}:
This follows from \refI{+1-I} and Note \RF{S=Sigma} \qed
\susec{Final}
Now only the point \mb{\hub} and the number \mb{k} remain fixed.
For each \mb{x \in X} such that \mb{x(hub) \geq k} and each
\mb{\rub=1,\ldots,k} we have constructed
trusses \mb{\A} and \mb{\B} and a set \ml{S}.
Now we can specify the \mb{k} disjoint sets
\mb{S_1,\ldots,S_k} mentioned in SEction 4.1:
these are the sets \mb{S} resulting from our construction
with \ml{\rub=1,\ldots,k}.
\LEMMA{
Given \mb{\hub} and \mb{k}, the sets \mb{S_1,\ldots,S_k} are disjoint.
\LL{disjoint}
}
\proof This follows from Notes \RF{upstart} and \RF{S-upstarts} \qed
Thus Theorem \RF{bounded-inf-T} is proved \qed
\sec{Proof of Theorem 3}
\susec{Outline}
Proof of Theorem 3 is similar to and based on the proof of Theorem 2.
In this case we construct for every point \mb{v}
two finite families \mb{\F'(v)} and \mb{\F''(v)} of
point-sets which have the following three properties:
\FORM{
\cases{
&If \mb{x(v) \geq k>0}, there are \mb{k} disjoint point-sets
\mb{S_1,\ldots,S_k \in \F'(v) \cup \F''(v)} \cr
&such that \mb{h_w=1} for all \mb{w \in S_1 \cup\ldots\cup S_k}.}
\LL{S-F+F}
}
\FORM{
\sum\{ \theta^{|S|},~S \in \F'(v) \} \leq f'(\theta)=\theta +O(\theta^2)
\LL{S-in-F'}
}
\FORM{
\sum\{ \theta^{|S|},~S \in \F''(v) \} \leq f''(\theta,v,\size) =
\const\cdot t(v) \cdot (\const\cdot\theta)^{\const\cdot\size}. \LL{S-in-F''}
}
\LEMMA{
Given \mb{\F'(v)} and \mb{\F''(v)} which satisfy
(\RF{S-F+F}), (\RF{S-in-F'}) and (\RF{S-in-F''}).
Then Theorem 3 holds. \LL{Theorem-3}
}
\proof We can choose \mb{C=\const} so that while \mb{t(v) < C^\size},
the right part of (\RF{S-in-F''}) is still less than
\mb{\const\cdot (\const\cdot \theta)^{\const\cdot\size}}.
Then we can choose such \mb{\size_0} that for all
\mb{\size \geq \size_0} this expression is \mb{O(\theta^2)},
and therefore \mb{f''(\cdot) \leq O(\theta^2)}. Thus,
$$
\sum\{\theta^{|S|},~S \in \F'(v) \cup \F''(v) \}\leq\theta+O(\theta^2) \qed
$$
\susec{Norm, Distance, Diameter and Span}
Choose any norm \mb{\norm(v)} in \mb{\R^{\dim+1}}, define distance
\mb{\dist(v,w)=\norm(v-w)}, let distance between two finite sets
\mb{\dist(S_1,S_2)} stand for the minimal distance between points of
\mb{S_1} and points of \ml{S_2}, and let \mb{\diam(S)} stand for
the diameter of \ml{S}, that is the maximal distance between its points.
\NOTE{
If a connected truss \mb{\T} consists of arrows and bows, then
$$
\diam(Range(\T)) \leq\const\cdot |\T|. \LL{connected-diam}
$$
}
\NOTE{
\mb{\diam(S_1 \cup S_2) \leq \diam(S_1)+\diam(S_2)+\dist(S_1,S_2)}. \LL{2-diam}
}
\LIMBO{
\LEMMA{
If a family \mb{\Sigma} of point-sets is connected, then \LL{family-diam}
$$
\diam(Union(\Sigma)) \leq \sum \{ \diam(S),~S \in \Sigma \}.
$$
}
\proof By induction, based on Note \RF{2-diam} \qed
}
Denote
$$
\lambda=\max\{\norm(\Delta s_i, \Delta t_i),~i=1,\ldots,\nn\},
\qquad \span(S)=\diam(S)+\lambda.
$$
\LIMBO{
\LEMMA{ \LL{S-span}
$$
\forall~\hub,~x,~\rub~:~|S(\hub,~x,~\rub)| \geq
\const\cdot \span(Range(\T(\hub,~x,~\rub))).
$$
}
\proof From Note \RF{connected-diam}, Lemma \RF{arrows-bows},
\refI{+1-I} and Note \RF{S=Sigma}:
\begin{eqnarray*}
\lefteqn{\span(Range(\T(\cdot)))=}\\
&&\diam(Range(\T(\cdot))) + \lambda
= \diam(Range(\A(\cdot) \ast \B(\cdot))) + \lambda \\
&&\prec |\A(\cdot)| + |\B(\cdot)| + 1 \prec |\B(\cdot)| + 1
=|\sigma(\cdot)|=|S(\cdot)| \qed
\end{eqnarray*}
}
Call two point-sets \ml{\lambda}-close if the distance
between them does not exceed \ml{\lambda}.
Call a family of point-sets \term{\ml{\lambda}-connected}
if it is possible to go from any its element to any other,
every step made between \ml{\lambda}-close sets.
\LEMMA{
If a family \mb{\Sigma} of point-sets is \ml{\lambda}-connected,
then \LL{connected-span}
$$
\span(Union(\Sigma)) \leq \sum \{ \span(S),~S \in \Sigma \}.
$$
}
\proof By induction, based on Note \RF{2-diam} \qed
\LEMMA{
For any \ml{v \in V}, \LL{span-neighbors}
$$
\span(N_G^\ALL(v)) \leq \sum \{ \span(N_G^\ALL(w)),~w \in N_G(v) \}+\lambda.
$$
}
\proof This follows from Lemma \RF{connected-span} \qed
\susec{Infinite Representation of The Finite Case}
We are considering a process \mb{P_\size} on
a finite volume \mb{V_\size=\Z_\size^{\dim} \cdot Time}.
Let us call elements of the finite volume \ml{\size}-points.
Let \mb{V_\infty=\Z_\infty^{\dim} \cdot Time}
stand for the corresponding infinite volume
whose elements are called \ml{\infty}-points now.
The map \mb{\fin~:~V_\infty \mapsto V_\size} is defined as follows:
\mb{\fin(s,t)=(s',t)} where components of \mb{s'}
are residues of components of \mb{s} modulo \ml{\size}.
The opposite map \mb{\inf~:~V_\size \mapsto V_\infty} is defined by
$$
\forall~(s,t) \in V_\size~:~\inf(s,t)=(s,t) \in V_\infty.
$$
Call elements of \mb{X_0^{V_\infty}}~~ \ml{\infty}-configurations.
To every \ml{\size}-configuration \mb{x} there corresponds
a periodical \ml{\infty}-configuration \ml{y=\INF(x)}
defined by the rule
$$
\forall~v \in V_\infty~:~y(v)=x(\fin(v)).
$$
We shall use the auxiliary infinite process \mb{P'_\infty} on \mb{V_\infty}
induced by the finite hidden measure \mb{\eta_\size} with the map
\mb{D'~:~H_\size \mapsto X_\infty} defined as follows:
$$
x(v)=\cases{0 &if \mb{t(v)<0},\cr
d(x(N(v)))+h(\fin(v)) &if \mb{t(v) \geq 0}.}
$$
\NOTE{
\mb{\forall~v \in V_\infty~:~P'_\infty|_v \equiv P_\size|_{\fin(v)}}.
\LL{inf=fin}
}
Say that a set \mb{S \subset V_\infty} \term{overlaps}
if \mb{\exists~v,v' \in S~:~\fin(v)=\fin(v')}.
\NOTE{
If \mb{S \subset V_\infty} does not overlap, then \ml{|\fin(S)|=|S|}.
\LL{not-overlap}
}
\NOTE{
If \mb{S \subset V_\infty} overlaps, then \ml{\diam(S) \geq \size}.
\LL{overlap-diam}
}
\susec{Description of the families $\F'(\cdot)$ and $\F''(\cdot)$}
{\bf To define \mb{\F'(v)}:} A point-set \mb{S \subset V_\size}
belongs to \mb{\F'(v)} if it is representable as \mb{S=\fin(S_\infty)}
where \mb{S_\infty} is such a subset of \mb{V_\infty} for which
there are such trusses \mb{\A} and \mb{\B} on \mb{V_\infty},
that the following {\bf Conditions F'} hold:
{\bf Conditions F':}
\begin{LIST}{F'}
\item \mb{\A} consists of arrows. \LL{arrows-F'}
\item \mb{\B} consists of bows. \LL{bows-F'}\\
\item The truss \mb{\A \ast \B} is overall-even. \LL{overall-even-F'}\\
\item The truss \mb{\T=\U(\inf(v)) \ast \A \ast \B} is connected.
\LL{connected-F'}
\item \mb{S_\infty} consists of those points in \mb{Range(\T)}
which are not tails of arrows in \ml{\A}. \LL{tails-F'}
\item \ml{|S_\infty|=|\B|+1}. \LL{+1-F'}
\item \mb{S_\infty} does not overlap. \LL{not-overlap-F'}
\end{LIST}
\LEMMA{
Family \mb{\F'(v)} satisfies (\RF{S-in-F'}). \LL{F'-f}
}
\proof is the same as in the infinite case (see Lemma \RF{F-f})\qed
{\bf To define \mb{\F''(v)}:} A point-set \mb{S \subset V_\size}
belongs to \mb{\F''(v)} if it is representable as \mb{S=\fin(S_\infty)}
where \mb{S_\infty} is such a subset of \mb{V_\infty} for which
there are such trusses \mb{\A} and \mb{\B} on \mb{V_\infty},
and such a point \mb{w \in V_\infty}
that the following {\bf Conditions F''} hold:
{\bf Conditions F'':}
\begin{LIST}{F''}
\item \mb{\A} consists of arrows. \LL{arrows-F''}
\item \mb{\B} consists of bows. \LL{bows-F''}\\
\item The truss \mb{\A \ast \B} is overall-even. \LL{overall-even-F''}\\
\item The truss \mb{\T=\U(w) \ast \A \ast \B} is connected
and \ml{t(w)0}
and a number \ml{\rub \in [1,~k]}, we make for them Inquest
described in Section \RF{Inquest} and obtain the triple \ml{(\A,~\B,~S)}.
Let \mb{S_\infty(v,x,\rub)} stand for the last term \mb{S} of this triple.
\LEMMA{
If \mb{S_\infty(v,x,\rub)} overlaps, then there exists such
a point \mb{\ersatz(v)} that
\BRACKET{
\item \mb{\ersatz(v) \in N_G^+(v)},
\item \mb{S_\infty(\ersatz(v),x,\rub)} does not overlap, and \LL{ersatz}
\item \mb{\span(Range(\T(\ersatz(v),~x,~\rub))) \geq (\size-\lambda) / \nn}.
}
}
\proof
Take the set of those points \mb{w \in N_G^\ALL(v)} for which
\mb{S_\infty(w,x,\rub)} overlaps, take a point in this set whose
time is the smallest, and call this point \ml{\lowest}.
Let us prove by contradiction that among \ml{G}-neighbors of \mb{\lowest}
there is at least one which fits (\RF{ersatz}). Assume that
$$
\forall~w \in N_G(\lowest)~:~\span(Range(\T(w))) < (\size-\lambda) / \nn.
$$
Then from Note \RF{S-belongs} and Lemma \RF{span-neighbors},
$$
\span(S_\infty(\lowest,x,\rub)) \leq \span (N_G^\ALL(\lowest)) < \size
$$
which contradicts Note \RF{overlap-diam} \qed
Now we can present a set \mb{S_\size \in \F(\hub) \cup \F''(\hub)}
for any \ml{\size}-point \ml{\hub}, \ml{\size}-configuration \mb{x}
and \mb{\rub \in [1,~k]}, where \ml{k \in [1,x(\hub)]}:
\FORM{
S_\size(\hub,~x,~\rub)=\fin(S_\infty(\inf(\hub),\INF(x),\rub)),
\LL{S-fin-dsnt}
}
if \mb{S_\infty(\inf(\hub),\INF(x),\rub)} does not overlap, and
\FORM{
S_\size(\hub,~x,~\rub)=\fin(S_\infty(\ersatz(\inf(\hub)),~\INF(x),~\rub)),
\LL{S-fin-does}
}
if \mb{S_\infty(\inf(\hub),\INF(x),\rub)} overlaps.
\LEMMA{
Every \mb{S_\size(\cdot)} defined by (\RF{S-fin-dsnt})
belongs to \mb{\F'(\hub)} and
every \mb{S_\size(\cdot)} defined by (\RF{S-fin-does})
belongs to \ml{\F''(\hub)}. \LL{S-in-F+F}
}
\proof The first assertion can be proved just as in the infinite case.
Let us prove the second. All {\bf Conditions F''} but the
last one were proved when treating of the infinite case.
The last condition follows from (\RF{ersatz}) \qed
LEMMA{
Sets \mb{S_\size(\hub,~x,~\rub),~~~\rub=1,\ldots,k} are disjoint.
\LL{fin-disjoint}
}
\proof is the same as in the infinite case \qed
Thus Theorem \RF{bounded-fin-T} is proved \qed
\sec{Proof of Theorem 4}
\susec{Preliminaries}
For any \mb{c \in \R^{\dim+1}} and \mb{A,B \subset \R^{\dim+1}} denote
$$
A+c=\{ a+c~:~a \in A \},~~~A+B=\{ a+b~:~a \in A,~~b \in B \}.
$$
Say that a set \mb{A \subset \R^{\dim+1}} is \term{obtuse}
for a set \mb{B \subset \R^{\dim+1}} if
$$
\forall~c \in \R^{\dim+1}~:~
(A+c) \cap B =\empset \implies (A+c) \cap conv(B) =\empset.
$$
\NOTE{
Given any sets \mb{A,B,C \subset \R^{\dim+1}} and any vectors
\mb{a,~b \in \R^{\dim+1}}. If \mb{A} is obtuse for \mb{B},
then \mb{A+C+a} is obtuse for \mb{B+b}. \LL{+obtuse}
}
\LEMMA{
For any \mb{A \subset \R^{\dim+1}} the set \mb{-k \cdot conv(A)} is obtuse
for \ml{A} provided \ml{k \geq \dim+1}. \LL{-obtuse}
}
\proof
Let it be proved for the case when \mb{A} is the set of vertices of a simplex.
The general proof is based on this and Carath\'{e}odory's theorem \qed
\LEMMA{
For any finite family of bounded sets there is a bounded set which is obtuse
for all of them and contains a sphere of any given radius. \LL{family-obtuse}
}
\proof It follows from Note \RF{+obtuse} and Lemma \RF{-obtuse} \qed
\susec{Tower}
\NOTE{
Every minimax function can be presented as a minimum of several terms,
everyone of which is a maximum of several arguments. \LL{normal-form}
}
Assume that our function \mb{d} is presented in the form described
in Note \RF{normal-form} and call \term{term-set} (of \ml{\origin}) the set
of neighbor vectors corresponding to arguments which enter one term.
Term-sets of any point \mb{v} are term-sets
of \mb{\origin} shifted by \ml{\origin}.
Call a set \mb{S \subset V} \term{self-sufficient}
if for any non-initial \mb{v \in S} every term-set of \mb{v} intersects \ml{S}.
\LEMMA{
There is such a self-sufficient set \ml{Tower}, that \LL{self-sufficient}
\FORM{
\forall~t~:~1 \leq | \{ v \in Tower \cap \Z^{\dim+1}~:~t(v)=t \} | \leq\const.
\LL{self-const}
}
}
\proof Take any ray \mb{\rho \subseteq \sigma(\Delta,d)}.
Take any large enough bounded set \mb{P} which is obtuse for all term-sets
(which exists from Lemma \RF{family-obtuse}), and so shifted
that all its points have time coordinate less than \ml{-\mem}.
Define \mb{Tower= P - \rho} and prove that it fits the claim.
The condition (\RF{self-const}) is evidently fulfilled.
It remains to prove that \mb{Tower} is self-sufficient.
Take any inner point \mb{v \in Tower} and any term-set \mb{T}.
Since \mb{\rho \subseteq \sigma}, \mb{\rho \subseteq ray(conv(T))}.
Thus, there is a point \mb{p \in conv(T) \cap \rho}. Thus,
$$
v+p \in conv(v+T) \cap (v+\rho).
$$
Since \mb{v \in Tower} and \mb{v+p \in \rho +p}, then \mb{v+p \in Tower}.
Thus, \mb{Tower} intersects \mb{conv(v+T)}.
Thus (Note \RF{+obtuse}), since \mb{Tower} is obtuse for \mb{v+T},
\mb{Tower} intersects \mb{v+T} \qed
\NOTE{
If a point-set \mb{Tower} satisfies (\RF{self-const}), then
$$
\forall~v \in V~~~\exists~s \in Space~:~ v \in Tower+s \LL{any-in-S}
$$
}
\susec{Final}
Take any self-sufficient set \mb{Tower} which satisfies (\RF{self-const})
and separate it into parts by the rule:
$$
Floor_i=\{ v \in Tower~:~m (i-1) \leq t(v) < m i \}.
$$
\NOTE{
\mb{\forall~i~:~1 \leq |Floor_i| \leq C=\const}. \LL{Floor-const}
}
\NOTE{
For any \mb{i \geq 1} and any \mb{v \in Floor_i} every term-set of \mb{v}
intersects \ml{Floor_{i-1}}. \LL{intersects}
}
\LEMMA{
\mb{\forall v \in V~:~\EX_\theta(v) \geq \theta^C \cdot t(v)/m},
where \mb{C} is that of Note \RF{Floor-const}. \LL{Theorem-4}
}
\proof First we prove that
$$
\forall~v \in Floor_i~:~E_\theta(\min\{x(v)~:~v \in Floor_i\})
\geq \theta^C \cdot i.
$$
This is because
\begin{eqnarray*}
\lefteqn{\min\{x(v),~v \in Floor_{i+1}\}=}\\
&&\min\{d(x(N(v)))+h(v),~v \in Floor_{i+1} \} \geq \\
&&\min\{d(x(N(v))),~v\in Floor_{i+1}\}+\min\{ h(v),~v \in Floor_{i+1} \}\geq\\
&&\min \{ x(v),~v \in Floor_i \} +\min\{ h(v),~v \in Floor_{i+1} \}.
\end{eqnarray*}
(Expectation of the last term is no less than \ml{\theta^C}.)
Assertion of the lemma follows from this and Note \RF{any-in-S} \qed
Theorem 4 follows from Lemma \RF{Theorem-4} \qed
\sec{Proof of Theorem 5}
Let \mb{d=\median}.
First, assume that a ray \mb{\rho} in question exists. Then
\mb{\sigma(\Delta,d) \supseteq \rho} which proves Theorem 5 in one direction.
Now to prove Theorem 5 in the other direction by contradiction:
If it is wrong, we can rotate \mb{\Pi} at a small angle
so that its new position will violate the following lemma:
\LEMMA{
Let a ray \mb{\alfa} belong to \ml{\sigma}.
Let hyperplane \mb{\Pi} contain \ml{\alfa}.
Assume that all the neighbor vectors that do not belong to \mb{\alfa},
do not belong to \mb{\Pi} also.
Then the number of neighbor vectors that belong to \mb{\alfa},
is greater than the difference between
the number of neighbor vectors on one side of \mb{\Pi} and
the number of neighbor vectors on the other side of \mb{\Pi}. \LL{plane-L}
}
\proof Assume otherwise. Then there is another hyperplane,
close to \mb{\Pi}, such that \mb{\rho} is on one side of \mb{\Pi}
and the majority of neighbor vectors is on the other side of \ml{\Pi},
which makes a contradiction \qed
\begin{thebibliography}{10}
\bibitem{BG-85} Charles H. Bennett and G. Grinstein.
Role of Irreversibility in Stabilizing Complex and Nonergodic Behavior
in Locally Interacting Discrete Systems. {\it Phys. Rev. Letters},
v. 55 (1985), n. 7, pp. 657-660.
\bibitem{Berman-Simon} Piotr Berman and Janos Simon.
Investigations of Fault-Tolerant Networks of Computers
(preliminary version), 1988.
\bibitem{Bramson-Gray} Maury Bramson and Lawrence Gray.
A Useful Renormalization Argument. (Preprint.)
\bibitem{LMS} Joel L. Lebowitz, Christian Maes and Eugene R. Speer.
Statistical Mechanics of Probabilistic Cellular Automata. (Preprint.)
\bibitem{Pippenger} Nicholas Pippenger.
Symmetry and Self-Repair (Extended Abstract).
\bibitem{Rockafellar} R. T. Rockafellar. Convex Analysis.
Princeton Univ. Press, 1970.
\bibitem{Toom-80} Andrei Toom.
Stable and Attractive Trajectories in Multicomponent Systems.
{\it Multicomponent Random Systems, (R.L.Dobrushin, Ya.G.Sinai, Eds.)}
Advances in Probability and Related Topics, V. 6 (1980), Dekker, pp. 549-575.
\bibitem{Toom-82} Andrei Toom. [Estimations for measures that describe
the behavior of random systems with local interaction.
{\it Interactive Markov Processes and their Application to the
Mathematical Modelling of Biological Systems}].
Pushchino, 1982, pp. 21-33 (in Russian).
\bibitem{Discrete-90}
A. Toom, N. Vasilyev, O. Stavskaya, L. Mityushin, G. Kurdyumov and S. Pirogov.
Discrete Local Markov Systems.
{\it Stochastic Cellular Systems : ergodicity, memory, morphogenesis}.
Ed. by R. Dobrushin, V. Kryukov and A. Toom.
Nonlinear Science: theory and applications,
Manchester University Press, 1990.
\bibitem{VPP}
N. B. Vasilyev, M. B. Petrovskaya and I. I. Piatetski-Shapiro.
Simulation of Voting with Random Errors.
{\it Automatica i Telemekhanika}, V. 10 (1969), pp. 103-107 (in Russian).
\end{thebibliography}
\end{document}