Let $G=(V,E)$ be a graph with an even number of vertices $|V|=2n$. Assume that $G$ is $K_{3,3}$-free i.e. it does not contain a graph isomorphic to biclique $K_{3,3}$. A perfect matching of $G$ is a partition of the set of vertices $V$ onto disjoint two-element subsets according to edges $E$.

Question: Are there any known upper bounds for the number of perfect matchings of such graphs?

I am not a specialist in graph theory and after an extensive internet search, I was only able to find that the complexity of computing perfect matchings for such $K_{3,3}$-free graphs is lower than the one in the general case (it reduces to NC from beeing #P hard).

Motivation: I stumbled on this problem while studying an unrelated physics problem that concerns contextuality in a restricted model of quantum computing based on Majorana fermions (see for example this work by Bravyi).

  • 5
    $\begingroup$ Such a graph without a $K_{3,3}$ has at most $n^{2-1/3}$ edges. This combined with a result of Alon and Friedland (arxiv.org/pdf/0803.2578.pdf) gives a non-trivial upper bound, but I do not know if it would be sharp. $\endgroup$
    – alpmu
    Dec 13, 2021 at 12:24
  • $\begingroup$ Thanks. These bounds turned out to be good enough for our purposes! Applying them gives that the maximal number of perfect matching in $K_{3,3}$-free graphs is at most $(n^{2/3}/2)^n$. $\endgroup$ Dec 14, 2021 at 16:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.