Lesson 4

Using the lemma, we'll design a randomized algorithm for the graph matching problem.

Let \(G([n], E)\) be a graph. A perfect matching in \(G\) is a set of \(n / 2\) edges such that each vertex of \(G\) is the endpoint of exactly one of the chosen edges.

The Tutte matrix of \(G\) is an \(n \times n\) matrix \(T\) over formal variables defined as follows: \[T_{ij}= \begin{cases}x_{ij} & \text{if \(i<j\) and \(\{i,j\} \in E\)}, \\ -x_{ji} & \text{if \(i>j\) and \(\{i,j\} \in E\)}, \\ 0 & \text{otherwise.}\end{cases}\] Observe that the determinant of the Tutte matrix is a polynomial in the variables \(x_{ij}\), with at most \(\frac{n \cdot (n - 1)}{2}\) variables.