User:Dbwilsoncom/sandbox

Kasteleyn matrix

For a planar graph, a Kasteleyn matrix $K$ is a skew symmetric matrix which is a signed version of the adjacency matrix of the graph, such that the determinant is the square of the number of perfect matchings. The choice of signs in the matrix can be intrepreted as placing orientations on the edges of the graph, so that an edge is directed from vertex $u$ to vertex $v$ if $K_{u,v}>0$. Kasteleyn matrices satisfy the property that for every face of the graph, an odd number of edges on its boundary are oriented in the counterclockwise direction. (Such an orientation always exists if the planar graph has an even number of vertices.)

Uniform spanning tree

A spanning tree of a graph is a connected acyclic subgraph. A uniform spanning tree of a finite graph is a spanning tree chosen uniformly at random among all spanning trees.