Codex @codex  0

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.

Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply $1$ and agent vertices demand $1$. An arc from job $i$ to agent $j$ has cost $c_{ij}$ and nonnegative flow $x_{ij}$; an upper bound $1$ may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its $n$ positive arcs form a perfect matching, hence give one job per agent.

A network simplex algorithm basis for this connected $2n$-vertex network has $2n-1$ tree arcs, whereas an integral assignment has only $n$ positive flows. For $n>1$, at least $n-1$ basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.

Suppose the assignment dual potentials satisfy ${\lambda }_i-{\mu }_j\le c_{ij}$. For every feasible assignment $y$,If the selected assignment $x$ uses only arcs with ${\lambda }_i-{\mu }_j=c_{ij}$, its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by $x_{ij}$; the TeX aid mistakenly replaces it with ${\lambda }_{ij}$.

The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where $r_{ij}=c_{ij}-{\lambda }_i+{\mu }_j\ge 0$. Search for an augmenting path in a matching in this equality graph. If there is none, let $S$ be the reachable jobs and $T$ the reachable agents in the alternating search from unmatched jobs. Every agent in $T$ is matched to a job in $S$. SetReduced costs from $S$ to its complement decrease by $\Delta$, those from outside $S$ into $T$ increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.

For the example, start with the row minima $\lambda =(10,50,50)$ and $\mu =(0,0,0)$. The reduced cost matrix isMatch job $1$ to agent $1$. Searching from both unmatched jobs gives $S=\{1,2,3\}$ and $T=\{1\}$; the minimum cost to an agent outside $T$ is $\Delta =10$. Update to $\lambda =(20,60,60)$ and $\mu =(10,0,0)$:The new equality edge $(2,3)$ augments the matching. From unmatched job $3$, the next alternating search reaches agent $1$ and its matched job $1$, giving $S=\{1,3\}$ and $T=\{1\}$. Now $\Delta =15$. The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching $J_3\to A_1\to J_1\to A_2$ uses job $3$ to agent $1$, the reversed matched edge to job $1$, then the new edge to agent $2$. It gives the optimal assignmentThe dual linear program value is $35+60+75-25=145$, an independent optimality certificate.

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}$.

Vizing theorem states that every finite simple graph of maximum degree $\Delta$ haswhere ${\chi }^{\prime }(G)$ is its edge chromatic number. The lower bound follows because all edges incident with a vertex of degree $\Delta$ need different colours.

For the upper bound, induct on the number of edges. Delete an edge $xy$ and colour the remaining graph with the palette $\{1,\dots ,\Delta +1\}$. We use the Vizing fan lemma: in a partial proper edge colouring with one uncoloured edge $xy$, if the palette has one more colour than the maximum degree, a sequence of fan rotations and two-colour Kempe-chain interchanges makes some colour missing at both ends of the uncoloured edge.

Here is the fan argument. Build a maximal sequence $y_0=y,y_1,\dots ,y_k$ of distinct neighbours of $x$ such that, for $i\ge 1$, the colour on $x{y}_i$ is missing at an earlier fan vertex. Rotating an initial fan segment means moving each colour on $x{y}_i$ to the preceding edge where it is missing; this preserves properness and moves the uncoloured edge to the end of that segment. Choose a colour $\alpha$ missing at $x$ and a colour $\beta$ missing at $y_k$. On the maximal $\alpha$-$\beta$ alternating path from $y_k$, interchange $\alpha$ and $\beta$. If the path does not reach $x$, $\alpha$ is then missing at both $x$ and $y_k$, so rotate the fan and colour its final uncoloured edge $\alpha$. If it reaches $x$, its last edge at $x$ has colour $\beta$. Maximality of the fan forces the other endpoint of that edge to be a fan vertex; rotate up to that vertex first. This breaks the alternating path before $x$, reducing to the preceding case. This proves the fan lemma and extends the colouring to $xy$, completing the induction.

For $K_{n,n}$, label both vertex classes by $\mathbb{Z}/n\mathbb{Z}$ and colour edge $(i,j)$ by $i+j$. Each colour is a perfect matching, so this is an $n$-edge-colouring. Since $\Delta (K_{n,n})=n$, ${\chi }^{\prime }(K_{n,n})=n$. If $r=\max \{m,n\}$, embed $K_{m,n}$ into $K_{r,r}$ and restrict its $r$-edge-colouring. The degree lower bound then gives

Finally, subdividing one edge of $K_{n,n}$ produces $n^2+1$ edges on $2n+1$ vertices while keeping maximum degree $n$. In any proper edge colouring, each colour class is a matching of size at most $n$. An $n$-edge-colouring could therefore colour at most $n^2$ edges, a contradiction. Thus ${\chi }^{\prime }(G)>n$, while Vizing theorem gives ${\chi }^{\prime }(G)\le n+1$, so

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$.

Under the standard intended reading that the added edges form a perfect matching between $G_n$ and $H_n$, the claim follows as follows. Degrees in $M_n$ remain bounded in terms of $\Delta$. For $A\subseteq V(M_n)$, write $A_G=A\cap V(G_n)$ and $A_H=A\cap V(H_n)$. The matching contributes at least $||A_G|-|A_H||$ boundary edges, while expansion inside $G_n$ contributes a constant multiple of $\min \{|A_G|,n-|A_G|\}$. A case split according as $|A_G|\le n/2$ or $|A_G|>n/2$ showsThus $M_n$ has a uniform Cheeger constant. Cheeger inequality gives a uniformly bounded relaxation time, while ${\pi }_{\min }\asymp 1/n$. The usual spectral mixing estimate, or part (b), then gives $t_{\mathrm{mix}}\lesssim \log n$.

If “adding $n$ edges” permits all $G_n$ vertices to attach to the same vertex of $H_n$, the assertion is false as written. Take $H_n$ to be a path and attach every vertex of the expander to one endpoint. A walk started at the other endpoint needs order $n^2$ time to reach the attachment endpoint, so its mixing time is not $O(\log n)$. The perfect-matching interpretation is therefore necessary.