A particular type of non-associative algebras and graph theory

A Particular Type of Non-associative Algebras and Graph Theory JUAN N ´ U˜ NEZ, MARITHANIA SILVERO & M. TRINIDAD VILLAR University of Seville Department of Geometry and Topology Aptdo. 1160. 41080-Seville SPAIN jnv[email protected], sylnov[email protected], [email protected] Abstract: - Evolution algebras have many connections with other mathematical fields, like group theory, stochastics processes, dynamical systems and other related ones. The main goal of this paper is to introduce a novel non-usual research on Discrete Mathematics regarding the use of graphs to solve some open problems related to the theory of graphicable algebras, which constitute a subset of those algebras. We show as many our advances in this field as other non solved problems to be tackled in future. Key–Words: Non-associative Algebras; Graphicable Algebras; Evolution Algebras; Evolution Operator; Directed Graphs; Pseudo-graphs. 1 Introduction In this paper we deal with the class of graphicable algebras, which constitutes a subset of the set of evolution algebras. The main goal is to deal with the study of the particular connection between graphicable algebras and Graph Theory by adding new results to those already known, which can be found in the final chapter of [6], where one can also find related open problems, some of which are solved in this paper. Note that it supposes to introduce a novel non usual research on Discrete Mathematics regarding the use of graphs to solve some open problems related to the theory of non-associative algebras. The concept of evolution algebra (non-associative algebras satisfying the condition eiej= 0, whenever ei,ejare two distinct basis elements) is relatively recent and lies between algebras and dynamical systems. These algebras, which were introduced by J. P. Tian around 2004 joint other collaborators [3] and later appeared as a book by himself in 2008 [6], have many connections with other mathematical fields including group theory, stochastics processes, dynamical systems, knot theory, 3-manifolds and other related ones. Indeed, they were based on the self-reproduction rule of non-Mendelian genetics [4]. The structure of the paper is as follows: Section 2 recalls some preliminaries on graphicable algebras and on Graph Theory. In Section 3 Graph Theory is used as a tool to obtain new results of these last algebras which allow us to give steps forward in the knowledge of the first ones. Section 4 is devoted to show some conclusions of this study. 2 Preliminaries Due to reasons of length this paper is not totally self-contained. For a general overview on evolution algebras and on Graph Theory, the reader can consult, respectively, [6, 3] and [1], for instance. In any case, we recall here some concepts. Regarding evolution and graphicable algebras, let Ebe an algebra (not necessarily associative) over a field Kequipped with multiplication and let ei, i ∈Λbe a basis of E. Then, eiej=Pk∈Λak ij ek,for some ak ij ∈K, where only finitely many structure constants ak ij are nonzero for a fixed i, j ∈Λ.Under these conditions, Tian defined an evolution algebra like that verifying ak ij = 0, whenever i6=j. Upon Recent Researches in Applied and Computational Mathematics ISBN: 978-1-61804-002-2 72 renaming the structure constants, we can write eiei=Pv j=1 aji ej.As an example, the algebra Ewith basis {e1, e2, e3}and multiplication defined by e1e1=e1+e2,e2e2=−e1−e2,e3e3=−e2+e3, is an evolution algebra. Tian [6] and Tian and Vojt-Echovsky [3] prove that, in general, evolution algebras are not associative, commutative, flexible, not power-associative and that they have a unitary element if and only if they are nonzero trivial algebras. It is important to note that in [6], Tian considers an element in a basis of an evolution algebra as an allele in genetics, or a state in stochastic processes and he asked himself when a state appears in the next step of the process. If Eis an evolution algebra with a generator set ei|i∈Λ, the linear map L:E7→ E|L(ei) = e2 i= Pkakiek, for all i∈Λis called the evolution operator of E. In his book [6] Tian introduced the concept of graphicable algebra as follows: a conmutative nonassociative algebra Ais called graphicable if it has a set of generators V={e1, e2, . . . , er}with the two defining relations e2 i=Pek∈Viek;ei·ej= 0,i6=j;i, j = 1,2, . . . , r, where Viis a subset of V. It is immediate to see that any graphicable algebra Ais an evolution algebra, although the converse is not true in general. With respect to Graph Theory, the primary concepts of simple graph, directed graph, loop, pseudograph, multigraph, neighbour, degree of a vertex in a simple graph and indegree of and outdegree of a vertex in a directed graph are supposed to be known. The concept of the adjacency matrix of a graph is very useful in this paper. Let Gbe a graph with n vertices v1, v2, . . . , vn. The adjacency matrix of G, with respect to this particular listing of the vertices of G, is the n×nmatrix M(G) = (mij)where the (i, j)th entry mij is the number of edges joining the vertex vito the vertex vj. A well-known result is the called first theorem of Graph Theory or Handshaking Lemma which says that for any simple graph with redges and nvertices v1, v2, . . . , vn: n X i=1 δ(vi) = 2rholds, where δ(vi) denotes the degree of the vertex vi. As an immediate consequence, in any simple graph G, there is an even number of vertices of odd degree. A version of this result related to graphicable algebras will be shown in section 3. 3 Graph Theory: a tool to study graphicable Algebras As we pointed out in the Introduction we wish to deal with the study of the particular connection between graphicable algebras and Graph Theory, using the last one as a tool with the purpose of adding some new results to those already known about these algebras. In any case, we have omitted all of the proofs of our results due to reasons of length. Some of them can be checked in [5]. 3.1 Graphicable algebras From here on we consider directed graph maybe with loops. Given a graph G= (V, E)there always exists an evolution algebra A(G)associated to G. Definition 3.1.[6] Let G= (V, E)be a graph, Vbe the set of vertices of G,Ebe the set of edges of G. We define an algebra A(G) = hV|Rias follows: taking V={e1, e2, . . . , er}as the generator set and R=   e2 i=X ek∈Γ(ei) ek;ei·ej= 0,i6=j; 1≤i, j ≤r    as the set of defining relations, where Γ(ei)is the set of neighbours of ei. The algebra A(G)is an evolution algebra as it can be checked straightforward. For the converse, in [6], there is no definition of graph associated to an evolution algebra A. We have defined this concept in [5]. Recent Researches in Applied and Computational Mathematics ISBN: 978-1-61804-002-2 73 From previous definitions, a graphicable algebra Ahas associated a directed graph, possibly with loops, G(A)=(V, E), as follows: Vis the set of generators of the algebra and Eis the set of edges linking ei with vertices in Γ(ei)for each ei. Let us remark that for a graphicable algebra, A, the associated graph to A,G(A), has a binary adjacency matrix. Ejemplo 3.2. Let Abe the graphicable algebra with generator set {e1, e2, e3, e4}with the defining relations 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], the graphicable algebras associated to the complete graphs, the cycles and the paths of nvertices, Kn,Cnand Pnrespectively, are illustrated. In [5] the graphicable algebra associated to the wheel graph Wn=Cn+vis collected and in future works we would like to tackle the problem of defining the graphicable algebras associated to other families of graphs such as the Petersen graphs and n-partite complete graphs. In any case, we would like to note that it is easy to show that if Ais a graphicable algebra and G=G(A)is its associated graph, then the associated algebra to Gis A(G) = A. The following result is specially useful in two directions: it provides a characterization of a graphicable algebra in terms of its associated graph and, conversely, a characterization of a graph in terms of its associated evolution algebra. The sufficient condition is the one collected in [6]. We give in [5] a more direct proof of the necessity than the one presented by Tian in that paper [6]. Theorem 3.3. Let A1and A2be two graphicable algebras, G1, G2their associated graphs. Then, A1 and A2are isomorphic if and only if G1and G2are isomorphic. Another result involving the concept of evolution operator of a graphicable algebra is the following Theorem 3.4.[6] Let Gbe a graph with vertex set V={e1, e2, . . . , er},Lthe evolution operator of a graphicable algebra A(G)and suppose Ln(ei) = ni1e1+ni2e2+. . . +nirer. Then, nij is the total number of paths with length nfrom vertex eito vertex ej. If nij = 0, for some pair i, j, this means that there is no path of length nbetween vertices eiand ejin G. Recent Researches in Applied and Computational Mathematics ISBN: 978-1-61804-002-2 74 The adjacency between generators of an evolution algebra is defined in [6] in terms of the evolution operator of the algebra. Here, we introduce the concept of adjacency in graphicable algebras by using the associated graph. Definition 3.5. Let Abe a graphicable algebra and G=G(A)its associated graph. Two generators e and e0of Aare said to be adjacent if their corresponding vertices are adjacent in G. If Gis a simple graph, the degree of the generator eof Ais the number of generators which are adjacent to e, it is denoted δ(e). If Gis a directed graph with loops, the indegree (respectively outdegree) of the generator eof Ais the indegree (outdegree) of the corresponding vertex in Gand they are denoted by δi(e)and δo(e)respectively. Recall that if the generator eof Ais self-adjacent, the loop corresponding to ein Gincreases +1 in both indegree and outdegree. Example 3.6. For the algebra given in Example 3.2. we obtain the following degrees generator e1e2e3e4 indegree 1 2 2 1 outdegree 2 2 2 0 It implies that e2 1=e1+e2, e2 2=e2+e3e2 3=e3+e4. Let us observe that for a simple graph associated to A, the degree of a generator eis the number of summands in e2. This does not occur in general for non simple graphs. We also introduce in graphicable algebras (see [5]) the analogous concepts of degree sequence of a simple graph and the Handshaking Lemma, which says that there is an even or null number of vertices of odd degree in any simple graph. We think that from these notions many interesting results could be deduced in future. For instance, the first part of the following result is the version of the Handshacking Lemma for graphicable algebras. It needs no proof. Proposition 3.7. Let Abe a non trivial graphicable algebra and G=G(A)its associated graph. The following statements hold. 1. If Gis a simple graph, then (a) There are an even (or null) number of generators of odd degrees in A. (b) There is at least one pair of generators of Awhose degrees are equal. 2. If Gis a directed graph, possibly with loops, then the sum of all the indegrees of the generators of A equals the sum of all the outdegrees of the generators of A. As a corollary of Proposition 3.7 a), we can affirm that there is no graphicable algebra with a simple graph associated and an odd number of generators of odd degree. In graphicable algebras can be also introduced the analogous concept of degree sequence of a simple graph. Definition 3.8. Let Abe a graphicable algebra with ngenerators, G=G(A)its associated simple graph and degrees d1≥d2≥. . . ≥dn, then the n−tuple (d1, d2, . . . , dn)is called the degree sequence of A. A non necessarily strictly decreasing integer sequence Dis said to be realizable if there exists a graphicable algebra whose degree sequence is D. Although the degree sequence is a graph invariant, it does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs can have the same degree sequence. For graphicable algebras we can deduce the same fact, but it is interesting to use the Havel-Hakimi algorithm ([2]) to find out the family of graphicable algebras of a given dimension and simple associated graphs. Recent Researches in Applied and Computational Mathematics ISBN: 978-1-61804-002-2 75 One process of obtaining a set of graphicable algebras of dimension ncan be scketched as follows 1. Let D= (d1, d2, . . . , dn)be an n−tuple of non necessarily strictly decreasing integers. 2. Apply the Havel-Hakimi algorithm ([2]) to decide if Dis the sequence degree of a simple graph G. (a) If Dis the sequence degree of a graph G, then do step 3. (b) If Dis not the sequence degree of any graph G, then there does not exist a graphicable algebra with sequence degree D. 3. For each graph Gwith sequence degree D, consider the adjacency matrix M(G)and the corresponding graphicable algebra A(G)whose evolution operator is given by M(G). 3.2 The evolution operator In [6], the evolution operator L, of a graphicable algebra Ais used as a tool to study some properties of the graph Gsuch that A(G) = A. In this paper, we introduce the notion of the graph determined by an evolution algebra by using the evolution operator of such an algebra. We think that this concept could be appropriate to be used when dealing with non-associative algebras in general. Definition 3.9. Let Ebe an evolution algebra with finite generator set {ei|i= 1,2, . . . , n}and let L:E 7→ E | L(ei) = e2 i=Pkakiek, for all i= 1,2, . . . , n be its evolution operator. The associated graph to E,G(E), is the weighted graph with vertex set V(E) = {v1, v2, . . . , vn}and adjacency matrix (aki), k, i ∈ {1,2, . . . , n}. Example 3.10. Let Lbe the evolution algebra given by the following relations e2 1=e2 e2 2= 2 e2+e3 e2 3=e3+ 2 e4 e2 4=−e1 The adjacency matrix of G(L)is given by     0 0 0 −1 1 2 0 0 0 1 1 0 0 0 2 0     ⇓ e3 e4 e2 e1 −1 2 2 Recent Researches in Applied and Computational Mathematics ISBN: 978-1-61804-002-2 76 4 Conclusions Although in this paper we have used Graph Theory as a tool to deal with graphicable algebras as a previous step to tackle, in a similar way, the study of evolution algebras, more results on graphicable algebras can be obtained in future. Indeed, in [5] can be checked some advances in this research. Apart from that and as Tian says in [6], another question one should dig into first is whether every statement or problem in graph theory can be translated into the language of evolution algebras. If this is indeed the case, we will have a brand new algebraic graph theory and it will bring, with no doubt, new and significant prospect in studying computer science. As we also know at present, non-associative algebras in general are not easy to study. We think that Graph Theory can also provide a tool to study them by using graphicable and evolution algebras in a similar way as the one indicated here. This is because there is a natural correspondence between evolution algebras and direct graphs. Finally, as the mathematical objects of genetic evolution are discrete spaces or graph-like spaces, it is natural to think that the study of the connection between evolutions algebras and Graph Theory could be relevant, since the utility of evolution algebras in genetic evolution. This is another of the many open problems in the study of both the applications and the understanding of the significance of these algebras in natural phenomena. References: [1] Clark, John and Holton, Derek Allan. A first look at Graph Theory, World Scientific, 1991. [2] Hakimi, S. L., On the realizability of a set of integers as degrees of vertices of a graph. SIAM J. Appl. Math. 10 (1962), 496-506. [3] Jianjun Paul Tian and Petr Vojt-Echovsky, Mathematical concepts of evolution algebras in nonmendelian genetics, Quasigroups Related Systems 14:1 (2006), 111-122. [4] Isaacson, Dean and Madsen, Richard. Markov Chains Theory and Applications, John Wiley and Sons, New York, 1976. [5] N´ u˜ nez, Juan, Silvero, Marithania and Villar, M. Trinidad, Graph Theory: a tool to study evolution algebras. Preprint. [6] Tian, Jiajun Paul, Evolution Algebras and their Applications, Lecture Notes in Mathematics, Vol 1921. Springer-Verlag, Berl´ ın, 2008. Recent Researches in Applied and Computational Mathematics ISBN: 978-1-61804-002-2 77