Minisymposium: Algebraic models arising from phenomenals in statistic, transportation problems, manufacturing and other fields Simplicial Complexes: mathematical innovative instruments for applications Vittoria BONANZINGA University of Reggio Calabria-DIMET Faculty of Engineering, via Graziella (Feo di Vito), 89100 Reggio Calabria (ITALIA). bonanzin@ing.unirc.it, vittoria.bonanzinga@tin.it Loredana SORRENTI University of Messina Department of Mathematics, C.da Papardo, Salita Sperone 31, 98166 Messina (ITALIA). sorrenti@dipmat.unime.it, sorrenti.loredana@tiscali.it 1 Introduction and formulation of the problems The morphisms in the categories of the simplicial complexes are capable of modelling many transformations used in graphics. We study some theoretical aspects of such combinatoric objects. Our approach is to determine some combinatoric properties of simplicial complexes by studying the algebraic properties of the monomial ideals associated. Let E denote the exterior algebra of the vector space V over a field k with basis e1, . . . , en. Here we consider a special class of monomial ideals of E, the so called completely lexsegment ideal. For any subset = {i1, ..., id} of {1, ..., n} with i1 < i2 < ... < id we call e = ei1 ^ ... ^ eid a monomial of degree d and we denote the set of all monomials of degree d by Md. In order to simplify notation, we set uv for the product u ^ v for any two elements u and v. An ideal I E generated by monomials is called a monomial ideal. We order the monomials lexicographically so that e1 > e2 > ... > en. A lexsegment of degree d is a subset of Md of the form L(u, v) = {w 2 Md : u w v}. A lexsegment ideal is an ideal generated by a lexsegment. Lexsegment ideals in the polynomial ring were first introduced by Hulett and Martin [8]. In extremal combinatorics one usually considers more special lexsegment ideals, which we call initial lexsegment ideals. These are ideals which in each degree are generated by initial lexsegments, that is, sets of the form: Li(v) = {w 2 Md : w v}, called simple lexsegments in usual terminology. A final lexsegment is a set of the form: Lf (u) = {w 2 Md : w u}. A final lexsegment ideal is an ideal which is generated by a final lexsegment. A lexsegment L is called completely lexsegment if all the iterated shadows of L are again lexsegment. We recall that the shadow of a set S of monomials in Md is the set of the non-zero monomials: Shad(S) = {sei : 8s 2 S, 8i /2 supp(s)}, where the support of a monomial u 2 E is supp(u) = {i : ei divides u}. We define the 1 i−th shadow recursively by Shadi(S) = Shad(Shadi−1(S)). We give a description of completely lexsegment ideals in the exterior algebra and we study the vanishing and non vanishing of reduced simplicial cohomology groups of a simplicial complex and of certain subcomplexes of with coefficients in a field k. 2 Results There is a full description of squarefree completely lexsegment ideals in [2]. In [4] squarefree completely lexsegment ideals with linear resolution have been characterized. In [1] Aramova, Avramov and Herzog showed that a squarefree monomial ideal I has a linear free resolution over the polynomial ring if and only if the corresponding ideal J in the exterior algebra has a linear free resolution. This correspondence gives us a description of completely lexsegment ideals with linear resolution in the exterior algebra by translating the results obtained in [4] for squarefree monomial ideals in the polynomial ring to the corresponding statements in the exterior algebra. In particular it holds the following: Theorem 2.1 Let u, v 2 Md monomials with u v be and I = (L(u, v)) be a completely lexsegment ideal. Let k be the smallest integer such that (ik, jk) 6= (k, k) and B = {w 2 Md : w < v, {1, . . . , k − 1} suppw} \ {w < v : xkw0 u}. Then I has a linear resolution if and only if one of the following conditions holds: (a) u = e1 · · · ek−1eik · · · eid with eik · · · eid ek+2 · · · ed+2 and v = e1 · · · ek−1en−d+ken−d+k+1 · · · en (b) ik = k and the following condition holds: for every (w1,w2) 2 B×B with w1 6= w2 there exists an index l, m(w1) l < M(w2) such that ekw1 em(w1) u, ekw2 xl u and w1 em(w1) 6= w2 el . We investigate some properties of the simplicial complexes associated with completely lexsegment ideals and with lexsegment ideals with linear resolution. Let be a simplicial complex on a set T of vertexes. We write I for the ideal of E generated by all monomials eF , F /2 . A simplicial complex is called lexsegment if the corresponding ideal I is a lexsegment ideal. In the following we study the vanishing and non vanishing of reduced simplicial cohomology groups of a simplicial complex when I has a linear resolution or when I is a completely lexsegment ideal. Proposition 2.2 If I is a monomial ideal generated in degree d n and with linear resolution then ˜H i(; k) = 0 for all i 6= d − 2 In the next theorem we compute the reduced simplicial cohomology groups of a certain subcomplex of a lexsegment simplicial complex. 2 Theorem 2.3 If I is a completely lexsegment ideal generated in degree d n. Then ˜H i(T , k) = 0 for all i 6= d − 2, d − 3 and all ; 6= T [n] 3 Applicative Aspects The computation of homology and cohomology simplicial groups is a useful tool in computational topology, an active research field which deals with the study of topological properties of an object that can be computed to some finite accuracy. There is a growing literature on the formalization and representation of topological questions for computer applications, see [5] for a survey of this field. Application areas include digital image processing, solid modelling for computer design, topology preserving morphisms in computer graphics, 3-d models of protein molecules. The earliest applications work on extracting topological information from data targeted digital images. These are typically represented by binary data on a fixed regular grid in two or in three dimensions, pixels and voxels. This field has many applications, for example, in computing the boundaries of a drainage basin from satellite data [14]. Much work in this area focuses on algorithms for the labeling of components [9], boundaries [14] and other features of digital images. An image can be modelled by a topological subspace X Rn. The homology groups of X characterize the number and the type of holes and the number of connected components. This type of information is used, for example, for determining similarities between proteins in molecular biology [5]. Existing work on extracting topological information by the analysis of a finite set of points of X includes a number of approaches to computational homology. The first step in computing homology from point sets is to build a triangulation that reflects the topology of the data. Once this is done, it is possible, though costly, to compute representations of the homology groups from the complex. The computability of homology groups from a given triangulation is well-known and the algorithm uses simple linear algebra [10]. However, these algorithms have run times at best cubic in the number of simplices. So, the problem of computing homology groups is an active area of research. In order to solve problems related to cost times it would be useful to build algorithms with a lower computational cost. Another approach is to compute homology using algebraic and topological tools. In [6] M. Grandis develops combinatorial homotopical tools consisting essentially of intrinsic homotopic theory for simplicial complexes and in [7] he applies these tools to explore mathematical models representing images. In many applications knowledge of the structure of the homology groups is not necessary, all that is needed is the rank of the simplicial homology groups, i.e., the Betti numbers. In [12] and in [11] V. Robins considers the problem of determining information about the topology of a subset X Rn given only a finite point approximation to X. Her approach is to compute topological information, such as the number of connected components and the number of holes, given by Betti numbers. For subset of R3 she interprets the 3 Betti number 0 as the number of path-connected components, 1 as the number of independent tunnels, and 2 as the number of enclosed voids. This kind of information can be deduced by applying results of [3], which give us the ranks of homology groups in some special cases, coming from triangulations associated with completely lexsegment ideals or with ideals with linear resolution, but with the advantage of computing the ranks of the homology groups not using computer implementations. REFERENCES 1. A. Aramova, L. L. Avramov, J. Herzog, Resolutions of monomial ideals and cohomology over exterior algebras, Trans. AMS. 352 (2) (2000), 579-594 2. V. Bonanzinga, Lexsegment ideals in the exterior algebra, in ”Geometric and Combinatorial aspects of commutative algebra”, (J. Herzog and G. Restuccia Eds.), Lect. Notes in Pure and Appl. Math., 4, Dekker, New York, (1999), 43-56. 3. V. Bonanzinga, L. Sorrenti, Lexsegment ideals and reduced simplicial cohomology groups, Preprint 2006. 4. V. Bonanzinga, L. Sorrenti, Squarefree lexsegment ideals with linear resolution, Preprint 2005. 5. T.K. Dey, H. Edelsbrunner, S. Guha, Computational topology, Advances in Discrete and Computational Geometry, 223, Contemporary mathematics. AMS, 1999. 6. M. Grandis, An intrinsec homotopy theory for simplicial complexes, with applications to image analysis, Appl. Cat. Structures 10 (2002), 99-155. 7. M. Grandis, Ordinary and directed combinatorial homotopy, applied to image analisys and cuncurrency, Homology, Homotopy and Applications, 5(2), 2003, pp. 211- 231. 8. H. A. Hulett, H. M. Martin, Betti numbers of lexsegment ideals, J. Algebra 275 (2004), 2, 629-638. 9. T. Y. Kong, A. Rosenfeld, Digital Topolgy: Introduction and survey, Computer Vision, Graphics and Image Processing, 48, 357-393, 1989. 10. J. R. Munkres, Elements of Algebraic Topology, Benjamin Cummings, 1984. 11. V. Robins, Computational Topology at Multiple Resolutions, PhD thesis, June 2000. 12. V. Robins, Computational Topology for Point Data: Betti Numbers of Alpha- Shapes, pp.261-275, in Morphology of Condensed Matter: Physics and Geometry of Spatially Complex Systems, Lecture Notes in Physics 600, Springer (2002). 13. J. K. Udupa, Surface connectedness in digital spaces, Topological Algorithms for Digital Images Processing, Elsevier, Amsterdam, 1993. 14. J. Williams, editor. Geographic information from Space: processing an applications of geocoded satellite images. Wiley, 1995. 4
Simplicial Complexes: mathematical innovative instruments for applications / Bonanzinga, Vittoria; Sorrenti, L.. - (2006). (Intervento presentato al convegno VIII Congresso Società Italiana di Matematica Applicata e Industriale - SIMAI 2006 tenutosi a Baia Samuele, Ragusa (Italia) nel 22-26 maggio 2006).
Simplicial Complexes: mathematical innovative instruments for applications
BONANZINGA, Vittoria;
2006-01-01
Abstract
Minisymposium: Algebraic models arising from phenomenals in statistic, transportation problems, manufacturing and other fields Simplicial Complexes: mathematical innovative instruments for applications Vittoria BONANZINGA University of Reggio Calabria-DIMET Faculty of Engineering, via Graziella (Feo di Vito), 89100 Reggio Calabria (ITALIA). bonanzin@ing.unirc.it, vittoria.bonanzinga@tin.it Loredana SORRENTI University of Messina Department of Mathematics, C.da Papardo, Salita Sperone 31, 98166 Messina (ITALIA). sorrenti@dipmat.unime.it, sorrenti.loredana@tiscali.it 1 Introduction and formulation of the problems The morphisms in the categories of the simplicial complexes are capable of modelling many transformations used in graphics. We study some theoretical aspects of such combinatoric objects. Our approach is to determine some combinatoric properties of simplicial complexes by studying the algebraic properties of the monomial ideals associated. Let E denote the exterior algebra of the vector space V over a field k with basis e1, . . . , en. Here we consider a special class of monomial ideals of E, the so called completely lexsegment ideal. For any subset = {i1, ..., id} of {1, ..., n} with i1 < i2 < ... < id we call e = ei1 ^ ... ^ eid a monomial of degree d and we denote the set of all monomials of degree d by Md. In order to simplify notation, we set uv for the product u ^ v for any two elements u and v. An ideal I E generated by monomials is called a monomial ideal. We order the monomials lexicographically so that e1 > e2 > ... > en. A lexsegment of degree d is a subset of Md of the form L(u, v) = {w 2 Md : u w v}. A lexsegment ideal is an ideal generated by a lexsegment. Lexsegment ideals in the polynomial ring were first introduced by Hulett and Martin [8]. In extremal combinatorics one usually considers more special lexsegment ideals, which we call initial lexsegment ideals. These are ideals which in each degree are generated by initial lexsegments, that is, sets of the form: Li(v) = {w 2 Md : w v}, called simple lexsegments in usual terminology. A final lexsegment is a set of the form: Lf (u) = {w 2 Md : w u}. A final lexsegment ideal is an ideal which is generated by a final lexsegment. A lexsegment L is called completely lexsegment if all the iterated shadows of L are again lexsegment. We recall that the shadow of a set S of monomials in Md is the set of the non-zero monomials: Shad(S) = {sei : 8s 2 S, 8i /2 supp(s)}, where the support of a monomial u 2 E is supp(u) = {i : ei divides u}. We define the 1 i−th shadow recursively by Shadi(S) = Shad(Shadi−1(S)). We give a description of completely lexsegment ideals in the exterior algebra and we study the vanishing and non vanishing of reduced simplicial cohomology groups of a simplicial complex and of certain subcomplexes of with coefficients in a field k. 2 Results There is a full description of squarefree completely lexsegment ideals in [2]. In [4] squarefree completely lexsegment ideals with linear resolution have been characterized. In [1] Aramova, Avramov and Herzog showed that a squarefree monomial ideal I has a linear free resolution over the polynomial ring if and only if the corresponding ideal J in the exterior algebra has a linear free resolution. This correspondence gives us a description of completely lexsegment ideals with linear resolution in the exterior algebra by translating the results obtained in [4] for squarefree monomial ideals in the polynomial ring to the corresponding statements in the exterior algebra. In particular it holds the following: Theorem 2.1 Let u, v 2 Md monomials with u v be and I = (L(u, v)) be a completely lexsegment ideal. Let k be the smallest integer such that (ik, jk) 6= (k, k) and B = {w 2 Md : w < v, {1, . . . , k − 1} suppw} \ {w < v : xkw0 u}. Then I has a linear resolution if and only if one of the following conditions holds: (a) u = e1 · · · ek−1eik · · · eid with eik · · · eid ek+2 · · · ed+2 and v = e1 · · · ek−1en−d+ken−d+k+1 · · · en (b) ik = k and the following condition holds: for every (w1,w2) 2 B×B with w1 6= w2 there exists an index l, m(w1) l < M(w2) such that ekw1 em(w1) u, ekw2 xl u and w1 em(w1) 6= w2 el . We investigate some properties of the simplicial complexes associated with completely lexsegment ideals and with lexsegment ideals with linear resolution. Let be a simplicial complex on a set T of vertexes. We write I for the ideal of E generated by all monomials eF , F /2 . A simplicial complex is called lexsegment if the corresponding ideal I is a lexsegment ideal. In the following we study the vanishing and non vanishing of reduced simplicial cohomology groups of a simplicial complex when I has a linear resolution or when I is a completely lexsegment ideal. Proposition 2.2 If I is a monomial ideal generated in degree d n and with linear resolution then ˜H i(; k) = 0 for all i 6= d − 2 In the next theorem we compute the reduced simplicial cohomology groups of a certain subcomplex of a lexsegment simplicial complex. 2 Theorem 2.3 If I is a completely lexsegment ideal generated in degree d n. Then ˜H i(T , k) = 0 for all i 6= d − 2, d − 3 and all ; 6= T [n] 3 Applicative Aspects The computation of homology and cohomology simplicial groups is a useful tool in computational topology, an active research field which deals with the study of topological properties of an object that can be computed to some finite accuracy. There is a growing literature on the formalization and representation of topological questions for computer applications, see [5] for a survey of this field. Application areas include digital image processing, solid modelling for computer design, topology preserving morphisms in computer graphics, 3-d models of protein molecules. The earliest applications work on extracting topological information from data targeted digital images. These are typically represented by binary data on a fixed regular grid in two or in three dimensions, pixels and voxels. This field has many applications, for example, in computing the boundaries of a drainage basin from satellite data [14]. Much work in this area focuses on algorithms for the labeling of components [9], boundaries [14] and other features of digital images. An image can be modelled by a topological subspace X Rn. The homology groups of X characterize the number and the type of holes and the number of connected components. This type of information is used, for example, for determining similarities between proteins in molecular biology [5]. Existing work on extracting topological information by the analysis of a finite set of points of X includes a number of approaches to computational homology. The first step in computing homology from point sets is to build a triangulation that reflects the topology of the data. Once this is done, it is possible, though costly, to compute representations of the homology groups from the complex. The computability of homology groups from a given triangulation is well-known and the algorithm uses simple linear algebra [10]. However, these algorithms have run times at best cubic in the number of simplices. So, the problem of computing homology groups is an active area of research. In order to solve problems related to cost times it would be useful to build algorithms with a lower computational cost. Another approach is to compute homology using algebraic and topological tools. In [6] M. Grandis develops combinatorial homotopical tools consisting essentially of intrinsic homotopic theory for simplicial complexes and in [7] he applies these tools to explore mathematical models representing images. In many applications knowledge of the structure of the homology groups is not necessary, all that is needed is the rank of the simplicial homology groups, i.e., the Betti numbers. In [12] and in [11] V. Robins considers the problem of determining information about the topology of a subset X Rn given only a finite point approximation to X. Her approach is to compute topological information, such as the number of connected components and the number of holes, given by Betti numbers. For subset of R3 she interprets the 3 Betti number 0 as the number of path-connected components, 1 as the number of independent tunnels, and 2 as the number of enclosed voids. This kind of information can be deduced by applying results of [3], which give us the ranks of homology groups in some special cases, coming from triangulations associated with completely lexsegment ideals or with ideals with linear resolution, but with the advantage of computing the ranks of the homology groups not using computer implementations. REFERENCES 1. A. Aramova, L. L. Avramov, J. Herzog, Resolutions of monomial ideals and cohomology over exterior algebras, Trans. AMS. 352 (2) (2000), 579-594 2. V. Bonanzinga, Lexsegment ideals in the exterior algebra, in ”Geometric and Combinatorial aspects of commutative algebra”, (J. Herzog and G. Restuccia Eds.), Lect. Notes in Pure and Appl. Math., 4, Dekker, New York, (1999), 43-56. 3. V. Bonanzinga, L. Sorrenti, Lexsegment ideals and reduced simplicial cohomology groups, Preprint 2006. 4. V. Bonanzinga, L. Sorrenti, Squarefree lexsegment ideals with linear resolution, Preprint 2005. 5. T.K. Dey, H. Edelsbrunner, S. Guha, Computational topology, Advances in Discrete and Computational Geometry, 223, Contemporary mathematics. AMS, 1999. 6. M. Grandis, An intrinsec homotopy theory for simplicial complexes, with applications to image analysis, Appl. Cat. Structures 10 (2002), 99-155. 7. M. Grandis, Ordinary and directed combinatorial homotopy, applied to image analisys and cuncurrency, Homology, Homotopy and Applications, 5(2), 2003, pp. 211- 231. 8. H. A. Hulett, H. M. Martin, Betti numbers of lexsegment ideals, J. Algebra 275 (2004), 2, 629-638. 9. T. Y. Kong, A. Rosenfeld, Digital Topolgy: Introduction and survey, Computer Vision, Graphics and Image Processing, 48, 357-393, 1989. 10. J. R. Munkres, Elements of Algebraic Topology, Benjamin Cummings, 1984. 11. V. Robins, Computational Topology at Multiple Resolutions, PhD thesis, June 2000. 12. V. Robins, Computational Topology for Point Data: Betti Numbers of Alpha- Shapes, pp.261-275, in Morphology of Condensed Matter: Physics and Geometry of Spatially Complex Systems, Lecture Notes in Physics 600, Springer (2002). 13. J. K. Udupa, Surface connectedness in digital spaces, Topological Algorithms for Digital Images Processing, Elsevier, Amsterdam, 1993. 14. J. Williams, editor. Geographic information from Space: processing an applications of geocoded satellite images. Wiley, 1995. 4I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
