Bringing Maths out of Marriage

Standard

I will consider following definition of marriage:

the legally or formally recognized union of a man and a woman as partners in a relationship.

It can be difficult, due to the emotions we have, to find suitable partner. But mathematicians have tried to solve this problem. Pretty cool, huh!

(1) Hall’s Marriage Theorem:  We have $n$ boys, each of whom has several girlfriends, under what conditions can we marry off the boys in such a way that each boy marries one of his girlfriends?

We claim that this problem has a solution if and only if for every $k$, $1\leq k\leq n$, every set of $k$ boys has collectively at least $k$ girlfriends.

The connecting lines indicate whether this man and woman like each other. (boyfriend-girlfriend relationship) [By Greg Graviton , Applications of Measure, Integration and Banach Spaces to Combinatorics]

Mathematically, we can restate it in graph theoretic language as

Let $G$ be a bipartite graph with bipartition $V = X \cup Y$. Then $G$ contains a matching that saturates every vertex in $X$ if and only if $|N(S)| \geq |S|$ for every subset $S$ of $X$

where, $N(S)$ is defined to be the set of all vertices adjacent to any set $S$ of vertices in graph $G$ and $|.|$ denotes “the number of elements in”.

The proof of this theorem is by Induction on $n$. See this Cut the Knot article for proof.

(2) Stable Marriage Problem:  There are $n$ women and $n$ men in a community. Each woman ranks each man in accordance with her preference for that man as a spouse. No ties are allowed, so that if a woman is indifferent between two men, we nonetheless require that she express some preference. The preferences are to be purely ordinal, and thus each woman ranks the men in order 1,2, …, n. Similarly, each man ranks the woman in the order 1,2,…, n.

We would like to arrange marriages between the men and women so that there is not a man and a woman who prefer one another to their spouses. Such marriages are  called stable. Does there always exist a stable marriage?

We claim that the answer to this question is YES! We just need to follow Gale–Shapley algorithm.  Watch this awesome Numberphile video explaining this

Other articles in same spirit: