1
$\begingroup$

Let $M, W\neq \emptyset$ be sets and $K\subseteq M\times W$. We say that $(M, W, K)$ has a marriage if there is an injective function $f:M\to W$ such that $f\subseteq K$.

If $(M,W, K)$ has a marriage, is there $W'\subseteq W$ such that

  1. $(M, W', K\cap(M\times W'))$ has a marriage, and
  2. every marriage $f: M\to W'$ is surjective

?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Why $W'=f(M)$ does not work? $\endgroup$
    – Fedor Petrov
    Commented Mar 17, 2015 at 10:58
  • 1
    $\begingroup$ Yes iff $M$ is finite. $\endgroup$
    – Goldstern
    Commented Mar 17, 2015 at 11:01
  • $\begingroup$ If not, for complete bipartite graph on countable sets the answer is negative, right? $\endgroup$
    – Fedor Petrov
    Commented Mar 17, 2015 at 11:05
  • $\begingroup$ Yes, there's no right to expect matchings from $M$ to $W$ to be bijective once the graph is infinite. $\endgroup$
    – Ben Barber
    Commented Mar 17, 2015 at 11:30

1 Answer 1

Reset to default
2
$\begingroup$

This answer may be yes under certain finiteness conditions, for example, K being a disjoint union of finite marriages. However, for the complete countable bipartite graph, any restriction of M and W to countably infinite subsets induces a complete graph on those subsets, and it is easy to find marriages on this subgraph that are not surjective. So in general the answer is no.

Gerhard "Characterization Seems To Be Harder" Paseman, 2017.11.09.

Improve this answer
$\endgroup$

You must log in to answer this question.

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