Tutte–Coxeter graph occupancy-fraction conjecture

Let αG(λ)\alpha_G(\lambda) denote the occupancy fraction of a graph GG in the hard-core model, and let H3,8H_{3,8} be the (3,8)(3,8)-cage, also known as the Levi graph or Tutte–Coxeter graph. Tutte–Coxeter occupancy-fraction conjecture. For every 33-regular graph GG of girth at least 77 and every λ>0\lambda>0,

αG(λ)αH3,8(λ).\alpha_G(\lambda)\leq\alpha_{H_{3,8}}(\lambda).

The conjecture identifies the (3,8)(3,8)-cage as the maximizer in this girth-constrained problem and is open.

Sources & referencesView supporting material

Primary source

Guillem Perarnau and Will Perkins, “Counting independent sets in cubic graphs of given girth”, arXiv:1611.01474 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.