February 14 – 19 , 2016, Dagstuhl Seminar 16071

Pattern Avoidance and Genome Sorting


Michael Albert (University of Otago, NZ)
Miklós Bóna (University of Florida – Gainesville, US)
István Miklós (Alfréd Rényi Institute of Mathematics – Budapest, HU)
Einar Steingrimsson (University of Strathclyde, GB)

For support, please contact

Dagstuhl Service Team


Dagstuhl Report, Volume 6, Issue 2 Dagstuhl Report
Aims & Scope
List of Participants
Dagstuhl's Impact: Documents available
Dagstuhl Seminar Schedule [pdf]


The seminar took place from February 14, 2016, to February 19, 2016. It had 36 participants, who were researchers in theoretical computer science, combinatorics, and molecular biology. It was a geographically diverse group, with participants coming from the US, Canada, Brazil, Germany, Iceland, the United Kingdom, Sweden, France, Slovakia, Hungary and New Zealand. The seminar featured 18 talks, three of which were hourlong talks, and an open problem session.

Numerous collaborative research efforts have been started. Here is a sampling.

Megan Martinez and Manda Riehl worked on a bijection between LP matchings (one of the RNA matchings described in Vincent Vatter's talk) and Klazar's nesting equivalent matchings. They studied a paper by Klazar and Aziza Jefferson's dissertation and made progress on the bijection.

István Miklós, Péter Erdös and Miklós Bóna worked on proving a log-convexity conjecture related to ordered degree sequences of bipartite graphs.

Brona Brejova and Manda Riehl discussed two potential future projects related to gene and species tree reconciliation. The most probable starting point is a project involving gene and species trees where a gene is allowed to duplicate a string inside itself. This situation was not allowed in previous models, however it seems that as long as the specific breakpoints are not reused from this insertion, a modification of the previous algorithms could still be effective.

Jay Pantone, David Bevan and Miklós Bóna collaborated on asymptotic enumeration of a balanced urns and balls model that was seen to be a step towards finding a better upper bound for a pattern avoidance enumeration problem.

We have all the reasons to believe that this, and many other joint research efforts that started during this seminar will lead to new results that would not have been possible without the seminar. Therefore, we strongly believe that the seminar was a success that we would like to repeat at some point in the future.

Summary text license
  Creative Commons BY 3.0 Unported license
  Miklós Bóna

Dagstuhl Seminar Series


  • Data Structures / Algorithms / Complexity
  • Semantics / Formal Methods
  • Soft Computing / Evolutionary Algorithms


  • Permutations
  • Patterns
  • Sorting
  • Lists
  • Evolutionary distance
  • Metrics


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.