Pattern-Avoidance in Binary Fillings of Grid Shapes (short version)

Résumé : Une $\textit{forme de grille}$ est un ensemble de cases choisies dans une grille carrée; un diagramme de Young en est un exemple. Cet article considère une notion de motif exclu pour un remplissage d'une forme de grille par des $0$ et des $1$, qui généralise la notion correspondante pour les permutations. Un remplissage évite certains motifs si aucune de ses sous-formes n'est égale à un motif. Nous nous concentrons sur les motifs qui sont des $\textit{paires de remplissages}$ de taille $2 \times 2$. Pour certaines formes, les remplissages évitant certaines paires de taille $2 \times 2$ sont en bijection avec les cellules de Grassmann totalement positives, ou bien avec les orientations acycliques de graphes bipartis. Nous démontrons plusieurs résultats analogues à l'équivalence de Wilf pour ces objets ―- c'est-à-dire, nous montrons que, pour certaines classes de formes, des remplissages évitant un motif donné sont en nombre égal à d'autres remplissages.
Type de document :
Communication dans un congrès
Krattenthaler, Christian and Sagan, Bruce. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pp.677-690, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01185144
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 19 août 2015 - 11:41:32
Dernière modification le : jeudi 11 mai 2017 - 01:02:53
Document(s) archivé(s) le : vendredi 20 novembre 2015 - 10:27:36

Fichier

dmAJ0158.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01185144, version 1

Collections

Citation

Alexey Spiridonov. Pattern-Avoidance in Binary Fillings of Grid Shapes (short version). Krattenthaler, Christian and Sagan, Bruce. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), pp.677-690, 2008, DMTCS Proceedings. 〈hal-01185144〉

Partager

Métriques

Consultations de la notice

50

Téléchargements de fichiers

164