Extremal Graphs with $p$ Perfect Matchings

Problem and Results Summary

Extremal graph theory determines the maximum or minimum number of edges in a graph with certain properties. The graph $K_{n-1} \cup K_1$ is the unique largest graph with no perfect matchings. However, what if we say that a graph has exactly $p$ perfect matchings?

Dudek and Schmitt determine that there is a constant $c_p$ such that for every $p \geq 1$ the extremal function is eventually $\frac{n^2}{4} + c_p$. Hetyei proved that $c_1 = 0$. Hartke, Stolee, West, and Yancey proved that $c_p \geq 1$ for all $p \geq 2$ and determined $c_p$ for all $p \leq 10$. Stolee used computational methods to determine $c_p$ for all $p \leq 27$, including the fact that $c_p$ is not monotonic (in fact, the sequence behaves poorly).

**Conjecture.** The sequence $c_p$ grows on the order of $(\log n / \log\log n)^2$.

Research Papers

S. G. Hartke, D. Stolee, D. B. West, M. Yancey,
On extremal graphs with a given number of perfect matchings,
*Journal of Graph Theory*, **73**(4), 449-468.

Web Version Official Version

Web Version Official Version

D. Stolee,
Isomorph-free generation of 2-connected graphs with applications,
*UNL-CSE Technical Report* #120, (2011).

Web Version ArXiv Version Research Project

Web Version ArXiv Version Research Project

Software

The - Source
- User Guide
- Requires TreeSearch and Utilities.

Support

Stephen G. Harke was supported by a Nebraska EPSCoR First Award and by National Science Foundation grant DMS-0914815. Derrick Stolee was supported by National Science Foundation grants CCF-0916525 and DMS-0914815. Douglas B. West was supported by National Security Agency Award H98230-10-1-0363. Matthew Yancey was supported by National Science Foundation grant DMS 08-38434, "EMSW21-MCTP: Research Experience for Graduate Students".

Related Work

A. Dudek and J. Schmitt, On the size and structure of graphs with a constant number of 1-factors. *Discrete Mathematics* 312 (2012), 1807-1811

L. Lovász and M. D. Plummer, *Matching Theory*. (AMS Chelsea Publishing; Providence, RI, 2009), xxxiii+547 pp.

Presentations

New bounds for the existence of many perfect matchings and large matchings (Presented by Matthew Yancey) *MECS Interdisciplinary Seminar (01/15/2014)*, AMS/MAA Joint Math Meetings, Baltimore, MD.

Generating $p$-extremal graphs. *MECS Interdisciplinary Seminar (12/09/2013)*, Iowa State University.

Slides

Slides