[{"page":"160 - 166","citation":{"short":"R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166.","mla":"Fulek, Radoslav, and János Pach. Thrackles: An Improved Upper Bound. Vol. 10692, Springer, 2018, pp. 160–66, doi:10.1007/978-3-319-73915-1_14.","chicago":"Fulek, Radoslav, and János Pach. “Thrackles: An Improved Upper Bound,” 10692:160–66. Springer, 2018. https://doi.org/10.1007/978-3-319-73915-1_14.","ama":"Fulek R, Pach J. Thrackles: An improved upper bound. In: Vol 10692. Springer; 2018:160-166. doi:10.1007/978-3-319-73915-1_14","apa":"Fulek, R., & Pach, J. (2018). Thrackles: An improved upper bound (Vol. 10692, pp. 160–166). Presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States: Springer. https://doi.org/10.1007/978-3-319-73915-1_14","ieee":"R. Fulek and J. Pach, “Thrackles: An improved upper bound,” presented at the GD 2017: Graph Drawing and Network Visualization, Boston, MA, United States, 2018, vol. 10692, pp. 160–166.","ista":"Fulek R, Pach J. 2018. Thrackles: An improved upper bound. GD 2017: Graph Drawing and Network Visualization, LNCS, vol. 10692, 160–166."},"date_published":"2018-01-21T00:00:00Z","scopus_import":1,"day":"21","intvolume":" 10692","title":"Thrackles: An improved upper bound","status":"public","_id":"433","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Submitted Version","alternative_title":["LNCS"],"type":"conference","abstract":[{"lang":"eng","text":"A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is 3/2(n-1), and that this bound is best possible for infinitely many values of n."}],"quality_controlled":"1","oa":1,"external_id":{"arxiv":["1708.08037"]},"main_file_link":[{"url":"https://arxiv.org/abs/1708.08037","open_access":"1"}],"language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-73915-1_14","conference":{"end_date":"2017-09-27","start_date":"201-09-25","location":"Boston, MA, United States","name":"GD 2017: Graph Drawing and Network Visualization"},"month":"01","publisher":"Springer","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2018","volume":10692,"date_updated":"2023-08-24T14:39:32Z","date_created":"2018-12-11T11:46:27Z","related_material":{"record":[{"id":"5857","relation":"later_version","status":"public"}]},"author":[{"first_name":"Radoslav","last_name":"Fulek","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8485-1774","full_name":"Fulek, Radoslav"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"}],"publist_id":"7390"},{"oa_version":"Published Version","date_updated":"2023-08-24T14:50:26Z","date_created":"2021-08-09T12:46:39Z","related_material":{"record":[{"id":"6095","relation":"used_in_publication","status":"public"}]},"author":[{"first_name":"Rui","last_name":"Faria","full_name":"Faria, Rui"},{"full_name":"Chaube, Pragya","last_name":"Chaube","first_name":"Pragya"},{"first_name":"Hernán E.","last_name":"Morales","full_name":"Morales, Hernán E."},{"full_name":"Larsson, Tomas","first_name":"Tomas","last_name":"Larsson"},{"first_name":"Alan R.","last_name":"Lemmon","full_name":"Lemmon, Alan R."},{"first_name":"Emily M.","last_name":"Lemmon","full_name":"Lemmon, Emily M."},{"full_name":"Rafajlović, Marina","first_name":"Marina","last_name":"Rafajlović"},{"full_name":"Panova, Marina","last_name":"Panova","first_name":"Marina"},{"full_name":"Ravinet, Mark","last_name":"Ravinet","first_name":"Mark"},{"first_name":"Kerstin","last_name":"Johannesson","full_name":"Johannesson, Kerstin"},{"orcid":"0000-0003-1050-4969","id":"3C147470-F248-11E8-B48F-1D18A9856A87","last_name":"Westram","first_name":"Anja M","full_name":"Westram, Anja M"},{"last_name":"Butlin","first_name":"Roger K.","full_name":"Butlin, Roger K."}],"publisher":"Dryad","department":[{"_id":"NiBa"}],"status":"public","title":"Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes","_id":"9837","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","year":"2018","abstract":[{"lang":"eng","text":"Both classical and recent studies suggest that chromosomal inversion polymorphisms are important in adaptation and speciation. However, biases in discovery and reporting of inversions make it difficult to assess their prevalence and biological importance. Here, we use an approach based on linkage disequilibrium among markers genotyped for samples collected across a transect between contrasting habitats to detect chromosomal rearrangements de novo. We report 17 polymorphic rearrangements in a single locality for the coastal marine snail, Littorina saxatilis. Patterns of diversity in the field and of recombination in controlled crosses provide strong evidence that at least the majority of these rearrangements are inversions. Most show clinal changes in frequency between habitats, suggestive of divergent selection, but only one appears to be fixed for different arrangements in the two habitats. Consistent with widespread evidence for balancing selection on inversion polymorphisms, we argue that a combination of heterosis and divergent selection can explain the observed patterns and should be considered in other systems spanning environmental gradients."}],"type":"research_data_reference","doi":"10.5061/dryad.72cg113","date_published":"2018-10-09T00:00:00Z","oa":1,"citation":{"chicago":"Faria, Rui, Pragya Chaube, Hernán E. Morales, Tomas Larsson, Alan R. Lemmon, Emily M. Lemmon, Marina Rafajlović, et al. “Data from: Multiple Chromosomal Rearrangements in a Hybrid Zone between Littorina Saxatilis Ecotypes.” Dryad, 2018. https://doi.org/10.5061/dryad.72cg113.","mla":"Faria, Rui, et al. Data from: Multiple Chromosomal Rearrangements in a Hybrid Zone between Littorina Saxatilis Ecotypes. Dryad, 2018, doi:10.5061/dryad.72cg113.","short":"R. Faria, P. Chaube, H.E. Morales, T. Larsson, A.R. Lemmon, E.M. Lemmon, M. Rafajlović, M. Panova, M. Ravinet, K. Johannesson, A.M. Westram, R.K. Butlin, (2018).","ista":"Faria R, Chaube P, Morales HE, Larsson T, Lemmon AR, Lemmon EM, Rafajlović M, Panova M, Ravinet M, Johannesson K, Westram AM, Butlin RK. 2018. Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes, Dryad, 10.5061/dryad.72cg113.","apa":"Faria, R., Chaube, P., Morales, H. E., Larsson, T., Lemmon, A. R., Lemmon, E. M., … Butlin, R. K. (2018). Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes. Dryad. https://doi.org/10.5061/dryad.72cg113","ieee":"R. Faria et al., “Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes.” Dryad, 2018.","ama":"Faria R, Chaube P, Morales HE, et al. Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes. 2018. doi:10.5061/dryad.72cg113"},"main_file_link":[{"url":"https://doi.org/10.5061/dryad.72cg113","open_access":"1"}],"article_processing_charge":"No","month":"10","day":"09"},{"oa_version":"Preprint","intvolume":" 16","status":"public","title":"Absorption and directed Jónsson terms","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"10864","abstract":[{"text":"We prove that every congruence distributive variety has directed Jónsson terms, and every congruence modular variety has directed Gumm terms. The directed terms we construct witness every case of absorption witnessed by the original Jónsson or Gumm terms. This result is equivalent to a pair of claims about absorption for admissible preorders in congruence distributive and congruence modular varieties, respectively. For finite algebras, these absorption theorems have already seen significant applications, but until now, it was not clear if the theorems hold for general algebras as well. Our method also yields a novel proof of a result by P. Lipparini about the existence of a chain of terms (which we call Pixley terms) in varieties that are at the same time congruence distributive and k-permutable for some k.","lang":"eng"}],"type":"book_chapter","date_published":"2018-03-21T00:00:00Z","page":"203-220","citation":{"ama":"Kazda A, Kozik M, McKenzie R, Moore M. Absorption and directed Jónsson terms. In: Czelakowski J, ed. Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science. Vol 16. OCTR. Cham: Springer Nature; 2018:203-220. doi:10.1007/978-3-319-74772-9_7","ista":"Kazda A, Kozik M, McKenzie R, Moore M. 2018.Absorption and directed Jónsson terms. In: Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science. vol. 16, 203–220.","ieee":"A. Kazda, M. Kozik, R. McKenzie, and M. Moore, “Absorption and directed Jónsson terms,” in Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science, vol. 16, J. Czelakowski, Ed. Cham: Springer Nature, 2018, pp. 203–220.","apa":"Kazda, A., Kozik, M., McKenzie, R., & Moore, M. (2018). Absorption and directed Jónsson terms. In J. Czelakowski (Ed.), Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science (Vol. 16, pp. 203–220). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-74772-9_7","mla":"Kazda, Alexandr, et al. “Absorption and Directed Jónsson Terms.” Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science, edited by J Czelakowski, vol. 16, Springer Nature, 2018, pp. 203–20, doi:10.1007/978-3-319-74772-9_7.","short":"A. Kazda, M. Kozik, R. McKenzie, M. Moore, in:, J. Czelakowski (Ed.), Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science, Springer Nature, Cham, 2018, pp. 203–220.","chicago":"Kazda, Alexandr, Marcin Kozik, Ralph McKenzie, and Matthew Moore. “Absorption and Directed Jónsson Terms.” In Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science, edited by J Czelakowski, 16:203–20. OCTR. Cham: Springer Nature, 2018. https://doi.org/10.1007/978-3-319-74772-9_7."},"publication":"Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science","article_processing_charge":"No","day":"21","series_title":"OCTR","scopus_import":"1","volume":16,"date_created":"2022-03-18T10:30:32Z","date_updated":"2023-09-05T15:37:18Z","author":[{"id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","last_name":"Kazda","first_name":"Alexandr","full_name":"Kazda, Alexandr"},{"full_name":"Kozik, Marcin","last_name":"Kozik","first_name":"Marcin"},{"first_name":"Ralph","last_name":"McKenzie","full_name":"McKenzie, Ralph"},{"last_name":"Moore","first_name":"Matthew","full_name":"Moore, Matthew"}],"editor":[{"full_name":"Czelakowski, J","last_name":"Czelakowski","first_name":"J"}],"publisher":"Springer Nature","department":[{"_id":"VlKo"}],"publication_status":"published","year":"2018","acknowledgement":"The second author was supported by National Science Center grant DEC-2011-/01/B/ST6/01006.","place":"Cham","language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-74772-9_7","quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1502.01072"}],"external_id":{"arxiv":["1502.01072"]},"publication_identifier":{"issn":["2211-2758"],"eisbn":["9783319747729"],"isbn":["9783319747712"],"eissn":["2211-2766"]},"month":"03"},{"year":"2018","acknowledgement":"Partially supported by the project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM) of Czech-French collaboration.","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"UlWa"}],"publication_status":"published","related_material":{"record":[{"id":"7108","relation":"later_version","status":"public"}]},"author":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"full_name":"Patakova, Zuzana","last_name":"Patakova","first_name":"Zuzana","orcid":"0000-0002-3975-1683","id":"48B57058-F248-11E8-B48F-1D18A9856A87"},{"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","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"volume":99,"date_created":"2018-12-11T11:45:04Z","date_updated":"2023-09-06T11:10:57Z","publist_id":"7736","file_date_updated":"2020-07-14T12:45:18Z","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"}],"month":"06","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"184","intvolume":" 99","status":"public","title":"Shellability is NP-complete","ddc":["516","000"],"oa_version":"Published Version","file":[{"date_updated":"2020-07-14T12:45:18Z","date_created":"2018-12-17T16:35:02Z","checksum":"d12bdd60f04a57307867704b5f930afd","file_id":"5725","relation":"main_file","creator":"dernst","file_size":718414,"content_type":"application/pdf","file_name":"2018_LIPIcs_Goaoc.pdf","access_level":"open_access"}],"type":"conference","alternative_title":["Leibniz International Proceedings in Information, LIPIcs"],"abstract":[{"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.","lang":"eng"}],"citation":{"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.","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.","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","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"},"page":"41:1 - 41:16","date_published":"2018-06-11T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"11"},{"publication_identifier":{"issn":["18688969"]},"month":"06","doi":"10.4230/LIPIcs.SoCG.2018.46","conference":{"end_date":"2018-06-14","location":"Budapest, Hungary","start_date":"2018-06-11","name":"SoCG: Symposium on Computational Geometry"},"language":[{"iso":"eng"}],"external_id":{"arxiv":["1712.00434"]},"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","publist_id":"7614","file_date_updated":"2020-07-14T12:45:51Z","article_number":"46","related_material":{"record":[{"relation":"later_version","status":"public","id":"7093"}]},"author":[{"full_name":"Huszár, Kristóf","first_name":"Kristóf","last_name":"Huszár","id":"33C26278-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5445-5057"},{"first_name":"Jonathan","last_name":"Spreer","full_name":"Spreer, Jonathan"},{"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:37Z","date_updated":"2023-09-06T11:13:41Z","acknowledgement":"Research of the second author was supported by the Einstein Foundation (project “Einstein Visiting Fellow Santos”) and by the Simons Foundation (“Simons Visiting Professors” program).","year":"2018","department":[{"_id":"UlWa"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","has_accepted_license":"1","article_processing_charge":"No","day":"01","scopus_import":1,"date_published":"2018-06-01T00:00:00Z","citation":{"mla":"Huszár, Kristóf, et al. On the Treewidth of Triangulated 3-Manifolds. Vol. 99, 46, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, doi:10.4230/LIPIcs.SoCG.2018.46.","short":"K. Huszár, J. Spreer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds,” Vol. 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.46.","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018. doi:10.4230/LIPIcs.SoCG.2018.46","ista":"Huszár K, Spreer J, Wagner U. 2018. On the treewidth of triangulated 3-manifolds. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 46.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99.","apa":"Huszár, K., Spreer, J., & Wagner, U. (2018). On the treewidth of triangulated 3-manifolds (Vol. 99). 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.46"},"abstract":[{"lang":"eng","text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol and of Scharlemann and Thompson, by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 48(k+1) (resp. 4(3k+1))."}],"type":"conference","alternative_title":["LIPIcs"],"oa_version":"Submitted Version","file":[{"creator":"dernst","content_type":"application/pdf","file_size":642522,"file_name":"2018_LIPIcs_Huszar.pdf","access_level":"open_access","date_updated":"2020-07-14T12:45:51Z","date_created":"2018-12-17T15:32:38Z","checksum":"530d084116778135d5bffaa317479cac","file_id":"5713","relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"285","intvolume":" 99","status":"public","ddc":["516","000"],"title":"On the treewidth of triangulated 3-manifolds"}]