https://www.dagstuhl.de/23121

19. – 24. März 2023, Dagstuhl-Seminar 23121

Pattern Avoidance, Statistical Mechanics and Computational Complexity

Organisatoren

David Bevan (University of Strathclyde – Glasgow, GB)
Miklós Bóna (University of Florida – Gainesville, US)
István Miklós (ELKH – Budapest, HU)
Seth Pettie (University of Michigan – Ann Arbor, US)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Jutka Gasiorowski zu administrativen Fragen

Michael Gerke zu wissenschaftlichen Fragen

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.

Motivation text license
  Creative Commons BY 4.0
  Miklós Bóna

Dagstuhl-Seminar Series

Classification

  • Computational Complexity
  • Discrete Mathematics

Keywords

  • Permutation patterns
  • Counting and sampling
  • Algorithms
  • Modeling
  • Statistical physics.

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.