[{"day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"2022-12-01T00:00:00Z","publication":"Discrete and Computational Geometry","citation":{"chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” Discrete and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-021-00364-7.","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” Discrete and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:10.1007/s00454-021-00364-7.","short":"Z. Patakova, M. Tancer, U. Wagner, Discrete and Computational Geometry 68 (2022) 1133–1154.","ista":"Patakova Z, Tancer M, Wagner U. 2022. Barycentric cuts through a convex body. Discrete and Computational Geometry. 68, 1133–1154.","apa":"Patakova, Z., Tancer, M., & Wagner, U. (2022). Barycentric cuts through a convex body. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-021-00364-7","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” Discrete and Computational Geometry, vol. 68. Springer Nature, pp. 1133–1154, 2022.","ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. Discrete and Computational Geometry. 2022;68:1133-1154. doi:10.1007/s00454-021-00364-7"},"article_type":"original","page":"1133-1154","abstract":[{"lang":"eng","text":"Let K be a convex body in Rn (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K∩h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p0 is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n≥2, there are always at least three distinct barycentric cuts through the point p0∈K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p0 are guaranteed if n≥3."}],"type":"journal_article","oa_version":"Preprint","_id":"10776","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","title":"Barycentric cuts through a convex body","intvolume":" 68","month":"12","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"doi":"10.1007/s00454-021-00364-7","language":[{"iso":"eng"}],"external_id":{"arxiv":["2003.13536"],"isi":["000750681500001"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2003.13536"}],"oa":1,"quality_controlled":"1","isi":1,"author":[{"full_name":"Patakova, Zuzana","last_name":"Patakova","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Tancer","first_name":"Martin","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568"}],"date_created":"2022-02-20T23:01:35Z","date_updated":"2023-08-02T14:38:58Z","volume":68,"year":"2022","acknowledgement":"The work by Zuzana Patáková has been partially supported by Charles University Research Center Program No. UNCE/SCI/022, and part of it was done during her research stay at IST Austria. The work by Martin Tancer is supported by the GAČR Grant 19-04113Y and by the Charles University Projects PRIMUS/17/SCI/3 and UNCE/SCI/004.","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer Nature"},{"abstract":[{"lang":"eng","text":"We prove general topological Radon-type theorems for sets in ℝ^d, smooth real manifolds or finite dimensional simplicial complexes. Combined with a recent result of Holmsen and Lee, it gives fractional Helly theorem, and consequently the existence of weak ε-nets as well as a (p,q)-theorem. More precisely: Let X be either ℝ^d, smooth real d-manifold, or a finite d-dimensional simplicial complex. Then if F is a finite, intersection-closed family of sets in X such that the ith reduced Betti number (with ℤ₂ coefficients) of any set in F is at most b for every non-negative integer i less or equal to k, then the Radon number of F is bounded in terms of b and X. Here k is the smallest integer larger or equal to d/2 - 1 if X = ℝ^d; k=d-1 if X is a smooth real d-manifold and not a surface, k=0 if X is a surface and k=d if X is a d-dimensional simplicial complex. Using the recent result of the author and Kalai, we manage to prove the following optimal bound on fractional Helly number for families of open sets in a surface: Let F be a finite family of open sets in a surface S such that the intersection of any subfamily of F is either empty, or path-connected. Then the fractional Helly number of F is at most three. This also settles a conjecture of Holmsen, Kim, and Lee about an existence of a (p,q)-theorem for open subsets of a surface."}],"type":"conference","alternative_title":["LIPIcs"],"file":[{"file_size":645421,"content_type":"application/pdf","creator":"dernst","file_name":"2020_LIPIcsSoCG_Patakova_61.pdf","access_level":"open_access","date_created":"2020-06-23T06:56:23Z","date_updated":"2020-07-14T12:48:06Z","checksum":"d0996ca5f6eb32ce955ce782b4f2afbe","relation":"main_file","file_id":"8005"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"7989","status":"public","ddc":["510"],"title":"Bounding radon number via Betti numbers","intvolume":" 164","day":"01","article_processing_charge":"No","has_accepted_license":"1","scopus_import":"1","date_published":"2020-06-01T00:00:00Z","publication":"36th International Symposium on Computational Geometry","citation":{"ama":"Patakova Z. Bounding radon number via Betti numbers. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.61","apa":"Patakova, Z. (2020). Bounding radon number via Betti numbers. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.61","ieee":"Z. Patakova, “Bounding radon number via Betti numbers,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","ista":"Patakova Z. 2020. Bounding radon number via Betti numbers. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 61:1-61:13.","short":"Z. Patakova, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” 36th International Symposium on Computational Geometry, vol. 164, 61:1-61:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.61.","chicago":"Patakova, Zuzana. “Bounding Radon Number via Betti Numbers.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.61."},"file_date_updated":"2020-07-14T12:48:06Z","article_number":"61:1-61:13","author":[{"last_name":"Patakova","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana"}],"date_updated":"2021-01-12T08:16:22Z","date_created":"2020-06-22T09:14:18Z","volume":164,"year":"2020","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"month":"06","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2020-06-26","start_date":"2020-06-22","location":"Zürich, Switzerland"},"doi":"10.4230/LIPIcs.SoCG.2020.61","language":[{"iso":"eng"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1908.01677"]},"quality_controlled":"1"},{"month":"06","publication_identifier":{"issn":["18688969"],"isbn":["9783959771436"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["2003.13536"]},"oa":1,"quality_controlled":"1","conference":{"end_date":"2020-06-26","location":"Zürich, Switzerland","start_date":"2020-06-22","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.4230/LIPIcs.SoCG.2020.62","language":[{"iso":"eng"}],"article_number":"62:1 - 62:16","file_date_updated":"2020-07-14T12:48:06Z","year":"2020","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","author":[{"full_name":"Patakova, Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683","first_name":"Zuzana","last_name":"Patakova"},{"first_name":"Martin","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"date_created":"2020-06-22T09:14:20Z","date_updated":"2021-01-12T08:16:23Z","volume":164,"scopus_import":1,"day":"01","has_accepted_license":"1","article_processing_charge":"No","publication":"36th International Symposium on Computational Geometry","citation":{"ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. In: 36th International Symposium on Computational Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:10.4230/LIPIcs.SoCG.2020.62","ista":"Patakova Z, Tancer M, Wagner U. 2020. Barycentric cuts through a convex body. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 62:1-62:16.","apa":"Patakova, Z., Tancer, M., & Wagner, U. (2020). Barycentric cuts through a convex body. In 36th International Symposium on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.62","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” in 36th International Symposium on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” 36th International Symposium on Computational Geometry, vol. 164, 62:1-62:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.62.","short":"Z. Patakova, M. Tancer, U. Wagner, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” In 36th International Symposium on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.62."},"date_published":"2020-06-01T00:00:00Z","type":"conference","alternative_title":["LIPIcs"],"abstract":[{"lang":"eng","text":"Let K be a convex body in ℝⁿ (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K ∩ h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p₀ is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n ≥ 2, there are always at least three distinct barycentric cuts through the point p₀ ∈ K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p₀ are guaranteed if n ≥ 3."}],"_id":"7992","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["510"],"status":"public","title":"Barycentric cuts through a convex body","intvolume":" 164","oa_version":"Published Version","file":[{"file_name":"2020_LIPIcsSoCG_Patakova.pdf","access_level":"open_access","creator":"dernst","file_size":750318,"content_type":"application/pdf","file_id":"8004","relation":"main_file","date_updated":"2020-07-14T12:48:06Z","date_created":"2020-06-23T06:45:52Z","checksum":"ce1c9194139a664fb59d1efdfc88eaae"}]},{"date_published":"2020-09-01T00:00:00Z","citation":{"ama":"Kalai G, Patakova Z. Intersection patterns of planar sets. Discrete and Computational Geometry. 2020;64:304-323. doi:10.1007/s00454-020-00205-z","ista":"Kalai G, Patakova Z. 2020. Intersection patterns of planar sets. Discrete and Computational Geometry. 64, 304–323.","apa":"Kalai, G., & Patakova, Z. (2020). Intersection patterns of planar sets. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00205-z","ieee":"G. Kalai and Z. Patakova, “Intersection patterns of planar sets,” Discrete and Computational Geometry, vol. 64. Springer Nature, pp. 304–323, 2020.","mla":"Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” Discrete and Computational Geometry, vol. 64, Springer Nature, 2020, pp. 304–23, doi:10.1007/s00454-020-00205-z.","short":"G. Kalai, Z. Patakova, Discrete and Computational Geometry 64 (2020) 304–323.","chicago":"Kalai, Gil, and Zuzana Patakova. “Intersection Patterns of Planar Sets.” Discrete and Computational Geometry. Springer Nature, 2020. https://doi.org/10.1007/s00454-020-00205-z."},"publication":"Discrete and Computational Geometry","page":"304-323","article_type":"original","article_processing_charge":"No","day":"01","scopus_import":"1","oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"7960","intvolume":" 64","title":"Intersection patterns of planar sets","status":"public","abstract":[{"text":"Let A={A1,…,An} be a family of sets in the plane. For 0≤i2b be integers. We prove that if each k-wise or (k+1)-wise intersection of sets from A has at most b path-connected components, which all are open, then fk+1=0 implies fk≤cfk−1 for some positive constant c depending only on b and k. These results also extend to two-dimensional compact surfaces.","lang":"eng"}],"type":"journal_article","doi":"10.1007/s00454-020-00205-z","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1907.00885","open_access":"1"}],"external_id":{"isi":["000537329400001"],"arxiv":["1907.00885"]},"isi":1,"quality_controlled":"1","publication_identifier":{"issn":["01795376"],"eissn":["14320444"]},"month":"09","author":[{"full_name":"Kalai, Gil","first_name":"Gil","last_name":"Kalai"},{"last_name":"Patakova","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana"}],"volume":64,"date_updated":"2023-08-21T08:26:34Z","date_created":"2020-06-14T22:00:50Z","acknowledgement":"We are very grateful to Pavel Paták for many helpful discussions and remarks. We also thank the referees for helpful comments, which greatly improved the presentation.\r\nThe project was supported by ERC Advanced Grant 320924. GK was also partially supported by NSF grant DMS1300120. The research stay of ZP at IST Austria is funded by the project CZ.02.2.69/0.0/0.0/17_050/0008466 Improvement of internationalization in the field of research and development at Charles University, through the support of quality projects MSCA-IF.","year":"2020","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"publication_status":"published"},{"article_number":"21","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"184"}]},"author":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"last_name":"Patak","first_name":"Pavel","id":"B593B804-1035-11EA-B4F1-947645A5BB83","full_name":"Patak, Pavel"},{"last_name":"Patakova","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","last_name":"Tancer"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"volume":66,"date_updated":"2023-09-06T11:10:58Z","date_created":"2019-11-26T10:13:59Z","year":"2019","publisher":"ACM","department":[{"_id":"UlWa"}],"publication_status":"published","publication_identifier":{"issn":["0004-5411"]},"month":"06","doi":"10.1145/3314024","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/pdf/1711.08436.pdf"}],"external_id":{"isi":["000495406300007"],"arxiv":["1711.08436"]},"oa":1,"isi":1,"quality_controlled":"1","issue":"3","abstract":[{"lang":"eng","text":"We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes. Another simple corollary of our result is that it is NP-hard to decide whether a given poset is CL-shellable."}],"type":"journal_article","oa_version":"Preprint","_id":"7108","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","intvolume":" 66","title":"Shellability is NP-complete","status":"public","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2019-06-01T00:00:00Z","citation":{"mla":"Goaoc, Xavier, et al. “Shellability Is NP-Complete.” Journal of the ACM, vol. 66, no. 3, 21, ACM, 2019, doi:10.1145/3314024.","short":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner, Journal of the ACM 66 (2019).","chicago":"Goaoc, Xavier, Pavel Patak, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete.” Journal of the ACM. ACM, 2019. https://doi.org/10.1145/3314024.","ama":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. Journal of the ACM. 2019;66(3). doi:10.1145/3314024","ista":"Goaoc X, Patak P, Patakova Z, Tancer M, Wagner U. 2019. Shellability is NP-complete. Journal of the ACM. 66(3), 21.","ieee":"X. Goaoc, P. Patak, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” Journal of the ACM, vol. 66, no. 3. ACM, 2019.","apa":"Goaoc, X., Patak, P., Patakova, Z., Tancer, M., & Wagner, U. (2019). Shellability is NP-complete. Journal of the ACM. ACM. https://doi.org/10.1145/3314024"},"publication":"Journal of the ACM","article_type":"original"},{"month":"06","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"quality_controlled":"1","doi":"10.4230/LIPIcs.SoCG.2018.41","conference":{"location":"Budapest, Hungary","start_date":"2018-06-11","end_date":"2018-06-14","name":"SoCG: Symposium on Computational Geometry"},"language":[{"iso":"eng"}],"publist_id":"7736","file_date_updated":"2020-07-14T12:45:18Z","year":"2018","acknowledgement":"Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration.","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","related_material":{"record":[{"status":"public","relation":"later_version","id":"7108"}]},"author":[{"first_name":"Xavier","last_name":"Goaoc","full_name":"Goaoc, Xavier"},{"full_name":"Paták, Pavel","first_name":"Pavel","last_name":"Paták"},{"full_name":"Patakova, Zuzana","first_name":"Zuzana","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683"},{"last_name":"Tancer","first_name":"Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"volume":99,"date_created":"2018-12-11T11:45:04Z","date_updated":"2023-09-06T11:10:57Z","scopus_import":1,"has_accepted_license":"1","day":"11","citation":{"mla":"Goaoc, Xavier, et al. Shellability Is NP-Complete. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16, doi:10.4230/LIPIcs.SoCG.2018.41.","short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 41:1-41:16.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Shellability Is NP-Complete,” 99:41:1-41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.41.","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Shellability is NP-complete. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:41:1-41:16. doi:10.4230/LIPIcs.SoCG.2018.41","ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2018. Shellability is NP-complete. SoCG: Symposium on Computational Geometry, Leibniz International Proceedings in Information, LIPIcs, vol. 99, 41:1-41:16.","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Shellability is NP-complete,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, p. 41:1-41:16.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2018). Shellability is NP-complete (Vol. 99, p. 41:1-41:16). Presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2018.41"},"page":"41:1 - 41:16","date_published":"2018-06-11T00:00:00Z","type":"conference","alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"abstract":[{"lang":"eng","text":"We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"184","intvolume":" 99","status":"public","ddc":["516","000"],"title":"Shellability is NP-complete","file":[{"relation":"main_file","file_id":"5725","date_created":"2018-12-17T16:35:02Z","date_updated":"2020-07-14T12:45:18Z","checksum":"d12bdd60f04a57307867704b5f930afd","file_name":"2018_LIPIcs_Goaoc.pdf","access_level":"open_access","content_type":"application/pdf","file_size":718414,"creator":"dernst"}],"oa_version":"Published Version"},{"date_updated":"2023-02-23T10:02:13Z","date_created":"2018-12-11T11:47:29Z","volume":222,"author":[{"first_name":"Xavier","last_name":"Goaoc","full_name":"Goaoc, Xavier"},{"last_name":"Mabillard","first_name":"Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"last_name":"Patakova","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","full_name":"Patakova, Zuzana"},{"last_name":"Tancer","first_name":"Martin","orcid":"0000-0002-1191-6714","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","full_name":"Tancer, Martin"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"}],"related_material":{"record":[{"id":"1511","status":"public","relation":"earlier_version"}]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer","acknowledgement":"The work by Z. P. was partially supported by the Israel Science Foundation grant ISF-768/12. The work by Z. P. and M. T. was partially supported by the project CE-ITI (GACR P202/12/G061) of the Czech Science Foundation and by the ERC Advanced Grant No. 267165. Part of the research work of M.T. was conducted at IST Austria, supported by an IST Fellowship. The research of P. P. was supported by the ERC Advanced grant no. 320924. The work by I. M. and U. W. was supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and SNSF-PP00P2-138948). The collaboration between U. W. and X. G. was partially supported by the LabEx Bézout (ANR-10-LABX-58).","year":"2017","ec_funded":1,"publist_id":"7194","language":[{"iso":"eng"}],"doi":"10.1007/s11856-017-1607-7","quality_controlled":"1","project":[{"grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1610.09063"}],"month":"10","oa_version":"Preprint","status":"public","title":"On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result","intvolume":" 222","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"610","abstract":[{"lang":"eng","text":"The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph Kn embeds in a closed surface M (other than the Klein bottle) if and only if (n−3)(n−4) ≤ 6b1(M), where b1(M) is the first Z2-Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1) embeds in R2k if and only if n ≤ 2k + 1. Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k − 1)-connected 2k-manifold with kth Z2-Betti number bk only if the following generalized Heawood inequality holds: (k+1 n−k−1) ≤ (k+1 2k+1)bk. This is a common generalization of the case of graphs on surfaces as well as the van Kampen–Flores theorem. In the spirit of Kühnel’s conjecture, we prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold with kth Z2-Betti number bk, then n ≤ 2bk(k 2k+2)+2k+4. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k−1)-connected. Our results generalize to maps without q-covered points, in the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition."}],"issue":"2","type":"journal_article","date_published":"2017-10-01T00:00:00Z","page":"841 - 866","publication":"Israel Journal of Mathematics","citation":{"mla":"Goaoc, Xavier, et al. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” Israel Journal of Mathematics, vol. 222, no. 2, Springer, 2017, pp. 841–66, doi:10.1007/s11856-017-1607-7.","short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, Israel Journal of Mathematics 222 (2017) 841–866.","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A van Kampen–Flores Type Nonembeddability Result.” Israel Journal of Mathematics. Springer, 2017. https://doi.org/10.1007/s11856-017-1607-7.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. 2017;222(2):841-866. doi:10.1007/s11856-017-1607-7","ista":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2017. On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. 222(2), 841–866.","apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2017). On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-017-1607-7","ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result,” Israel Journal of Mathematics, vol. 222, no. 2. Springer, pp. 841–866, 2017."},"day":"01","scopus_import":1},{"department":[{"_id":"UlWa"}],"publisher":"International Press","publication_status":"published","year":"2017","volume":24,"date_created":"2018-12-11T11:48:00Z","date_updated":"2021-01-12T08:11:28Z","author":[{"first_name":"Jan","last_name":"Kynčl","full_name":"Kynčl, Jan"},{"full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova","first_name":"Zuzana"}],"publist_id":"6996","file_date_updated":"2020-07-14T12:47:47Z","quality_controlled":"1","oa":1,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["10778926"]},"month":"07","intvolume":" 24","ddc":["500"],"status":"public","title":"On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"701","oa_version":"Submitted Version","file":[{"file_name":"IST-2018-984-v1+1_Patakova_on_the_nonexistence_of_k-reptile_simplices_in_R_3_and_R_4_2017.pdf","access_level":"open_access","creator":"system","file_size":544042,"content_type":"application/pdf","file_id":"5077","relation":"main_file","date_created":"2018-12-12T10:14:25Z","date_updated":"2020-07-14T12:47:47Z","checksum":"a431e573e31df13bc0f66de3061006ec"}],"pubrep_id":"984","type":"journal_article","issue":"3","abstract":[{"lang":"eng","text":"A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d = 2, triangular k-reptiles exist for all k of the form a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only k-reptile simplices that are known for d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra can exist only for k = m^3. We then prove a weaker analogue of this result for d = 4 by showing that four-dimensional k-reptile simplices can exist only for k = m^2."}],"page":"1-44","citation":{"ama":"Kynčl J, Patakova Z. On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. 2017;24(3):1-44.","ista":"Kynčl J, Patakova Z. 2017. On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. 24(3), 1–44.","ieee":"J. Kynčl and Z. Patakova, “On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4,” The Electronic Journal of Combinatorics, vol. 24, no. 3. International Press, pp. 1–44, 2017.","apa":"Kynčl, J., & Patakova, Z. (2017). On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4. The Electronic Journal of Combinatorics. International Press.","mla":"Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices in ℝ^3 and ℝ^4.” The Electronic Journal of Combinatorics, vol. 24, no. 3, International Press, 2017, pp. 1–44.","short":"J. Kynčl, Z. Patakova, The Electronic Journal of Combinatorics 24 (2017) 1–44.","chicago":"Kynčl, Jan, and Zuzana Patakova. “On the Nonexistence of k Reptile Simplices in ℝ^3 and ℝ^4.” The Electronic Journal of Combinatorics. International Press, 2017."},"publication":"The Electronic Journal of Combinatorics","date_published":"2017-07-14T00:00:00Z","has_accepted_license":"1","day":"14"},{"department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","acknowledgement":"The work by Z. P. was partially supported by the Charles University Grant SVV-2014-260103. The\r\nwork by Z. P. and M. T. was partially supported by the project CE-ITI (GACR P202/12/G061) of\r\nthe Czech Science Foundation and by the ERC Advanced Grant No. 267165. Part of the research\r\nwork of M. T. was conducted at IST Austria, supported by an IST Fellowship. The work by U.W.\r\nwas partially supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and\r\nSNSF-PP00P2-138948).","year":"2015","volume":"34 ","date_updated":"2023-02-23T12:38:00Z","date_created":"2018-12-11T11:52:27Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"610"}]},"author":[{"first_name":"Xavier","last_name":"Goaoc","full_name":"Goaoc, Xavier"},{"id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","last_name":"Mabillard","first_name":"Isaac","full_name":"Mabillard, Isaac"},{"first_name":"Pavel","last_name":"Paták","full_name":"Paták, Pavel"},{"orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87","last_name":"Patakova","first_name":"Zuzana","full_name":"Patakova, Zuzana"},{"full_name":"Tancer, Martin","first_name":"Martin","last_name":"Tancer","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"}],"publist_id":"5666","ec_funded":1,"file_date_updated":"2020-07-14T12:44:59Z","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SOCG.2015.476","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2015-06-25","start_date":"2015-06-22","location":"Eindhoven, Netherlands"},"month":"06","ddc":["510"],"title":"On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1511","oa_version":"Published Version","file":[{"creator":"system","file_size":636735,"content_type":"application/pdf","access_level":"open_access","file_name":"IST-2016-502-v1+1_42.pdf","checksum":"0945811875351796324189312ca29e9e","date_created":"2018-12-12T10:11:18Z","date_updated":"2020-07-14T12:44:59Z","file_id":"4871","relation":"main_file"}],"pubrep_id":"502","alternative_title":["LIPIcs"],"type":"conference","abstract":[{"text":"The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.","lang":"eng"}],"page":"476 - 490","citation":{"apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2015). On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result (Vol. 34, pp. 476–490). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SOCG.2015.476","ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 476–490.","ista":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2015. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 476–490.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:476-490. doi:10.4230/LIPIcs.SOCG.2015.476","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result,” 34:476–90. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPIcs.SOCG.2015.476.","short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–490.","mla":"Goaoc, Xavier, et al. On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–90, doi:10.4230/LIPIcs.SOCG.2015.476."},"date_published":"2015-06-11T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"11"}]