--- _id: '186' abstract: - lang: eng text: 'A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The ℤ2-genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t × t grid or one of the following so-called t-Kuratowski graphs: K3, t, or t copies of K5 or K3,3 sharing at most 2 common vertices. We show that the ℤ2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its ℤ2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani-Tutte theorem on orientable surfaces.' alternative_title: - LIPIcs article_processing_charge: No author: - first_name: Radoslav full_name: Fulek, Radoslav id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87 last_name: Fulek orcid: 0000-0001-8485-1774 - first_name: Jan full_name: Kynčl, Jan last_name: Kynčl citation: ama: 'Fulek R, Kynčl J. The ℤ2-Genus of Kuratowski minors. In: Vol 99. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:40.1-40.14. doi:10.4230/LIPIcs.SoCG.2018.40' apa: 'Fulek, R., & Kynčl, J. (2018). The ℤ2-Genus of Kuratowski minors (Vol. 99, p. 40.1-40.14). 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.40' chicago: Fulek, Radoslav, and Jan Kynčl. “The ℤ2-Genus of Kuratowski Minors,” 99:40.1-40.14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPIcs.SoCG.2018.40. ieee: 'R. Fulek and J. Kynčl, “The ℤ2-Genus of Kuratowski minors,” presented at the SoCG: Symposium on Computational Geometry, Budapest, Hungary, 2018, vol. 99, p. 40.1-40.14.' ista: 'Fulek R, Kynčl J. 2018. The ℤ2-Genus of Kuratowski minors. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 99, 40.1-40.14.' mla: Fulek, Radoslav, and Jan Kynčl. The ℤ2-Genus of Kuratowski Minors. Vol. 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14, doi:10.4230/LIPIcs.SoCG.2018.40. short: R. Fulek, J. Kynčl, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 40.1-40.14. conference: end_date: 2018-06-14 location: Budapest, Hungary name: 'SoCG: Symposium on Computational Geometry' start_date: 2018-06-11 date_created: 2018-12-11T11:45:05Z date_published: 2018-06-11T00:00:00Z date_updated: 2023-08-14T12:43:51Z day: '11' department: - _id: UlWa doi: 10.4230/LIPIcs.SoCG.2018.40 external_id: arxiv: - '1803.05085' intvolume: ' 99' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1803.05085 month: '06' oa: 1 oa_version: Submitted Version page: 40.1 - 40.14 project: - _id: 261FA626-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: M02281 name: Eliminating intersections in drawings of graphs publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '7734' quality_controlled: '1' related_material: record: - id: '11593' relation: later_version status: public scopus_import: '1' status: public title: The ℤ2-Genus of Kuratowski minors type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 99 year: '2018' ... --- _id: '433' 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.' alternative_title: - LNCS author: - first_name: Radoslav full_name: Fulek, Radoslav id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87 last_name: Fulek orcid: 0000-0001-8485-1774 - first_name: János full_name: Pach, János last_name: Pach citation: 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' 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.' 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.' 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.' short: R. Fulek, J. Pach, in:, Springer, 2018, pp. 160–166. conference: end_date: 2017-09-27 location: Boston, MA, United States name: 'GD 2017: Graph Drawing and Network Visualization' start_date: 201-09-25 date_created: 2018-12-11T11:46:27Z date_published: 2018-01-21T00:00:00Z date_updated: 2023-08-24T14:39:32Z day: '21' department: - _id: UlWa doi: 10.1007/978-3-319-73915-1_14 external_id: arxiv: - '1708.08037' intvolume: ' 10692' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1708.08037 month: '01' oa: 1 oa_version: Submitted Version page: 160 - 166 publication_status: published publisher: Springer publist_id: '7390' quality_controlled: '1' related_material: record: - id: '5857' relation: later_version status: public scopus_import: 1 status: public title: 'Thrackles: An improved upper bound' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 10692 year: '2018' ... --- _id: '9837' 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. article_processing_charge: No author: - first_name: Rui full_name: Faria, Rui last_name: Faria - first_name: Pragya full_name: Chaube, Pragya last_name: Chaube - first_name: Hernán E. full_name: Morales, Hernán E. last_name: Morales - first_name: Tomas full_name: Larsson, Tomas last_name: Larsson - first_name: Alan R. full_name: Lemmon, Alan R. last_name: Lemmon - first_name: Emily M. full_name: Lemmon, Emily M. last_name: Lemmon - first_name: Marina full_name: Rafajlović, Marina last_name: Rafajlović - first_name: Marina full_name: Panova, Marina last_name: Panova - first_name: Mark full_name: Ravinet, Mark last_name: Ravinet - first_name: Kerstin full_name: Johannesson, Kerstin last_name: Johannesson - first_name: Anja M full_name: Westram, Anja M id: 3C147470-F248-11E8-B48F-1D18A9856A87 last_name: Westram orcid: 0000-0003-1050-4969 - first_name: Roger K. full_name: Butlin, Roger K. last_name: Butlin citation: 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' 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' 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.' ieee: 'R. Faria et al., “Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes.” Dryad, 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.' 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). date_created: 2021-08-09T12:46:39Z date_published: 2018-10-09T00:00:00Z date_updated: 2023-08-24T14:50:26Z day: '09' department: - _id: NiBa doi: 10.5061/dryad.72cg113 main_file_link: - open_access: '1' url: https://doi.org/10.5061/dryad.72cg113 month: '10' oa: 1 oa_version: Published Version publisher: Dryad related_material: record: - id: '6095' relation: used_in_publication status: public status: public title: 'Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes' type: research_data_reference user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf year: '2018' ... --- _id: '5457' abstract: - lang: eng text: "We consider the problem of expected cost analysis over nondeterministic probabilistic programs, which aims at automated methods for analyzing the resource-usage of such programs. Previous approaches for this problem could only handle nonnegative bounded costs. However, in many scenarios, such as queuing networks or analysis of cryptocurrency protocols, both positive and negative costs are necessary and the costs are unbounded as well.\r\n\r\nIn this work, we present a sound and efficient approach to obtain polynomial bounds on the expected accumulated cost of nondeterministic probabilistic programs. Our approach can handle (a) general positive and negative costs with bounded updates in variables; and (b) nonnegative costs with general updates to variables. We show that several natural examples which could not be handled by previous approaches are captured in our framework.\r\n\r\nMoreover, our approach leads to an efficient polynomial-time algorithm, while no previous approach for cost analysis of probabilistic programs could guarantee polynomial runtime. Finally, we show the effectiveness of our approach by presenting experimental results on a variety of programs, motivated by real-world applications, for which we efficiently synthesize tight resource-usage bounds." alternative_title: - IST Austria Technical Report author: - first_name: '1' full_name: Anonymous, 1 last_name: Anonymous - first_name: '2' full_name: Anonymous, 2 last_name: Anonymous - first_name: '3' full_name: Anonymous, 3 last_name: Anonymous - first_name: '4' full_name: Anonymous, 4 last_name: Anonymous - first_name: '5' full_name: Anonymous, 5 last_name: Anonymous - first_name: '6' full_name: Anonymous, 6 last_name: Anonymous citation: ama: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4, Anonymous 5, Anonymous 6. Cost Analysis of Nondeterministic Probabilistic Programs. IST Austria; 2018. apa: Anonymous, 1, Anonymous, 2, Anonymous, 3, Anonymous, 4, Anonymous, 5, & Anonymous, 6. (2018). Cost analysis of nondeterministic probabilistic programs. IST Austria. chicago: Anonymous, 1, 2 Anonymous, 3 Anonymous, 4 Anonymous, 5 Anonymous, and 6 Anonymous. Cost Analysis of Nondeterministic Probabilistic Programs. IST Austria, 2018. ieee: 1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, 5 Anonymous, and 6 Anonymous, Cost analysis of nondeterministic probabilistic programs. IST Austria, 2018. ista: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4, Anonymous 5, Anonymous 6. 2018. Cost analysis of nondeterministic probabilistic programs, IST Austria, 27p. mla: Anonymous, 1, et al. Cost Analysis of Nondeterministic Probabilistic Programs. IST Austria, 2018. short: 1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, 5 Anonymous, 6 Anonymous, Cost Analysis of Nondeterministic Probabilistic Programs, IST Austria, 2018. date_created: 2018-12-12T11:39:26Z date_published: 2018-11-11T00:00:00Z date_updated: 2023-08-25T08:07:48Z day: '11' ddc: - '000' file: - access_level: open_access checksum: ba3adafd36fe200385ccda583063b9eb content_type: application/pdf creator: system date_created: 2018-12-12T11:53:32Z date_updated: 2020-07-14T12:47:00Z file_id: '5493' file_name: IST-2018-1066-v1+1_techreport.pdf file_size: 4202966 relation: main_file - access_level: closed checksum: 6cf3a19164bb8e5048a9c8c84dfd9fa3 content_type: text/plain creator: dernst date_created: 2019-05-10T13:22:12Z date_updated: 2020-07-14T12:47:00Z file_id: '6402' file_name: authors-names.txt file_size: 322 relation: main_file file_date_updated: 2020-07-14T12:47:00Z has_accepted_license: '1' language: - iso: eng month: '11' oa: 1 oa_version: Published Version page: '27' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '1066' related_material: record: - id: '6175' relation: later_version status: public scopus_import: 1 status: public title: Cost analysis of nondeterministic probabilistic programs type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2018' ... --- _id: '10864' abstract: - lang: eng 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. acknowledgement: The second author was supported by National Science Center grant DEC-2011-/01/B/ST6/01006. article_processing_charge: No author: - first_name: Alexandr full_name: Kazda, Alexandr id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87 last_name: Kazda - first_name: Marcin full_name: Kozik, Marcin last_name: Kozik - first_name: Ralph full_name: McKenzie, Ralph last_name: McKenzie - first_name: Matthew full_name: Moore, Matthew last_name: Moore 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' 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' 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.' 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.' 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.' 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. date_created: 2022-03-18T10:30:32Z date_published: 2018-03-21T00:00:00Z date_updated: 2023-09-05T15:37:18Z day: '21' department: - _id: VlKo doi: 10.1007/978-3-319-74772-9_7 editor: - first_name: J full_name: Czelakowski, J last_name: Czelakowski external_id: arxiv: - '1502.01072' intvolume: ' 16' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1502.01072 month: '03' oa: 1 oa_version: Preprint page: 203-220 place: Cham publication: Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science publication_identifier: eisbn: - '9783319747729' eissn: - 2211-2766 isbn: - '9783319747712' issn: - 2211-2758 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' series_title: OCTR status: public title: Absorption and directed Jónsson terms type: book_chapter user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 16 year: '2018' ...