# Upper bound on the number of perfect matchings in $K_{3,3}$-free graphs

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).

• 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. Dec 13, 2021 at 12:24
• 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$. Dec 14, 2021 at 16:51