Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713

Warning: Cannot modify header information - headers already sent by (output started at /home/public/wp-content/themes/simplelin/functions.php:1) in /home/public/wp-includes/rest-api/class-wp-rest-server.php on line 1713
{"id":201,"date":"2017-02-02T11:42:31","date_gmt":"2017-02-02T11:42:31","guid":{"rendered":"http:\/\/babarber.uk\/?p=201"},"modified":"2017-02-02T11:42:31","modified_gmt":"2017-02-02T11:42:31","slug":"matchings-and-minimum-degree","status":"publish","type":"post","link":"https:\/\/babarber.uk\/201\/matchings-and-minimum-degree\/","title":{"rendered":"Matchings and minimum degree"},"content":{"rendered":"

A Tale of Two Halls<\/em><\/p>\n

(Philip) Hall’s theorem.<\/strong> \u00a0Let $\"G\"$ be a bipartite graph on vertex classes $\"X\"$ , $\"Y\"$ . \u00a0Suppose that, \u00a0for every $\"S \subseteq X\"$ , $\"|N(S)| \geq |S|\"$ . \u00a0Then there is a matching from $\"X\"$ to $\"Y\"$ .<\/em><\/p>\n

This is traditionally called Hall’s marriage theorem. \u00a0The picture is that the people in $\"X\"$ are all prepared to marry some subset of the people in $\"Y\"$ . \u00a0If some $\"k\"$ people in $\"X\"$ are only prepared to marry into some set of $\"k-1\"$ people, then we have a problem; but this is the only problem we might have. \u00a0There is no room in this picture for the preferences of people in $\"Y\"$ .<\/p>\n

Proof.<\/em> Suppose first that\u00a0 $\"|N(S)| > |S|\"$ \u00a0for all $\"S \subset X\"$ . \u00a0Then we can match any element of $\"X\"$ arbitrarily to a neighbour in $\"Y\"$ and obtain a smaller graph on which Hall’s condition holds, so are done by induction.<\/p>\n

Otherwise\u00a0 $\"|N(S)| = |S|\"$ for some $\"S \subset X\"$ . \u00a0By induction there is a matching from $\"S\"$ to $\"N(S)\"$ . \u00a0Let $\"T = X \setminus S\"$ . \u00a0Then for any $\"U \subseteq T\"$ we have <\/p>\n

<\/span> <\/span> $\"\[|N(U) \setminus N(S)| + |N(S)| = |N(U \cup S)| \geq |U \cup S| = |U| + |S|\]\"$ <\/p>\n

hence $\"|N(U) \setminus N(S)| \geq |U|\"$ and Hall’s condition holds on $\"(T, Y \setminus N(S))\"$ . \u00a0So by induction there is a matching from $\"T\"$ to $\"Y \setminus N(S)\"$ , which together with the matching from $\"S\"$ to $\"N(S)\"$ is a matching from $\"X\"$ to $\"Y\"$ . $\"\square\"$ <\/p>\n

Corollary 1.<\/strong> \u00a0Every $\"k\"$ -regular bipartite graph has a perfect matching.<\/em><\/p>\n

Proof.<\/em> Counted with multiplicity, $\"|N(S)| = k|S|\"$ . \u00a0But each element of $\"Y\"$ is hit at most $\"k\"$ times, so $\"|N(S)| \geq k|S| / k = |S|\"$ in the conventional sense. $\"\square\"$ <\/p>\n

Corollary 2.<\/strong> Let $\"G\"$ be a spanning subgraph of $\"K_{n,n}\"$ with minimum degree at least $\"n/2\"$ . \u00a0Then $\"G\"$ has a perfect matching.<\/em><\/p>\n

This is very slightly more subtle.<\/p>\n

Proof.<\/em> If $\"|N(S)| = n\"$ there is nothing to check. \u00a0Otherwise there is a $\"y \in Y \setminus N(S)\"$ . \u00a0Then $\"N(y) \subseteq X \setminus S\"$ and $\"|N(y)| \geq n/2\"$ , so $\"|S| \leq n/2\"$ . \u00a0But $\"|N(S)| \geq n/2\"$ for every $\"S\"$ . $\"\square\"$ <\/p>\n

Schrijver proved<\/a> that a $\"k\"$ -regular bipartite graph with $\"n\"$ vertices in each class in fact has at least $\"\left(\frac {(k-1)^{k-1}} {k^{k-2}}\right)^n\"$ perfect matchings. \u00a0For minimum degree $\"k\"$ we have the following.<\/p>\n

(Marshall) Hall’s theorem.<\/strong> \u00a0If each vertex of $\"X\"$ has degree at least $\"k\"$ and there is at least one perfect matching then there are at least $\"k!\"$ .<\/em><\/p>\n

This turns out to be easy if we were paying attention during the proof of (Philip) Hall’s theorem.<\/p>\n

Proof.<\/em> By (Philip) Hall’s theorem the existence of a perfect matching means that (Philip) Hall’s condition holds. \u00a0Choose a minimal $\"S\"$ on which it is tight. \u00a0Fix $\"x \in S\"$ and match it arbitrarily to a neighbour $\"y \in Y\"$ . \u00a0(Philip) Hall’s condition still holds on $\"(S - x, Y-y)\"$ and the minimum degree on this subgraph is at least $\"k-1\"$ , so by induction we can find at least $\"(k-1)!\"$ perfect matchings. \u00a0Since there were at least $\"k\"$ choices for $\"y\"$ we have at least $\"k!\"$ perfect matchings from $\"S\"$ to $\"N(S)\"$ . \u00a0These extend to perfect matchings from $\"X\"$ to $\"Y\"$ as in the proof of (Philip) Hall’s theorem. $\"\square\"$ <\/p>\n

Thanks to\u00a0Gjergji Zaimi for pointing me to (Marshall) Hall’s paper<\/a> via MathOverflow<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"