7
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 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
    Commented 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$
    – Michał Oszmaniec
    Commented Dec 14, 2021 at 16:51

0

Reset to default

You must log in to answer this question.