Derrick Stolee - Iowa State University - Research Browser

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
D. Stolee, Generating p-extremal graphs, (2011).
Web Version ArXiv Version
D. Stolee, Isomorph-free generation of 2-connected graphs with applications, UNL-CSE Technical Report #120, (2011).
Web Version ArXiv Version Research Project
Software
The EarSearch project contains the isomorph-free generation algorithm for 2-connected graphs, including the one to generate $p$-extremal chambers.
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

Derrick Stolee - Iowa State University - Research Browser