TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 23121

Pattern Avoidance, Statistical Mechanics and Computational Complexity

( Mar 19 – Mar 24, 2023 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23121

Organizers

Contact



Schedule

Summary

The Dagstuhl Seminar took place from March 19, 2023 to March 24, 2023. It had 36 participants, who were researchers in theoretical computer science, combinatorics, and statistical mechanics. The aftermath of COVID made the planning of the seminar more challenging than usual; for instance, researchers from China, Australia and New Zealand were still extremely reluctant to travel. However, in the end we succeeded in bringing together a geographically diverse group of researchers. The participants came from 12 countries, from Canada, the Czech Republic, Denmark, Finland, France, Germany, Hungary, Iceland, Italy, Turkey, the United Kingdom, and the United States. The seminar featured 21 talks, four of which were hour-long talks, and two open problem sessions.

Several collaborative projects have been started. For example, David Bevan started a collaboration with Mathilde Bouvel on the scaling limit of permutation classes avoiding a pattern with extremal first or last point. Jessica Striker, Mathilde Bouvel and Rebecca Smith started working on the open questions in Striker's talk on six-vertex configurations. Colin Defant, Rebecca Smith, Miklós Bóna and Justin Troyka discussed new observations on pattern avoiding permutations whose squares are also pattern avoiding. Jessica Striker and Sergi Elizalde started working together on promotion in cylindric tableaux. Natasha Blitvic and Sergi Elizalde explored why counting permutations avoiding a pattern seems to yield moment sequences, and how to interpret that phenomenon.

The open problem sessions were especially successful. In earlier seminars, we held one open problem session. However, this time there was so much interest in presenting open problems that we decided to hold two open problem sessions. Six families of open questions were presented at each of them.

Numerous participants expressed their pleasure with the seminar and its sequence of talks. The prevailing view was that while the participants came from three different fields, they were all open to the other two fields, and therefore, they all learned about results that they would not have learned otherwise. Therefore, we have all the reasons to believe that the seminar was a success, and we would like to repeat something similar sometime in the future. We have even discussed specific plans for a possible future seminar.

Copyright Miklós Bóna,, David Bevan, and István Miklós

Motivation

This Dagstuhl Seminar aims to bring together researchers from three related, but distinct, communities to communicate and exploit synergies: theoretical computer scientists whose main research interest focuses on counting complexity, computer scientists and mathematicians studying pattern avoidance, and computer scientists, mathematicians and physicists whose area of research is statistical mechanics.

Some of the most exciting recent results in Enumerative Combinatorics were negative results, namely they showed that the generating functions of certain natural objects, such as pattern avoiding permutations, did not have certain properties. For example, they were not rational, algebraic, or differentiably finite. These negative properties can be expressed in terms of Formal Languages, and therefore, it is not unreasonable to expect that Computational Complexity could prove additional tools that could lead to the proof of new theorems of the above kind.

The method of differential approximations, a recent method in which Jay Pantone was one of the major contributors is ideally suited to attack enumeration problems that appear in all three communities. Participants can make the most of their time together attempting to apply the latest versions of this method to their relevant problems.

A recent connection between permutations and permutation patterns and models in statistical mechanics is a bijection that connects the PASEP (partially asymmetric simple exclusion process) and the Abelian Sandpile Model (ASM) on certain bipartite graphs, via bijections between certain tableaux and permutations. In fact, the bijective connection between the PASEP and the ASM goes via permutations, which is how this correspondence was discovered. Restricting those permutations to avoid various patterns gives natural restrictions on the corresponding tableaux, and thereby on the corresponding configurations of the ASM. Thus, given the crucial part permutations play in this connection between the PASEP and the ASM, it is natural to study it via permutations and their patterns.

We plan to structure the seminar as follows. There will be a one-hour talk each morning, followed by two or three half-hour talks. This will result in a morning session lasting roughly from 9 am to noon. After lunch, there will be a long period with no talks scheduled, providing ample time for freeflowing conversations. During this time, we will self-organize into small groups to discuss the topics that were the subject of the talks up to that point. This period will end with the afternoon cake. There will be three short talks between 4 pm and 6 pm. In the evening of the first day, there will be an Open Problem Session. There will be a free afternoon on Wednesday, with a planned excursion to Saarbrücken.

Copyright Miklós Bóna

Participants
  • Benjamin Aram Berendsohn (FU Berlin, DE) [dblp]
  • David Bevan (University of Strathclyde - Glasgow, GB) [dblp]
  • Natasha Blitvic (Queen Mary University of London, GB) [dblp]
  • Miklós Bóna (University of Florida - Gainesville, US) [dblp]
  • Mathilde Bouvel (LORIA - Nancy, FR) [dblp]
  • Robert Brignall (The Open University - Milton Keynes, GB) [dblp]
  • Alexander Burstein (Howard University - Washington, US) [dblp]
  • Parinya Chalermsook (Aalto University, FI) [dblp]
  • Anders Claesson (University of Iceland - Reykjavik, IS) [dblp]
  • Sylvie Corteel (Université Paris Cité, FR) [dblp]
  • Péter Csikvári (Alfréd Rényi Institute of Mathematics - Budapest, HU) [dblp]
  • Radu Curticapean (IT University of Copenhagen, DK) [dblp]
  • Colin Defant (MIT - Cambridge, US) [dblp]
  • Sergi Elizalde (Dartmouth College - Hanover, US) [dblp]
  • Péter L. Erdös (Alfréd Rényi Institute of Mathematics - Budapest, HU) [dblp]
  • Luca Ferrari (University of Firenze, IT) [dblp]
  • Sylvie Hamel (University of Montréal, CA) [dblp]
  • Carina Letong Hong (University of Oxford, GB) [dblp]
  • Vít Jelínek (Charles University - Prague, CZ) [dblp]
  • László Kozma (FU Berlin, DE) [dblp]
  • Jan Kyncl (Charles University - Prague, CZ) [dblp]
  • Anthony Labarre (Gustave Eiffel University - Marne-la-Vallée, FR) [dblp]
  • István Miklós (ELKH - Budapest, HU) [dblp]
  • Torsten Mütze (University of Warwick - Coventry, GB) [dblp]
  • Michal Opler (Czech Technical University - Prague, CZ) [dblp]
  • Lara K. Pudwell (Valparaiso University, US) [dblp]
  • Erik Slivken (University of North Carolina Wilmington, US) [dblp]
  • Rebecca Smith (The College at Brockport, US) [dblp]
  • Jessica Striker (North Dakota State University - Fargo, US) [dblp]
  • Gábor Tardos (Alfréd Rényi Institute of Mathematics - Budapest, HU) [dblp]
  • Bridget Tenner (DePaul Uniersity - Chicago, US) [dblp]
  • Justin Troyka (California State University - Los Angeles, US)
  • Henning Ulfarsson (Reykjavik University, IS) [dblp]
  • Gökhan Yildirim (Bilkent University - Ankara, TR) [dblp]
  • Sorrachai Yingchareonthawornchai (Aalto University, FI) [dblp]
  • Viktor Zamaraev (University of Liverpool, GB) [dblp]

Related Seminars
  • Dagstuhl Seminar 16071: Pattern Avoidance and Genome Sorting (2016-02-14 - 2016-02-19) (Details)
  • Dagstuhl Seminar 18451: Genomics, Pattern Avoidance, and Statistical Mechanics (2018-11-04 - 2018-11-09) (Details)

Classification
  • Computational Complexity
  • Discrete Mathematics

Keywords
  • Permutation patterns
  • counting and sampling
  • algorithms
  • modeling
  • statistical physics.