BULLETIN OF MATHEMATICAL BIOPHYSICS VOLUME 18, 1956

A NOTE ON RASHEVSKY'S THEOREM ABOUT FOINT-BASES IN TOPOLOGICAL BIOLOGY

ERNESTO TRUCCO COMMITTEE ON MATHEMATICAL BIOLOGY THE UNIVERSITY OF CHICAGO A graph G may have more than one p o i n t - b a s e BG. In a primordial graph P of R a s h e v s k y ' s (1954) T r a n s f o r m a t i o n T~ some of t h e pointb a s e s may c o n s i s t of n o n s p e c i a l i z e d points only, and some other pointb a s e s m a y c o n t a i n s p e c i a l i z e d p o i n t s . In t h i s oasep R a s h e v s k y ~ s Theorem (1955a) on p o i n t - b a s e s may not hold. The T h e o r e m is c e r t a i n l y true if all p o i n t - b u s e s of P c o n s i s t of n o n s p e c i a l i z e d points. A rigoro u s proof is g i v e n . Some r e s u l t s are d e r i v e d for the more g e n e r a l c a s e , when p o i n t - b a s e s i n c l u d e both k i n d s of p o i n t s . A general e x p r e s s i o n for the p o i n t - b a s e ratio of the transformed graph P ( T ) i s o b t a i n e d . It is shown that with s o m e b i o l o g i c a l l y p l a u s i b l e a s s u m p t i o n s R a s h e v s k y ' s i n t e r p r e t a t i o n of the p o i n t - b a s e r a t i o and his c o n c l u s i o n s are s t i l l true. A few s i m p l e T h e o r e m s on p o i n t - b a s e s of graphs are i n c l u d e d in t h i s work.

Recently N. Rashevsky (1954) has presented a transformation, leading from a relatively simple primordial graph P to a more complicated graph T(P), as a possible theoretical explanation of relations existing between biological organisms. Underlying Rashevsky~s work is the general principle that agl the topological spaces or complexes by which different organisms are represented should be obtained from one or, at most, a few primordial spaces or complexes by the same transformation. For further comments on the choice of this transformation--clearly a very important point in constructing the t h e o r y - - t h e reader is referred to a later paper by N. Rashevsky (1955b). In this note, however, we shall limit ourselves to the original transformation T given in the 1954 paper. It is assumed that the topological complexes describing relations within an organism, or possibly between an organism and its surroundings or between members of a society, to which the trans65

66

ERNESTO TRUCCO

formation T is applied, are finite, plane, directed graphs. As a result of the transformation we obtain again finite, plane, directed graphs. In a s u b s e q u e n t paper (1955a), N. R a s h e v s k y has examined in particular the problem of finding the relation between the pointbases of the primordial and the transformed graph. His result is embodied in Theorem 2, and the Corollary to Theorem 2 of which he has a l s o given an interesting biological interpretation (Ibid., pp. 124, 125). It appears, however, that R a s h e v s k y ' s Theorem requires a more p r e c i s e formulation b e c a u s e , as is made clear in Khnig's book (1936), a graph P may have more than one point-base Bp. We shall show in this paper that the strictly correct version of R a s h e v s k y ' s result is the following: The point-base ratio rT of the transformed graph T(P) is greater than the point-base ratio rp of the primordial graph P, if among all the possible point-bases B p of P there is none which includes specialized points. Before proceeding any further we recall here the definition and properties of a point-base in a directed graph G. By a path of the graph we mean a sequence of a d j a c e n t lines; a path in which all the lines are directed in the same manner will be called a way. In general for our purposes a way is sufficiently specified by indicating its end-points; a way whose end-points coincide will be denoted as a cycle (or directed circuit).* If p, ~ r , . . . are the points of the graph G we construct the s e t s lip, Ilq, I I r , . . . a s follows: IIp c o n s i s t s of the point p and all the points of G which can b e r e a c h e d by a way from p, and similarly for IIq, Hr, etc. Performing this procedure for all the points of the graph, we shall find a certain number of these s e t s , s a y IIs, [iv, 1]w, , . . etc., ,which are not proper s u b s e t s of any of the others. Such a special set, like for instance Ils, is called a fundamental s e t (Grundmenge) having the point s as its source (Quelle). A fundamental s e t may have more than one source, e.g., l] v = l]w, but indicating one of them will s p e c i f y t h e fundamental set completely. On the other hand, two different fundamental s e t s may have some points in common, but these common points cannot be sources, Choosing one source from each fundamental s e t of the graph G we obtain a point, base Br of G, which clearly has the following two properties: (a) any point of G can be * Or "uniformly directed cycle" in Rashevsky's terminology (lee. cir., 1955b, p. 210).

TOPOLOGICAL BIOLOGY

67

reached by a way from a point of B e . (b) there is no way connecting any two points of B e . Conversely, the point-base may be defined by the above two properties (KSnig, lee. cit., pp. 88 frO. A graph G can, and in general will, therefore, have more than one point-base; all of them, however, have the same number of points Pc, namely, as many points as there are fundamental s e t s in the graph. The quantity Pc will be called the point-base number. In the following we shall often s a y that a point is " a source of a graph" meaning that it is a source of a fundamental s e t in the graph. It is clear that each point of a graph belongs to at l e a s t one fundamental s e t (Ibid., p. 88., Theorem 2). Returning now to the primordial graph P in R a s h e v s k y ' s transformation, we shall have to consider its fundamental s e t s ; the points of P are thus subdivided into sources and non-sources. But it will be recalled that R a s h e v s k y also distinguishes between specialized and nonspecialized points of P . A priori there is no reason why a fundamental s e t should contain only nonspecialized points as sources. In the most general c a s e , we can, in fact, subdivide the fundamental sets into three categories: (a) those whose sources c o n s i s t only of s p e c i a l i z e d points; (b) those whose sources c o n s i s t only of nonspecialized points; (c) those whose sources include both s p e c i a l i z e d and nonspecialized points. In P, let p', p " , and p " " b e the number of fundamental sets of category (a), (b), and (c)i respectively. Then any point-base of P has

pe =p" +p" +p""

(I)

points, and the point-base ratio of P is defined as p" + p"" + p " "

rp

=

,

0C0

0c0 being the total number of points in the graph P. I n the graph of Figure 1 we have, for example, p" = p'" = p"" = 1. As we have already pointed out, R a s h e v s k y ' s Theorem on pointb a s e s is certainly true if p" = p " " = O.

(3)

Then rT

> re

,

where r T denotes the point-base ratio of the transformed graph.

(4)

ERNESTO TRUCC0

68 i

2

4

5

6

O

9 NON-SPECIALIZED POINTS O SPECIALIZED PO1NTS

F I G U R E 1. F i r s t f u n d a m e n t a l s e t c o n s i s t s of t h e p o i n t s 1, 2, 3, 4 w i t h p o i n t 1 a s s o u r c e (p" = 1). S e c o n d f u n d a m e n t a l s e t c o n s i s t s of the p o i n t s 4, 5, 6 w i t h p o i n t 5 a s s o u r c e ( p " = 1). T h i r d f u n d a m e n t a l s e t i n c l u d e s t h e p o i n t s 3, 4, 7, 8, 9 w i t h p o i n t s 7, 8, a a d 9 a s s o u r c e s ( p , . t = 1).

If, however, condition (3) is not satisfied, we may have r T > r p or r T < rp. To show this, we shall consider four very simple examples with p " = O. We take primordial graphs P with ~ = 5 points, of which n = 3 are specialized (Figures 2a, 3, 4, 5). For the parameter m (Rashevsky, loc. cir., 1954) we choose the value 2. We recall that

TT 9

~

=

|

9 NON-SPECIALIZED POINTS |

(~--<.--we

,,,\

POINTS FIGURE 2a

(=~)

,"~;2 -~ ----" "" P'*

(1)

J ; It

(1)

P' 9

(

,:

~"lP" It,"

I." f

el)

_~'"

~'3

-',' :

.4

l

(3)> .

,

!

--e

it,

4

;

i/ , ~ t 9

| SPECIALIZED AND SUBSIDIARY POINTS FIGURE 2h

9

TOPOLOGICAL BIOLOGY

69

the transformation T is determined by six s t e p s , TI, T 2 , . . . T6. Referring to Figure 2a, we shall s p e c i f y T2 as follows: the first component primordial graph (i = i in R a s h e v s k y ' s notation) specializes in r and s (n 1 = 2 ) , and l o s e s t ( n - n ~ = 1 ) ; the second component primordial (i --- 2 = m) s p e c i a l i z e s in t (% = 1) and l o s e s the two points r a n d s ( n - n 2 = 2 ) . As for T4, we shall attach one ,4.

.S

f

P

t

* NON-SPECIALIZED

POINTS

O SPECIALIZED POINTS

FIGURE A

3 $

I. 9 NON-SPECIALIZED POINTS O SPECIALIZED POINTS FIGURE

"

4

N O N - SPECIALIZED POINTS

O SPECIALIZED POINTS

FIGURE

5

subsidiary point to r and n o n e t o s (for i = 1); for i = 2 we shall attach t w o subsidiary points to t. The same rules T 2 and T4 apply a l s o to the graphs of Figures 3, 4, and 5. The r e s i d u a l g r a p h cons i s t s simply of the line p --* q. Figure 2b shows the transformed graph obtained from that of Figure 2a. The result of Ts (cf. R a s h e v s k y , l o c . c i r . 1954) can be v i s u a l i z e d as giving the primordial graph P in m (= 2) layers with

70

ERNESTO TRUCCO

each specialized point fused into one; in Figure 2b the first layer consists of the points r, s, t, p ( o , q(1); the second layer of the points r, s, t, p(9) q(2), and their connecting solid lines. After Th, we have added the three subsidiary points ra, tl, and t 2 with their proper connections (dotted lines in Figure 2b), and finally by T6, we add the n ( m - 1 ) = 3 residual graphs (1), (2), and (3) with their connecting lines (r162(fi), and (y) (broken lines in Figure 2b). By these same rules the reader will easily be able to construct the transformed graphs of the primordials shown in Figures 3, 4, and 5. The point-base ratio of the primordial graph i s equal to ~- in all our four examples; the transformed graphs have 16 points and their 1 point-base ratio varies between T~" and 1"~-. T h e s e results are collected in Table 1. T A B L E 1. Primordial Graph of

p'of Primordial

p"" of Primordial

Fig. 2 Fig. 3

0

1

o = pp

rp 1 1

rT

PT 4

> rp •fl-E

3

!

2

Fig. 4

1=; e

o

-~

2

i~-< rp

Fig. 5

0

1 = pp

1 -~

1

"-f'~< r p

1

In particular we see that our second and fourth examples (Figures 3 and 5) contradict R a s h e v s k y ' s Theorem as originally stated since for them we can choose a point-base Bp consisting only of nonspecialized points, and y e t r T < r e . It was pointed out by R a s h e v s k y (loc. cir., 1954, 1955b) that c y c l e s of graphs may play an important role in topological biology; for this reason it is worth-while stating two Theorems on pointbases and cycles; they are so simple as to require no proof, and yet will be found very useful in the following. Theorem 1: If p and q are two different sources of the same fundamental set, there exists a way from p to q (including possibly other points of the graph) and also a way from q to p, i.e., p and q are two points belonging to the same cycle. Theorem ~: If it is known that the point ~ is a source of a fundamental s e t lip and there exists a way from another point ~ of the

TOPOLOGICAL BIOLOGY

71

graph to p, then q is also a source of the same fundamental s e t lip, i . e . , .we have Hq =IIp (of. KSnig, .loe. tit~ p. 89, Theorem 3). By Theorem 1, p and q then belong to the same c y c l e . All other points, if any, on this cycle are also sources of lip. We recall at this point that R a s h e v s k y ' s proof of his Theorem 2 was based on a preceding Lemma (loc. cir. 1955a, p. 120). In the following let K, p, B, K', B', w, Aw, and Kwhave the same meaning as in R a s h e v s k y ' s paper. We shall show that the Lemma as stated there is certainly true only if the point p which we remove from the graph K is not a source of K. Proof: Any point which is a source of K is also a source of K'. This could be derived in the same manner as Theorem 3 below. We shall, however, give a slightly different proof which follows more closely, and completes, the one given by Rashevskyo 1. It may be that all the points of K (except p) can be reached from points of B by ways that do not pass through p, in which case there is nothing to prove. 2. Otherwise, the point-base of K" c o n s i s t s of the points of B and those of B w. The first point-base property is obvious. As for the second point-base criterion we notice that a) there can be no way connecting any two points of B or any two points of B . b) having removed p, there can be no way from a point of B to apointofB . c) assume that there were a way
PK" >~PK ; again the proof is the same as that of Theorem 3.

(5) But inequality

72

ERNESTO TRUCCO

(5) is not s u f f i c i e n t to show that r r > rp. F i n a l l y , if from K we remove a point p which is the only s our ce of a fundamental s e t I I p - and therefore must belong to B - - t h e point-base B" may have one point l e s s than the point-base B (cf. F i g u r e s 7a, 7b). T hi s will happen if p is the only point of the fundamental s e t 1]p which does not belong to any other fundamental s e t of K. Otherwise relation (5) will s till hold. t

P

~,

v

U

v

.u

9

1

f

\./

K'

$

FIGURE 6. 1) Choose points r and u as point-base B of K. Pointbase B" of K" consists of the same points r and u~ and additional point t. 2) Choose points s and u as point-base B of K. Point-base B" of K" consists of the points r, u, and t. Thus, there i s a point s of B which is not included in B'.

The residual graph R i s obtained from the primordial P by removing all the s p e c i a l i z e d points and their connecting lines from P.* L e t p, q, r , . . . d e n o t e the nonspecialized points of P, and p, q, r, . . . t h e corresponding points of R. To any way of R there corresponds one in P, but, of course, the c o n v e r s e is not true si nce a way in P may pass through a s p e c i a l i z e d point. Definition: A primary fundamental s e t n 7 of the r e s i d u a l graph R is one whose source p corresponds to a point p which is the source of a fundamental s e t IIp in P. By Theorem 1, a n y other source q of ~ " corresponds to a source ~ of IIp. We now prove Theorem 3: The residual graph has at l e a s t p'" + p"" primary fundamental s e t s (its point-base BR, therefore, at l e a s t p " + p"" points). * N. Rashevsky (Zoc. cir., 1955a, p. 121) includes one subsidiary point with the additional residual graph. We shall, however, keep the original definition of residual graph (Rashevsky, loc. cir. 1954, p. 333).

TOPOLOGICAL BIOLOGY

T3

In P, let IIp be a fundamental s e t of the second or third category, and the nonspecialized point p one of its sources 9 Then: (a) either is a source of a (primary) fundamental s e t H~ in R, or (b) p is not a source of R. In this latter case~ .however ~ belongs to at l e a s t one fundamental s e t n ~ of R with source ~. Hence~ ,there exists a connection q - - * p in R, and therefore, a way q ~ p in P . By Theorem 2~ g i s a source of the fundamental s e t lIp, s o that n ~ i s : a primary fundamental s e t of R. P 0

FIGURE 7a. s only.

s

,~ 9

9

9

9

K

s

K'

P o i n t = b a s e B c o n s i s t s of p o i n t s p and s, p o i n t - b a s e B" of

t9

u.-

,..//I

ii

s9

K'

FIGURE 7b. P o i n t = b a s e B h a s two p o i n t s (p and s), b u t point=base B" h a s t h r e e p o i n t s ( s , t, and u).

Thus to each fundamental s e t of the second or third category in P there corresponds at l e a s t one primary fundamental s e t of R9 On the other hand, a primary fundamental s e t of R cannot correspond to more than one fundamental set of P 9 We conclude that R must have at l e a s t p'" + p"" primary fundamental s e t s , q.e.d. In particular, if lip and I'll- have the same meaning as above~ .it is e a s y to s e e that for a fundamental s e t lip of the aeoond category in P~ there is a one-to-one correspondence between the sources of IIp and those of 9 -p 9

74

ERNESTO TRUCCO

Figure 8a shows a very simple primordial graph P formed by only one fundamental s e t of the third category. The corresponding residual graph R, shown in Figure 8b, c o n s i s t s of two primary fundamental sets and also of a third fundamental set. So far we have been dealing mainly with situations arising when we remove a poin t from a graph. We shall now prove a Theorem which-has to do with adding some lines between two graphs. L e t G and K be two distinct directed graphs, as shown, for example, in Figure 9 (solid lines). We denote by B c a point-base of G, and by B K one of K. The point-base numbers shall be Pc and PK for the graphs G and K respectively.

sa

" N O N - SPECIALIZED POINTS

((2)

0 SPECIALIZED POINTS

(b)

FIGURE 8 T h e o r e m 4: Draw any number of d i r e c t connections between arbitrary points of K and one point s of G (Figure 9, broken lines). Denote the resulting graph by L and l e t B L be its point-base. Furthermore, in L, the points of B K shall be subdivided into two subsets: B"K consisting of those P'K points P "l , P'2, "" 9 P "p "K, which c a n n o t be reached by at l e a s t one way from s, and B'~: including

the remaining p 9 points of B K. Thus Pr = PI~ + P ~ " (1) If s is not a source of G, the point-base B L has 9 PL = PG + PK = P c + PK - P"K9

(6)

points. (2 a) If s is a source of G, w e still have Pc = Pc + PK provided there is no way from any of the points p" of B g to s. (2 b) Otherwise, if there is at l e a s t one of the points p" which has a connection to s, but none from s, Pc is given by

PC=PC + P9E - I

"" =Pc +PK-PK

-I.

('7)

75

TOPOLOGICAL BIOLOGY

We shall give the proof in detail for c a s e 1 above, by showing that a point-base B L of L c o n s i s t s of all points of B c and all points of B~. a) Any point of G, including s, can be reached from some point of B e ; any point of K from some point of B~ or B ~ . But each point of B'~ can, in turn, be reached from s; thus, the first pointb a s e criterion is s a t i s f i e d by B L . b) s is not a source of G; hence, by Theorem 2~ there is no way from s to any point of B c . Also, there is no way from s to a point of B~. Furthermore, though there may be connections to and from

I I I I ___J

3 ss 2

G TNE POINTS 9

K FOP,.M A POINT

BASE IN G AND ONE IN K

FIGURE 9 S*t

s and B K, there is, of course, no way in E between a point of B~ and one of B'/~. It follows from all this that in L there can be no connection between any two points of B c , or to and from a point of B G and one of B~. Finally, if P'i and Pi" are two different points of B~, a connection from P'i to PI" could have been e s t a b l i s h e d only by passing through s, which is impossible since there is no way s --> p~. Thus the second point-base criterion is also s a t i s f i e d for B L . If s is a source of G, the point-base B c will contain one source s* of the fundamental s e t II s of G (s and s* may coincide). By arguments similar to those above, it can be seen that in c a s e 9 a, a point-base B L c o n s i s t s of all points of B c and all points of B~;

76

ERNESTO TRUCCO

in case 2 b, to obtain BL we take the points of B~ and all those of B c except s*. Knowing BL, equations (6) or (7) follow at once. Clearly when equation (7) applies, the set B~ cannot be empty (p~ ~> 1). Hence, we have quite generally:

Pc <~PL <'Pc + Pr " (8) From the proof given above it is e a s y to deduce the following Corollary to Theorem $: In G, assume that s is not a source and that it belongs to a fundamental sat I](p6). Then any point of II(pc) which is not a source of fl(pc) cannot be a source of the completed graph L~ We are now ready to prove the Theorem enunciated at the beginning of this paper. Denote by P8 the graph obtained after, and i n c l u d i n g , ' t h e step Ts of the transformation T. As we have seen, Ps contains m primordial graphs P(~) arranged in m layers and " f u s e d together" at each specialized point. Thus ida has a 0 + (m-1)((x 0 - n ) = m(xo - n ( m - 1 ) points. The e a s i e s t way to find a point-base Bpa for Pa is as follows. Construct a point-base of P containing the maximum number of specialized points, i.e., from each fundamental s e t of the third category choose a specialized point as source. In Pa take one such point-base from each layer. Since the specialized points are " f u s e d , " a source of the first or third category will be represented only once. The two point-base properties can e a s i l y be verified for the point-base Bpa thus constructed; altogether it has

PP8 = p" + rap'" + p"" points.

In Bpa any specialized source of the third category can be

replaced by a nonspecialized source taken from any one, but only one, of the layers. If now P5 is the graph obtained after the step Ta of the transformation T, i.e., after addition of the subsidiary points and their connections, we s e e that Bpa is a point-base also for the graph Ps" In fact, any one of the subsidiary points can be reached by a way from a point of Pa; on the other hand, the lines added in going

TOPOLOGICAL BIOLOGY

77

from Ps to P5 do not give rise to a way between any two points of

Bpa. Therefore, PP5 = Pea = p" +rap'" + p " ,

(9)

and, since P5 has m~ 0 points,

PP5

rP5 =m~o

P* + P"*

mcr

P'"

+~0

(10)

It is interesting to note that the point-base ratio of P5 is never larger than that of P . We have p* + p'"" p,, rP 5 .~ rp =

C~o

+ ~o

(11)

equality holding only for p" = p " " = O9 In P5 we denote the n s p e c i a l i z e d points by sl, s 2 , . . , s n (correspending to s(1P), s(~P),.., s ~ ) of the primordial); s.I b. shall be the , vth subsidiary point attached to the s p e c i a l i z e d point s i. The index v takes on the values O, 1, 2, . . . li, it being understood that Sio is the same point as s i and some of the quantities 1i may be zero 9 Since there are n ( m - 1 ) subsidiary points we have the relation ]ffil g.I = n ( m - 1 ) .

(1~)

By arguments similar to those used in the proof of Theorem 3 it can be shown that if the s p e c i a l i z e d point s(kP) is not a source of P , the corresponding point s k cannot be a source of Ps" Moreover, in this c a s e , none of the subsidiary points sk~ ( v = 1, 2, . . la) can be a source of Pn. This follows directly from Theorem 9. since there is a way from s k to _s]~v. On the other hand, if s (P) is a source of the third category in P (and therefore s k a source of P s ) , each of the points Sky will be a source of P_. For, according to Theorem 1, there is a way from s(kP) to p(P)aand also a way from p(P) to s (P)~, p(e) being a nons p e c i a l i z e d source of the fundamental s e t [Is(P). Therefore, by the rules of the transformation T, in P5 there is a way from sky to sk, so that by virtue of Theorem 2 s k v must be a source of Ps" The l a s t step, Te, of the transformation T, c o n s i s t s in adding one residual graph /~ v to each of the subsidiary points sir (u >11). Using Theorem 4 we find that the point-base number i n c r e a s e s by a

78

ERNESTO TRUCCO

certain amount xi~ (0 ~< xiv ~< PR)as we i n s e r t each of the graphs Ri~" Thus the point-base number of the transformed graph T ( P ) i s given by

Or=OP5 +j=l ~=1~"

(18)

In many cases the quantities ~v will not depend on the index v, and may be written xi. Then equation (13) becomes

PT : PP5 + /~= 1 1.X.. 1 1

(14)

If B//u is a point-base of R/~ and Yiu the number of points of B/u that are not reached by a way from sju to Riu , we shall have either x/~ -Yiu or ~ = Yi~- 1, depending on conditions set forth in Theorem 4. Assume now that 9

p = p

9

= 0.

(8)

B e c a u s e of our assumption (3) none of the s p e c i a l i z e d points s/(P) is a source of P, and thus none of the points s/u can be a source of Ps" Also, repeated application of the Corollary to Theorem 4 shows that none of the points s/u can ever be a source of the graphs resulting in the process of adding the various Ri~'s" Hence c a s e 1 of Theorem 4 applies throughout. Moreover, it is e a s y to s e e that equation (14) can be used instead of (18). Equations (2) and (14) reduce to Pl

:

P

--,

(is)

0ro n

PT : raP9 + j~= 1' l.x. I I

(16)

By mapping the graph T(P) onto P according to the rules given in R a s h e v s k y ' s paper (lot. tit. 1954, p. 334), we can show that xi :

yj. >~

p"

(17)

for all values of ]. In fact, let ~/~ be a primary source of R so that the point p(P), corresponding to ~/~, will be a source of p1.~ It is clear that in the graph T(P) there can be no way from ~i~ to ~/~ since such a way would map onto a connection s.(P)---, p(P which, 1

TOPOLOGICAL BIOLOGY

79

by Theorem 2, would imply that s.1(P) is also a source of P. Inequality (17) follows at once because there are p'" primary fundamental sets in R/v. The transformed graph T(P) has

% = m% + n ( ~ - l )

(%-n)

(lS)

points. Using (16), (18), (17), and (12) we get

rr=

Pr

rap'" + n ( m - 1 ) p "

>1

ST

ma 0 + n ( m - 1 ) (0rO - n )

= r~

(19)

Now, it is obvious that r~ > re ,

(20)

where, we remember, rp is given by equation (15). Indeed, since m > 1, inequality (20) reduces to 0ro > 0~O - n. Thus from (19) and (20) we finally obtain the result rr>r P

which we had s e t out to prove. For the case when p" and p " " do not vanish, it seems rather difficult to obtain some general criterion which would enable us to decide whether rr is greater or smaller than rp. From (8) we derive immediately the relations

p" + rap'" + p " " m% + n(m-

I)

(%.

~)

.<. rr ~

p" + mp'" + p " " + n ( m - 1 ) p R m % + n(m -

1) ( % - n)

,

(21)

where PR is the point-base number of the residual graph (of course

PR < % - n ) . Subtracting the quantity rR = pR/(Oto-n) from both sides of the second inequality in (21) we can see that: if

rps .< rR ,

(22)

rT <. rR .

(2a)

then

Proof: From (21) and (22) we get rp5 - rR

rT - rR <"

n ( ~ - l ) , ,~%-n~ <"0 . 1+

m%

(9,4)

80

ERNESTO TRUCCO Because of (11), inequality (22) certainly holds if re <~ rR 9

(25)

Furthermore, (25) is s a t i s f i e d whenever Pe ~
(26)

F i n a l l y , by Theorem 3, this l a s t inequality (96) is true if p" = 0. But it follows from our remarks in connection with Figure 7 that (26) is likely to hold even for p" > 0, except for some rather special choice of the primordial graph and its s p e c i a l i z e d points. In particular the relation (25) will follow if the graph P is such that p9

n

(P'" ~< -(%_~)

+

P'")

,

(27)

since (97) is equivalent to

rp~<

P

Ps

s,s

+p 0~ 0 -

n

If re - rR > O

(which, as we have seen, is very unlikely), it follows from (11) and the first half of (24) that rr - rR < rp - rR, i.e., r r < re

.

By the same method used in deriving (17) we can now find a lower limit to the quantities ~v of (13) as follows: Bp and B/~ are the point-bases of the graphs P and R/~. It is convenient to choose a base Be with the maximum number of nonspecialized points, and such that each point of the second or third category in Bp corresponds to a (primary) point of B.u . 1) L e t the specialized point s ~) be a source of the first category i in P. Then in Ps, s/v may or may not be a source. However, it is clear that if ~ is any source of ~/v, in the graph T(P) there can be no way from ~ to % since this would map onto p(P)--, ~q'), where p(P) is a nonspecialized point of P. Thus we are either in case 1 or in c a s e 2a of Theorem 4 so that x/u = Yiv" On the other hand, there can be no connection from ~ to a primary point of B/v since the corresponding way in P would contradict the second point-base property of Be. Hence, in this c a s e ,

~

= yj~ >~ p'" + p " , .

(28)

TOPOLOGICAL BIOLOGY

81

2) Now assume that s]~ ) is not a source of P. The same argument that led to (17) shows that in this c a s e we have again inequality (28). 3) Finally, let s.i~) be a source of the third category in P. Using as before the principle of mapping the graph T(P) onto P we find: a) There can be no way from a point g of B/~ to ~v unless the point g corresponds to a nonspecialized source p(e) of the fundamental s e t [ l ( P ) . b) Consider the fundamental s e t s of the second and third category in P . Each of them, except p o s s i b l y II(p.) gives rise to at

1

Pa~ f"

~p-

) / /,"

$l

o=/

$'l(~"- - '~- "4 - -

SI~

_

-

/~

Rm

s

~ "

I

i

,

Illi / "-$~'~" It~ " " " 3 " "

9 NON-SPECIALIZED POINTS

P,[

~

| SPECIALIZED POINTS

t ~'' ~,,

~'[

FIGURE lOa

f

" .., ~ I /

s /.s ,' I ~ ,4 ! ' i

';'r163

-~'" 9

~

~a2

-

$I3

f331

~'3l

Ra'

|

AND SUBSIDIARY POINTS FIGURE 10b

l e a s t one primary point of B/v which cannot be reached by a way from s/v. Hence, y/~/> p'" + p " " - 1 .

(29)

c) However, it follows e a s i l y from a and b that if c a s e 2b of Theorem 4 is r e a l i z e d we must have + 1 :

P'" + P"" 9

(30)

Thus the inequality p'" + e"" - 1

(31)

holds quite generally for this category of subsidiary points. Figure 10 will serve to illustrate the various p o s s i b i l i t i e s that may arise if s/(P) is a source of the third category. L e t the primordial graph, or a partial graph of the primordial, be as shown in Figure 10a with the three s p e c i a l i z e d points s p s2, s a and the nonspecial-

82

ERNESTO TRUCCO

ized point p as sources of the same fundamental set. L e t there be one subsidiary point sll for sl, two subsidiary points s21 and s22 for s2, and one subsidiary point ssl for s s. These subsidiary points are shown in Figure 10b with their connecting lines (for simplicity we have drawn only one layer of Ps)" Starting from Ps, add first the residual graph Rll. C a s e 2a of Theorem 4 applies with

y~ :xa~ ~ p " + p ' " - l . Next, let us add the residual graph R21. We are now in c a s e 2b of ... Theorem 4, and we have Ygx /> P'" + P , therefore, x2~ = Y21- 1 ) p " + p ' " -

1.

After this we add the graphs R22 and Ral. For both of them we have c a s e 1 of Theorem 4, but %2 = Y22 /> P'" + P"" , rr

81

=ysl>/p"+p"'-l.

If the residual graphs were added in a different order, the values of the x.v's might change; however, the final result for PT would, 1 of course, always be the same. In conclusion we find that P

p +rnp"+p'"+

p

+p"'-l)+

+

1

J +

n(m-1) (%-n)

' (a2)

where the first sum refers to those s p e c i a l i z e d points s/(P) which are sources of the third category in P, and the second sum to the remaining s p e c i a l i z e d points of P. The inequality (31) certainly holds for all values of j and v. In many c a s e s and, in particular, if p " " = 0, the primordial graph may be such that x/u/> p " + p"" for all j and v. On the other hand, the condition rr ) re

(33)

can be e x p r e s s e d in terms of ~, the Mean value of the quantities x/v. ~ is defined by the equation

5,,; j=I

"~ffil

(34)

TOPOLOGICAL BIOLOGY

83

because of (31) we have ~ > p'" + p"" - 1 .

(35)

Inserting (34) into (13) and writing out the inequality (33) we find

x)

+(p" +

i-

.

n

(36)

Notice that p" + p " "

< 1.

- - -

(37)

Inequality (36) is completely equivalent to (33), but it has the advantage that the quantity ~ c a n be obtained, at l e a s t in principle, by inspection of the primordial and the residual graph. Clearly, when p " + p ' " - 1 is larger than the right-hand side of (36) we have rr > rp. Another consequence of (36), not involving the quantity ~ explicitly, is the following T h e o r e m 5: If a) p" = 0 (38)

b) ~ >. ~ / ~

(39)

0C0

c) p'" ~> - - ,

(40)

n

then ~'v >>"rp. Proof: From (39) we obtain 1

n

.... n

< 0,

(41)

~o

and from (40),

-i~>- - - p " .

(42)

0Co

Thus, starting from (35), using (41) and (42) we find:

/>p"+p""

0r0 p

/>P'"

_

+p

+p

which is the same as (36) with p" = 0. In a similar way we can derive T h e o r e m 6: If, in addition to (35), the more stringent inequality />p'+p"+p"'+l is satisfied, t h e n r T > re .

(43)

84

ERNESTO TRUCCO

Proof: (36) follows e a s i l y from (43) and (37): 5")p"

+p'" +p""

+ 1)

P" + p'" + p 1

>

,,,

+

P" + P " "

III

n

+(O" +O

+O

-

9

These l a s t two Theorems, 5 and 6, are sufficient to show that if we restrict ourselves to transformations T for which rT > ~ , this does not constitute a very severe limitation provided: a) p" = 0 ,

(44)

b) c~0 is sufficiently large.

(45)

Consider for example the relation (39); the larger ~0, the more (39) is likely to be true. As for (40), we have to remember that p'" must a l w a y s satisfy the condition p"~< % - n - p ' " ( c ~

0-n.

(46)

It is not hard to see that the three inequalities (39), (40), and (46) can e a s i l y be fulfilled if 0r0 is large enough. Again, in view of (35), it is clear that the inequality (43) is likely to hold for a primordial graph with many points (more precisely, a graph with a large number of fundamental sets) if p" is not too large. In particular, (43) may be satisfied even if some of the x~v's are < p" + /~'" + p " " + 1.

Finally, we shall d i s c u s s briefly the two assumptions (44) and (45). T h e second of these is a very natural one, since, as stated by N. Rashevsky, even the graph of a relatively simple biological organism is probably very complex. As for (44), it means essentially the same as R a s h e v s k y ' s assumption that specialized points should not be sources of the graph. In other words, a biological function upon which several other subordinate biological functions are dependent, should, in general, not become specialized. This again is a rather p l a u s i b l e hypothesis. Exceptions may arise for sources of the third category. But, as we have seen, such sources are always included in a cycle which comprises at l e a s t one nonspecialized point. As far as the point-base properties are concerned, all the points on the c y c l e s are equivalent; yet, biologically, it is natural to assume that a nonspecialized point be considered as the origin of the cycle. For instance, in Figure 3 we may regard the nonspecialized point p as a " b i o l o g i c a l point-

TOPOLOGICAL BIOLOGY

85

b a s e " or as the " s t a r t i n g p o i n t " of the whole graph. The line s---. p which c l o s e s the cycle is thought of as having been formed after the connections p---, q---,r---~ s were already present. Thus the biological point-bases are a s u b s e t of all p o s s i b l e point-bases. It is true that in P6 each nonspecialized point is represented ra times; nevertheless the complexity of the final graph T(P) (caused by addition of the residual graphs R.v) is such that in most c a s e s rr > ~.. We s e e , therefore, from this d i s c u s s i o n that there is no reason to abandon R a s h e v s k y ' s interpretation of point-bases and that, in general, his conclusions still hold true. It should be emphasized again that these conclusions were only probabilistic and may not hold in some particular c a s e s . LITERATURE K~nig, Denes. 1936. Thsorie der end~ichen und unendlichen Graphen. Leipzig: Akaziemische Verlagsgesellsvhaft. Rashevsky, N. 1954. "Topology and Life: In Search of General Mathematical Principles in Biology and Sociology." Bull. Math. Biophysics, 16, 317-48. 1955a. "Some Theorems in Topology and a Possible Biological Implication." Ibid., 17, 111-26. ~__. 1955b. "Some Remarks on Topological Biology." Ibid., 17, 207-18. RECEIVED 9-- 9,0--55