A Pa icula Type o Non-associa i e Algeb as and G aph Theo y
JUAN N ´
U˜
NEZ, MARITHANIA SILVERO & M. TRINIDAD VILLAR
Uni e si y o Se ille
Depa men o Geome y and Topology
Ap do. 1160. 41080-Se ille
SPAIN
jn [email p o ec ed], sylno [email p o ec ed], [email p o ec ed]
Abs ac : - E olu ion algeb as ha e many connec ions wi h o he ma hema ical ields, like g oup heo y,
s ochas ics p ocesses, dynamical sys ems and o he ela ed ones. The main goal o his pape is o in oduce a
no el non-usual esea ch on Disc e e Ma hema ics ega ding he use o g aphs o sol e some open p oblems
ela ed o he heo y o g aphicable algeb as, which cons i u e a subse o hose algeb as. We show as many
ou ad ances in his ield as o he non sol ed p oblems o be ackled in u u e.
Key–Wo ds: Non-associa i e Algeb as; G aphicable Algeb as; E olu ion Algeb as; E olu ion Ope a o ;
Di ec ed G aphs; Pseudo-g aphs.
1 In oduc ion
In his pape we deal wi h he class o g aphicable algeb as, which cons i u es a subse o he se o e o-
lu ion algeb as. The main goal is o deal wi h he s udy o he pa icula connec ion be ween g aphicable
algeb as and G aph Theo y by adding new esul s o hose al eady known, which can be ound in he inal
chap e o [6], whe e one can also ind ela ed open p oblems, some o which a e sol ed in his pape .
No e ha i supposes o in oduce a no el non usual esea ch on Disc e e Ma hema ics ega ding he use o
g aphs o sol e some open p oblems ela ed o he heo y o non-associa i e algeb as.
The concep o e olu ion algeb a (non-associa i e algeb as sa is ying he condi ion eiej= 0, whene e
ei,eja e wo dis inc basis elemen s) is ela i ely ecen and lies be ween algeb as and dynamical sys ems.
These algeb as, which we e in oduced by J. P. Tian a ound 2004 join o he collabo a o s [3] and la e
appea ed as a book by himsel in 2008 [6], ha e many connec ions wi h o he ma hema ical ields including
g oup heo y, s ochas ics p ocesses, dynamical sys ems, kno heo y, 3-mani olds and o he ela ed ones.
Indeed, hey we e based on he sel - ep oduc ion ule o non-Mendelian gene ics [4].
The s uc u e o he pape is as ollows: Sec ion 2 ecalls some p elimina ies on g aphicable algeb as
and on G aph Theo y. In Sec ion 3 G aph Theo y is used as a ool o ob ain new esul s o hese las algeb as
which allow us o gi e s eps o wa d in he knowledge o he i s ones. Sec ion 4 is de o ed o show some
conclusions o his s udy.
2 P elimina ies
Due o easons o leng h his pape is no o ally sel -con ained. Fo a gene al o e iew on e olu ion
algeb as and on G aph Theo y, he eade can consul , espec i ely, [6, 3] and [1], o ins ance. In any case,
we ecall he e some concep s.
Rega ding e olu ion and g aphicable algeb as, le Ebe an algeb a (no necessa ily associa i e) o e
a ield Kequipped wi h mul iplica ion and le ei, i ∈Λbe a basis o E. Then, eiej=Pk∈Λak
ij ek, o
some ak
ij ∈K, whe e only ini ely many s uc u e cons an s ak
ij a e nonze o o a ixed i, j ∈Λ.Unde
hese condi ions, Tian de ined an e olu ion algeb a like ha e i ying ak
ij = 0, whene e i6=j. Upon
Recen Resea ches in Applied and Compu a ional Ma hema ics
ISBN: 978-1-61804-002-2
72
enaming he s uc u e cons an s, we can w i e eiei=P
j=1 aji ej.As an example, he algeb a Ewi h
basis {e1, e2, e3}and mul iplica ion de ined by e1e1=e1+e2,e2e2=−e1−e2,e3e3=−e2+e3, is an
e olu ion algeb a.
Tian [6] and Tian and Voj -Echo sky [3] p o e ha , in gene al, e olu ion algeb as a e no associa i e,
commu a i e, lexible, no powe -associa i e and ha hey ha e a uni a y elemen i and only i hey a e
nonze o i ial algeb as. I is impo an o no e ha in [6], Tian conside s an elemen in a basis o an
e olu ion algeb a as an allele in gene ics, o a s a e in s ochas ic p ocesses and he asked himsel when a
s a e appea s in he nex s ep o he p ocess.
I Eis an e olu ion algeb a wi h a gene a o se ei|i∈Λ, he linea map L:E7→ E|L(ei) = e2
i=
Pkakiek, o all i∈Λis called he e olu ion ope a o o E.
In his book [6] Tian in oduced he concep o g aphicable algeb a as ollows: a conmu a i e non-
associa i e algeb a Ais called g aphicable i i has a se o gene a o s V={e1, e2, . . . , e }wi h he wo
de ining ela ions e2
i=Pek∈Viek;ei·ej= 0,i6=j;i, j = 1,2, . . . , , whe e Viis a subse o V. I is
immedia e o see ha any g aphicable algeb a Ais an e olu ion algeb a, al hough he con e se is no ue
in gene al.
Wi h espec o G aph Theo y, he p ima y concep s o simple g aph, di ec ed g aph, loop, pseudo-
g aph, mul ig aph, neighbou , deg ee o a e ex in a simple g aph and indeg ee o and ou deg ee o a
e ex in a di ec ed g aph a e supposed o be known.
The concep o he adjacency ma ix o a g aph is e y use ul in his pape . Le Gbe a g aph wi h n
e ices 1, 2, . . . , n. The adjacency ma ix o G, wi h espec o his pa icula lis ing o he e ices o
G, is he n×nma ix M(G) = (mij)whe e he (i, j) h en y mij is he numbe o edges joining he
e ex i o he e ex j.
A well-known esul is he called i s heo em o G aph Theo y o Handshaking Lemma which says
ha o any simple g aph wi h edges and n e ices 1, 2, . . . , n:
n
X
i=1
δ( i) = 2 holds, whe e δ( i)
deno es he deg ee o he e ex i. As an immedia e consequence, in any simple g aph G, he e is an e en
numbe o e ices o odd deg ee. A e sion o his esul ela ed o g aphicable algeb as will be shown in
sec ion 3.
3 G aph Theo y: a ool o s udy g aphicable Algeb as
As we poin ed ou in he In oduc ion we wish o deal wi h he s udy o he pa icula connec ion
be ween g aphicable algeb as and G aph Theo y, using he las one as a ool wi h he pu pose o adding
some new esul s o hose al eady known abou hese algeb as. In any case, we ha e omi ed all o he
p oo s o ou esul s due o easons o leng h. Some o hem can be checked in [5].
3.1 G aphicable algeb as
F om he e on we conside di ec ed g aph maybe wi h loops. Gi en a g aph G= (V, E) he e always
exis s an e olu ion algeb a A(G)associa ed o G.
De ini ion 3.1.[6] Le G= (V, E)be a g aph, Vbe he se o e ices o G,Ebe he se o edges o G.
We de ine an algeb a A(G) = hV|Rias ollows: aking V={e1, e2, . . . , e }as he gene a o se and
R=


e2
i=X
ek∈Γ(ei)
ek;ei·ej= 0,i6=j;
1≤i, j ≤



as he se o de ining ela ions, whe e Γ(ei)is he se o neighbou s o ei.
The algeb a A(G)is an e olu ion algeb a as i can be checked s aigh o wa d. Fo he con e se, in
[6], he e is no de ini ion o g aph associa ed o an e olu ion algeb a A. We ha e de ined his concep in
[5].
Recen Resea ches in Applied and Compu a ional Ma hema ics
ISBN: 978-1-61804-002-2
73
F om p e ious de ini ions, a g aphicable algeb a Ahas associa ed a di ec ed g aph, possibly wi h loops,
G(A)=(V, E), as ollows: Vis he se o gene a o s o he algeb a and Eis he se o edges linking ei
wi h e ices in Γ(ei) o each ei.
Le us ema k ha o a g aphicable algeb a, A, he associa ed g aph o A,G(A), has a bina y adjacency
ma ix.
Ejemplo 3.2. Le Abe he g aphicable algeb a wi h gene a o se {e1, e2, e3, e4}wi h he de ining
ela ions
e2
1=e1+e2
e2
2=e2+e3
e2
3=e3+e4
⇓
L≡




1 0 0 0
1 1 0 0
0 1 1 0
0 0 1 0




⇓
e3e4
e2e1
In [6], he g aphicable algeb as associa ed o he comple e g aphs, he cycles and he pa hs o n e ices,
Kn,Cnand Pn espec i ely, a e illus a ed.
In [5] he g aphicable algeb a associa ed o he wheel g aph Wn=Cn+ is collec ed and in u u e
wo ks we would like o ackle he p oblem o de ining he g aphicable algeb as associa ed o o he amilies
o g aphs such as he Pe e sen g aphs and n-pa i e comple e g aphs. In any case, we would like o no e
ha i is easy o show ha i Ais a g aphicable algeb a and G=G(A)is i s associa ed g aph, hen he
associa ed algeb a o Gis A(G) = A.
The ollowing esul is specially use ul in wo di ec ions: i p o ides a cha ac e iza ion o a g aphica-
ble algeb a in e ms o i s associa ed g aph and, con e sely, a cha ac e iza ion o a g aph in e ms o i s
associa ed e olu ion algeb a. The su icien condi ion is he one collec ed in [6]. We gi e in [5] a mo e
di ec p oo o he necessi y han he one p esen ed by Tian in ha pape [6].
Theo em 3.3. Le A1and A2be wo g aphicable algeb as, G1, G2 hei associa ed g aphs. Then, A1
and A2a e isomo phic i and only i G1and G2a e isomo phic.
Ano he esul in ol ing he concep o e olu ion ope a o o a g aphicable algeb a is he ollowing
Theo em 3.4.[6] Le Gbe a g aph wi h e ex se V={e1, e2, . . . , e },L he e olu ion ope a o o a
g aphicable algeb a A(G)and suppose Ln(ei) = ni1e1+ni2e2+. . . +ni e . Then, nij is he o al
numbe o pa hs wi h leng h n om e ex ei o e ex ej. I nij = 0, o some pai i, j, his means ha
he e is no pa h o leng h nbe ween e ices eiand ejin G.
Recen Resea ches in Applied and Compu a ional Ma hema ics
ISBN: 978-1-61804-002-2
74
The adjacency be ween gene a o s o an e olu ion algeb a is de ined in [6] in e ms o he e olu ion
ope a o o he algeb a. He e, we in oduce he concep o adjacency in g aphicable algeb as by using he
associa ed g aph.
De ini ion 3.5. Le Abe a g aphicable algeb a and G=G(A)i s associa ed g aph. Two gene a o s e
and e0o Aa e said o be adjacen i hei co esponding e ices a e adjacen in G. I Gis a simple g aph,
he deg ee o he gene a o eo Ais he numbe o gene a o s which a e adjacen o e, i is deno ed δ(e).
I Gis a di ec ed g aph wi h loops, he indeg ee ( espec i ely ou deg ee) o he gene a o eo Ais he
indeg ee (ou deg ee) o he co esponding e ex in Gand hey a e deno ed by δi(e)and δo(e) espec i ely.
Recall ha i he gene a o eo Ais sel -adjacen , he loop co esponding o ein Ginc eases +1 in
bo h indeg ee and ou deg ee.
Example 3.6. Fo he algeb a gi en in Example 3.2. we ob ain he ollowing deg ees
gene a o e1e2e3e4
indeg ee 1 2 2 1
ou deg ee 2 2 2 0
I implies ha e2
1=e1+e2, e2
2=e2+e3e2
3=e3+e4.
Le us obse e ha o a simple g aph associa ed o A, he deg ee o a gene a o eis he numbe o
summands in e2. This does no occu in gene al o non simple g aphs.
We also in oduce in g aphicable algeb as (see [5]) he analogous concep s o deg ee sequence o a
simple g aph and he Handshaking Lemma, which says ha he e is an e en o null numbe o e ices o
odd deg ee in any simple g aph. We hink ha om hese no ions many in e es ing esul s could be deduced
in u u e.
Fo ins ance, he i s pa o he ollowing esul is he e sion o he Handshacking Lemma o g aph-
icable algeb as. I needs no p oo .
P oposi ion 3.7. Le Abe a non i ial g aphicable algeb a and G=G(A)i s associa ed g aph. The
ollowing s a emen s hold.
1. I Gis a simple g aph, hen
(a) The e a e an e en (o null) numbe o gene a o s o odd deg ees in A.
(b) The e is a leas one pai o gene a o s o Awhose deg ees a e equal.
2. I Gis a di ec ed g aph, possibly wi h loops, hen he sum o all he indeg ees o he gene a o s o A
equals he sum o all he ou deg ees o he gene a o s o A.
As a co olla y o P oposi ion 3.7 a), we can a i m ha he e is no g aphicable algeb a wi h a simple
g aph associa ed and an odd numbe o gene a o s o odd deg ee.
In g aphicable algeb as can be also in oduced he analogous concep o deg ee sequence o a simple
g aph.
De ini ion 3.8. Le Abe a g aphicable algeb a wi h ngene a o s, G=G(A)i s associa ed simple g aph
and deg ees d1≥d2≥. . . ≥dn, hen he n− uple (d1, d2, . . . , dn)is called he deg ee sequence o A. A
non necessa ily s ic ly dec easing in ege sequence Dis said o be ealizable i he e exis s a g aphicable
algeb a whose deg ee sequence is D.
Al hough he deg ee sequence is a g aph in a ian , i does no , in gene al, uniquely iden i y a g aph; in
some cases, non-isomo phic g aphs can ha e he same deg ee sequence.
Fo g aphicable algeb as we can deduce he same ac , bu i is in e es ing o use he Ha el-Hakimi
algo i hm ([2]) o ind ou he amily o g aphicable algeb as o a gi en dimension and simple associa ed
g aphs.
Recen Resea ches in Applied and Compu a ional Ma hema ics
ISBN: 978-1-61804-002-2
75
One p ocess o ob aining a se o g aphicable algeb as o dimension ncan be scke ched as ollows
1. Le D= (d1, d2, . . . , dn)be an n− uple o non necessa ily s ic ly dec easing in ege s.
2. Apply he Ha el-Hakimi algo i hm ([2]) o decide i Dis he sequence deg ee o a simple g aph G.
(a) I Dis he sequence deg ee o a g aph G, hen do s ep 3.
(b) I Dis no he sequence deg ee o any g aph G, hen he e does no exis a g aphicable algeb a
wi h sequence deg ee D.
3. Fo each g aph Gwi h sequence deg ee D, conside he adjacency ma ix M(G)and he co espond-
ing g aphicable algeb a A(G)whose e olu ion ope a o is gi en by M(G).
3.2 The e olu ion ope a o
In [6], he e olu ion ope a o L, o a g aphicable algeb a Ais used as a ool o s udy some p ope ies
o he g aph Gsuch ha A(G) = A. In his pape , we in oduce he no ion o he g aph de e mined by an
e olu ion algeb a by using he e olu ion ope a o o such an algeb a. We hink ha his concep could be
app op ia e o be used when dealing wi h non-associa i e algeb as in gene al.
De ini ion 3.9. Le Ebe an e olu ion algeb a wi h ini e gene a o se {ei|i= 1,2, . . . , n}and le
L:E 7→ E | L(ei) = e2
i=Pkakiek, o all i= 1,2, . . . , n be i s e olu ion ope a o . The associa ed
g aph o E,G(E), is he weigh ed g aph wi h e ex se V(E) = { 1, 2, . . . , n}and adjacency ma ix
(aki), k, i ∈ {1,2, . . . , n}.
Example 3.10. Le Lbe he e olu ion algeb a gi en by he ollowing ela ions
e2
1=e2
e2
2= 2 e2+e3
e2
3=e3+ 2 e4
e2
4=−e1
The adjacency ma ix o G(L)is gi en by




0 0 0 −1
1 2 0 0
0 1 1 0
0 0 2 0




⇓
e3
e4
e2
e1
−1
2
2
Recen Resea ches in Applied and Compu a ional Ma hema ics
ISBN: 978-1-61804-002-2
76

4 Conclusions
Al hough in his pape we ha e used G aph Theo y as a ool o deal wi h g aphicable algeb as as
a p e ious s ep o ackle, in a simila way, he s udy o e olu ion algeb as, mo e esul s on g aphicable
algeb as can be ob ained in u u e. Indeed, in [5] can be checked some ad ances in his esea ch.
Apa om ha and as Tian says in [6], ano he ques ion one should dig in o i s is whe he e e y
s a emen o p oblem in g aph heo y can be ansla ed in o he language o e olu ion algeb as. I his is
indeed he case, we will ha e a b and new algeb aic g aph heo y and i will b ing, wi h no doub , new and
signi ican p ospec in s udying compu e science.
As we also know a p esen , non-associa i e algeb as in gene al a e no easy o s udy. We hink ha
G aph Theo y can also p o ide a ool o s udy hem by using g aphicable and e olu ion algeb as in a simila
way as he one indica ed he e. This is because he e is a na u al co espondence be ween e olu ion algeb as
and di ec g aphs.
Finally, as he ma hema ical objec s o gene ic e olu ion a e disc e e spaces o g aph-like spaces, i
is na u al o hink ha he s udy o he connec ion be ween e olu ions algeb as and G aph Theo y could
be ele an , since he u ili y o e olu ion algeb as in gene ic e olu ion. This is ano he o he many open
p oblems in he s udy o bo h he applica ions and he unde s anding o he signi icance o hese algeb as
in na u al phenomena.
Re e ences:
[1] Cla k, John and Hol on, De ek Allan. A i s look a G aph Theo y, Wo ld Scien i ic, 1991.
[2] Hakimi, S. L., On he ealizabili y o a se o in ege s as deg ees o e ices o a g aph. SIAM J. Appl.
Ma h. 10 (1962), 496-506.
[3] Jianjun Paul Tian and Pe Voj -Echo sky, Ma hema ical concep s o e olu ion algeb as in non-
mendelian gene ics, Quasig oups Rela ed Sys ems 14:1 (2006), 111-122.
[4] Isaacson, Dean and Madsen, Richa d. Ma ko Chains Theo y and Applica ions, John Wiley and Sons,
New Yo k, 1976.
[5] N´
u˜
nez, Juan, Sil e o, Ma i hania and Villa , M. T inidad, G aph Theo y: a ool o s udy e olu ion
algeb as. P ep in .
[6] Tian, Jiajun Paul, E olu ion Algeb as and hei Applica ions, Lec u e No es in Ma hema ics, Vol 1921.
Sp inge -Ve lag, Be l´
ın, 2008.
Recen Resea ches in Applied and Compu a ional Ma hema ics
ISBN: 978-1-61804-002-2
77