{"id":229,"date":"2017-04-14T14:26:54","date_gmt":"2017-04-14T22:26:54","guid":{"rendered":"https:\/\/matsguru.com\/?p=229"},"modified":"2017-04-14T14:26:54","modified_gmt":"2017-04-14T22:26:54","slug":"random_discrete_morse","status":"publish","type":"post","link":"https:\/\/matsguru.com\/?p=229","title":{"rendered":"Random_Discrete_Morse"},"content":{"rendered":"<p><a href=\"https:\/\/boolesrings.org\/matsguru\/2013\/01\/31\/simplicial-homology\/\">Computing the topological type<\/a>, or homology, of a given a simplicial complex is straight forward, but not always computationally feasible. The bottleneck is in computing the <a href=\"https:\/\/boolesrings.org\/matsguru\/2013\/03\/22\/smith-normal-form-2\/\">Smith Normal Form<\/a>, which is a polynomial time algorithm [Kannan-Bachem], but still too slow on large examples (about cubic).<\/p>\n<p>Discrete Morse theory [Whitehead, Forman] provides a tool set which can be used to find reasonable upper bounds. \u00a0A randomized search for small discrete Morse vectors was introduced by <a href=\"https:\/\/arxiv.org\/abs\/1303.6422\">Benedetti and Lutz<\/a>, which we\u00a0implemented as a client for the <a href=\"https:\/\/polymake.org\/doku.php\">topological software package polymake<\/a>.<\/p>\n<p>I gave a <a href=\"http:\/\/page.math.tu-berlin.de\/~tsuruga\/discmorse.html\">workshop on <code>Random_Discrete_Morse<\/code><\/a> at the Homology: Theoretical and Computational Aspects (HTCA 2015) conference in Genoa, Italy.<\/p>\n<p>While experimenting with <code>Random_Discrete_Morse<\/code>, we discovered a whole family of contractible, yet non-collapsible simplicial 2-complexes. We call them the sawblade complexes. <a href=\"https:\/\/arxiv.org\/abs\/1405.3848\">Read more about the sawblade complexes here.<\/a><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-160 size-full\" src=\"https:\/\/matsguru.com\/wp-content\/uploads\/2017\/03\/sawblade-1.png\" width=\"1214\" height=\"654\" srcset=\"https:\/\/matsguru.com\/wp-content\/uploads\/2017\/03\/sawblade-1.png 1214w, https:\/\/matsguru.com\/wp-content\/uploads\/2017\/03\/sawblade-1-300x162.png 300w, https:\/\/matsguru.com\/wp-content\/uploads\/2017\/03\/sawblade-1-768x414.png 768w, https:\/\/matsguru.com\/wp-content\/uploads\/2017\/03\/sawblade-1-644x347.png 644w\" sizes=\"auto, (max-width: 1214px) 100vw, 1214px\" \/><\/p>\n<p>This project was joint work with <a href=\"http:\/\/page.math.tu-berlin.de\/~lutz\/\">Frank Lutz<\/a> and <a href=\"http:\/\/page.math.tu-berlin.de\/~joswig\/\">Michael Joswig<\/a>, with help from <a href=\"https:\/\/www.math.tu-berlin.de\/fachgebiete_ag_diskalg\/fg_diskrete_mathematik_geometrie\/v_menue\/mitarbeiter\/benjamin_lorenz\/v_menue\/home\/\">Benjamin Lorenz<\/a>, <a href=\"http:\/\/www.math.miami.edu\/~bruno\/\">Bruno Benedetti<\/a>, and <a href=\"http:\/\/www.ma.huji.ac.il\/~adiprasito\/\">Karim Adiprasito<\/a>.<\/p>\n<h4>References<\/h4>\n<ul>\n<li><a href=\"http:\/\/www.math.miami.edu\/~bruno\/\">B Benedetti<\/a> and <a href=\"http:\/\/page.math.tu-berlin.de\/~lutz\/\">FH Lutz<\/a>. <a href=\"https:\/\/arxiv.org\/abs\/1303.6422\">Random discrete Morse theory and a new library of triangulations<\/a>. Exp. Math., 23:66\u201394, 2014.<\/li>\n<li><a href=\"http:\/\/math.rice.edu\/~forman\/\">R Forman<\/a>. <a href=\"http:\/\/math.rice.edu\/~forman\/user.ps\">A user\u2019s guide to discrete Morse theory<\/a>. Se\u0301min. Lothar. Comb., 48:B48c, 35 p., electronic only, 2002.<\/li>\n<li>R Kannan and A Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput., 8(4):499\u2013507, 1979.<\/li>\n<li>JHC Whitehead. Simplicial spaces, nuclei and m-groups. Proc. Lond. Math. Soc., II. Ser., 45:243\u2013327, 1939.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Computing the topological type, or homology, of a given a simplicial complex is straight forward, but not always computationally feasible. The bottleneck is in computing the Smith Normal Form, which is a polynomial time algorithm [Kannan-Bachem], but still too slow on large examples (about cubic). Discrete Morse theory [Whitehead, Forman] provides a tool set which&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-229","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/matsguru.com\/index.php?rest_route=\/wp\/v2\/posts\/229","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matsguru.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matsguru.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matsguru.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/matsguru.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=229"}],"version-history":[{"count":1,"href":"https:\/\/matsguru.com\/index.php?rest_route=\/wp\/v2\/posts\/229\/revisions"}],"predecessor-version":[{"id":230,"href":"https:\/\/matsguru.com\/index.php?rest_route=\/wp\/v2\/posts\/229\/revisions\/230"}],"wp:attachment":[{"href":"https:\/\/matsguru.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=229"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matsguru.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=229"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matsguru.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=229"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}