Invariant Gaussian processes and independent sets on regular graphs of large girth
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.
invariant gaussian process independent set regular graph large girth independence ratio random regular graph regular tree factor of i.i.d.