1
$\begingroup$

Are there necessary and sufficient conditions for a uniform hyper graph to have a perfect fractional matching ?

$\endgroup$
4
  • $\begingroup$ The definition is already a nice characterization. What are you looking for? A necessary and sufficient condition that is combinatorial? $\endgroup$ Jun 14, 2012 at 13:34
  • 4
    $\begingroup$ Could you provide some context, background, and motivation? $\endgroup$
    – Kaveh
    Jun 14, 2012 at 16:20
  • $\begingroup$ To me it seem that if you can solve the problem quickly in uniform hypergraphs, you can also solve the problem quickly in arbitrary hypergraphs – just add gadgets that make the hypergraph uniform while preserving the existence of a perfect fractional matching. And in the case of arbitrary hypergraphs, it seems to me that the problem is almost as difficult as solving a general 0/1 packing LP. Hence I would not expect that there is a particularly useful formulation of a necessary & sufficient condition. $\endgroup$ Jun 15, 2012 at 7:52
  • $\begingroup$ 1. Yes, combinatorial condition, like Tuttes's theorem 2. No it is not like 1/0, because for ex. regular graph has perfect fractional matching, but very few is known about 1/0 problem for it. $\endgroup$
    – user9755
    Jun 16, 2012 at 17:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.