Invariant Gaussian processes and independent sets on regular graphs of large girth

Understand

We prove that every 3-regular, n-vertex simple graph with sufficiently large girth contains an independent set of size at least 0.4361n.

• (The best known bound is 0.4352n.) In fact, computer simulation suggests that the bound our method provides is about 0.438n.
• Our method uses invariant Gaussian processes on the d-regular tree that satisfy the eigenvector equation at each vertex for a certain eigenvalue \lambda.
• We show that such processes can be approximated by i.i.d.