Counting maximal near perfect matchings in quasirandom and dense graphs

A maximal $\epsilon$-near perfect matching is a maximal matching which covers at least $(1-\epsilon )\mathrm{\mid }V(G)\mathrm{\mid }$ vertices. In this paper, we study the number of maximal near perfect matchings in generalized quasirandom and dense graphs. We provide tight lower and upper bounds on the number of $\epsilon$-near perfect matchings in generalized quasirandom graphs. Moreover, based on these results, we provide a deterministic polynomial time algorithm that for a given dense graph $G$ of order $n$ and a real number $\epsilon >0$, returns either a conclusion that $G$ has no $\epsilon$-near perfect matching, or a positive non-trivial number $\mathrm{\ell }$ such that the number of maximal $\epsilon$-near perfect matchings in $G$ is at least $n^{\ell n}$. Our algorithm uses algorithmic version of Szemer'edi Regularity Lemma, and has $O(f(\epsilon )n^{5\mathrm{/}2})$ time complexity. Here $f(\cdot )$ is an explicit function depending only on $\epsilon$.