IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

A Combinatorial Chebyshev equality for d-Matching Polynomials

  • Oct. 7, 2016
  • 2:30 p.m.
  • LeConte 312

Abstract

For any graph $G$ we may construct an associated polynomial called the matching polynomial, which is a variant on a generating function for matchings of $G$. When $G$ is a cycle or path graph with $n$ vertices, the resulting polynomials are essentially the Chebyshev polynomials $T _ n(x)$ and $U _ n(x)$ respectively. It is known that the only divisibility relations among the $U _ n$ have the form $\frac{U _ {mn-1}}{U _ {n-1}} = U _ {m-1}\circ T _ n$; we interpret this equality combinatorially. In particular we show the right-hand side is an object with combinatorial meaning, called the $d$-matching polynomial by Hall, Pruder and Sawin (2015).

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC