|
|
 |
|
Mardi 21 Octobre
| Heure: |
14:00 - 17:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
A general theory of Wilf-equivalence for Catalan structures |
| Description: |
Mathilde Bouvel It is a commonly observed phenomenon in enumerative combinatorics thatseveral combinatorial classes share the same enumeration. For any twoclasses which seem to have the same enumeration sequence, a naturalproblem is to prove that it is indeed the case, ideally with abijective proof that allows to map the structure of one class to thatof the other.Such coincidences of enumeration are called Wilf-equivalences in thecontext of pattern-avoiding permutation classes (the definition ofpattern-avoidance will be given during the talk). Wilf-equivalence hasbeen a popular topic in the research on pattern-avoiding permutations,from its beginnings in the seventies until now. It is fair to say thatmost of the works done so far are specific to given pairs ofequi-numerous classes, thus forming a sort of "case-by-case catalogue"of the known Wilf-equivalences.In this talk, we explore a different approach: we are interested indescribing all Wilf-equivalences between permutations classes definedby the avoidance of two patterns: 231 and an additional pattern p(w.l.o.g., we can assume that p itself avoids 231). We will explainthat this is one way of phrasing a seemingly more general (butactually equivalent) question: that of describing allWilf-equivalences between classes of Catalan objects subject to onefurther avoidance restriction. Such classes are denoted Av(A), A beinga Catalan object.Our results, to be presented in the talk, are the following.First, we define an equivalence relation ~ among Catalan objects. Ourmain result is that it refines Wilf-equivalence: if A ~ B, then Av(A)and Av(B) have the same enumeration. The proof is subdivided inseveral cases, and it is bijective in all cases but one. We furtherconjecture that the converse statement holds, i.e., that this relation~ coincides with Wilf-equivalence.Then, we show how to enumerate the number of equivalence classes for~, hereby providing an upper bound on the number of Wilf-equivalenceclasses.It is also interesting to study a special ~-equivalence class, whichcan be understood at a very fine level of details. Our results on this~-class (called the "main" one) unify and generalize several resultsof the literature on Wilf-equivalence.Finally, we explain how our bijective cases in the proof of the maintheorem can often be refined to provide comparison results between theenumerations of classes Av(A) and Av(B) when A and B are notequivalent for ~. A consequence is that the "main" ~-class correspondsto the largest possible enumeration sequence.This is a joint work with Michael Albert (University of Otago), and apreprint is available at arXiv:1407.8261. |
|
|
