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":214,"date":"2017-02-07T16:10:15","date_gmt":"2017-02-07T16:10:15","guid":{"rendered":"http:\/\/babarber.uk\/?p=214"},"modified":"2017-02-07T16:10:15","modified_gmt":"2017-02-07T16:10:15","slug":"matchings-without-halls-theorem","status":"publish","type":"post","link":"https:\/\/babarber.uk\/214\/matchings-without-halls-theorem\/","title":{"rendered":"Matchings without Hall’s theorem"},"content":{"rendered":"

In practice matchings are found not by following the proof of Hall’s theorem but by starting with some matching and improving it by finding\u00a0augmenting paths<\/em>. \u00a0Given a matching $\"M\"$ in a bipartite graph on vertex classes $\"X\"$ and $\"Y\"$ , an augmenting path is a path $\"P\"$ from $\"x \in X \setminus V(M)\"$ to $\"y \in Y \setminus V(M)\"$ such that ever other edge of $\"P\"$ is an edge of $\"M\"$ . \u00a0Replace $\"P \cap M\"$ by $\"P \setminus M\"$ produces a matching $\"M'\"$ with $\"|M'| = |M| + 1\"$ .<\/p>\n

Theorem.<\/strong> \u00a0Let $\"G\"$ be a spanning subgraph of $\"K_{n,n}\"$ . \u00a0If (i) $\"\delta(G) \geq n/2\"$ or (ii) $\"G\"$ is $\"k\"$ -regular, then $\"G\"$ has a perfect matching.<\/p>\n

Proof.<\/em> Let $\"M = \{x_1y_1, \ldots, x_ty_t\}\"$ be a maximal matching in $\"G\"$ with $\"V(M) \subset V(G)\"$ .<\/p>\n

(i) Choose\u00a0 $\"x \in X \setminus V(M)\"$ , $\"y \in Y \setminus V(M)\"$ . \u00a0We have $\"N(x) \subseteq V(M) \cap Y\"$ and $\"N(y) \subseteq V(M) \cap X\"$ . \u00a0Since $\"\delta(G) \geq n/2\"$ there is an $\"i\"$ such that $\"x\"$ is adjacent to $\"y_i\"$ and $\"y\"$ is adjacent to $\"x_i\"$ . \u00a0Then $\"xy_ix_iy\"$ is an augmenting path.<\/p>\n

(ii) Without loss of generality, $\"G\"$ is connected. \u00a0Form the directed graph $\"D\"$ on $\"v_1, \ldots, v_t\"$ by taking the directed edge $\"\vec{v_iv_j}\"$ \u00a0( $\"i \neq j\"$ ) whenever $\"x_iy_j\"$ is an edge of $\"G\"$ . \u00a0Add directed edges arbitrarily to $\"D\"$ to obtain a $\"k\"$ -regular digraph $\"D'\"$ , which might contain multiple edges; since $\"G\"$ is connected we have to add at least one directed edge. \u00a0The edge set of $\"D'\"$ decomposes into directed cycles. \u00a0Choose a cycle $\"C\"$ containing at least one new edge of $\"D'\"$ , and let $\"P\"$ be a maximal sub-path of $\"C\"$ containing only edges of $\"D\"$ . \u00a0Let $\"v_i\"$ , $\"v_j\"$ be the start- and endpoints of $\"P\"$ respectively. \u00a0Then we can choose $\"y \in N(x_i) \setminus V(M)\"$ and $\"x \in N(y_j) \setminus V(M)\"$ , whence\u00a0 $\"yQx\"$ is an augmenting path, where $\"Q\"$ is the result of “pulling back” $\"P\"$ from $\"D\"$ to $\"G\"$ , replacing each visit to a $\"v_s\"$ in $\"D\"$ by use of the edge $\"y_sx_s\"$ of $\"G\"$ . $\"\square\"$ <\/p>\n

<\/p>\n","protected":false},"excerpt":{"rendered":"

In practice matchings are found not by following the proof of Hall’s theorem but by starting with some matching and improving it by finding\u00a0augmenting paths. \u00a0Given a matching in a bipartite graph on vertex classes and , an augmenting path is a path from to such that ever other edge of is an edge of … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[17,24],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/214"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=214"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/214\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}