Advances in Applied Mathematics, t. 29, p. 215-242, 2002.
Bodo Lass
Variations sur le thème E+Ê = XY
Résumé.
Soit G = (X,Y;E) un graphe biparti et G' = (X,Y;Ê) le graphe biparti complémentaire.
Notons p(G,r) le nombre des r-couplages de G.
Il est classique que le vecteur [p(G',r)] (r=1,2,...) est déterminé par [p(G,r)] (r=1,2,...).
Nous explicitons ce fait en démontrant des théorèmes de dualité nouveaux, généralisant et
globalisant notamment les résultats de Chow, Foata, Gessel, Joni, Rota et Zeilberger.
Pour des graphes orientés on obtient ainsi une preuve rapide de l'identité fondamentale de Berge entre des chemins et
des circuits hamiltoniens.
Exprimée dans le langage des fonctions d'ensembles, celle-ci implique immédiatement la conjecture de Chung et Graham
(établie d'abord par Chow et Gessel) ainsi que les théorèmes de parité de Rédei sur les tournois,
de Lovász sur
les graphes non-orientés et de Camion et Rao sur les graphes auto-complémentaires.
Finalement, nous étudions les relations entre les fonctions d'ensembles et les fonctions symétriques.
Le théorème principal de la thèse de Chow devient ainsi une conséquence directe de l'identité de Berge.
Les versions suivantes sont disponibles :
Version du journal :