Our paper, titled How to Realize a Graph on Random Points, has been accepted at CCCG (Canadian Conference on Computational Geometry) 2019. I’ll write more about it in future posts.

In this note, we are going to state the PCP theorem and its relation to the hardness of approximating some NP-hard problem.

PCP Theorem: the Interactive Proof View

Intuitively, a PCP (Probabilistically Checkable Proof) system is an interactive proof system where the verifier is given random bits and he is allowed to look into the proof in many locations. If the string is indeed in the language, then there exists a proof so that the verifier always accepts. However, if is not in the language, no prover can convince this verier with probability more than . The proof has to be short i.e., of size at most . This class of language is designated as PCP[r(n), q(n)].

Theorem A (PCP theorem). Every NP language has a highly efficient PCP verifier. In particular,

This is an elementary (yet important) fact in matrix analysis.

Statement

Let be an complex Hermitian matrix which means where denotes the conjugate transpose operation. Let be two different eigenvalues of . Let be the two eigenvectors of corresponding to the two eigenvalues and , respectively.

Then the following is true:

Here denotes the usual inner product of two vectors .

We will show that the eigenvalues of the Laplacian matrix of the complete graph are where the eigenvalue has (algebraic) multiplicity and the eigenvalue has multiplicity .

In this post, we provide a proof of Kirchhoff’s Matrix Tree theorem [1] which is quite beautiful in our biased opinion. This is a 160-year-old theorem which connects several fundamental concepts of matrix analysis and graph theory (e.g., eigenvalues, determinants, cofactor/minor, Laplacian matrix, incidence matrix, connectedness, graphs, and trees etc.). There are already many expository articles/proof sketches/proofs of this theorem (for example, see [4-6, 8,9]). Here we compile yet-another-expository-article and present arguments in a way which should be accessible to the beginners.

Statement

Suppose is the Laplacian of a connected simple graph with vertices. Then the number of spanning trees in , denoted by , is the following:

The reader is a beginner, like me, and have already glanced through the Spielman-Srivastava paper (from now on, the SS paper).

The reader has, like me, a basic understanding of spectral sparsification and associated concepts of matrix analysis. I will assume that she has read and understood the Section 2 (Preliminaries) of the SS paper.

The reader holds a copy of the SS paper while reading my post.

First, I will mention the main theorems (actually, I will mention only what they “roughly” say).