<p>You are asking many things in the question, and I can only answer part of it:</p>

<blockquote>
  <p>necessary and/or sufficient conditions for existence perfect matchings</p>
</blockquote>

<p>It is unlikely that a nice necessary and sufficient characterization is known, because deciding whether a given 3-regular hypergraph has a perfect matching or not is NP-complete.  Indeed, it is equivalent to the <a href="http://en.wikipedia.org/wiki/One-in-three_3SAT#Variations" rel="nofollow">monotone 1-in-3 SAT</a> problem, which is proved to be NP-complete by Schaefer [Sch78].  (In [Sch78], the same problem is called “ONE-IN-THREE SATISFIABILITY” without the word “monotone.”)  To see this equivalence, interpret each hyperedge as a variable and each vertex as a clause.</p>

<p>[Sch78] Thomas J. Schaefer.  The complexity of satisfiability problems.  In <em>Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC)</em>, pp. 216–226, May 1978.  DOI: <a href="http://dx.doi.org/10.1145/800133.804350" rel="nofollow">10.1145/800133.804350</a>.</p>

CC BY-SA 3.0
2012-05-23T23:30:53.333Z
2012-05-25T21:05:04.117Z
2012-05-25T21:05:04.117Z
Tsuyoshi Ito
<p>I have been looking in general for results on matching for regular hypergraphs that are not uniform, but I could not find any. Papers I found by internet search seem to focus on uniform hypergraphs (sometimes in addition to being regular). The relative scarcity of results on regular hypergraph matching is somewhat puzzling, since uniform and regular hypergraphs are duals of each other and one would expect that matching may have been studied for both kinds.</p>

<p>I would appreciate if someone can point me to any sources. Of most interest to me are necessary and/or sufficient conditions for existence perfect matchings and closed form expressions or bounds for fractional matchings. I am also curious to know explanations (conceptual, historical etc) for the lack of results of this kind for regular hypergraphs.</p>

<p><strong>Edit:</strong> A matching is a collection of pairwise disjoint hyperedges; a perfect matching is a matching that covers all vertices.</p>

CC BY-SA 3.0
2012-05-20T13:47:37.897Z
How do you define a perfect matching in a hypergraph?
Tyson Williams
CC BY-SA 3.0
2012-05-20T19:27:50.390Z
@TysonWilliams added a definition above.
Ankur
CC BY-SA 3.0
2012-05-30T09:37:38.703Z
As you have observed, the dual of a regular hypergraph is uniform. A matching of a regular hypergraph corresponds to a strong independent set in its dual. You would try to search with "strong independent set" in a "uniform hypergraph."
Yoshio Okamoto
<reference-request><co.combinatorics>
(perfect fractional) matching in regular hypergraphs
Ankur
# (perfect fractional) matching in regular hypergraphs

(Asked by: username_0 on 2012-05-20)

I have been looking in general for results on matching for regular hypergraphs that are not uniform, but I could not find any. Papers I found by internet search seem to focus on uniform hypergraphs (sometimes in addition to being regular). The relative scarcity of results on regular hypergraph matching is somewhat puzzling, since uniform and regular hypergraphs are duals of each other and one would expect that matching may have been studied for both kinds.

I would appreciate if someone can point me to any sources. Of most interest to me are necessary and/or sufficient conditions for existence perfect matchings and closed form expressions or bounds for fractional matchings. I am also curious to know explanations (conceptual, historical etc) for the lack of results of this kind for regular hypergraphs.

**Edit:** A matching is a collection of pairwise disjoint hyperedges; a perfect matching is a matching that covers all vertices.

**Tags:** reference-request, co.combinatorics

> **Comments:**
> **username_1**: How do you define a perfect matching in a hypergraph?  
> **username_0**: @TysonWilliams added a definition above.  
> **username_2**: As you have observed, the dual of a regular hypergraph is uniform. A matching of a regular hypergraph corresponds to a strong independent set in its dual. You would try to search with "strong independent set" in a "uniform hypergraph."  

---

## 1 answers

### Answer by username_3 on 2012-05-23. Score: 5

You are asking many things in the question, and I can only answer part of it:

> necessary and/or sufficient conditions for existence perfect matchings

It is unlikely that a nice necessary and sufficient characterization is known, because deciding whether a given 3-regular hypergraph has a perfect matching or not is NP-complete. Indeed, it is equivalent to the [monotone 1-in-3 SAT](http://en.wikipedia.org/wiki/One-in-three_3SAT#Variations) problem, which is proved to be NP-complete by Schaefer [Sch78]. (In [Sch78], the same problem is called “ONE-IN-THREE SATISFIABILITY” without the word “monotone.”) To see this equivalence, interpret each hyperedge as a variable and each vertex as a clause.

[Sch78] Thomas J. Schaefer. The complexity of satisfiability problems. In *Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC)*, pp. 216–226, May 1978. DOI: [10.1145/800133.804350](http://dx.doi.org/10.1145/800133.804350).


---

