.PH ""
.nr Pt 1
.EQ
delim $$
gsize 12
define aA % {x sub i} %
define bB % {x sub j} %
define cC % {J sub i} %
define dD % {c sub 1} %
define eE % {c sub 2} %
define fF % {c sub 3} %
define gG % {c sub 4} %
.EN
.am DE
.sp
..
.ds HP 12 12 12 12 12 12 12
.ds HF 3 3 3 3 3 3 3
.ls 1
.ce 99
.S 12
.B
On the periods of some graph transformations
.R
.sp
.I
A. M. Odlyzko
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, NJ 07974
.sp
.I
D. J. Randall
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, NJ 07974
.sp
and
.sp
Harvard University
Boston, MA 02139
.sp 2
.B
ABSTRACT
.R
.ce 0
.sp 1.5
.P
.ls 2
For any undirected graph with arbitrary integer values
attached to the vertices, simultaneous updates are performed
on these values, in which the value of a vertex is moved by 1
in the direction of the average of the values of the neighboring
vertices.
(A special rule applies when equality occurs.)
It is shown these transformations always reach a cycle of length
1 or 2.
.bp
.ls 1
.ce 99
.B
On the periods of some graph transformations
.R
.sp
.I
A. M. Odlyzko
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, NJ 07974
.sp
.I
D. J. Randall
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, NJ 07974
.sp
and
.sp
Harvard University
Boston, MA 02139
.ce 0
.sp
.H 1 "Introduction"
.ls 2
.P
Let $G$ be an undirected graph with vertices labelled $1 ^,...,^ n$, and
suppose that for each $i$, an integer $x ~(0)$ is initially assigned
to vertex $i$.
We perform a sequence of synchronous updates on these values.
If $x~(t)$ is the value of vertex $i$ at time $t$, then:
.DS 3
.EQ
aA ^(t+1) ~=~ left {
matrix {
lcol {aA ^(t) ~-~ 1 above aA ^(t) above aA ^(t) ~+~ 1}
lcol {roman if above roman if above roman if}
lcol {sum from {j ^epsilon^ cC} ~bB^(t) ~<~ d sub i ^aA ^(t), above bB ^(t) ~=~ aA^(t) {roman {f o r~a l l}}~ j ~epsilon~ cC ,
above sum from {j ^epsilon^ cC} ~bB^(t) ~>=~ d sub i ^aA^(t) ~roman and above {roman {f o r~some}}~j ~epsilon~ cC , ~bB^(t) ~!=~ aA^(t),}
}
.EN
.DE
where
.DS
.TS
center;
c1 c1 l.
.ls 1
$J$	$=$	$"{" j:$ vertex $j$ is connected to vertex $i "}"$,
.sp
$d$	$=$	$| cC | ~=$ degree of vertex $i$.
.TE
.DE
.pn 2
.PH "''- \\\\nP -''"
Less formally, the value $aA ^(t)$ assigned to vertex $i$ moves by
1 in the direction of the average of the values assigned to the neighbors
of vertex $i$, but a special rule applies when $aA ^(t)$ equals
this average.
Since $max from i ~aA ^(t)$ does not increase and $min from i ~aA ^(t)$
does not decrease as $t$ varies, the iteration described above eventually
reaches a cycle, so that for some minimal $p ~>~ 1, ~aA ^(t+p) ~=~ aA ^(t)$
for all $i$ and all $t ~>~ t sub 0$.
Our main result is that the length of the cycle is 1 or 2.
.sp
.I
Theorem:\0\0For any undirected graph $G$ and any initial assignment
of integers $x sub 1 ^(0) ^,...,^ x sub n ^(0)$ to the vertices of $G$,
there is a $t sub 0$ such that the above iteration satisfies
$aA ^(t+2) ~=~ aA ^(t)$ for all $i$ and all $t ~>~ t sub 0$.
.R
.P
The problem of determining the cycle length of the above iteration
arose in the work of D. Ghiglia and G. Mastin [1].
They considered such iterations for the cases of $G$ being (a) a simple
path (i.e., vertex $i$ being connected to vertex $j$ if and only if
$| i-j | ~=~ 1$) and (b) a $k$ by $m$ rectangular grid of lattice
points, with edges between points that are horizontal or vertical neighbors.
The rules described above were constructed as part of an algorithm
for ``phase unwrapping''; i.e., determining the argument of a complex
function given the principal value of the argument, so on to eliminate
the discontinuation by integer multiples of $2^ pi$.
.P
The ``phase unwrapping'' origin of the transformation accounts for the
irregularity in the rules prescribing that if the average of the values
of a sites neighbors equals the value at that site, but not all the
neighbors are equal to the site, then the value of the site should
be incremented by 1.
As it turns out, even if this condition is relaxed, the length of
the cycle is still at most 2.
The proof of this is similar to that of our theorem.
.P
Ghighlia and Mastin found by extensive simulations that iterations
of the transformation always led to cycles of length 1 or 2.
They conjectured that this is always the case, and their ``phase unwrapping''
algorithm is based on the assumption that this conjecture is true.
Our theorem, which proves this conjecture, guarantees that the Ghighlia-Mastin
algorithm will always terminate.
.P
E. Brickell and M. Purtill were the first to consider the general
transformation as we defined it above.
When all the $aA ^(0)$ are 0 or 1, they showed (unpublished) assigned
a value of by a very elegant combinatorial argument that the cycle
length is at most two.
At any time $t$, divide the vertices of $G$ into four classes as follows:
.DS
.TS
center;
c1 c1 l.
.ls 1
$dD$	$=$	$"{" i: ~aA ^(t) ~=~ 0$ and $bB ^(t) ~=~ 0$ for all $j ~epsilon~ cC "}"$,
.sp
$eE$	$=$	$"{" i: ~aA ^(t) ~=~ 1$ and $bB ^(t) ~=~ 1$ for all $j ~epsilon~ cC "}"$,
.sp
$fF$	$=$	$"{" i: ~aA ^(t) ~=~ 0$ and there exists $j ~epsilon~ cC$ with $bB ^(t) ~=~ 1 "}"$,
.sp
$gG$	$=$	$"{" i: ~aA ^(t) ~=~ 1$ and there exists $j ~epsilon~ cC$ with $bB ^(t) ~=~ 1 "}"$.
.TE
.DE
.P
Any site in $dD$ at time $t$ will be in $dD$ or $fF$ at time $t+1$ since
the value will remain 0, but we cannot predict what will happen to its
neighbors.
Similarly, any site which falls in $eE$ at time $t$ will be in $eE$ or
$gG$ at time $t+1$.
Anything in $fF$ will move to $gG$ at time $t+1$, and all members
of $gG$ will move to $fF$.
Therefore eventually all elements will either stay in $dD$ or in $eE$
or will continue switching between $fF$ and $gG$, and so the cycle
length will be 1 or 2.
.P
Where the $aA ^(0)$ are not all 0 or 1 (or $x$ and $x+1$, more generally),
the iteration is much more complicated and no simple combinatorial
argument has been found to prove the theorem.
For example, even when $G$ is a simple path, differences between
values of adjacent vertices can be arbitrarily large on a cycle
(as large as a constant times $n$ for a path of length $n$).
This can be seen by generalizing the construction
$( x sub 1 ^(0) ^,...,^ x sub H ^(0)) ~=~ (0,1,1,4,6,11,15,22,25,28,27)$.
.P
The proof we will give for the theorem is based on a modification
of the proof used by Goles-Chacc, Fogelman-Soulic, and Pellegrin [2]
to prove that cycle lengths are at most two in certain threshold
networks.
Their Theorem implies the Brickell-Purtill results, but does not
seem to cover the general case of our iteration.
However, their concept of decreasing energy is a key ingredient
in our proof.
Another case where iterations on graphs produce cycles of length
at most 2 occurs in the make of Poljab and Sora [3], but their
model and method of proof are quite different from ours.
.H 1 "Proof of theorem"
It clearly suffices to prove the theorem when $G$ is connected,
and so we will assume this from now on.
.sp
\f2Lemma\f1:\0\0If the period of the cycle is not 1, then for
all large $t$ and for all $i$,
.DS 3
.EQ
x sub i sup t ^(t) ~!=~ aA ^(t+1) ~.
.EN
.DE
\f2Proof of lemma\f1:\0\0Suppose there exists $i prime ^,^ t$ such that
$x sub {i prime} ^(t) ~=~ x sub {i prime} ^(t+1)$ and
that the $t$-th iteration is in the cycle.
We know there exists $j prime$ such that $x sub {j prime} ^(t) ~!=~ x sub {j prime} ^(t+1)$
since the period of the cycle is not 1.
Hence we can find $i$ and $j$ that are connected such that:
.DS
.TS
l l.
.ls 1
but	$aA ^(t) ~=~ aA ^(t+1)^,$
.sp
	$bB ^(t) ~!=~ bB ^(t+1)^,$
.sp
	$bB ^(t+1) ~=~ bB ^(t) ~+-~ 1~.$
.sp
So	$aA ^(t) ~-~ bB ^(t) ~==~ 0 ~( mod ~2)$
.sp
and
	$aA ^(t+1) ~-~ bB ^(t+1) ~==~ 1 ~( mod ~2)~.$
.TE
.DE
But if $aA ^(t+k) ~-~ bB ^(t+k) ~==~ 1 ~( mod ~2)^,$ then
$aA ^(t+k) ~!=~ bB ^(t+k)^,$ so
$aA ^(t+k+1) ~=~ aA ^(t+k) ~+-~ 1$ and
$bB ^(t+k+1) ~=~ bB ^(t+k) ~+-~ 1^,$
so $aA ^(t+k+1) ~-~ bB ^(t+k+1) ~==~ 1 ~( mod ~2)~.$
.sp
Since this is true for all $k$, there does not exist any
$k prime ~>~ 0$ such that $aA ^(t+ k prime ) ~=~ bB ^(t+ k prime )$
which means that $aA ^(t)$ cannot be in the cycle and we
have reached a contradiction, which proves the lemma.
$blot$
.sp
\f2Proof of Theorem\f1:\0\0Using the idea of a decreasing ``energy''
function utilized by Goles-Chacc et. al. [2], we define:
.DS 3
.EQ
E(t) ~=~ -~ sum from {i,j ^=^ 1} to n ~a sub ij ~aA ^(t) ~bB ^(t-1) ^,
.EN
.DE
where
.DS 3
.EQ
a sub ij ~=~ left {
matrix {
lcol {1 above -d sub i above 0}
lcol {roman if above roman if above roman if}
lcol {i ~!=~ j ~roman but ~j ~epsilon~ cC ^; above i ~=~ j ^; above i ~!=~ j ~roman and ~j ~epsilon~ cC ~.}
}
.EN
.DE
Note that $E$ is bounded below since the maximal element at any
stage never increases with time.
.sp
We now consider the change in energy during iterations of the transformation:
.DS 3
.EQ
DELTA E(t) ~=~ E(t+1) ~-~ E(t) ~mark =~ -~ sum from {i,j ^=^1} to n ~a sub ij
^aA ^(t+1) ~bB ^(t) ~-~ sum from {i,j ^=^ 1} to n ~a sub ij ^aA ^(t) ~
bB ^(t-1)
.EN
.sp
.EQ (*)
~lineup =~ -~ sum from i=1 to n ~[( aA ^(t+1) ~-~ aA ^(t-1)) ~sum from j=1 to n
~a sub ij ~bB ^(t)] ^,
.EN
.DE
since $a sub ij ~=~ a sub ji$ for all $i,j$.
For each $i$, if $sum from j=1 to n ~a sub ij ~bB ^(t) ~<~ 0$, then
.DS 3
.EQ
d sub i ^aA ^(t) ~>~ sum from {j ^epsilon^ cC} ~bB ^(t) ^,
.EN
.DE
so
.DS
.TS
center;
l l.
.ls 1
	$aA ^(t+1) ~<~ aA ^(t)^,$
.sp
	$aA ^(t+1) ~-~ aA ^(t-1) ~<=~ 0 ^,$
.sp
and	$-^( aA ^(t+1) ~-~ aA ^(t-1)) ~sum from j=1 to n ~a sub ij ^bB ^(t) ~<=~ 0~.$
.TE
.DE
If $sum from j=1 to n ~a sub ij ^bB ^(t) ~>=~ 0$, then:
.DS 3
.EQ
d sub i ^aA ^(t) ~<=~ sum from {j ^epsilon^ cC} ~bB ^(t) ^,
.EN
.DE
.DS
.TS
center;
l l.
.ls 1
	$aA ^(t+1) ~>~ aA ^(t) ^,$
.sp
	$aA ^(t+1) ~-~ aA ^(t-1) ~>=~ 0^,$
.sp
and	$-^( aA ^(t+1) ~-~ aA ^(t-1)) ~sum from j=1 to n ~a sub ij ^bB ^(t) ~<=~ 0~.$
.TE
.DE
Thus in both cases $DELTA E(t) ~<=~ 0$ and each term in the sum
on $i$ on the right side of (*) is $<= ~0$.
Since $E$ is bounded below, we must have $DELTA E(t) ~=~ 0$ for
all large $t ~>=~ t sub 0$, and moreover, for all such
$t ~>=~ t sub 0$ we have for each $i$,
.DS 3
.EQ
( aA ^(t+1) ~-~ aA ^(t-1)) ~sum from j=1 to n ~a sub ij ^bB ^(t) ~=~ 0 ~.
.EN
.DE
.P
Now suppose there exists an $i$ such that $aA ^(t+1) ~!=~ aA ^(t-1)$
for some $t ~>=~ t sub 0$.
If $aA ^(t-1) ~>~ aA ^(t+1)$ and
.DS 3
.EQ
sum from {j ^epsilon^ cC} ~bB ^(t) ~>~ d sub i ^aA ^(t) ^,
.EN
.DE
then
.DS 3
.EQ
aA ^(t+1) ~>~ aA ^(t) ^,
.EN
.DE
which is a contradiction.
If
.DS 3
.EQ
aA ^(t+1) ~>~ aA ^(t-1)
.EN
.DE
then there exists a $k$ such that $aA ^(t+k+1) ~>~ aA ^(t+k-1)$,
so $sum from {j ^epsilon^ cC} ~bB ^(t+k) ~>~ d sub i ^aA ^(t+k)$,
which is also a contradiction.
.P
Therefore $aA ^(t+1) ~=~ aA ^(t-1)$ whenever $aA ^(t-1)$ is in the
cycle, so the length of the cycle is at most 2.
$blot$
.sp
Note:\0\0It is not true that $DELTA E(t) ~<~ 0$ for $t$ not in the cycle.
For example, when $G$ consists of a simple path of length 5, with
$( x sub 1 ^(0) ^,...,^ x sub 5 ^(0)) ~=~ (0,2,2,3,5)$, then
$E(1) ~=~ E(2) ~=~ -1$, but the cycle starts only at $t ~=~ 2$.
.HU "Acknowledgements"
The authors are grateful to G. J. Simmons for information about the
problem and references, to E. F. Brickell and M. Purtill for permission
to include their argument for the case of all $aA ^(0) ~=~ 0$ or 1,
to G. Vishkiac for providing the crucial reference [2], and
to L. Lovasz for the reference [3].
.bp
.ce
.B
References
.R
.sp
.AL
.LI
D. C. Ghiglia and G. A. Mastin, A cellular automatic method for phase
unwrapping, to be published.
.LI
E. Goles-Chacc, F. Fogelman-Soulic, and D. Pellegrin, Decreasing
energy functions as a tool for studying threshold functions,
\f2Discrete Appl. Math. 12\f1 (1985), 261-277.
.LI
S. Poljak and M. Sura, On periodical behavior in sociaties with
symmetric influences, \f2Combinatorica\f1 \f23\f1 (1983), 119-121.
.LE