Petite école de combinatoire LaBRI, année 2006/07

Chapitre 1, Orthogonalité, moments et récurrence linéaire,
(leçons 1,2,3,4 des 13, 20, 27 Oct et 10 Nov 2006) (pdf 5,7 Mo)

Références:
- Une théorie combinatoire des polynômes orthogonaux,
Lecture Notes LACIM, UQAM, Montréal, 1984, 219 pages
- divers articles (à préciser)

Une vue d’ensemble de la petite école ... (pdf, 14,4 Mo)
exposé au séminaire d’Informatique du LaBRI, 28 Septembre 2006

Chapitre 2, Histoires et moments,
§1,2,3, leçons 5,6 des 17, 23 Nov 2006 (pdf 5,8 Mo)
§ 4,5,6,7, leçons 7,8,9 du 1er, 8, 15 Déc 2006 (pdf, 2,7 Mo)

Chapitre X, Histoires et opérateurs, en construction
leçon 10 du 12 Janvier 2007

Chapitre 3, Fractions continues
leçons 11, 12 des 19 et 26 Janvier 2007 (pdf, 7,1 Mo)
leçons 13, 14, 15 des 2, 9 Février et 2 mars 2007 (pdf 8,5 Mo)

Chapitre 4, Calcul des coefficients b_k et lambda_k
leçon 16 du 16 mars 2007 (pdf 3,4 Mo)
leçons 17, 18, 19 du 30 mars, 20 et 27 Avril 2007 (pdf, 6,6 Mo)

Chapitre 5, Orthogonalité et structures exponentielles
leçons 20, 21, 22 du 4, 11 Mai et 8 Juin 2007 (pdf 6,2 Mo)
leçons 23, 24 du 15 et 29 Juin 2007 (pdf, 3,1 Mo)

Chapitre 6, Applications, interactions, extensions
(résumé du 29 Juin 2007)

Petite école de combinatoire
LaBRI, année 2011/2012

L’ Ansatz cellulaire

sous-titre:
Physique combinatoire et algèbre quadratique:
une approche cellulaire

Most of the slides are in english. See a complete map of the lectures with english abstract at the secondary website «courses», page petite école

résumé:
Dans un premier temps, l'Ansatz cellulaire est une méthodologie permettant, par une approche cellulaire sur un réseau carré, d'associer des objets combinatoires (les Q-tableaux) à certaines algèbres quadratiques Q définies par relations et générateurs. Cette notion est équivalente à la notion d' "automate planaire" ou de "réécritures planaires".

L'exemple de base est l'algèbre définie par la relation UD = DU + Id (ou algèbre de Weyl-Heisenberg, bien connue en physique). Les Q-tableaux associés sont les permutations. Un deuxième exemple est l'algèbre définie par la relation DE = qED + E + D qui est à la base de la résolution en physique des systèmes dynamiques du modèle du PASEP ("partially asymmetric exclusion process") avec le calcul des probabilités stationnaires. Des Q-tableaux associés ont fait récemment l'objet de nombreuses études combinatoires sous le nom de "tableaux alternatifs", "permutation tableaux" ou encore "tree-like tableaux". Une autre algèbre, ou algèbre du modèle "8-vertex" permet de retrouver les fameuses matrices à signes alternants, les partitions planes, les configurations de chemins ne se coupant pas ou encore des pavages sur réseaux planaires.

Dans un deuxième temps, l'Ansatz cellulaire permet la construction "guidée" de bijections entre les Q-tableaux et d'autres objets combinatoires, dès que l'on a une "représentation" par opérateurs combinatoires de l'algèbre quadratique Q. L'exemple de base pour l'algèbre de Weyl-Heisenberg est la classique correspondance RSK (Robinson-Schensted-Knuth) entre permutations et paires de tableaux de Young. Pour l'algèbre du PASEP on obtient une bijection entre tableaux alternatifs et permutations. La théorie combinatoire des polynômes orthogonaux joue un rôle important, ainsi que la théorie des "histoires de fichiers" introduite informatique pour l'analyse du cout intégré des structures de données. Nous terminerons par des extensions et problèmes ouverts, en particulier pour l'algèbre du modèle "8-vertex".

Chapitre 1 Q-tableaux et automates planaires
PEC1 (23Sep2011, pdf 3,7 Mo)
PEC2 (30Sep2011, pdf 3,5 Mo)
PEC3 (7Oct2011, pdf 2,2 Mo)
PEC4 (14Oct2011, pdf 3,9 Mo)

Chapitre 2 Q-tableaux, automates planaires, extensions, exemples, problèmes
PEC5 (21Oct2011, pdf 9,2 Mo version préliminaire)
PEC6 (4Nov2011 pdf 2,5 Mo) encore une version prélliminaire
PEC7 (18Nov2011 pdf 4,4 Mo) toujours une version préliminaire

Chapitre 3 L’algèbre UD=DU+Id et la correspondance RSK
PEC8 (2Dec2011 pdf 13,5 Mo)
PEC9 (9Dec2011 pdf 8,1 Mo)

Chapitre 4 L’algèbre du PASEP DE=ED+E+D et la bijection
tableaux alternatifs -- permutations
PEC10 (4Mai2012 pdf 2,5 Mo) (version corrigée, 10 Mai 2012)
PEC11 (11Mai2012 pdf 4,8 Mo)

Chapitre 5 Compléments, perpectives
PEC12 (25Mai2012 pdf 6,4 Mo)
PEC13 (8Juin201212 pdf 9,8 Mo)
PEC14 (15Juin2012 pdf 9,6Mo) (2ème version, 15 Juin 2012)
PEC15 (22Juin2012 pdf 8,5Mo)