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 )


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

Organizers

Contact

Dagstuhl Reports

As part of the mandatory documentation, participants are asked to submit their talk abstracts, working group results, etc. for publication in our series Dagstuhl Reports via the Dagstuhl Reports Submission System.

  • Upload (Use personal credentials as created in DOOR to log in)

Shared Documents


Schedule

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

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.