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
- 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)
Contact
- Michael Gerke (for scientific matters)
- Jutka Gasiorowski (for administrative matters)
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
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
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.
Creative Commons BY 4.0
Miklós Bóna
- 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]
- Victor Zamaraev (University of Liverpool, GB) [dblp]
Related Seminars
Classification
- Computational Complexity
- Discrete Mathematics
Keywords
- Permutation patterns
- counting and sampling
- algorithms
- modeling
- statistical physics.
