0
$\begingroup$
  1. Maximal and maximum matchings seem to be with respect to different partial orders, do they? In the set of all matchings in a graph, a maximal matching is with respect to a partial order defined by growing a matching, while a maximum matching is with respect to a partial order defined by its size.
  2. Wikipedia says:

    While a partially ordered set can have at most one each maximum and minimum it may have multiple maximal and minimal elements.

    But there can be several maximum matchings in a graph. What goes wrong?

Thanks!

$\endgroup$
1
$\begingroup$

What you call "with respect to a partial order defined by growing a matching" is usually referred to as "(partially) ordered by inclusion".

A maximum matching isn't defined with respect to a partial order defined by size. This is because a partial order requires $(a\le b\land b\le a)\Rightarrow a=b$, whereas two matchings may have the same size yet be different. Thus, it's only the sizes that are partially (in fact totally) ordered, not the matchings. There is indeed only one maximum size, but several maximum matchings may have it.

$\endgroup$
  • $\begingroup$ Thanks! If the order on matchings in terms of their sizes is not partial, what type of order is it? $\endgroup$ – StackExchange for All Nov 25 '12 at 13:55
  • $\begingroup$ Or what type of relation, more precisely? $\endgroup$ – StackExchange for All Nov 25 '12 at 14:15
  • $\begingroup$ @Tim: It's a preorder or quasiorder, a reflexive transitive relation that's not necessarily antisymmetric. $\endgroup$ – joriki Nov 25 '12 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.