A Kunneth Formula for Finite Sets?

Chong WANG Shiquan REN Jian LIU

Abstract In this paper, the authors define the homology of sets, which comes from and contains the ideas of path homology and embedded homology. Moreover, A K¨unneth formula for sets associated to the homology of sets is given.

Keywords K¨unneth formula, Finite set,Principal ideal domain,Cartesian product,Free R-module

1 Introduction

LetRbe a commutative ring with unit, and let (C,?) be a complex of finitely generated freeR-modules of rankn. LetX={x1,···,xn} be a finite set. Then there is a natural map

wheree1,···,enis a basis ofC. For the sake of simplicity, we denoteC=(R[X],?). LetSbe a graded subR-module ofC. Let Inf?(S,C)=(S∩??1S,?). Then Inf?(S,C) is a subcomplex ofC.

Definition 1.1Let Y be a subset of X, and let R[Y]be a free R-module generated by Y.The homology of the set Y associated to C=(R[X],?)is

If there is no ambiguity, we denote H(Y)=HC(Y;R).

The idea of the homology of sets is essentially from the path homology of digraphs (see [4])and multi-graphs(see [5]) and the embedded homology of hypergraphs(see [2]). In this paper,we will always consider freeR-modules instead of abelian groups.

K¨unneth formulas describe the homology of a product space in terms of the homology of the factors. In [7], Hatcher gave the classical algebraic K¨unneth formula. In[4, 6], Grigor’yan,Lin,Muranov and Yau studied the K¨unneth formula for the path homology (with field coefficients)of digraphs. In this paper, we study the K¨unneth formula for sets which can be applied to digraphs and hypergraphs.

From now on,Ris assumed to be a principal ideal domain. For convenience, the tensor product is always overR.

Theorem 1.1Let R be a principal ideal domain. Let C=R[X],C′=R[X′]be complexes of free R-modules generated by finite sets X, X′,respectively, and let Y, Y′be subsets of X, X′,respectively. Then there is a natural exact sequence

where Y×Y′is the Cartesian product of sets.

Recently, people are interested in digraphs in topology (see [4, 6]). LetG= (V,E) be a digraph. LetXbe the set of regular paths onV. Then we can obtain a chain complex(C,?)=(R[X],?) (see [6]). LetA(G) be the set of allowed paths onG. We find that the path homology of digraphGcoincides with the homology of setA(G), i.e.,

Grigor’yan et al. studied the K¨unneth formula for digraphs over a field (see [6]). LetG′be another digraph. In view of Theorem 1.1, in order to get the K¨unneth formula for digraphs with ring coefficients, we need to show where □denotes the Cartesian product of digraphs.

A hypergraph is a potential topic connecting simplicial complex in topology and a graph in combinatorics,which is worth studying both in theory and application (see [1—3, 9]). Let H be a hypergraph. Let KHbe the smallest simplicial complex containing H. Note that H is a set of hyperedges, we observe that

where (C,?) = (C?(KH;R),?) is the chain complex of simplicial complex KH. Let H′be another hypergraph. By Theorem 1.1, we have

where H×H′is the Cartesian product of sets. Unfortunately, H×H′is not a hypergraph.In another paper, we give a product of hypergraphs and show the K¨unneth formula for hypergraphs.

In the next section, we build a basic algebraic language. In Section 3, we prove Theorem 1.1.

2 Preliminaries

In this section, let (C,?)=(R[X],?) be a complex of freeR-modules generated by a finite setX. LetD=R[Y] be a freeR-module generated byY?X.

Proposition 2.1(see [8])Let M be an m×n matrix over R. Then we have

wheredet(U)=det(V)=1andΛis a matrix of form(ΛmO)or. Here,ΛmandΛnare diagonal matrices.

Lemma 2.1Suppose that z∈D and λz∈Inf?(D,C)for some nonzero element λ∈R.Then we have z∈Inf?(D,C).

ProofLetX= {x1,···,xn}. Thenx1,···,xnis a basis ofR[X]. For convenience,we denoteeX= (x1,···,xn)T. LetZbe the set of complement ofYinX. Then we haveX=Y?Z. Assume that

where a = (a1,···,a|Y|) ∈R1×|Y|, b = (b1,···,b|Z|) ∈R1×|Z|andeY,eZare given by setsY,Z, respectively. Sinceλ?z∈D, it follows that

SinceRis an integral domain, we have beZ=0. Thus we obtain

The lemma is proved.

Lemma 2.2There is a basis e1,···,er(D)of D such that e1,···,eαis a basis ofInf?(D,C)for some α, where r(D)is the rank of D.

ProofLete1,···,enbe a basis ofD, and letf1,···,fαbe a basis of Inf?(D,C). Then we have

where f = (f1,···,fα)T,e = (e1,···,en)TandAis anα×nmatrix overR. By Proposition 2.1, we obtain

where det(U)=det(V)=1 and

Let (x1,···,xα)=U?1f and (y1,···,yn)=Ve, then we have

By Lemma 2.1, we haveyi∈Inf?(D,C),i= 1,···,α. It follows thaty1,···,yαis a basis of Inf?(D,C). Thusy1,···,ynis the desired basis.

Example 2.1Let (C,?) = (Z[x,y],?),?y=x,?x= 0,degx= 1, and letD= Z[2x,y] be a free Z-module generated by 2x,y. Note that

Thus the condition thatDis a freeR-module generated by a subset ofXis necessary for Lemma 2.2.

Lemma 2.3Let K=ker??C. Then there is a basis e1,···,er(C)of C such that e1,···,eαis a basis of K for some α, where r(C)is the rank of C.

ProofBy a similar argument with the proof of Lemma 2.2, we have this lemma.

Definition 2.1Let M be a finitely generated free R-module, and let N?M be a free sub R-module of M. We say a family of elements x1,···,xn∈M is linearly independent modulo N if the condition

implies c1=···=cn=0.

By Lemma 2.3,we haveC=V⊕K, whereK=ker?andVis the space of the complement ofKinC. Note that a family of elementsx1,···,xn∈Cis linearly independent moduloKif and only if?x1,···,?xnis linearly independent.

3 The Proof of Main Theorem

In this section, letC=R[X],C′=R[X′] be complexes of finitely generated freeR-modules generated by setsX,X′, respectively. LetD=R[Y],D′=R[Y′] be finitely generated freeR-modules generated byY?X,Y′?X′, respectively. For convenience, all the differentials will be denoted by?if there is no ambiguity.

The keypoint of proving Theorem 1.1 is to show

We will give some lemmas first.

Lemma 3.1Let M,N be finitely generated free R-modules. For each z∈M?N, there exists a nonzero element λ∈R such that

where{xi}1≤i≤k,{yi}1≤i≤kare two families of linearly independent elements in M,N, respectively.

ProofLetz=wherexi∈M,yi∈N,i=1,···,n. Ifx1,···,xnare not linearly independent, we have

We may assumecn/=0. It follows that

Letzi=cnyi?ciyn. Then we haveBy finite steps, the above equation can be reduced to

whereλ/= 0 and {xi}1≤i≤k,{y}1≤i≤kare two families of linearly independent elements inMandN, respectively.

Remark 3.1In the above lemma, we can chooseλ= 1. Let {ei}1≤i≤m,{fi}1≤i≤nbe the bases ofM,N, respectively. Then we have

LetA=(aij)1≤i≤m,1≤j≤nbe a matrix overR. By Proposition 2.1, we have

where det(U)=det(V)=1 andHere,

Denote e=(e1,···,em)Tand f =(f1,···,fn)T. Then we have

which is the desired result.

The following lemma is a very useful tool in proving our main theorem.

Lemma 3.2Let{xi}1≤i≤k,{yi}1≤i≤kbe two families of linearly independent elements in C and C′, respectively.then we have

ProofLete1,···,eα,eα+1,···,embe a basis ofCsuch thate1,···,eαis a basis ofD.Similarly, letf1,···,fα,fα+1,···,fnbe a basis ofC′such thatf1,···,fβis a basis ofD′.Assume that

whereais,bit∈Rfor 1 ≤s≤m,1 ≤t≤n. Note that

and

It follows that

Since rank(AT0)≥rank(AT0B0)=k, we have

Thus we obtainB1=O. Similarly, we haveA1=O. These imply the lemma.

The following two lemmas are important parts of the proof of Theorem 3.1.

Lemma 3.3Let z=Inf?(D?D′,C?C′)such that

and each of the following sets

is linearly independent. Then there exists a nonzero element λ∈R such that λz∈Inf?(D,C)?Inf?(D′,C′).

ProofBy Lemma 3.2, we have

Note that

If?xk,β1,···,βnare not linearly independent, we have

Thenck?xk∈D. Moreover, we obtain

We may assume that?xk,β1,···,βnare not linearly independent form′+1 ≤k≤m. By finite steps, the above equation can be reduced to

for some nonzero elementλ∈R, wherey′j?λ?yj(j= 1,···,n) is linearly generated byαm′+1,···,αm. In addition,?x1,···,?xm′,β1,···,βnare linearly independent. Ify′j,α1,···,αm′are not linearly independent,we can changey′jsimilarly as above. Then the above equation can be reduced to

for some nonzero elementsλ,λ1∈R, wherex′i?λ1λ?xi(i= 1,···,m′) is linearly generated byβn′+1,···,βn. In addition,y′1,···,y′n′,α1,···,αm′are linearly independent. Ifx′1,···,x′m′,β1,···,βn′are not linearly independent, then?x1,···,?xm′,β1,···,βnare not linearly independent, which contradicts to our construction. Thusx′1,···,x′m′,β1,···,βn′are linearly independent. By Lemma 3.2, we have

It follows that

Recall that we haveck?xk∈D,ck/= 0 form′+1 ≤k≤m. It follows thatλ?xk∈Dform′+1 ≤k≤m. Similarly, we haveλ1y′t∈D′forn′+1 ≤t≤n. Hence, we obtain that

Thus there exists a nonzero elementλ2∈Rsuch thatλ2z∈Inf?(D,C)?Inf?(D′,C′).

Lemma 3.4Let C=V⊕K and C′=V′⊕K′, where K and K′are the spaces of cycles in C and C′, respectively. For each element z∈C?C′, there exists a nonzero element λ∈R such that

where

for1 ≤i≤N1,1 ≤j≤N2,1 ≤k≤N3,1 ≤l≤N4and

(i)x1,···,xN1,y1,···,yN3,u1,···,uN2,v1,···,vN4are linearly independent;

(ii)x1,···,xN1,y1,···,yN3are linearly independent modulo K;

(iii)x′1,···,x′N1,y′1,···,y′N2,u′1,···,u′N3,v′1,···,v′N4are linearly independent;

(iv)x′1,···,x′N1,y′1,···,y′N2are linearly independent modulo K′.

ProofNote that

In view of Lemma 3.1, for each elementz∈C?C′, we have

for someλ1∈R, where

for 1 ≤i≤N1,1 ≤j≤N2,1 ≤k≤N3,1 ≤l≤N4and each of the following sets

is a family of linearly independent elements. Ifx1,···,xN1,yk0are not linearly independent,we obtain

for some nonzero elementck0∈R. Thus we have

By finite steps, the above equation can be reduced to

whereare linearly independent moduloK′andx1,···,xN1,y1,···,yN′3are linearly independent. Ifare not linearly independent, by a similar substitution,we can obtain such that

(ii)are linearly independent moduloK;

(iv)are linearly independent moduloK′.To complete our proof, it suffices to consider the elementsv1,···,vN4andv′1,···,v′N4. Ifvl0,u1,···,uN′2are linearly independent, by a similar method as above, we can obtain the desired result.

Now, we return to the theorem mentioned before.

Theorem 3.1Inf?(D?D′,C?C′)=Inf?(D,C)?Inf?(D′,C′).

ProofIt can be directly verified that

Our main work is to show the inverse.

For each elementz∈Inf?(D?D′,C?C′), we have

whereλ∈R,xi,yk∈C,uj,vl∈K,x′i,y′k∈C′,u′k,v′l∈K′are given in Lemma 3.4. Sincez∈D?D′, by Lemma 3.2, we have

for 1 ≤i≤N1,1 ≤j≤N2,1 ≤k≤N3,1 ≤l≤N4. Note that

Sincex1,···,xN1,y1,···,yN3are linearly independent moduloK, we obtain that

are linearly independent. Ifuj0,?x1,···,?xN1,?y1,···,?yN3are not linearly independent, we have

It follows that

We may assume thatuj0,?x1,···,?xN1,?y1,···,?yN3are not linearly independent forN′2+1 ≤j0≤N2. By finite steps, we can reduce the above equation to

for some nonzero elementsλ1,μ1,μ2∈R, where

are linearly independent. By the above construction, we have that

are linearly independent. Ifare not linearly independent, by a similar progress, we can obtain

for some nonzero elementsλ2,ν1,ν2,ν3,ν4∈R, where

are linearly independent and

are linearly independent. Recall that?z∈D?D′. By Lemma 3.2, we have

It follows that

Similarly, we havex′1,···,x′N1,y′1,···,y′N′2∈Inf?(D′,C′). It implies that

Let

The previous construction implies thatuN′2+1,···,uN2andu′N′3+1,···,u′N3are boundaries. By Lemma 3.3, there exists a nonzero elementλ′∈Rsuch thatλ′z1∈Inf?(D,C)?Inf?(D′,C′).Therefore we have

By Lemma 2.2, there exists a basisS1?T1ofDsuch thatS1is a basis of Inf?(D,C).Similarly, there is a basisS2?T2ofD′such thatS2is a basis of Inf?(D′,C′). LetS=S1?S2.Thus we can choose a basisS?TofD?D′such thatSis a basis of Inf?(D,C)?Inf?(D′,C′).Assume that

where a = (a1,···,a|S|) ∈R1×|S|, b = (b1,···,b|T|) ∈R1×|T|. Sinceλλ′z∈Inf?(D,C)?Inf?(D′,C′), it follows that

Recall thatRis a principal ideal domain, we have beT=0. This implies that

which gives the desired result.

Example 3.1Continuing with Example 2.1, let (C′,?) = (Z[x′,y′],?),?y′=x′,?x′=0,degx′=1, and letD′=Z[2x′,y′] be a free Z-module generated by 2x′,y′. Then we have

A straightforward calculation shows that

Thus the result in Theorem 3.1 also depends on the condition thatD,D′are freeR-modules generated by subsets ofX,X′, respectively.

Theorem 3.2(see [7, Theorem 3B.5])Let R be a principal ideal domain, and let C,C′be chain complexes of free R-modules. Then there is a natural exact sequence

Proof of Theorem 1.1Note thatR[Y]?R[Y′] ～=R[Y×Y′].The theorem follows from Theorems 3.1—3.2.

AcknowledgementThe authors would like to thank Prof. Yong Lin and Prof. Jie Wu for their supports, discussions and encouragements. The authors also would like to express their deep gratitude to the reviewer(s)for their careful reading,valuable comments and helpful suggestions.