SIMPLE STRUCTURES DEFINED ON A TRANSITIVE AND REFLEXIVE GRAPH

Matematisk Seminar Universitetet i Oslo

Nr. f.

Ha.i 1965

SIHPLE S;lJQJCT'URES DEFINED ON A TRAN~UTIVE

By

B .H. ~¹fayoh

- , ^-

1 • H?rRODUCTION

Let A denote the set of common descendants of a subset, A , of the vertices in a transitive and reflexive directed graph~ By defini.tion any set of vertices that can be v'lritten in the form A

tJ

^A is a c 1 a n This conct:pt \>IB.s first introduced by S. 1¹1arcus as an explication of the notion of a ¹¹part of speech¹¹ in a natural language ( ( 1, 2)) , but it is of independent interest.

This paper is devoted to various questions - for the most part sug- gested by Marcus ((1 po 106)) on the possible internal structures of a clan; and the results are much richer than wight be expected for so simply defined an object as a clar1o In particular the question of whether or not a given clan is the sum of two disjoint clans reduces to the open problem of characterising those collect:i.ons of sets that haYe hro disjoint choice sets

i.e. two disjoint sets \'lith at least one element from each set in the collectiono

2. CLAl~S AND THEIR GENERATORS

Consider a graph G

= (V,R)

that is defined by a transitive and reflex- ive binary relation R on a non-empty set of vertices

v . ^Let

^{us write}

A ~B if A and B are subsets of

v

such that X

R

^y for every X

in A and every y in B • 'rhe largest set B such that A_..B is:

A ={vertices x such that A

-'){x}}

D

e 1' • A set of vertices C is said to be a c 1 a n , if there is

A A

a set A C V such that C

=

A

U

A .. Any set A satisfying C

=

A

U

^{A is}

said to be a g e n e r a t o r of the clan C • Such a generator A is

- 2 -

said ^tr) be c r i t i c a l if every other generator is either included in

A

or includes

A •

The primary purpose of this section is to eharacterise the generators of a clan C • Clearly any genE-rator of C iB a subset of C , and trans- itivity ensures that C itself is its own generator. Further we may suppose

"

that the clan C is not empty~ since for the empty set

¢

we have

¢ :.:

V and

V

is not empty.

D e f

.

^{The f arn i 1 y of} vertices containing ^a given vertex ^X is

F(x) ^:::::

l

^{V8l'wlC8S +' y} such that ^X fl. y and yRx

. l

A :family is b a r r e n if F

=

F •

If fM.ily F and set A are contairied in a elan C and such that A~F ~C ^A <md F

C

C , then we say that the set A is

F -

c r ⁱ t i e a ^{, J.. •}

Theorem ^~ I • S0ppose i.'am;.ly F and set ·A ~·e contained in a clan C If A :i.s F -critical and meets F ^~ then A is a generator of

c

⁰

P r o o f As the farrd.ly F cannot be empt;y, trausitivitJ on

A -')F ~C.: A immediately gives G-A4C.A and C C. A '-" A • No~.;

con::;:i.der any vertex X in ^A

.

^{Since AI)F is not} f:'t:lpt,y' vie have

-.,xl ^-')lx}

^{"' "'}

At\F

and ^F _• But this means

x4!FC,.C

_> so A

is contained in

c

and ^A generates the clan

c .

T h e o r e m 2 Suppose family F and set A are contained in a clan C If A is F -cri.tic:al but does not :meet F ~ we have:

a) A tJ F is a cr:i tical generator of C ;

b) if A contains a genf:l'ator of C , then A is a critical

- 3-

generator of . C ;

c) if B is a. non-empty proper subset of F , then A U B is a non- critical generat0r of

C •

P r o o f For any generatur B of the clan C we have: ·

B ~A- B 1)

Since A is F -critical a.rd B - A is i.nclUded in C - A we have:

A -;>B- A 2)

From 1) and 2) we can in~er:

B - A . . . A - B . . . . B - A 3)

Suppose A and B are incomparable so neitLer A - B nor B - A are empty. Transi.ti vi ty and 3) ensure that both · A - B and B - A are in- cluded in some family

r .

As A - B is not empty 9

r

meets the F - critical set A and we have :r..X ~ F • As B - A is non-empty and in- cluded in C - A we have F ~

f'* .

^But

r

^{~ F -':)}

r

^implies

F =

f*

as F and

r

are families, a.nd this contradicts the fact. that A does ·not meet F •

Suppose A U F and B are incomparable so that there are vertices x and ^y such that:

4)

As B generates C we have \ x

1-> ^f

^y

l ,

^{as A}

^~

^F

^~

^{C - A we}

have

t

^y

1-') ^~

^x

l ,

^{so x} and y a.r·e in the same family. By 4)

this family cannot be F so ~r

«f.

^it

and B are incomparable.

But this 1.s absurd as i t implies fl.

Thus if A and AUF are generators, tbPy are cr'itica.l. By theorem 1,

AU

^F is in fact a generator.

E5uppose A contains a generator B • Clearly _A C B CC " But as A is F -critical we ha.ve _{C - A} C A ^j so in this case A is a generator.

Finally suppose D is a non--empty proper :=:ubset of F • There is a vertex x in F but not in B • By theorem 1 both A

U

B an.d A

U (

x}

are gent-... Lors of ^{G •} As they are incomparable,

AU

B is non-critical and the proof of theorem 2 is complet13.

T h

e o r e m 3 (Marcus) • The only non-critical generators of a clan C are those given by part c of theorem 2.

P r o o f _{If A} is a non--critical generator, then C has a gener- ator B such that neither B - A nor J\. - B is c:mpty. As in the last proof WE~ have

B - i:,_

-> ;;,_ -

^{B -;J' B - fo.}

and transitivity ensures that t.hero is a family F containing both A - B

)o.

and B - A • S:Lnc~e B-ACC::-,AUr. we have and thereby A~ F ~ But this irnplies

,, "

F C,A C C

Ho1Afever, ^{H. '}

-

B is a subset of both F and ^A so il -...~!)

c -

^A gives A

-

^{B ~c it and F-') C}

-

^A

.

^{Thus d. ' is F} -critical and the theorem Ls proven.

D e f • ^{The k e r n e l} of a clan

c

is defined to be ^the smalles·

c.ritical generator A of C , unless there is a family F such that A is

- 5-

F -critical and meets F • In this ex~eptional case the kernel of C shall be A - F •

The theorems proved above ensure that the kernel of C is well-defined and contained in every generator of C • The kernel of a clan may be the entire clan., the empty srt, or some set lying between these two.

D

e f • A subset L of a clan C is said to be a 1 a y e r , j_f

it can be written

as

B • A , where B and A are either

a

critic~l gen- erator or the kernel of C • It is said to be a p r i m i t i v e

1 a y e r if no other critical generator of C lies betv.reen B and A •

T h

e o r e m

4 .

A layer of a. clan is the union of one or mort com- plete families.

P r o o f : Let us use the notation of the above definition and supposE

A is a critical generator. Consider any family F +,hat meets our layer

L = B - A • As F meets C - A and A generates C , we must have A~l ,., "

and F C A C. C • If A met F , A

-!>

^{C -} A would imply F -!) C - A

and A would be F -criticalo But then the fact that A is critical con- tradicts theorem 2a.

Similarly if F had. a vertex in common with C - B J we ·would have since B generates and meets F • But then ^B Nould be F -critica.l and not critical by theorem 2 c.

Thus any family F that meets L lies entirely within L • As thtJOrem 2 ensures that the layer:

smallest critical generator oi' C - kernel of C

is either empty or consisw of a single family, the proof of theorem

4

is complete.

Summarising the above four theorems, we can say that the critical gen- erators of a clan C are given by adding successive primitive layers to

-· 6 -

the kernel of C (the kernel itself may or may not be a critical generator).

outer.tw .. .~::;t

prim.itJve layer

Figure 1

kernel

c

These primitive layers consist of one or more complete families. If a prim.i ti ve layer B - A consists of a single famil;y· F , then non-critical generators of C are given by adding any non-empty proper sub~et of F to A , and all rion-critical generators of C arise in this v1ay.

T h e o r e m

5 •

The outermost primitive layer of a clan C exists and consists of a single barren family if and only if C is not empty. In this case C is +he outermost primitive layer of C •

Pro.of: Let G be a clan such that C is not empty. As C C. C

,.. ....

,.e

have C -') C , so transitivity· ensures that C is a subset of some family F • But for any A the set A consists of complete families.

A

Therefore C :::: F' and the family F is barren. Obviously C - C is F critical so theorem 2 ensures that the outermost primitive layer of C is

c •

ConverseJy let C be a clan with an outermost primitive layer that. ccn-

- '1 -

sists of a single family F • By definition C - F is either a critical generator of C or the kernel of C • In either case we have C - F ~F and "thereby F C. C • This proves the theorem.

This theorem allowe one to classify clans into the following three types:

""

1) the kernel of the clan C is C itself, and C is emptyj

2) the kernel of the clan C differs from C , +,he outermost primitive

"'

layer contains two or more complete families,

and C

is empty;

3)

the kernel of the clan

C ·

differs from

C ,

the outezmoat primit;t.ve layer consists of a single barren frunily

F , and C = F •

One can easily verify that a barren f'a.mj.ly F can only me.et e. clan C if C is of type i or

if

F forme part of the outermost primitive larer of C • So if ·there is

a.

bal'ren family that meets a clan C without lying within

C ,

then the clc~ is of type

1.

3.

PRODUCTIVE AND llU1'IA1 GENERATORS ·

A ·set of vertices in our graph, A , is se.·~d to be productive if there is a

vertex

x such that A

~(x] ^;

^it

^is

said to be i_niti¥.. if there is !!2 vertex

x f

^.A su<.:h that

{x ^{~ ~}

^{A •}

T h

e o r e m

6 •

A clan C does not have a productive generator if and only if it is oi' type 1.

P r o o f : If C is of type ·1, its only generator is C itself. As C is empty, this gener(l.tor is not a. productive set. Otherwise the outer- most primitive layer of C is defined a.nd can be written as C - B • If C is of type 2, the definitions of kernel and layer ensure that B is a gen- erator. But B is productive since B-) C - B o Finally, if C is of type

3,

it

is

productiv13 as well as being its own generator.

~ 8 ·-

Marcus ((1 P• 105)) classified clans into those without productive

g~1erators, those with

two

or more generators, at least one being productive, .and. those with just one generator but one that was productive. However, it

is now apparent that a clan C in the last of these classes is somewhat pathological; C

must

be a barren family consisting of just one

vertex,

a.ncl C -· C must be the kernel of C •

T h e o r e m

7 •

A necessary and sufficient condition for a. cla.;1 C with a. non-empty kernel K to be initial is for K to be an initial set.

P r o o f : If the clan C is not initial there is a vertex x· -~. C

·such that ~re have · .x ~ K and

K is not initial so

1x. }..,.,.,

^{C • As K is} co11tained in C

f:x~ ...:)

^{K so K is not irtitial. Now suppose that}

we ha.ve a

ved.e.x

x ~ ^K

such that

f x3 ^~)

^K

^~

^{'!'he relation K}

^c.)

^{C - K}

followS from the definitions of kernel, generator and F -critical. Aa K is not empty, transitivity gives

~ :x.J ....

^{C • lf} x were an element of

C , we would ha.ve K With this would imply that

lay in some family and contradict the fa~t that the layer C - K

·contains all of the family F(x) • Thus C is not an initial set, and our theorem is provs:n.

The first part of the above proof gives:

~•an initial set generates ^a.11 in.i.tial clan".

'.fhe .following theorem shOliS that the converse of ~his is nearly true.

T h

e o r e m

8 •

If a non-in.i tial non-empty set A gene,;: :a.tes an initial c:lan C , th.en C has

a.n

e!!lpty kernel and A is a proper subset of a. f&ll.i.ly' F that generates C ..

P r o o f ^o By hypothesis there is a vertex x

~A

euch that

t·x ^{~ ~)}

^{A .. As}

^A~"

^{C - A v.se have ( x}

J--")

^{C .. As C is}

^a.n

- 9-

initial set, this means that X is in C - A and we have A - ' )

lxl

^G

But

{x}...)

^{A and} A . . .

~xl

^together imply that

A~{x}

^.... ,f-\.") ^~..,

eontained in some fa.r-nily F • It now foLlows that ^F generates

c

^i'or

A " ^,,

F =A and A C. ^{F C.F} imply ^F UF ^{:::: AUA} -

c

^By theorem 2 F iti

the smallest critical generator of C and the kernel of C is empty.

4.

l.UNIH.4_L CLANS

In this section the clans tha+. contain no other c:.lan are characterised.

A barren family j s a simple example of such a clan.

D e f • A clan C is mj_ni.mal if there is no other el.J.n co:~-

tained in C •

D

e f Two families, ^F

1 and F2 , ^are said to be 1 n c o m p a r - a b 1 e if neithe:t' F1-') ^F2 nor ^F2^.-')F1 holds.

T h e o r e m 9 • A necessary and sufficient condition for a clan C to be mintma.l is for it either to be a barren family, or to consist of a single vertex from two or more mttt.ually 1ncomp2 .. rable families

satisfying:

fo.c ea.ch i there is an svrt-, that C - F.

1

F

1 , 2 •

F

• ••

P r o o f : The conditio21. i8 clearly suffj_cier/(,. ^Fell' ~1er~essit:r fj_rst suppose that a clan C has tvfO vertices, x and

:r ,

from the sane~ family~

Either C -

l

^{x }} is a. clan or vle have But

C-1xl_, ^{xl

^{implies and C ~F(:x) , s0 F(x)}

is a barren family and thereby a. clan. As Fh) C. C this me<m~l tha.t either C is the barren fami.ly F(x) or ^C.: is not a minimal clan.

Therefore onl;':l· clans C with at most one vertex from any .family need be eonsidered. If C consists of a single vertex x , ^lie have F(x) \JCC.C ::::

~x}

'·

- 10-

so C is a barren family. Flnally let x be any vertex in a. minimal clan C that .is not a. barren .f'.-:.rnily. As above we cP.m10t have

1

G() there must be x: C. C such that

(1 t

>,)

- lx}

is not a clan). Fur·thermore we c.a.nnot have

xRx

for then

t ^x}

^t

c

wo11ld not be a clan*

But

for any y :tn

,.,

-

^{vre have}

^yRx

v

'

awi. transitivity wuuld give x R x if \'fB had

x

R y • Therefore F(x) and F(y) r..re incomparable for any x and y in G , end thE- proof of theorem

9

is c0mplete.

5. THE; SPLITTING OF CLANS

'I'he remainder of this paper is devoted. to tbe aorner."tlnt difficult quF.Jstion of characteris:lng those cllns ths.t can be split i.uto two diajoint clans.

D

e .f • A c.lan is r e d u c :1. b 1 e i.f it ia the union of

two

dis- joint clans~ otherwise

it

is i r r e d u c i b 1 e ..

1 e m m a • Any set of vertices, tba.t eonto.i;'1s a cla.n, is itself a

c1e.n~

P r o o f : Suppose a set of ver'tiees X co:oJ.tains a. clan C F'or

and this ,implies that X is a clan.

Cor o 1 1 a r y·.

A clan is l~educible if and only if i·~.,. contain·3 t\"ro disjoint clans.

Tl:l~ corollary ahowa that a i,'inite clan C is reducible if and only :Lf it cont.aine

two

disjotnt m:in .. i.mal. cla.na for any clan 1:,r:ing in C is .f'i.n.tt e and thereby includes a. min.iJ!'1l.l ^r:]Jm ~ However, the following co,.xnter-

-· 11 -

axampJe shows that this is no longer true if C ic denumerably infinite.

E x a m

p

l e

^~ Suppose there i.s a denumcr.::~ble set of verti·~es

. c ;;::

_"

.... for every

finite set oi' positive integers Further suppose

if J.nd only if , a.nd othe!'ldse

x R y if and only if x

=

^{y •} Clearly C is a

clan,

and a s1ibset S of C is a clan if ·'lnd only if S is iufit;lite. But this implies C contains no mj_n:ma.l cla.n. Even so G is reducible since ^{• • 0}

and are

cla.nsa

It :1 s not difficult to mod5.fy this example to give an irreducible clan

- that conta.ins no minirr.a.l clan ..

The above corollary sho!l'lfl that any clan contair""ing two or more barren families is redu.cible. The follow'lng resi:J.t gives informa.t.icn about clans that c:c·ntair; precisely one ba~rren family •.

T h e o r e m 10 • Suppose tht) clan C contains a single barren fami.ly F • Conaid(-'lr the set:

L

= ~ ^x6

^{C s·uch that} does net. hold

1

a) If L is empty, then ·"' u ifl :ic:-reducible.

b) If both 1 and F' have more than om~ el.0mont, then C is irreducible.

c) If .L is not empty and either L or F has just one. element, then C

is

irreducible :Lf and only l.f C - F is a clan.

p r 0 0 i'

. .

a)

If

^)~ is empty~ WB hav0 G -*) F • Blct this mea,ns

s _.,.)

F

for

a.ny tllllJSCt

s

oi

c

_" Thus ^filly tW'O

clans,

lying in

c , ^both

contain ^1~ and t.herE;•by are not d:La.joint ~

b) We have elem.ents _f1

, _f2

^{i.n F and 1} ₁

'

^{12 in 1}

^Then

f ^f1

^t

^{111 »}

^and

\

^f;2

^{, 12} l ^are

d.t.sjoint sets within

c

_•

But

both

- 12 -

these sets are clans as

.t

^fi

J ... tx 1

impliBs x

f&.

F since f? is barren, and then we do not iHlv·e

~1 1 ^}

^...,

t

^{xJ •}

c) If C- F iB a dan, C can be split: I<' V(C- F). No,,.r eupposA ..

c -

^{F is not a. clan., Since L is} not empty, there is a ve.r.tex. X J aot

:tn

c

J such that

c -

^F

-,\xJ

^~ Tl;lus a. subset qi'

c

ca.a only be

a

clan :i.f it contains

an

elamen{. of F •

If

our subset has no ^elem~=Jnt of L _J it is not disjo:lnt from arJl•· other clP..n in C • Therefore a.ny clan concerned in a splitting ccntains an element ~.:~i' F and an (3loment of L ., As either L or "' ·has only ... a elanent., C is irreducible.

6. TP • .E SET REPRESENTATION

The0rem 10 reduces thE: question of whether or not a clan splits to the connideration of a set S ei·(.her C or C - F that contai.~1s no barren farnily. · Now let us a.ssoc:Lat•a a subset SF of · S with each fami.:i,y F in our graph by:

s

_F such that does not hold

l·

Let

f::

^be the collection of s1:b;1ets of S t.hat a.rise in th:ls · '1-:a.y.

D

e f A. subsot X S is a. ^c h o i {) e. s e t for a. coll0ction of subsets of S if it. (',ontains at least one elem.ent from each set in the collection.

As S contair;s no barren family,- tl1e following (;l:mc..itions on a. subset X arc equi.rd.lent.:

'I) X is a clan,

....

2) X is empty,

J) X is a cboiee Sfl'C for

-~ ..

- 13-

Under the eonditions o.f theorem 10 c, this ensures that the following ere equivalent:

C is reducible;

1) 2) 3)

the collectton , defined by

S = C - F , has a choice eet;

no

set in this collection·

t$ ^{i~ empty.}

Furthermore it is

also apparent tha+: the

follc,l'r.lng conditions

are egui-

valent when S iD a clan

containing··

no barren family:

1) C is

irreducible,

2)

tl

^has two dis,ioiht choice

sets,

3) there is a choice set of

C ^that

^dods

not completely contain apy

of the sets :in

-,s ..

A sufficient condition for such a clan C . to b~ irred11cible is that SOfD.e eat in contains

only

one element. However,

this

condition is not necessary for it ie not satisfied in the ·1oliowing example:

Irreducible

clan: c -- { ^~·

. l ^~

Xz ' x3}·

Collection:

^:::: ... 1 ^(:'

·'

^{.:>2 ,.. t (.•}

⁰³

where

Cl. ,..

J.

-- cwf-1~1}

^{for i :::: 1~ 2,}

³

^•

Little is kno~n ~s to when a collection

~

of aubsete of a

se-t~

^S

~

each with. two or more elements~ has two dist:Lnct choj_c.e sets.. Only in

the

very special case when each aet in

t='

has exactly

two

elemf;,nts is the

solution known. In this case there ia an associated undirectc;;d grap!t on S , defined by:

there is an edgo joining x. ar..d y if and only if there is

a.

aubr;et of S tn

t:

^{tha.t containt? x ar1d} -:1 "

- 14

^.-1

The collection has two disjoint choice sets if and only if the assc- ciated graph is bichromatic - i .. e. its vertices can be divided into

two

groups in

auch

a way that every edge connect

a

the groups.. But by a theorem .'of K6nig. '

((3

P• 31)) a graph is bich:roma.tic if and only if

it

contains no

loop with an odd number of edges.

References

- -

( ( 1))

s

~ .f.Ia..rcus= Sur un modele logique de la. categorie gramma.ticale elementaH'e. I. Rev. Math. Puree Appl. 7 (1962) 91-107.

((2))

s.

Marcus: Sur un mod~le logique de la_ eat6gorie granlna.tica.le elementaff.e• II. Z. Math. Logik Grundla.gen Math. 8 (1962)

.1.39-145•

III. Hev• Math o Puree Appl. 7· ( 1962) 683-691 •

' '

( ( 3))

c.

^Berge: Theorie dee graphee et see applications. Dunod, Paris, 1958a