https://www.dagstuhl.de/23121

March 19 – 24 , 2023, Dagstuhl Seminar 23121

Pattern Avoidance, Statistical Mechanics and Computational Complexity

Organizers

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)

For support, please contact

Jutka Gasiorowski for administrative matters

Michael Gerke for scientific matters

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.

Documentation

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.

Publications

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