NDLI: Matching Polynomials And Duality

Content Provider	Springer Nature Link
Author	Lass, Bodo
Copyright Year	2004
Abstract	Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by $$ \mu {\left( {G,x} \right)}: = {\sum\nolimits_{r = 0}^{{\left\lfloor {n/2} \right\rfloor }} {{\left( { - 1} \right)}^{r} \cdot p{\left( {G,r} \right)} \cdot x^{{n - 2r}} } } $$ and the signless matching polynomial of G by $$ \overline{\mu } {\left( {G,x} \right)}: = {\sum\nolimits_{r = 0}^{{\left\lfloor {n/2} \right\rfloor }} {p{\left( {G,r} \right)} \cdot x^{{n - 2r}} } } $$ .It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement $$ \overline{G} $$ . We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions $$ e^{{ - x^{2} /2}} \mu {\left( {G,x} \right)} $$ and $$ e^{{ - x^{2} /2}} \mu {\left( {\overline{G} ,x} \right)} $$ are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foata’s combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.
Ending Page	440
Page Count	14
Starting Page	427
File Format	PDF
ISSN	02099683
e-ISSN	14396912
Journal	Combinatorica
Issue Number	3
Volume Number	24
Language	English
Publisher	Springer-Verlag
Publisher Date	2004-01-01
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Factorization, matching, partitioning, covering and packing Exact enumeration problems, generating functions Combinatorial inequalities Polynomials: location of zeros (algebraic theorems)
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Combinatorial proofs of inverse relations and log-concavity for Bessel numbers

Linear $k$-Chord Diagrams

A critical quartet for queuing couples

Counting Bubbles in Linear Chord Diagrams

Enumeration of Matchings: Problems and Progress

Double Aztec Rectangles

Generating Functions for Domino Matchings in the $2\times k$ Game of Memory

Graphical condensation, overlapping Pfaffians and superpositions of matchings

A note on a 2-enumeration of antisymmetric monotone triangles

Matching Polynomials And Duality

Similar Documents

Combinatorial proofs of inverse relations and log-concavity for Bessel numbers

Linear $k$-Chord Diagrams

A critical quartet for queuing couples

Counting Bubbles in Linear Chord Diagrams

Enumeration of Matchings: Problems and Progress

Double Aztec Rectangles

Generating Functions for Domino Matchings in the $2\times k$ Game of Memory

Graphical condensation, overlapping Pfaffians and superpositions of matchings

A note on a 2-enumeration of antisymmetric monotone triangles

Matching Polynomials And Duality