UNORDERED LOVE IN INFINITE DIRECTED GRAPHS

Internat. J. Math. & Math. Sci VOL. 15 NO. 4 (1992) 753-756

753

UNORDERED LOVE IN INFINITE DIRECTED GRAPHS

PETER D. JOHNSON, JR.

Department

ofAlgebra,Combinatorics, and Analysis Auburn University

Auburn,Alabama 36849

(Received

September4,

1990)

ABSTRACT. A

digraph D (V,A) has the Unordered

Love Property (ULP)

^{if any} two different verticeshave auniquecommonoutneighbor. If both (V,A) and (V,A-

1)

have theULP,wesaythat Dhas theSDULP.

A

love-masterin D isa vertex0 connected bothways to everyother vertex, suchthat D-v0 is/adisjointunionofdirectedcycles.

The following results, more or less well-known for finite digraphs, are proven here for D infinite:

(i)

ifD islooplessand has the

SDULP,

theneither Dhasalove-master,orD isassociable witha projectiveplane,obtainablebytaking

v

as the set of points and the sets ofoutneighborsof verticesasthelines;

(ii)

everyprojectiveplanearisesfromadigraph^withthe

SDULP,

inthis way.

KEY

WORDS

AND PHRASES.

Digraph, projectiveplane,friendshipgraph.

1991

AMS SUBJECT CLASSIFICATION CODES.

Primary05C20, Secondary51A05.

1. INTRODUCTION.

Throughout, D (V,A),AC_ VxV, will be a directedgraph. Loosely followingthe terminology faetiously introduced by Hammersley

[4],

^{we will} say that Dhas the Unordered

Love Property (abbreviated ULP)

if u,,EV and u# imply the existence of a unique t=t(u,) such that (u,t),(,w)E^A. Hammersley mainlyconsiders theunfortunately named Self-Dual Unordered Love

Property (SDULP),

in which both (V,A) and

(V,A-1)

have the

ULP.

Both properties are analogues of the friendship property in undirected graphs, the finite possessors of whichare thefamous friendshipgraphs

[10].

^Thereasonfor the word "unordered" is the role of unordered pairs in the definition. There isalso an Ordered Love

Property

definedby Hammersley, in which for eachorderedpair (u,v)

v

xV, ifu# then thereisa uniquer Vsuch that (u, w), (t, v) A.

We

shall not consider this property here, but remark that it should not be confused with the more exigent requirement satisfied by Knuth’s

[6]

digraph realizations of the central groupoids of

Evans [3],

^{in which}the requirement that u$v isomittedfrom thedefinition.

Thus Knuth’s digraphs are among Hammersley’s

(with

^the

OLP),

and it turns out that the containment isproper. Sofarasweknow,there has notyet beenanyinvestigation beyond Knuth’s of the liaison between digraphs with the

OLP, ULP,

or SDULP, andalgebraic structures like the centralgroupoids.

754 P.D. JOHNSON, JR.

Hammersley

[4]

^{makes the connectionbetween} finitedigraphswith theSDULP and projective planes (or degenerate projective planes. However, perhaps because he is greatly concerned with loops, he misses the fact that inlooplessfinite digraphs, theULP implies the SDULP. This, and the conclusionof Theorem 1, below, for finite loopless digraphs with the

ULP,

follow easily from the famous theorem of de Bruijn and Erd6s

[2]

^{or its} improvement by

Ryser [8]. In

theinfinite case, ^a

moment’s

thought shows thatlooplessness andthe

ULP

do not imply the

SDULP,

northe conclusion of Theorem 1. The loopless infinite digraphs with the ULP do not form such a neat package;thispaper isabout suchgraphswiththe

SDULP,

whichdo.

The analogue of Theorem 2, below, for the finite projective planes follows easily from the existence of perfect matchings in finite regular bipartite graphs

(see [1],

Chapter

8);

^{by such a} matchingwematch the points andlinesofafiniteprojectiveplaneso that the matched points and linesarenot incident, and then proceed^asinthe proof of Theorem2.

2.

DEFINITIONS.

Suppose

^thatD (V,A)^isadirectedgraph. ForvEV, t,(v) {u V;(u,O a},

Out(v) {ueV;(v,u)eA}, and,following

[1],

id(v) In(v) the cardinality of In(v), and od(v) IOut(v)

IfDhas the

ULP,

let e(u,v) denote the unique member of Out(u)nOut(v),foru,v.V,u#^v.

A

vertex

v0v

^{is a} love-master in G if (u,

v0),(v0,u)A

^{for each}

uEV\{v0},

^{and D-v}₀ ^{is a}

disjointunionofdirectedcyclesoflength >2.

In

caseV isinfinite,weallowas adirectedcycleany infinite path isomorphic to the digraph with integers ^as vertices, and directed edges (n,n

+

1), for eachintegern.

3. MAIN

RESULTS.

THEOREM 1.

Suppose

that D=(V,A) is alooplessinfinite digraphwith the SDULP. Then either

(a)

^somev₀^eVisalove-masterinO or

(b)

^{if we} take a#=

v,

{Out(v);ve v} and as the incidence relation between points and lines, then(,L, isaprojectiveplane.

THEOREM

2.

Suppose

that 2 (,L, is an infinite projective plane. Then there is an infiniteloopless digraph D (V,A) with the SDULP suchthat the projectiveplaneassociated with DasinTheorem

l(b)

^isisomorphicto

z.

4. PROOFS.

LEMMA

1.

Suppose

that D=(V,A) ^is a digraph with the

ULP,

u,vV, and (u,v).^A. Then d(,,)<_od(,O.

PROOF’.

The map l:ln(v)--.Out(u) defined by l(w)= (u,w)^is well defined,since u In(v). If

Wl,W2

_

^{In(v) andw}

_.

w2, then {v}

Out(wl)flOut(w2).

^Since

f(wi) Out(wi),i

^{1,2, andv} Out(u),^it followsthat

Y(Wl) I(w2).

^Thus

^!

^isaninjection of In(v)intoOut(u).

COROLLARY

1. IfD (V,A)isaloopless digraphwiththe

SDULP,

then id(v)=od(v)foreach vGV.

PROOF. Takeu vinLemma1.

LEMMA

2.

Suppose

that D (V,A)isalooplessinfinitedigraphwiththe

SDULP;

thenv0 GV is alove-masterin D ifandonlyif

In(vo)= V\{v0}.

PROOF. ^The"onlyif’ assertion is trivial.

UNORDERED LOVE IN INFINITE DIRECTED GRAPHS 7

We shallseethat

ln(vo)= V\{vO}

^impliesthat

Out(Vo)= v\{vo}. ^Suppose

^that

v/V\{vo}.

^Since

(V,A

-1)

^{has the}

ULP, In(Vo)nln(v)={u},

^{for some uC{v,}

v0}

^and ln(v)r31n(u)={u,}, ^{for some}

we

^{{u,v}. If}w#^v₀^thenweV\{v

O} In(vO),

^whichimplies that

, In(vo)Oln(v)=

{u}, whence,=u, anabsurdity.

Therefore,

^v₀ ^w In(v), sov

Out(VO).

^{Since v}

V\{v0}

^{wasarbitrary,it}follows that

0(0)

^v\

0).

It

remains to be seen that D-v₀ is the disjoint union of directed cycles, of length >2

(including, possibly, two-sidedly infinite directed paths). Observe that, for

Out(v)=

{v0,0(v, v0)

^{}, since v has}

^exactly

^{one common} outneighbor with v0 and

Out(v0)= v\{v0}.

Similarly, In(v) has exactly one member beside v

0. Thus

idD_vo(V)=OdD_vo(V)=

^{I. The}

remainderof theproofis easy.

LEMMA

^3.

Suppose

that D (V,A)is alooplessinfinite digraph ^with the

SDULP,

and u

v

hasfiniteoutdegreeorindegree. ThenDhasalove-master.

PROOF. By

Corollary 1, id(u)=oct(u)<^oo. Since each v V\{u} has ^a commonoutneighbor with u, and

v

isinfinite, Out(u)finite,^{some v}₀ Out(u) must haveinfiniteindegree.

By Lemma

I,

w

In(v0)

^{for every w}

v

withid(w)=od(w) finite.

By

Lemma 2, it sufficesto show that v 0 is the onlyvertexof infiniteindegree.

If v v0 is another vertex of infinite indegree, then, by

Lemma

1 again, w

In(Vl)

^whenever

id(w)=od(w)<oo. Thus therecanbeat mostonesuchw, since

lln(vO)fIn(Vl)

^I.

^But

^thereare

infinitely many such w, since, by

Lemma

1 again, ^if weV\Out(u), then id(w)<_od(u)<oo. This contradiction shows thatnosuchv exists,^sov₀isalove-master.

LEMMA

4.

Suppose

ageometry

z

(,, satisfies

(i)

any two distinct pointsareincidentwithexactlyoneline,

(ii)

^anytwodistinct linesareincident withexactlyonepoint, and

(iii)

each lineisincident to at least three points, and thereareatleast two lines.

ThenZis aprojectiveplane.

Theproofisstraightforward,andisomitted.

PROOF OF

THEOREM

1.

By

Lemma^3, wemayas wellassumethat id(u)= od(u)isinfinite foreachu V. Let ^g (@,, beasin

(b).

^{Zsatisfiescondition}

(i)

^ofLemma4 because (V,A-

I)

has the

ULP,

condition

(ii)

because (V,A) has the

ULP,

and condition

(iii)

because od(u)isinfinite foreachu V. Thus^gisaprojectiveplane.

LEMMA

5.

Every

infinite

regular

bipartite graph with infinite

degree

^{admits a} perfect matching.

PROOF.

Thisis an easyapplicationofatheoremof K6nig

[7,

p.

221]. See

also

[9,

^p.

142].

PROOF

OF THEOREM 2. We form a bipartite

graph

G with bipartition @,/. by defining PLe E(G) if andonly ifP L

(i.e.,

the point Pandtheline L are not

incident).

Gclearlysatisfies the hypothesis of

Lemma

5, and so admits a perfect matching.

Therefore,

there is a bijection

:-,

such that P #(P) for each Pe

.

Define D=(V,A) be setting^V @ and (P.()e A ifand only if e#(P). The condition P #(P) implies that Dhas noloops. The bijectivity of and the two-points-determine-a-line, two-lines-determine-a-point properties of Z imply, respectively, that

(V,A-I)

and (V,A) have the

ULP.

If each lineofZ is identified with the set of points onit, then thelines ofZ arethe same asthe lines of the projectiveplaneassociated with D; thepoints of the twoplanesarealreadythesame,andtheincidencerelations become identical.

5.

REMARKS AND

PROBLEMS.

A

digraph D=(V,A)is anti-symmetric, ororiented,if and onlyif (u,v)Aimplies that (v,u)A, for allu,veV. Notethatanorienteddigraphisnecessarilyloopless.

756 P.D. JOHNSON, JR.

PROBLEM 1. Is every projective plane associated,^as in Theorem l(b) and Theorem 2, with anoriented digraphwith theSDULP?

The analogue of Theorem 2 for finite projective planessays that. every finite projective plane has an incidence matrix B with tr(B)=O. If theanswer toProblem l’s question is yes, thenevery finiteprojective plane has anincidence matrix Bsatisfyingtr{B

2)

^0.

It

is clearthat ifD (V,A) hasalove-master, thenD isisomorphic, as adigraph, to

(V,A-1).

When (V,A) has theSDULP andisassociated with aprojectiveplane

z,

then

(V,A-1)

^{is associated}

withaplane isomorphic tothe dualz*of

z. ["In"

^isabijectionfromthelinesofz* tothelinesof theplane associated with

(V,A-1),

and "Out" is a bijection from the points of the

(V,A-1)

plane to the points of

z*;

the fact that uEIn(v) iff^vq.Out(u) says that these correspondences preserve

incidence.]

Since there areprojective planes, both finite and infinite, which arenot isomorphic to their duals

(see [5]),

^{it follows from} Theorem 2 that there exist both finite and infinite loopless digraphs(V,A)withtheSDULP which are notisomorphicto

(V,A-1).

PROBLEM

2.

Are

there any projectiveplanes

z

for which anydigraph D (V,A) associated with

z

asin Theorem 2isisomorphic to (V,A-

1)?

PROBLEM 3. Arethereanyprojectiveplanesforwhichthereis onlyoneloopless digraph,up toisomorphism,associated with theplane,asinTheorem 2?

ACINOWLEDGEMENT.

My thanks to John Fink, Crispin Nash-Williams, Luc Teirlinck, and especially,DeanHoffman,for settingmestraightonvariousmatters connectedwith this paper. All

errorsandinfelicities aremyown.

REFERENCES

i.

BEHZAD,

M.

CHARTRAND, G.;

^and

LESNIAK-FOSTER, L.,

Graphand Digraphs,Prindle, Weber,

&

Schmidt InternationalSeries,

Boston,

1979.

2.

DE BRUIJN,

N.G. and

ERD(S, P.,

On acombinatorial problem,^{IVederl.Akad.Wetensch.Proc.}

Sect.Sci.51

(1948),

^1277-1279.

EVANS, T.,

Products of points somesimplealgebrasand theiridentities, Am. Math. Monthly 74

(1967),

^362-372.

HAMMERSLEY, J.M.,

The .friendship theorem and the love problem,

Surveys

in Combinatorics

(invited

papers for the ninth British Combinatorial

Conference, 1983),

London Math.

Soc. Lecture

NoteSeries82,pp. 32-54, CambridgeUniversity

Press,

Cambridge-London New York,1983.

5.

HUGHES, D.R.

and

PIPER, F.C.,

ProjectivePlanes, Springer,

New

York-Heidelberg-Berlin, 1973.

6.

KNUTH, D.E.,

Notesoncentral groupoids,J.Comb.Theory8

(1970),

376-390.

7.

K(NIG, D.,

Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgesellschaft, Leipzig, 1936.

8.

RYSER, H.J., An

extensionofatheorem of de Bruijn and ErdSs oncombinatorialdesigns, ^J.

Algebra10

(1968),

^246-261.

9.

THOMASSEN, C.,

_In.finite Graphs, Chap. 5, pp. 129-160, "Selected Topics in Graph Theory

II’,

ed. L. W.Beinekeand

R.J.

Wilson,Academic

Press,

1983.

10.

WILF, H.S.,

The .friendship theorem, Combinatorial Math. and Its Applications,

Proc.

ofthe OxfordConference, 1969, Academic

Press,

London

(1971),

307-309.