Problem with Hall's marriage theorem

726 Views Asked by At

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.

2

There are 2 best solutions below

0
On

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.

0
On

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.