Bipartite matchings and SDRs

Matchings in bipartite graphs and systems of distinct representatives (SDRs) of systems of subsets are closely related. More precisely, let \mathcal{A}=\{A_1,...,A_m\}\subseteq 2^X, for X a finite set. We can construct a bipartite graph \Gamma=(\mathcal{A}\cup X,E), where E=\{(A,x)\mid x\in A\in\mathcal{A}\}.

An SDR of \mathcal{A} is Y\subseteq X such that A_i\cap A_j\cap Y=\emptyset for all i\neq j and |A_i\cap Y|=1 for all i. In particular Y contains exactly one element y_A for each A\in\mathcal{A}.
Then \{(A,y_A)\mid A\in\mathcal{A}\} is a matching of \Gamma saturating the part \mathcal{A}. In particular, it is a maximum matching.
Conversely, a matching of \Gamma saturating \mathcal{A} gives rise to an SDR for \mathcal{A}.

An obvious necessary condition for existing of an SDR for \mathcal{A}
is the following Hall’s condition:

| \cup_{A\in\mathcal{B}} A|\geq |\mathcal{B}|,\qquad \forall\ \mathcal{B}\subseteq\mathcal{A}.

In view of this, Hall’s Theorem for matchings is equivalent to the following

An SDR for \mathcal{A} exists iff it satisfies Hall’s condition.

To see that Hall’s condition is sufficient, we proceed by induction on m. For m=1 the claim is obvious. Assume that it is true for all collections of less than m sets. We now establish that it holds for m-set collections, too.

If | \cup_{A\in\mathcal{B}} A|> |\mathcal{B}|,\quad \forall\ \mathcal{B}\subset\mathcal{A}, then we take any A\in \mathcal{A} and set y_A=y for some y\in A. Now by induction there is an SDR Y' for \mathcal{A}\setminus\{A\}. Then \{y_A\}\cup Y' is an SDR for \{B\setminus\{y_A\}\mid B\in\mathcal{A}\}.

In the remaining case there exists k< m such that | \cup_{A\in\mathcal{B}} A|=|\mathcal{B}|=k,\quad  \mathcal{B}\subset\mathcal{A}. By induction, there is an SDR Y' for \mathcal{B}.
Let \mathcal{C}\subseteq \mathcal{A}\setminus\mathcal{B}. Then | \cup_{A\in\mathcal{C}} A\setminus Y'|\geq |\mathcal{C}|=s, for otherwise | \cup_{A\in\mathcal{C}\cup\mathcal{B}} A|< s+k, contradicting Hall’s condition. Now we can take an SDR Y'' for \{A\setminus Y'\mid A\in\mathcal{A}\setminus\mathcal{B}, and observe that Y'\cup Y'' is an SDR for \mathcal{A}.

Advertisements

Tags: , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: