1
$\begingroup$

Let $P_1=\{A_1,A_2,...,A_{10}\}$ and $P_2=\{B_1,B_2,...,B_{10}\}$ be two distinct partitions of a set of $100$ people into groups of $10$. Let $G$ be a bipartite graph with $P_1$ and $P_2$ as bipartitions. There is an edge between $A_i$ and $B_j$ if $A_i$ and $B_j$ are disjoint.

Show $G$ has a matching.

$\endgroup$
  • 2
    $\begingroup$ Do you mean not disjoint? If $A_1$ has one element in common with each of the $B_j$, then I don't see how there can be a matching. $\endgroup$ – Gerry Myerson Jan 28 '18 at 1:18
  • 1
    $\begingroup$ Ah, i saw just now your comment. $\endgroup$ – Aqua Jan 28 '18 at 6:55
1
$\begingroup$

As far as i can see this is not true. Suppose we arrange people in table $10\times 10$, so that each field of table contains exactly one person. If we think that $P_1$ is a set of columns and $P_2$ a set of horizontal lines then we see that this graph has no edge and so no matching.

$\endgroup$
1
$\begingroup$

On the other hand if we do as Gerry suggested, so $$A_i\sim B_j \Longleftrightarrow A_i\cap B_j \ne \emptyset$$ then there is a perfect matching. Take any $X \subset P_1$ and let $N(X)\subset P_2$ be the set of all neighbors of vertices in $X$. Say $|X|=k$ and $|N(X)| = l$. Then we have $$\bigcup _{A\in X} A \subseteq\bigcup _{B\in N(X)} B $$ since set on left and sets on right are disjoint we have $$10k= \sum _{A\in X} |A|\leq \sum _{B\in N(X)} |B| =10l $$ we have $k\leq l$ so $|X|\leq |N(X)|$ and so Hall condition is fulfilled and we are done.

$\endgroup$

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.