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$.
Web Version Official Version
Web Version ArXiv Version Research Project
- Source
- User Guide
- Requires TreeSearch and Utilities.
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".
Slides