Towards optimality in discrete Morse Theory through chain homotopies

Towa ds Op imali y in Disc e e Mo se Theo y h ough Chain Homo opies ∗ Ped o Real, Helena Molina-Ab il Uni e si y o Se illa, Depa men o Applied Ma hema ics, Se illa, Spain. [email p o ec ed], [email p o ec ed] Abs ac Once a disc e e Mo se unc ion has been de ined on a ini e cell complex, in o - ma ion abou i s homology can be deduced om i s c i ical elemen s. The main objec i e o his pape is o de ine op imal disc e e g adien ec o ields on gene al ini e cell complexes, whe e op imali y en ails ha ing he leas numbe o c i ical elemen s. Ou app oach is o conside his p oblem as a homology compu a ion ques ion o chain complexes endowed wi h ex a algeb aic nilpo en ope a o . Keywo ds: Disc e e Mo se Theo y, cell complex, in eg al-chain complex, chain homo opy, g aph, homology, g adien ec o ield. 1 In oduc ion Mo se heo y has been conside ed a powe ul ool in i s applica ions o compu a ional opology, compu e g aphics and geome ic modeling. In [5] Fo man o mula es a e sion o his heo y o disc e e s uc u es such as cell complexes. The aim o Disc e e Mo se Theo y is o ind simplicial collapses ha ans o m K o a smalle complex. This heo y elies ei he on admissible unc ions on a cell complex, called disc e e Mo se unc ions, o equi alen ly hei g adien ec o ield. Fo man p o ed ha he opology o a cell complex can be pa ly ead ou o he c i ical cells o a disc e e g adien ec o ield de ined on i . A g adien ec o ield is op imal i i has he minimum possible numbe o c i ical cells. The opological in o ma ion o he ini ial cell complex will be concise i he disc e e g adien ec o ield has ew c i ical cells. In [10] he au ho s de eloped a heu is ic o compu ing op imal Mo se ma chings. This heu is ic compu es op imal g adien ec o ields o combina o ial 2–mani olds. Howe e , o gene al cell complexes his p oblem has no been sol ed ye . In his pape we eco e all he algeb aic machine y unde lying in Disc e e Mo se Theo y, es ablishing a new amewo k o dealing wi h special chain complexes associa ed o ini e cell complexes. This can be done using an essen ially algeb aic amewo k in which “homological o es s” (see [11]) de ined on he ini ial cell complex a e con enien ools in o de o ob ain he minimum numbe o c i ical cells, ha is, he minimal homological exp ession o he ini ial complex. The idea he e is o classi y chain homo opies as g adien ec o ields on a ini e cell complex. The pape is o ganized as ollows: In Sec ion 2 some basic de ini ions a e in oduced. The heo e ical undamen s o ou wo k is de ailed in Sec ion 3. In Sec ion 4 he ela ion be ween his algeb aic machine y and he op imali y in Disc e e Mo se Theo y a e s ablished. We inish he pape wi h some conclusions. . ∗This wo k has been pa ially suppo ed by ”Compu a ional Topology and Applied Ma hema ics” PAICYT esea ch p ojec FQM-296, ”Andalusian esea ch p ojec PO6-TIC-02268 and Spanish MEC p ojec MTM2006- 03722 33 2 P eliminai es In his sec ion, we in oduce some basic de ini ions in o de o unde s and ou algeb aic– opological app oach. Fi s , we es ablish a no ion o (combina o ial) cell complex in a ini e–dimensional Euclidean space wi h he cell bounda y in o ma ion desc ibed in algeb aic e ms. This objec can be iden i ied wi h he chain complex canonically associa ed o a cell complex such ha he homology o i coincides wi h he singula homology o he cell complex. In ac , he geome ic ealiza ion o such cell complex in a ini e–dimensional Euclidean space has a ep esen a ion in e ms o a pa icula ype o egula cell complex (see [9] o a deep s udy o cell-complexes). Simplicial, cubical and polyhed al complexes a e, pa icula cases o cell complexes. The ollowing de ini ions a e necessa y in o de o classi y chain homo opies as g adien ec o ields on a ini e cell complex. The ing o coe icien s Λis a commu a i e ield ( o example, a ini e ield, he a ional numbe s, he eal numbe s,...). Le {x1,x 2, ..., xn}be a ini e se o symbols. We deno e by Λ[x1, . . . , xn] he module o o mal linea combina ions λ1x1+λ2x2+. . . λnxn, wi h λi∈Λ. Le "be a posi i e in ege . Le B!={x∈E!s. . |x|≤1) be he closed uni ball in he "-dimensional Euclidean space E!. The bounda y o B!is he uni ("−1)-sphe e S(!−1) and he in e io o B!, deno ed by In B!, is he open uni "-dimensional ball In B!={x∈E!s. . |x|<1}. Ap-cell in E!(wi h 0 <p≤") is a subse o E!which is homeomo phic o he open uni ball In Bp( ha is, o Rp). A 0–cell is a a opological space homeomo phic o a poin o a ini e-dimensional Euclidean space. The dimension o a p-cell σis |σ|=pand he no a ion σ(p)will indica e ha σis a cell o dimension p. The union as poin se o a se o cells Kin E!is called he ca ie o Kand i is deno ed by |K|. Le us de ine he bounda y o a p-cell σas ∂σ =σ σ, whe e σis he closu e o σ. To indica e ela ionships be ween cells, we w i e τ>σ(o σ<τ) and we say ha σis a ace o τi σ%=τand σ⊂¯τ, whe e ¯τis he closu e o τ. We w i e τ≥σi ei he τ=σo τ>σ. The s a o a cell σconsis s o all cells ha ing σas a ace, including σi sel , and he link consis s o all aces o cells in he s a ha a e disjoin om σ. S σ={τ∈K|σ<τ} Lk σ={ ∈K| <τ∈S σ, ∩σ=∅}. Acell complex K={Ki}! i=0 embedded in E!is a ini e collec ion o cells {σ( )i=1,...n i∈K }o di e en dimensions 0 ≤ ≤"such ha : (i) |K|= n ! i=1 σi=|K0|∪|K1|∪. . . ∪|K!| . The se K consis s o all he -cells o K, o 0 ≤ ≤". I is possible ha Ki=∅ o some 0 <i≤". (ii) σi∩σj=∅(i%=j); (iii) I dim(σi)=p(wi h 0 ≤p≤"), hen ∂σi⊂"p−1 i=1 Ki, The p-skele on K(p) o Kis he se o all k-cells wi h 0 ≤k≤p. The dimension o he cell complex is he smalles na u al numbe such ha he condi ion K( )=K( +1) is sa is ied. I all he cells o Ka e con ex se s o E!, hen Kis called con ex cell complex. Simplicial, Cubical and some polyhed al complexes a e special cases o con ex cell complexes. A cell complex is speci ied by he “ ace pose ”, he pa ial o de de e mined by he cells and i s bounda y ela ions. Roughly speaking, he idea o homology is o analyze he deg ee o connec i i y o cell com- plexes using o mal sums o cells. A di e en ial ope a o o a cell complex Kwi h coe icien s in 34 Λis a linea map d:Λ[K]→Λ[K], such ha he image o a p-cell σis a linea combina ion o some (p−1)-cells o he bounda y ∂(σ) and d◦d= 0. Taking in o accoun ha ou cell complex Kis embedded in E!, i s geome ic ealiza ion |K|is a egula iangulable cell complex and he e can be always de ined a di e e en ial ope a o ∂, called bounda y ope a o , wi h coe icien s in he ield Λ, ha comple ely de e mines he singula homology o |K|. The chain complex canonically associa ed o he cell complex Kis he g aded di e en ial ec o space (C∗(K),∂), whe e Cp(K)=Λ[Kp], o all p=0,1,... , and ∂:C∗(K)→C∗−1(K) is he p e ious bounda y ope a o o he cell complex K. Fo ins ance, o ind a bounda y ope a o ∂ o a simplicial complex is s aigh o wa d, bu i is no , in gene al, an easy ask o o he s cell complexes. The ollowing is one o he undamen al esul s in he heo y o CW-complexes. Theo em 1 (Fo man).Le Ka ini e cell complex. The e a e algeb aic bounda y maps ∂p: Cp(K, Λ)→Cp−1(K, Λ), o each p, so ha ∂p−1◦∂p=0and such ha he esul ing di e en- ial complex {Cp(K, Λ),∂p} p=0 calcula es he homology o K. Tha is, i we de ine Hp(C, ∂)= Ke (∂p)/∂p+1(C). In o he wo ds, Hp(C, ∂)∼ =Hp(|K|,Λ). F om now on, a ini e cell complex Kwill be deno ed by (K, ∂), whe e ∂:C∗(K)→C∗−1(K) is he bounda y ope a o o K. 3 Algeb aic Disc e e Mo se Theo y The aim o Disc e e Mo se Theo y is o ind simplicial collapses ha ans o m a complex K o a smalle one. This can be done using an essen ially algeb aic amewo k in which disc e e Mo se unc ions a e con enien ools o keep ack o he collapses, and in which o de hey a e done. Now, we eco e all he algeb aic machine y unde lying in Disc e e Mo se Theo y, es ablishing a new amewo k o dealing wi h special chain complexes associa ed o ini e cell complexes and we show ha a con enien combina o ial ool o sol ing he homological compu a ion p oblem in his a ea is ha o a ee. De ini ion 1. An in eg al chain complex (C, d, φ)is a g aded module C={Cp}n p=0 endowed wi h wo linea maps: a di e en ial ope a o d:C∗→C∗−1, and an in eg al ope a o (also called algeb aic g adien ec o ield [5] o chain homo opy ope a o [4]) φ:C∗→C∗+1, sa is ying he global nilpo ency p ope ies d◦d=0and φ◦φ=0. An in eg al chain complex (C, d, φ)is d-pu e ( esp. φ-pu e) i he condi ion d=d◦φ◦d, called homology condi ion ( esp. he condi ion φ=φ◦d◦φ, called s ong de o ma ion e ac condi ion) is sa is ied. An in eg al chain complex (C, d, φ) ha is bo h, d-pu e and φ-pu e, is called homology in eg al chain complex. De ini ion 2. Gi en wo in eg al chain complexes (C, d, φ)and (C#,d #,φ#),amap o in eg al chain complexes ( , g):(C, d, φ)⇒(C#,d #,φ#)is a couple o linea maps :C→C#and g:C#→C such ha ◦d=d#◦ ,g◦d#=d◦g, ◦φ=φ#◦ ,g◦φ#=φ◦g.(C, d, φ)and (C#,d #,φ#) a e in eg al chain equi alen i he e exis s a map o in eg al chain complexes ( , g), such ha id C− ◦g=π(d#,φ#)and idC!−g◦ =π(d, φ). The homology H∗(C, d, φ)o an in eg al chain complex (C, d, φ)is he g aded abelian g oup H∗(C), such ha (H∗(C),0,0) is in eg al chain equi alen o (C, d, φ). The di e en ial ( esp. in eg al) homology o an in eg al chain complex (C, d, φ)is he homology o (C, d, 0) ( esp. he homology o (C, 0,φ)). I (C, d, φ)is a homology in eg al-chain complex, hen H∗(C, d, φ)∼H∗(C, d, 0) ∼H∗(C, 0,φ). The se o in eg al chain complexes ( esp. he se o pu e in eg al chain complexes) and hei co esponding maps o m a ca ego y. In ac , he in eg al chain equi alence ela ion can be seen as he na u al ex ension o he classical chain homo opy equi alence be ween chain complexes o he in eg al case (see, o example, [4]). E ec i e Homology [13] is a heo y in which he homology compu a ion p oblem is de e mined in e ms o an explici chain homo opy equi alence be ween a chain complex (C, d) and i s ho- mology. In ac , using ou e minology he e ec i e homology o he chain complex (C, d, 0) can 35 be desc ibed as an algeb aic in eg al ope a o φ, such ha (C, d, φ) is in eg al-chain equi alen o (C, d, 0). On he o he hand, Disc e e Mo se Theo y (DMT, o sho ) gi es a posi i e answe o he p oblem o inding combina o ial chain homo opy ope a o s φ o chain complexes (C∗(K),d) o ini e cell complexes, such ha he in eg al homology o (C∗(K), d, φ) is a “good” app oxima ion (measu ed in e ms o c i ical cells) o i s di e en ial homology. The minimum numbe o c i ical cells in each deg ee is de e mined by he Be i numbe s (weak Mo se inequali ies). The compu a ion o he homology o a chain complex (C, d) is speci ied in e ms o inding an in eg al ope a o φ:C∗→C∗+1, sa is ying he S ong De o ma ion Re ac (SDR o sho ) and homology condi ions wi h ega ds, o he di e en ial ope a o d([7, 8]). The no ion o pu e in eg al chain complex (C, d, φ) is unde lying in he wo k o Se ge ae [13], Fo man [5, 6] and ha o Theo y o Disc e e Di e en ial Fo ms [2]. P oposi ion 1. Le (C, d, φ)an in eg al chain complex. Le π:C∗→C∗be he linea map, (called low o (C, dφ)), de ined by π=idC−d◦φ−φ◦dand le ∆:(C∗,d)→C∗be he linea map, called Laplacian o (C, dφ), de ined by ∆=d◦φ+φ◦d. Then, he ollowing p ope ies holds: (a) d◦π=d−d◦φ◦d=π◦dand φ◦π=φ−φ◦d◦φ=π◦φ. In he case o a homology in eg al chain complex, d◦π= 0 = π◦dand φ◦π= 0 = π◦φ. (b) d◦∆=d◦φ◦d=∆◦dand φ◦∆=φ◦d◦φ=∆◦φ. In he case o a homology in eg al chain complex, d◦∆=d=∆◦dand φ◦∆=φ=∆◦φ. (c) Gi en a p-chain a, we ha e he ollowing equali y a=π(a)+∆(a). (d) π2=π−φ(d−d◦φ◦d)−(d−d◦φ◦d)◦φ=π−d(φ−φ◦d◦φ)−(φ−φ◦d◦φ)d. The in eg al chain complex π(C, d, φ) = (π(C),d|π(C),φπ(C))is he ha monic complex associa ed o (C, d, φ). I (C, d, φ) is a d-pu e o a φ-pu e in eg al chain complex, hen π2=π◦π=π and π(C)={x∈C|x=π(x)}. In o he wo ds, he ha monic complex (π(C),d|π(C),0) associa ed o a pu e in eg al chain complex (C, d, φ) is o med by he π-equi a ian s chains o C. I (C, d, φ) is a homology in eg al chain complex, i s ha monic complex is o he kind (π(C),0,0) and he chain map πdesc ibes o each p-chain a ep esen a i e cycle o he di e en ial ( esp. in eg al) homology class associa ed o his p-chain. (e) ∆2=(d+φ)∆(d+φ). The in eg al chain complex ∆(C, d, φ)=(∆(C),d|∆(C),φ|∆(C)) is he Laplacian complex associa ed o (C, d, φ). I (C, d, φ) is a d-pu e o φ-pu e in eg al chain complex, hen ∆◦∆=∆and ∆(C)={x∈C|x=∆(x)}. In o he wo ds, he Laplacian complex ∆(C, d, φ) associa ed o a pu e in eg al chain complex (C, d, φ) is o med by all he ∆-equi a ian s chains. ( ) π◦∆=(d−d◦φ◦d)◦φ+φ◦(d−d◦φ◦d)=d(φ−φ◦d◦φ)+(φ−φ◦d◦φ)d=∆π. P oposi ion 2. I (C, d, φ)is a (di e en ial o in eg al) pu e in eg al-chain complex, we can de i e he ollowing p ope ies: (p1) π◦∆= 0 = ∆◦π. (p2) (C, d, φ)=π(C, d, φ)⊕∆(C, d, φ)as in eg al-chain complexes. In pa icula , Ke ∆=π(C) and ∆(C) = Ke π. (p3) ∆(C)=φ(C)⊕d◦φ)(C)as g aded modules. In o de o emphasize he dependency o πand ∆wi h ega ds dand φ, we will deno e hese maps by π(d,φ)and ∆(d,φ), espec i ely. The ollowing p oposi ion will be undamen al in de eloping an in eg al-chain amewo k o Disc e e Mo se Theo y. In ac , i shows ha o use pu e in eg al ope a o s as chain homo opies decomposing a ini ely gene a ed chain complexes is a key poin : 36 P oposi ion 3. I (C, d, φ)is a (di e en ial o in eg al) pu e in eg al-chain complex, we ha e ha Ke φ∼ =π(C)⊕φ(C)∼ =Ke ∆(C)⊕φ(C) as g aded modules. In pa icula , a map o in eg al-chain complexes ( , g) sa is y ha ◦π(d,φ)=π(d!,φ!) ,g◦ π(d!,φ!)=π(d,φ)◦g, ◦∆(d,φ)=∆(d!,φ!)◦ and g◦∆(d!,φ!)=∆(d,φ)◦g. Tha is, and ga e compa ible wi h ega ds o he espec i e lows and Laplacians. In spi e o i s simplici y, he ollowing esul is essen ial o de eloping ou homological heo y o in eg al-chain complexes: Lemma 1. [In eg al-Chain Lemma] An in eg al chain complex (C, d, φ)is in eg al-chain equi - alen o i s ha monic complex π(C, d, φ). This las ha monic complex π(C, d, φ)is o he o m (π(C),d π,φπ)whe e dπ(π(x)) = (d−d◦φ◦d)(x)and φπ(π(x)) = (φ−φ◦d◦φ)(x). P oo . Le :C→π(C) be he linea map de ined by (x)=π(x), ∀x∈C∗. Le g:π(C)→C be he linea map de ined by g(x)=x,∀x∈π(C). Then, i is a simple exe cice o show ha ( , g) is a couple o maps o in eg al chain complexes which induces he in eg al-chain equi alence. The es o asse ions can be di ec ly deduced om P oposi ion 1 (a). ! Co olla y 1. The ha monic complex π(C, d, φ)associa ed o a d-pu e ( esp. φ-pu e) in eg al-chain complex (C, d, φ)is o he o m (π(C),0,φπ)( esp. (π(C),d π,0)), whe e φπ(π(x)) = (φ−φ◦φ◦)(x) ( esp. dπ(π(x)) = (d−d◦φ◦d)(x)). Now, we gi e some de ini ions ela ed o in eg al-chain pe u ba ion o complexes. De ini ion 3. An in eg al chain complex (C, d, φ)is called di e en ial ( esp. in eg al poin wise nilpo en ) i o any a∈C he e is some n(a)∈Nwi h d(1 −d◦φ−φ◦d)n(a)=0( esp. wi h φ(1 −d◦φ−φ◦d)n(a)=0). The smalles alue o n(a)is e e ed o as he deg ee o di e en ial ( esp. in eg al) nilpo ency o a. P oposi ion 4 (Fo man).Gi en an in eg al ( esp. di e en ial) poin wise nilpo en in eg al chain complex (C, d, φ)is in eg al chain equi alen o a φ-pu e ( esp. d-pu e) in eg al chain complex (C, d, ˜ φ)( esp. (C, ˜ d, φ)). P oo . We only p o e he exis ence o he φ-pu e in eg al chain complex (C, d, ˜ φ). The o he esul can be de i ed di ec ly om he ac ha (C, φ,d) is also a poin wise nilpo en in eg al- chain complex. De ine ˜ φ:C∗→C∗+1 by ˜ φ=#k≥0φ◦(1−d◦φ)k. This is well de ined due o he poin wise nilpo ency o (C, d, φ), since all bu ini ely many e ms anish on he igh hand side. The map ˜ φis 2-nilpo en (˜ φ◦˜ φ= 0) and sa is ies he SDR p ope y ˜ φ◦d◦˜ φ=˜ φ. The couple o maps (π(d, ˜ φ),idC) es ablish he in eg al chain equi alence be ween (C, d, φ) and (C, d, ˜ φ). ! Finally, we de ine he composi ion o an in eg al-chain complex. De ini ion 4. Gi en a d-pu e ( esp. wo φ-pu e) in eg al-chain complexes (C, d, φ)and a di e - en ial ope a o d#sa is ying he homology condi ion ( esp. an in eg al ope a o φ#sa is ying he s ong de o ma ion e ac condi ion) o π(d,φ)(C), a new d-pu e ( esp. φ-pu e) in eg al chain complex (C, d +d#◦π(d,φ),φ)( esp. (C, d, φ+φ#◦π(d,φ))) can be cons uc ed. This new in eg al chain complex is called composi ion o (C, d, φ)by φ#.Ad-pu e in eg al chain complex (C, d, φ) can su e composi ion wi h ega ds o he own di e en ial ope a o d( esp. wi h ega d o he own in eg al ope a o φ) es ic ed o π(d,φ)(C). F om now on, all he in eg al chain complexes we conside in he pape will be in eg al poin wise nilpo en s. Analogous esul s can be de e mined o di e en ial poin wise nilpo en . In he nex sec ion, we de ine some no ions in o de o do he link wi h he algeb aic wo k unde lying in Disc e e Mo se Theo y. 37 4 Disc e e Mo se Theo y and op imali y Disc e e Mo se Theo y gi es a posi i e answe o he p oblem o inding combina o ial chain homo opy ope a o s φ o chain complexes (C∗(K),d) o ini e cell complexes, such ha i s in eg al homology H(C, 0,φ) is a “good” app oxima ion o i s di e en ial one H(C, d, 0). Using Pe sis en Homology [3] Be i numbe s can be g adually de e mined om a il e ed chain complex. We will show he e ha Homological Pe u ba ion Theo y can be used as a ool o eaching in e es ing combina o ial esul s in DMT ( o example, abou g adien pa hs). Mo e p ecisely, he homology o a chain complex (C, d) can be speci ied in DMT in e ms o inding a combina o ial in eg al ope a o φ:C∗→C∗+1 de i ed om disc e e Mo se unc ions and sa is ying he SDR condi ion wi h ega ds, o he di e en ial ope a o d. De ini ion 5. Le (K, ∂)a ini e cell complex. An ope a o :C∗(K)→C∗± (K)is said o be combina o ial i ∀p-cell σ(p), (σ(p))=λβ (p± ), whe e λ∈Zand βis a (p± )−cell. Tha is, in DMT we sea ch o a combina o ial ope a o φsuch ha (C(K), d, φ) is a φ-pu e in eg al-chain complex. Gi en a cell complex K, he in eg al-chain complex canonically associa ed o Kis (C(K),∂,)), whe e ∂is he bounda y o di e en ial ope a o o C∗(K) and ):C∗(K)→C∗+1(K) is he cobounda y ope a o de ined by )(α(p))=Σ<∂β,α>β, whe e he sum is aken o all he cells β(p+1), such ha a∈∂(β) (i.e. apa icipa es in a non-null manne in he linea combina ion ∂(β)). In DMT, we sea ch o a combina o ial ope a o φwhich can be de i ed (choosing one summand in he o mula o ) o each cell) such ha he numbe o c i ical cells in (C(K),∂,φ) is minimal. Now, we gi e some basic no ions o DMT wi h some sligh ly modi ica ions and wi hou using, in p inciple, disc e e Mo se unc ions. De ini ion 6. [5, 6] A combina o ial in eg al ope a o Vde ined on a cell complex Kis a collec ion o disjoin pai s o (non-necesa ly inciden ) cells {α(p)<β(p+1)}. I he pai s a e cons i u ed by inciden cells hen, Vis called combina o ial ec o ield. We will ep esen a combina o ial ec o ield by an a ow om he cell o lowe dimension o i s pai ed cell o highe dimension. A combina o ial ec o ield can be seen as a pa ial ma ching in he Hasse diag am o K.AV-pa h o g adien pa h γis an al e na ing sequence o cells a(p) 0,b (p±1) 0,a (p) 1,b (p±1) 1,a (p) 2, . . ., such ha o each pai o consecu i e simplices, one is a maximal ace o he o he , and he ollowing condi ion is sa is ied: one o he couples {a(p) i<b (p±1) i}o {b(p±1) i<a (p) i+1}belongs o V,∀i≥0. I he inal cell in he g adien pa h γabo e is α(p) , hen we say ha γhas leng h . I i ends wi h β(p±1) hen we say ha γhas leng h 1 2. I he cells bio he g adien pa h γa e o dimension p+1 and i has leng h 1 2, he g adien pa h γis called uppe V- pa h o uppe g adien pa h. Fo any cells aand b, le Γ(a, b)deno e he se o g adien pa hs om a o b(o any leng h), i.e., such ha he i s cell in he sequence is aand he las cell in he sequence is b.AV-pa h is non i ial and closed i ≥1and he i s and las cells in he sequence a e he same. A closed V-pa h is jus an o ien ed ci cui in he Hasse diag am. A cell αis a c i ical cell o Vi i is no pai ed wi h any o he cell in V. The numbe o c i ical cell depends on he disc e e g adien ec o ield conside ed. Fo man p o ed [5, 6] ha he opology o a disc e e mani old is ela ed o he c i ical elemen s o a disc e e unc ion de ined on i , micmicking he esul s o Mo se in he smoo h case. In [10], he p oblem o he op imali y (minimizing he numbe o c i ical cells o combina o ial ec o ields) on a 2-mani old is analyzed using Hasse diag am and hype g aph ools. The e o e, a disc e e g adien ec o ield is a special kind o combina o ial in eg al ope a o . Fi s , he combina o ial in eg al ope a o s de i ed om combina o ial ec o ields a e φ- poin wise nilpo en . P oposi ion 5. A combina o ial ec o ield Vgi es ise o a φ-poin wise nilpo en in eg al-chain complex (C(K), d, V ). 38 Le us emphasize ha wo pai s {a, b}and {a#,b #}o Vha e no elemen s in common. The combina o ial ec o iel Vgi es ise o a linea map V:C∗(K)→C∗+1(K), de ined by V(a)=b i {a, b}∈Vand V(a) = 0, in he es o cells. I is clea ha V◦V= 0. The map Vis an in eg al ope a o o C∗(K). To p o e ha (C(K), d, V ) is φ-poin wise in eg al-chain complex is s aigh o wa d. ! Combining P op. 1, P op. 2 and P op. 3, we asse he ollowing esul which is he key o ein e p e ing DMT in in eg al-chain e ms: P oposi ion 6. I (C, d, φ)is a φ-poin wise nilpo en in eg al-chain complex being φa combina- o ial ec o ield, hen he e is an in eg al-chain equi alen φ-pu e complex (C, d, ˜ φ), such ha i s ha monic complex π(C, d, ˜ φ) = ( Ke ˜ φ ˜ φ(C),d π,0). This las in eg al-chain complex is con- s i u ed by ini e linea combina ions o he di e en c i ical cells o φand dπcan be seen as he bounda y ope a o o he co esponding cell complex de e mined by he c i ical cells, also called ha monic Mo se cell complex M(C, d, φ)associa ed o (C, d, φ). Analogously, he Laplacian com- plex ∆(C, d, ˜ φ)can be seen as he acyclic chain complex o he cell complex M(C, d, φ), also called Laplacian Mo se complex associa ed o (C, d, φ). Mo eo e , i s bounda y ope a o ∂Mis de e - mined by ∂M(∆(σ(p))) = d◦˜ φ◦d(σ(p)),∀σ(p)∈C. P oo . Due o P op. 3 and P op. 1 and de ining ˜ φ:C∗→C∗+1 by ˜ φ=# k=0 φ◦(1 −d◦φ)k= # k=0(1 −φ◦d)kφ, we ha e ha ( , g) : Ke ˜ φ ˜ φ(C)∼ =π(C, d, ˜ φ) is an isomo phism o chain complexes, wi h : Ke ˜ φ ˜ φ(C)→π(C, d, ˜ φ) and g:π(C, d, ˜ φ)→ Ke ˜ φ ˜ φ(C) espec i ely de ined by (σ)=π(d, ˜ φ)(σ)=σ−˜ φ◦d(σ), ∀σ∈: Ke ˜ φ ˜ φ(C) and g(π(d, ˜ φ))(β)) = β−d◦˜ φ(β), ∀β∈C. Now, le us p o e ha Ke ˜ φ= Ke φand ˜ φ(C)=φ(C). I is clea ha Ke φ⊂Ke ˜ φ. Le x∈Ke ˜ φbe an elemen such ha x/∈Ke φ. Tha means ha # k=0 π(d, φ)k(x)∈Ke φ. Tha implies ha φ(1 −π +1)(x)=φ(d◦φ+φ◦d)◦ $# k=0 π(d, φ)k%(x) = 0 and, hen φ(x)=φπ +1(x) = 0. In a simila manne , i is possible o deduce ha ˜ φ(C)=φ(C) and ha i also admi s a combina o ial basis. Le us now p o e ha he chain complex (˜ φ(C)⊕(d◦˜ φ)(C),d) is acyclic. We ha e ha d(˜ φ(C)) ⊂(d◦˜ φ)(C) and d((d◦˜ φ))(C) = 0. Now, le us suppose ha he e is a chain x= x#+x## ∈˜ φ(C)⊕(d◦˜ φ)(C) such ha d(x) = 0. This means ha d(x#) = 0. Since x#=˜ φ(z), hen (d◦˜ φ)(z) = 0. Due o he ac ha he in eg al ope a o sa is y he SDR condi ion ˜ φ◦d◦˜ φ=˜ φ, we conclude ha x#= 0. Finally, he bounda y ope a o o M(C, d, φ) is he di e en ial ope a o d es ic ed o i and i s acyclici y can be p o ed using P op. 3. ! Le us no e ha H∗(M(C, d, φ)) ∼ =H∗(K, Λ). Mo eo e , he bounda y ope a o dπo he Mo se cell complex M(C, d, φ) ha e a clea in e p e a ion in e ms o g adien pa hs o ˜ φ. P oposi ion 7. In he condi ions o P op. 6, and gi en a p-cell α,˜ φ(α)is an uppe g adien φ-pa h. In [12, 1], a homology in eg al ope a o φis de e mined om a il e ed cell complex using an inc emen al echnique. The homology in eg al ope a o φgi es ise in a na u al way o a combina o ial in eg al unc ion on K. Using spanning homological o es s echniques [11] and cancella ion–like heo ems [6] in ol ing g adien pa hs, we can conclude ha ob aining a combi- na o ial ec o ield on Kis s aigh o wa d. 39 5 Conclusions In his pape “homological o es s” a e p esen ed as an use ul ool owa ds he op imalli y o a combina o ial g adien ec o ield de ined o e a ini e cell complex. Rela ions be ween E ec i e Homology echniques and Disc e e Mo se Theo y ha e been es ablished, and a common dic iona y o e ms has been de ined. This algeb aic amewo k allows us o ensu e he “ educ ion” o he ini ial complex o i s minimal homological exp ession. The in oduced s uc u e allows a di ec ansi ion om he in eg al ope a o compu ed o e a cell complex, o a minimal combina o ial g adien ec o ield. Re e ences [1] A. Be ciano, H. Molina-Ab il, A. Pacheco, P. Pila czyk, and P. Real. Decomposing ca i ies in digi al olumes in o p oduc s o cycles. In S ecko B lek, Ch is ophe Reu enaue , and Xa ie P o en¸cal, edi o s, DGCI, olume 5810 o Lec u e No es in Compu e Science, pages 263–274. Sp inge , 2009. [2] M. Desb un, E. Kanso, and Y. Tong. Disc e e di e en ial o ms o compu a ional modeling. In SIGGRAPH ’06: ACM SIGGRAPH 2006 Cou ses, pages 39–54, New Yo k, NY, USA, 2006. ACM. [3] H. Edelsb unne , D. Le sche , and A. Zomo odian. Topological pe sis ence and simpli ica ion. Disc e e Compu . Geom., 28:511–533, 2002. [4] S. Eilenbe g and S. Mac Lane. On he g oups h(π,n), i, ii, iii. Annals o Ma h, 58, 60, 60:55–106,48–139, 513–557, 1953,1954. [5] R. Fo man. A Disc e e Mo se Theo y o Cell Complexes. Topology and Physics o Raoul Bo , S.T. Yau, ed., In e na ional P ess., 1995. [6] R. Fo man. Mo se heo y o cell complexes. Ad . In Ma h., 134:90–145, 1998. [7] V. K. A. M. Gugenheim, L. A. Lambe, and J. D. S ashe . Pe u ba ion heo y in di e en ial homological algeb a. Illinois J. Ma h, 33:357–373, 1989. [8] V. K. A. M. Gugenheim, L. A. Lambe, and J. D. S ashe . Pe u ba ion heo y in di e en ial homological algeb a. ii. Illinois J. Ma h., 35(3):357–373, 1991. [9] R. Kle e. Cell complexes h ough ime. Communica ion and In o ma ion Technology Re- sea ch Technical Repo , 60, 2000. [10] T. Lewine , H. Lopes, G. Ta a es, and L. Ma m´ıdia. Towa ds op imali y in disc e e Mo se heo y. Expe imen al Ma hema ics, 12:2003, 2003. [11] H. Molina-Ab il and P. Real. Homological compu a ion using spanning ees. In Edua do Bay o-Co ochano and Jan-Olo Eklundh, edi o s, CIARP, olume 5856 o Lec u e No es in Compu e Science, pages 272–278. Sp inge , 2009. [12] P. Real, H. Molina-Ab il, and W.G. K opa sch. Homological ee-based s a egies o image analysis. In Xiaoyi Jiang and Nicolai Pe ko , edi o s, CAIP, olume 5702 o Lec u e No es in Compu e Science, pages 326–333. Sp inge , 2009. [13] F. Se ge ae . The compu abili y p oblem in algeb aic opology. Ad ances in Ma hema ics, 104:1–29, 1994. 40