{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T20:03:58Z","timestamp":1760731438157,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T00:00:00Z","timestamp":1618272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T00:00:00Z","timestamp":1618272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The combination of persistent homology and discrete Morse theory has proven very effective in visualizing and analyzing big and heterogeneous data. Indeed, topology provides computable and coarse summaries of data independently from specific coordinate systems and does so robustly to noise. Moreover, the geometric content of a discrete gradient vector field is very useful for visualization purposes. The specific case of multivariate data still demands for further investigations, on the one hand, for computational reasons, it is important to reduce the necessary amount of data to be processed. On the other hand, for analysis reasons, the multivariate case requires the detection and interpretation of the possible interdepedance among data components. To this end, in this paper we introduce and study a notion of perfectness for discrete gradient vector fields with respect to multi-parameter persistent homology, called relative-perfectness. As a natural generalization of usual perfectness in Morse theory for homology, relative-perfectness entails having the least number of critical cells relevant for multi-parameter persistence. As a first contribution, we support our definition of relative-perfectness by generalizing Morse inequalities to the filtration structure where homology groups involved are relative with respect to subsequent sublevel sets. In order to allow for an interpretation of critical cells in 2-parameter persistence, our second contribution consists of two inequalities bounding Betti tables of persistence modules from above and below, via the number of critical cells. Our last result is the proof that existing algorithms based on local homotopy expansions allow for efficient computability over simplicial complexes up to dimension 2.<\/jats:p>","DOI":"10.1007\/s10878-021-00729-x","type":"journal-article","created":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T11:06:11Z","timestamp":1618311971000},"page":"2347-2374","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Relative-perfectness of discrete gradient vector fields and multi-parameter persistent homology"],"prefix":"10.1007","volume":"44","author":[{"given":"Claudia","family":"Landi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4010-6507","authenticated-orcid":false,"given":"Sara","family":"Scaramuccia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,13]]},"reference":[{"key":"729_CR1","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.jsc.2015.11.020","volume":"78","author":"M Allili","year":"2017","unstructured":"Allili M, Kaczynski T, Landi C (2017) Reducing complexes in multidimensional persistent homology theory. J Symb Comput 78:61\u201375","journal-title":"J Symb Comput"},{"key":"729_CR2","doi-asserted-by":"crossref","unstructured":"Allili M, Kaczynski T, Landi C, Masoni F (2017) Algorithmic Construction of Acyclic Partial Matchings for Multidimensional Persistence. In: Discrete Geometry for Computer Imagery DGCI 2017. Lecture Notes in Computer Science, vol 10502, pp. 375\u2013387","DOI":"10.1007\/978-3-319-66272-5_30"},{"issue":"08","key":"729_CR3","doi-asserted-by":"publisher","first-page":"3003","DOI":"10.1090\/S0002-9939-10-10312-8","volume":"138","author":"F Cagliari","year":"2010","unstructured":"Cagliari F, Di Fabio B, Ferri M (2010) One-dimensional reduction of multidimensional persistent homology. Proc Am Math Soc 138(08):3003\u20133003","journal-title":"Proc Am Math Soc"},{"key":"729_CR4","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1090\/S0273-0979-09-01249-X","volume":"46","author":"G Carlsson","year":"2009","unstructured":"Carlsson G (2009) Topology and data. Bull Am Math Soc 46:255\u2013308","journal-title":"Bull Am Math Soc"},{"issue":"1","key":"729_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s00454-009-9176-0","volume":"42","author":"G Carlsson","year":"2009","unstructured":"Carlsson G, Zomorodian A (2009) The theory of multidimensional persistence. Discret Comput Geom 42(1):71\u201393","journal-title":"Discret Comput Geom"},{"key":"729_CR6","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1016\/j.camwa.2013.06.004","volume":"66","author":"N Cavazza","year":"2013","unstructured":"Cavazza N, Ethier M, Frosini P, Kaczynski T, Landi C (2013) Comparison of persistent homologies for vector functions: from continuous to discrete and back. Comput Math Appl 66:560\u2013573","journal-title":"Comput Math Appl"},{"key":"729_CR7","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1002\/mma.2704","volume":"36","author":"A Cerri","year":"2013","unstructured":"Cerri A, Di Fabio B, Ferri M, Frosini P, Landi C (2013) Betti numbers in multidimensional persistent homology are stable functions. Math Methods Appl Sci 36:1543\u20131557","journal-title":"Math Methods Appl Sci"},{"key":"729_CR8","unstructured":"Cerri A, Frosini P (2009) Discontinuities in Multidimensional Size Functions. ArXiv repository pp. 1\u201323"},{"issue":"2","key":"729_CR9","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1111\/cgf.12596","volume":"34","author":"L De Floriani","year":"2015","unstructured":"De Floriani L, Fugacci U, Iuricich F, Magillo P (2015) Morse complexes for shape segmentation and homological analysis: discrete models and algorithms. Comput Gr Forum 34(2):761\u2013785","journal-title":"Comput Gr Forum"},{"key":"729_CR10","volume-title":"Computational topology - an introduction","author":"H Edelsbrunner","year":"2010","unstructured":"Edelsbrunner H, Harer J (2010) Computational topology - an introduction. American Mathematical Society, Providence"},{"issue":"1","key":"729_CR11","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF02684323","volume":"14","author":"J Eells","year":"1962","unstructured":"Eells J, Kuiper NH (1962) Manifolds which are like projective planes. Publications Math\u00e9matiques de L\u2019Institut des Hautes Scientifiques 14(1):5\u20136","journal-title":"Publications Math\u00e9matiques de L\u2019Institut des Hautes Scientifiques"},{"key":"729_CR12","volume-title":"The geometry of syzygies: a second course in commutative algebra and algebraic geometry","author":"D Eisenbud","year":"2005","unstructured":"Eisenbud D (2005) The geometry of syzygies: a second course in commutative algebra and algebraic geometry. Springer, New York"},{"key":"729_CR13","doi-asserted-by":"crossref","unstructured":"Fellegara R, Luricich F, De Floriani L, Weiss K (2014) Efficient computation and simplification of discrete morse decompositions on triangulated terrains. In: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - SIGSPATIAL \u201914, pp. 223\u2013232","DOI":"10.1145\/2666310.2666412"},{"key":"729_CR14","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1006\/aima.1997.1650","volume":"134","author":"R Forman","year":"1998","unstructured":"Forman R (1998) Morse theory for cell complexes. Adv Math 134:90\u2013145","journal-title":"Adv Math"},{"key":"729_CR15","unstructured":"Fugacci U, Kerber M (2019) Chunk reduction for multi-parameter persistent homology. In: 35th International Symposium on Computational Geometry (SoCG 2019), vol. 129"},{"issue":"3","key":"729_CR16","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1111\/cgf.12933","volume":"35","author":"C Heine","year":"2016","unstructured":"Heine C, Leitte H, Hlawitschka M, Iuricich F, De Floriani L, Scheuermann G, Hagen H, Garth C (2016) A survey of topology-based methods in visualization. Comput Gr Forum 35(3):643\u2013667","journal-title":"Comput Gr Forum"},{"key":"729_CR17","doi-asserted-by":"crossref","unstructured":"Iuricich F, Scaramuccia S, Landi C, De Floriani L (2016) A discrete Morse-based approach to multivariate data analysis. SIGGRAPH ASIA 2016 Symposium on Visualization on - SA \u201916 Dec, 1\u20138","DOI":"10.1145\/3002151.3002166"},{"issue":"3","key":"729_CR18","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1109\/TVCG.2012.110","volume":"19","author":"J Kehrer","year":"2013","unstructured":"Kehrer J, Hauser H (2013) Visualization and visual analysis of multifaceted scientific data: a survey. IEEE Trans V Comput Gr 19(3):495\u2013513","journal-title":"IEEE Trans V Comput Gr"},{"issue":"4","key":"729_CR19","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1080\/10586458.2005.10128941","volume":"14","author":"H King","year":"2005","unstructured":"King H, Knudson K, Mramor N (2005) Generating discrete morse functions from point data. Exp Math 14(4):435\u2013444","journal-title":"Exp Math"},{"key":"729_CR20","doi-asserted-by":"crossref","unstructured":"Knudson K (2008) A refinement of multi-dimensional persistence. Homology, Homotopy and Applications","DOI":"10.4310\/HHA.2008.v10.n1.a11"},{"key":"729_CR21","volume-title":"Algebraic topology","author":"S Lefschetz","year":"1942","unstructured":"Lefschetz S (1942) Algebraic topology. Colloquium Publications, Providence"},{"key":"729_CR22","unstructured":"Lesnick M, Wright M (2015) Interactive Visualization of 2-D Persistence Modules. ArXiv preprint pp. 1\u201375"},{"issue":"3","key":"729_CR23","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/S0925-7721(03)00014-2","volume":"26","author":"T Lewiner","year":"2003","unstructured":"Lewiner T, Lopes H, Tavares G (2003) Optimal discrete Morse functions for 2-manifolds. Comput Geom 26(3):221\u2013233","journal-title":"Comput Geom"},{"key":"729_CR24","doi-asserted-by":"publisher","DOI":"10.1515\/9781400881802","volume-title":"Morse theory","author":"J Milnor","year":"1963","unstructured":"Milnor J (1963) Morse theory. Princeton University Press, Princeton"},{"issue":"2","key":"729_CR25","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/s00454-013-9529-6","volume":"50","author":"K Mischaikow","year":"2013","unstructured":"Mischaikow K, Nanda V (2013) Morse theory for filtrations and efficient computation of persistent homology. Discret Comput Geom 50(2):330\u2013353","journal-title":"Discret Comput Geom"},{"issue":"8","key":"729_CR26","doi-asserted-by":"publisher","first-page":"1646","DOI":"10.1109\/TPAMI.2011.95","volume":"33","author":"V Robins","year":"2011","unstructured":"Robins V, Wood PJ, Sheppard AP (2011) Theory and algorithms for constructing discrete Morse complexes from grayscale digital images. IEEE Trans Pattern Anal Mach Intell 33(8):1646\u20131658","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"729_CR27","doi-asserted-by":"publisher","first-page":"101623","DOI":"10.1016\/j.comgeo.2020.101623","volume":"89","author":"S Scaramuccia","year":"2020","unstructured":"Scaramuccia S, Iuricich F, De Floriani L, Landi C (2020) Computing multiparameter persistent homology through a discrete Morse-based approach. Comput Geom Theory Appl 89:101623","journal-title":"Comput Geom Theory Appl"},{"issue":"2","key":"729_CR28","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF00485983","volume":"31","author":"S Smale","year":"1975","unstructured":"Smale S (1975) Global analysis and economics - Pareto optimum and a generalization of Morse Theory. Synthese 31(2):345\u2013358","journal-title":"Synthese"},{"key":"729_CR29","doi-asserted-by":"crossref","unstructured":"Varli H, Pamuk M, Kosta NM (2018) Perfect discrete Morse functions on connected sums. Homology, Homotopy and Applications","DOI":"10.4310\/HHA.2018.v20.n1.a13"},{"key":"729_CR30","volume-title":"An introduction to homological algebra,","author":"CA Weibel","year":"1995","unstructured":"Weibel CA (1995) An introduction to homological algebra, vol 38. Cambridge University Press, Cambridge"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00729-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00729-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00729-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:18:58Z","timestamp":1665778738000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00729-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,13]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["729"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00729-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,4,13]]},"assertion":[{"value":"31 March 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"\u2019Not applicable\u2019","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}