Polynomial functions on Young diagrams arising from bipartite graphs

International audience We study the class of functions on the set of (generalized) Young diagrams arising as the number of embeddings of bipartite graphs. We give a criterion for checking when such a function is a polynomial function on Young diagrams (in the sense of Kerov and Olshanski) in terms o...

Full description

Bibliographic Details
Main Authors: Dolęga, Maciej, Sniady, Piotr
Other Authors: Instytut Matematyczny, Uniwersytet Wroclawski = University of Wroclaw, Instytut Matematyczny PAN, Polska Akademia Nauk = Polish Academy of Sciences = Académie polonaise des sciences (PAN), Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
Format: Conference Object
Language:English
Published: HAL CCSD 2011
Subjects:
Polynomial functions on Young diagrams
coloring of bipartite graphs
differential calculus on Young diagrams
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Iceland
Online Access:https://inria.hal.science/hal-01215109
https://inria.hal.science/hal-01215109/document
https://inria.hal.science/hal-01215109/file/dmAO0124.pdf
https://doi.org/10.46298/dmtcs.2908
Description
Summary:International audience We study the class of functions on the set of (generalized) Young diagrams arising as the number of embeddings of bipartite graphs. We give a criterion for checking when such a function is a polynomial function on Young diagrams (in the sense of Kerov and Olshanski) in terms of combinatorial properties of the corresponding bipartite graphs. Our method involves development of a differential calculus of functions on the set of generalized Young diagrams. Nous étudions la classe des fonctions sur l'ensemble des diagrammes de Young (généralisés) qui sont définies comme des nombres d'injections de graphes bipartites. Nous donnons un critère pour savoir si une telle fonction est une fonctions polynomiale sur les diagrammes de Young (au sens de Kerov et Olshanski) utilisant les propriétés combinatoires des graphes bipartites correspondants. Notre méthode repose sur le développement d'un calcul différentiel sur les fonctions sur les diagrammes de Young généralisés.

Similar Items