Speaker
Dr
Sergey Perepechko
(Petrozavodsk State University)
Description
\documentclass[12pt]{article}
\usepackage{amssymb}
\sloppy
\paperwidth=210mm
\paperheight=297mm
\textheight=250mm
\textwidth=165mm
\oddsidemargin=-0.4mm
\evensidemargin=-5.4mm
\topmargin=-5.4mm
\begin{document}
\begin{center}
Near-perfect matchings on cylinders $C_m \times P_n$ of odd order
\end{center}
Abstract:\\
The problem of counting near-perfect matchings on cylinders $C_m \times P_n$ is
discussed when both parameters $m$ and $n$ are odd. A distinctive feature of
these matchings is the presence of exactly one node which is left unmatched.
This node will be called vacancy.
This combinatorial problem is directly related to the dimer problem, one of the
classical lattice models of statistical physics. If at least one of the
lattice parameters is even, then maximum matchings often turn out to be perfect
matchings. But if the order of the graph is odd, then maximum matchings are
usually near-perfect matchings. The generating function for the number of
near-perfect matchings is identical to generating function for the dimer model
when activities of all dimers are the same.
The methods known to date are able to find closed-form expressions for the
number of near-perfect matchings on $C_m \times P_n$ graphs only when the vacancy
is located on the boundary~\cite{Wu1}. Summation over all possible vacancy locations
for arbitrary values of parameters $m$ and $n$ is beyond the scope of available
analytical tools.
In our work, a counting problem is considered for a fixed value of the parameter
$m$. Under this condition, generating functions $G_m^P(z)$ for the number of
perfect matchings in the graphs $C_m \times P_{2n}$ and $G_m^N(z)$ for the number
of near-perfect matchings in the graphs $C_m \times P_{2n+1}$ are rational. These
generating functions can be reconstructed from sufficiently long initial segments
of sequences, the elements of which are numbers of near-perfect matchings in graphs
for fixed values of $m$ and changing $n$.
The implementation of the method by Wilf~\cite{Wilf1} in computer algebra system
Maple allowed us to obtain a set of recurrence relations and generating functions
for the number of near-perfect matchings for fixed odd values of the parameter
$3 \leqslant m \leqslant 13$. The coefficients of the asymptotic expansions are
calculated for $3 \leqslant m \leqslant 19$.
The study of generating functions $G_m^N(z)$ made it possible to establish a
close connection between their denominators and the denominators $G_m^P(z)$. For
all values of $m$ studied in our research, the denominator $G_m^N(z)$ had been
always the square of the denominator $G_m^P(z)$.
% ---------------------------------------------
\begin{thebibliography}{9}
%References\\
\bibitem{Wu1}
F. Y. Wu, Wen-Jer Tzeng and N. Sh. Izmailian, Physical Review E 83, 011106, (2011).
\bibitem{Wilf1}
H. S. Wilf, Journal of Combinatorial Theory, 4, 246--258, (1968).
\end{thebibliography}
% ---------------------------------------------
\end{document}
Primary author
Dr
Sergey Perepechko
(Petrozavodsk State University)
