School Seminars and Colloquia

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