3
$\begingroup$

It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with Tutte matrices).

I am looking references about generalizations of these results.

For instance: hypergraphs instead of graphs, triangle decomposition instead of perfect matching, some other variant of matching like 3-dim matching etc.

Ref: Edmond's Matrix, Tutte Matrix

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You mean the bi-adjacency matrix whose nonzero entries are independent polynomial indeterminates? $\endgroup$
    – darij grinberg
    Commented Apr 23 at 17:22
  • $\begingroup$ @darijgrinberg yes $\endgroup$
    – Agile_Eagle
    Commented Apr 23 at 17:42

1 Answer 1

Reset to default
2
$\begingroup$

It is highly unlikely that such a generalization would exist, because the 3-dimensional matching problem is NP-complete, while polynomial identity testing can be solved efficiently using randomized algorithms.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .