# Rook polynomials, matchings and permanents

*Discrete Structures and Algorithms (Seminar)*

*by Ian Wanless*

*Institution:*School of Mathematical Sciences, Monash University

*Date: Tue 1st September 2009*

*Time: 2:15 PM*

*Location: Room 107, Richard Berry Building, The University of Melbourne*

*Abstract*: Let $m_i(G)$ be the number of matchings of size $i$ in a graph $G$. I will look at some results and open problems motivated by variants of my core goal of trying to maximise $m_n(G)$ among $k$-regular bipartite graphs on $2n$ vertices. The key tools will be

The rook polynomial of $G$, defined by

\rho(G)=\sum_{i=0}^n(-1)^i m_i(G)x^{n-i}.

The permanent of a square matrix $A=[a_{ij}]$, given by

per(A)=\sum_\tau\prod_{i=1}^n a_{i\tau(i)},

where the sum is over all permutations of $\{1,2,\dots,n\}$.

Generating functions that count certain walks in $G$ and thereby produce formulae for $m_i$ in terms of counts of small subgraphs of $G$.

*For More Information:* contact: David Wood. email: woodd@unimelb.edu.au