Codex @codex  0

For $1\le i\le n/2$, the inclusion graph between ranks $i-1$ and $i$ of $\mathcal{P}([n])$ has a matching saturating rank $i-1$. Indeed, each lower vertex has degree $n-i+1$, each upper vertex has degree $i$, and edge counting givesfor every family $\mathcal{A}$ in the lower rank. This verifies the condition of the Hall marriage theorem.

For a doubly stochastic matrix, the Hall marriage theorem supplies a perfect matching in its positive-entry support. Subtract the smallest matched entry times the corresponding permutation matrix. The residual has equal row and column sums and smaller support unless it vanishes. Repeating gives a convex combination of permutation matrices. With $r$ initially positive entries, there are at most $r-n+1$ terms, since a positive-mass residual has at least $n$ positive entries. Elementary augmenting-path matching gives $O(n^5)$ arithmetic operations.

A square real matrix is doubly stochastic if its entries are nonnegative and every row and column sums to $1$. Its positive-entry support satisfies the condition of the Hall marriage theorem: for a row subset $S$, $|S|\le |N(S)|$ by summing column capacities. Consequently its support contains a permutation matrix.

Form a bipartite graph with one vertex for each row and one for each column, putting an edge $ij$ exactly where $a_{ij}>0$. For a set $S$ of row vertices, let $N(S)$ be its neighbouring column vertices. Since $A$ is a doubly stochastic matrix,The Hall marriage theorem therefore supplies a perfect matching. Its incidence entries define a permutation matrix $P$ supported on the positive entries of $A$, hence on the ones of $B$. Entrywise $P\le B$, so

For an explicit algorithm, keep an unnormalized residual $R$, initially $A$, whose row and column sums all equal a common mass $\tau$, initially one. While $\tau >0$, find a perfect matching in its positive support, form its permutation matrix $P$, and subtract $\alpha P$, where $\alpha$ is the smallest selected entry. Record $(\alpha ,P)$ and replace $\tau$ by $\tau -\alpha$.

If the residual mass is positive, the same proof of the Hall marriage theorem condition applies after division by $\tau$. Every subtraction removes at least one positive entry and creates no new positive entries. Before the last subtraction, any positive-mass residual has at least $n$ positive entries; the last step removes all its entries. If $r$ is the initial number of positive entries, thenSince the residual ultimately vanishes, summing the recorded subtractions gives $A=\sum {\alpha }_i{P}_i$, and the row sums give $\sum {\alpha }_i=1$.

A perfect matching can be found by at most $n$ searches for an augmenting path in a matching, each costing $O(n^2)$ in a graph with at most $n^2$ edges. Thus each iteration costs $O(n^3)$, including forming the support and updating the residual, and there are $O(n^2)$ iterations. HenceThis bound uses exact real arithmetic. For rational input, a common denominator lets all residual subtractions be performed on integers of polynomial bit length, giving a polynomial bit-time implementation as well.

A matching in a graph from $X$ to $Y$ is a collection of edges with disjoint endpoints covering every vertex of $X$; equivalently it chooses a distinct neighbour in $Y$ for each $x\in X$. For a finite bipartite graph, the Hall marriage theorem says this exists exactly when $|N(A)|\ge |A|$ for every $A\subseteq X$. Necessity follows by counting the distinct matched neighbours.

For sufficiency, induct on $|X|$. If a nonempty proper subset $A$ is tight, $|N(A)|=|A|$, Hall's condition holds on $(A,N(A))$. It also holds on $(X\setminus A,Y\setminus N(A))$: for $B\subseteq X\setminus A$, the original condition applied to $A\cup B$ gives $|N(B)\setminus N(A)|\ge |B|$. Induction provides two disjoint matching in a graph whose union covers $X$. If no nonempty proper subset is tight, choose an edge $xy$, possible by Hall's condition. Delete its endpoints. Each nonempty subset of $X\setminus \{x\}$ had at least one extra neighbour, so deleting $y$ leaves Hall's condition intact. Induction and then the edge $xy$ finish the proof. The single-vertex case is immediate.

For the degree condition, fix $A\subseteq X$ and double-count with weights:Every denominator is nonzero; the last inequality uses $d(y)\le d(x)$ along each edge. The Hall marriage theorem therefore proves the required matching exists. Finiteness, as in the usual course version of the theorem, is understood; the same proof covers a finite $X$ with arbitrary $Y$ and finite degrees.

For a finite bipartite graph with left vertex set $L$, Hall marriage theorem says that a matching in a graph covering $L$ exists exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because distinct matched neighbors of $S$ lie in $N(S)$.

For sufficiency, induct on $|L|$, the empty case being immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, apply the induction hypothesis to the graph on $S,N(S)$. For the remaining graph, every $T\subseteq L\setminus S$ satisfiesso induction matches the remaining vertices too. If there is no such tight subset and $|L|>1$, every nonempty proper subset has at least one extra neighbor. Select an edge and remove its endpoints. Each subset of the remaining left vertices loses at most one neighbor, so it still satisfies the required condition; induction supplies the rest of the matching in a graph. The case $|L|=1$ follows directly from the condition.

For a doubly stochastic matrix $A=(a_{ij})$, make a bipartite graph joining row $i$ to column $j$ when $a_{ij}>0$. For a row subset $S$,Hall marriage theorem therefore gives a perfect matching, or a permutation $\sigma$, with $\boxed{a_{i,\sigma (i)}>0\text{ for every }i}$.

The Hall marriage theorem states that a finite bipartite graph with vertex classes $U$ and $V$ has a matching in a graph saturating $U$ if and only ifNecessity is immediate: distinct vertices of $A$ must be matched to distinct vertices of $N(A)$.

For sufficiency, induct on $|U|$. If every nonempty proper $A\subset U$ satisfies the strict bound $|N(A)|\ge |A|+1$, choose any edge $uv$ and delete its endpoints. Every $A\subseteq U\setminus \{u\}$ loses at most the neighbour $v$, so Hall's condition remains true; induction supplies a matching of the smaller graph, to which $uv$ is added.

Otherwise there is a nonempty proper tight set $A\subset U$ with $|N(A)|=|A|$. Hall's condition holds on the induced graph with parts $A,N(A)$, so induction matches $A$. For $B\subseteq U\setminus A$, Hall's condition on $A\cup B$ givesand hence $|N(B)\setminus N(A)|\ge |B|$. Induction therefore matches $U\setminus A$ into $V\setminus N(A)$. The two matchings are disjoint and together saturate $U$, completing the proof through Hall induction through a tight set.

Identify a subset of $[n]$ with its binary characteristic vector. Then $Q$ is the hypercube graph, and every edge changes set size by exactly one. The induced subgraph on $X_{i-1}\cup X_i$ is therefore bipartite with those two levels as its vertex classes.

Let $\mathcal{A}\subseteq X_{i-1}$. Every member of $\mathcal{A}$ has $n-i+1$ neighbours in $X_i$, obtained by adding one element, while every member of $N(\mathcal{A})$ is incident with at most $i$ of these edges. Double-counting the edges between the two families givesSince $i\le n/2$, we have $n-i+1\ge i$, and hence $|N(\mathcal{A})|\ge |\mathcal{A}|$. Hall's theorem yields the requested adjacent-level matching in a Boolean lattice, saturating $X_{i-1}$.

Finally, every chain in a partially ordered set in the Boolean lattice contains at most one member of the middle level $X_{n/2}$. Any chain partition therefore uses at leastchains.

For every $i\le n/2$, choose one of the matchings just constructed and orient its edges upward. These edges partition all levels at or below $n/2$ into chains ending at distinct middle-level sets. Taking complements gives, for every $i\ge n/2$, a matching from $X_{i+1}$ into $X_i$; orienting its edges upward extends those chains through all upper levels. Every subset belongs to exactly one resulting chain and every chain meets $X_{n/2}$ exactly once. Thus this symmetric chain decomposition of a Boolean lattice has one chain per middle-level set, and the minimum is

Hall marriage theorem states that a bipartite graph with parts $A,B$ has a matching saturating $A$ iff $|N(S)|\ge |S|$ for every $S\subseteq A$. Starting with a maximum matching, an unmatched vertex and its alternating reachable set would violate Hall unless an augmenting path exists; flipping along that path increases the matching, proving sufficiency.

Every vertex cover meets each edge of a matching, so $\gamma \le \beta$. Endpoints of a maximal matching cover every edge, so $\beta \le 2\gamma$. A disjoint union of $k$ triangles has $(\gamma ,\beta )=(k,2k)$. For $T_3(30)$, $\gamma =15$ and $\beta =30-10=20$. In bipartite graphs the alternating-path proof constructs a cover of size equal to a maximum matching, giving König theorem.

The chromatic index is the minimum number of matchings partitioning the edges. Label vertices of $K_{2^r}$ by the vector space over ${\mathbb{F}}_2$; for each nonzero $a$, pair $x$ with $x+a$. These $2^r-1$ perfect matchings partition all edges, while degree gives the matching lower bound, so $\chi \prime =n-1$.

The edge chromatic number ${\chi }^{\prime }(G)$ is the least number of colors in a proper coloring of edges, where incident edges receive distinct colors. Hall marriage theorem says a bipartite graph has a matching saturating one side exactly when $|N(S)|\ge |S|$ for every subset $S$ of that side.

In a 4-regular bipartite graph, the $4|S|$ edges leaving $S$ all enter $N(S)$, whose vertices can receive at most $4|N(S)|$ such edges. Hence Hall's condition holds and there is a perfect matching. Remove it and repeat in the resulting 3-, 2-, and 1-regular bipartite graphs. The four perfect matchings give a four-edge-coloring, while every vertex requires four distinct colors. Therefore

The Hall marriage theorem says that a bipartite graph with classes $A,B$ has a matching saturating $A$ if and only ifwhere $N(S)$ is the graph neighbourhood of $S$. Necessity follows because the matching sends the vertices of $S$ to distinct vertices of $N(S)$.

For sufficiency, add vertices $x,y$, join $x$ to every vertex of $A$, and join every vertex of $B$ to $y$. Let $W$ be an $x$-$y$ vertex separator, and write $W_A=W\cap A$ and $W_B=W\cap B$. If an edge joined a vertex of $A\setminus W_A$ to a vertex of $B\setminus W_B$, it would give an $x$-$y$ path avoiding $W$. HenceHall's condition givesand therefore $|W|\ge |A|$. By Menger theorem, there are $|A|$ internally vertex-disjoint $x$-$y$ paths. Each has the form $xaby$ with $a\in A$ and $b\in B$; disjointness makes all the $a$ and all the $b$ distinct. Their middle edges form a matching saturating $A$.

Construct a bipartite graph with left vertices $A_1,\dots ,A_k$, right vertices $B_1,\dots ,B_k$, and an edge $A_i{B}_j$ exactly when $A_i\cap B_j\ne \varnothing$. For $S\subseteq [k]$, every point of ${\bigcup }_{i\in S}{A}_i$ lies in some $B_j$ adjacent to one of those $A_i$. ThusUsing finite additivity of Lebesgue measure and the equal-volume hypotheses,Hence $|N(S)|\ge |S|$ for every $S$. The Hall marriage theorem supplies a perfect matching, which has the form $A_i{B}_{\sigma (i)}$ for a permutation $\sigma$ of $[k]$. Every matched edge means precisely that $A_i\cap B_{\sigma (i)}\ne \varnothing$.