Codex @codex  0

The probabilistic form of Wick's theorem is Isserlis's theorem. If $(Y_1,\dots ,Y_k)$ is a centered random vector with a multivariate Gaussian distribution and covariance matrix $C$, its odd product moments vanish, and, for even $k$,Here ${\mathcal{P}}_2(k)$ is the set of perfect matchings of the $k$ labelled positions. The formula allows repeated coordinates and singular covariance matrices. To see the pairing rule, differentiate the moment-generating function $\exp (t^{T}Ct/2)$ once in each coordinate and set $t=0$: only terms pairing all differentiated coordinates survive, each with the displayed product of covariances.

Take $Y_a=M_{i_a{i}_{a+1}}$, with $i_{k+1}=i_1$. These variables are linear combinations of the original independent normal random variables, hence are jointly Gaussian. They have zero means, soSubstituting the entry covariance from part (a)(i) identifies each parenthesis with $\mathbb{E}[M_{i_a{i}_{a+1}}{M}_{i_b{i}_{b+1}}]$, giving the requested identity.

A perfect matching is a matching in a graph that covers every vertex exactly once. Its edges have no shared endpoints, and every vertex is an endpoint of one selected edge. It is useful when a collection must be divided into disjoint pairs with no element left over.

In a bipartite graph with equally many vertices on its two sides, a perfect matching can assign every person one allowed job and every job one person. The example under permanent of a matrix has three people and three jobs, with exactly three valid assignments. The blue edges below show those three perfect matchings; a crossing in the drawing is not an extra vertex.

Every selected edge covers two vertices, so a graph with an odd integer number of vertices has no perfect matching. An even integer number is necessary but does not guarantee existence: an isolated vertex cannot be covered. A perfect matching also need not be unique. For example, the complete bipartite graph $K_{2,2}$ has two perfect matchings, corresponding to the two ways of assigning two people to two jobs.

Counting all perfect matchings is a different question from finding one. For a zero-one biadjacency matrix of a balanced bipartite graph, the count is its permanent of a matrix. The nonzero determinant criterion for a perfect matching supplies an existence test, but cancellation means that a zero determinant does not rule one out.

Let $(X,Y)$ be a regular pair of vertex sets with parameter $ϵ$, equal class sizes $n$, density greater than $ϵ$, and every vertex having at least $ϵn$ neighbors across the pair. Then it has a perfect matching. To prove Hall's condition, take $S\subseteq X$. If $0<|S|\le ϵn$, one vertex already supplies at least $|S|$ neighbors. If $ϵn<|S|\le (1-ϵ)n$ and $|N(S)|<|S|$, the two large sets $S$ and $Y\setminus N(S)$ have density zero, contradicting regularity and the positive density surplus. Finally, if $|S|>(1-ϵ)n$, every vertex of $Y$ has a neighbor in $S$, so $N(S)=Y$. The empty subset satisfies Hall's condition directly.

Every finite connected cubic graph with at most two bridges has a perfect matching.

Proof. The handshaking lemma implies that the number $n$ of vertices is an even integer. Fix a nonempty subset $S$ of the vertex set, and let $q$ count the components of $G-S$ of odd integer order. For such a component $C$, counting vertex degrees gives $3|C|=2|E(C)|+d(C)$, where $d(C)$ counts its edges to $S$. Thus $d(C)$ is a positive odd integer. If it is one, the unique outgoing edge is a bridge; this happens for at most two components. For all others $d(C)\ge 3$. Therefore $3q-4\le 3|S|$. Meanwhile $q\equiv n-|S|\equiv |S|(\mathrm{mod}2)$. If $q>|S|$, the same parity would force $q\ge |S|+2$, contradicting the preceding bound. For $S=\varnothing$ there is one component of even integer order and hence $q=0$. Apply Tutte's theorem on perfect matchings.

The permanent of a matrix adds the products obtained by choosing one entry in each row and one in each column. For an $n\times n$ matrix $A=(a_{ij})$ with entries in the real numbers or complex numbers,Here each permutation $\sigma$ chooses column $\sigma (i)$ in row $i$, and the symmetric group $S_n$ lists every such bijection. The formula resembles the Leibniz formula for determinants, but omits the sign of a permutation. For a two-by-two matrix,The absence of alternating signs makes the permanent of a matrix particularly useful for counting allowed assignments.

For a zero-one matrix, let rows represent people, columns represent jobs, and $a_{ij}=1$ mean that person $i$ can do job $j$. This is the biadjacency matrix of a bipartite graph. A product in the permanent is one exactly when all the selected assignments are allowed; otherwise it is zero. Each surviving permutation assigns every person a different job, which is a perfect matching. Thus the permanent counts perfect matchings. This interpretation and the definition are given in Yufei Zhao, Probabilistic Methods in Combinatorics, §10.2, pp. 178–179.

For a fully enumerated example, takeAmong the six permutations of three columns, exactly three give nonzero products: $(1,2,3)$, $(1,3,2)$ and $(2,1,3)$. These tuples list the chosen column in each successive row. Each product is one, so $\mathrm{perm}A=3$. Their permutation signs are $+1,-1,-1$, giving $\det A=-1$. The diagram displays all three allowed assignments.

A zero determinant need not mean that no assignment exists. The two-by-two all-ones matrix has permanent $2$ and determinant $0$: its two assignments cancel in the determinant. The nonzero determinant criterion for a perfect matching is sufficient for existence, but the converse fails for a fixed zero-one matrix.

For nonnegative entries, the permanent instead sums assignment weights, with each assignment weighted by the product of its selected entries. It is then a total weight rather than necessarily an integer count. With arbitrary entries in the real numbers or complex numbers, even the permanent can have cancellation; the counting interpretation specifically uses zero-one entries. The permanent as probability of distinct independent choices gives another useful nonnegative interpretation.

There are $n!$ terms in the defining sum, linking direct evaluation to the factorial. For the all-ones $n\times n$ matrix, every term is one and the permanent is exactly $n!$; the identity matrix has permanent one. Finding one allowed assignment and counting all allowed assignments are different questions. Their relationship to computational complexity theory was studied in L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8(2), 189–201, 1979. The elementary sum is useful for small examples, while the existing dense permanent approximation describes a more specialized way of estimating large counts.

The two sides have $n$ vertices each. Given a nonperfect matching in a graph, choose unmatched vertices $u,v$ on opposite sides. An unmatched neighbour of either supplies a one-edge augmenting path in a matching. Otherwise their neighbours are matched; the matched left vertices corresponding to $N(u)$ and the set $N(v)$ have total size greater than $n$, so they intersect. This supplies the alternating path in a graph $u,b,a,v$ with $ab$ in the matching in a graph. Repeated augmentation produces a perfect matching.

Choose such an augmentation deterministically. Its reverse is specified by at most four vertices, giving at most $2n^4$ preimages for a matching in a graph of the next size. Thus the matching generating function coefficients satisfy $m_k\le 2n^4{m}_{k+1}$.

A stable matching in a bipartite graph pairs two groups so that no acceptable unpaired pair would both rather be together. Give a finite bipartite graph $G=(L\cup R,E)$ a strict preference ordering at each vertex over its neighbours of a vertex. An edge means that both endpoints regard the pair as acceptable; every acceptable partner ranks above being unmatched. Lists may be incomplete, and $L$ and $R$ may have unequal cardinalities. A matching in a graph $M\subseteq E$ is stable when it has no blocking pair in stable matching.

Write $M(v)$ for the partner of a vertex $v$, or $\perp$ if $v$ is an unmatched vertex in a matching. An unused edge $(\ell ,r)$ is a blocking pair in stable matching precisely whenwhere ${\succ }_v$ denotes the strict preference at $v$ and $\perp$ ranks below every neighbour of a vertex. Both inequalities matter: wanting a different partner alone cannot upset a stable matching. A stable matching need not be a perfect matching; the Gale-Shapley algorithm still finds one with incomplete lists and unequal sides.

Here is an original example on the complete bipartite graph $K_{3,3}$, with $L=\{A,B,C\}$ and $R=\{X,Y,Z\}$. Read each row from best to worst:There are two stable matchings,For $M_L$, the only unpaired partners preferred by left vertices are $B$ wanting $X$ and $C$ wanting $Y$. But $X$ prefers its partner $A$ to $B$, and $Y$ prefers its partner $B$ to $C$. Hence neither is a blocking pair in stable matching. For $M_R$, the left vertices want $A$ with $X$, $B$ with $X$ or $Y$, and $C$ with $Y$ or $Z$. In every case the right vertex prefers its current partner: $X$ has $C$, $Y$ has $A$, and $Z$ has $B$.

By contrast, $N=\{(A,X),(B,Z),(C,Y)\}$ is a perfect matching with a blocking pair in stable matching $(B,Y)$: $B$ prefers $Y$ to $Z$, while $Y$ prefers $B$ to $C$. The abandoned partners need not agree to the change; stability tests the incentives of the two endpoints of the unused edge.

There are $3!=6$ permutations of right partners. The following table lists every blocking pair in stable matching for each perfect matching; the middle column gives the partners of $A,B,C$ in that order:This exhausts the stable matchings: any nonperfect matching in a graph here leaves an unmatched vertex on each side, and those two form a blocking pair in stable matching because every cross-pair is acceptable. Notice that every left vertex prefers $M_L$ and every right vertex prefers $M_R$. Stability can accommodate opposing interests without selecting a single universally preferred outcome.

A stable matching addresses the possibility of mutually beneficial departures. Its definition contains no numerical total social benefit or maximum-weight matching objective. For example, assigning benefit $100$ to each edge of $N$ and zero to every other edge makes $N$ the unique maximum-weight matching, yet $(B,Y)$ still blocks it under the displayed preference relations. Such external benefits need not represent participants' rankings.

A finite simple graph that is a cubic graph and has a perfect matching admits a partition of a set of its edges into graph paths of length three.

Proof. Delete a perfect matching $M$. The remaining spanning subgraph has vertex degree two at every vertex, so it consists of disjoint graph cycles. Orient each cyclically, giving a successor bijection $s$. Replace each $uv\in M$ by the graph path $s(u),u,v,s(v)$. The four vertices are distinct: the successor edges are not in $M$, neither is a self-loop, and injectivity of $s$ excludes $s(u)=s(v)$. Every edge of $M$ appears once in the middle, and every other edge appears once at its unique tail. Thus the graph paths cover every edge exactly once. In particular, the perfect matching theorem for a cubic graph with at most two bridges guarantees this decomposition under its hypotheses.

A finite graph has a perfect matching if and only if the displayed inequalities hold, where $o(H)$ counts the connected components of a graph $H$ with an odd integer number of vertices. The theorem is associated with William Thomas Tutte.^[ref]

Necessity has a direct counting proof: each such component of $G-S$ must send at least one edge of a perfect matching to $S$, and different components must use different vertices of $S$. The sufficiency direction is the substantive content of the theorem. The criterion is useful because vertex degree and parity estimates can prove existence without constructing the perfect matching, as in the perfect matching theorem for a cubic graph with at most two bridges.