Howroyd's periodicity conjecture for maximum independent sets

Let G3(d)G_3(d) be the graph on the monomials of degree dd in three variables, with two monomials adjacent exactly when their least common multiple has degree d+1d+1. Let a3(d)\mathbf{a}_3(d) denote the number of maximum independent sets of G3(d)G_3(d). Howroyd's periodicity conjecture. The sequence {a3(d)}d9\{\mathbf{a}_3(d)\}_{d \geq 9} is 33-periodic, with a3(9)=1\mathbf{a}_3(9)=1, a3(10)=27\mathbf{a}_3(10)=27, and a3(11)=27\mathbf{a}_3(11)=27; equivalently, for d9d \geq 9,

a3(d)={1,d0(mod3),27,d≢0(mod3).\mathbf{a}_3(d)=\begin{cases}1,&d\equiv 0\pmod{3},\\27,&d\not\equiv 0\pmod{3}. \end{cases}

This conjecture, attributed to A. Howroyd through OEIS sequence A297557, concerns the eventual periodicity and exact values of the number of maximum independent sets. The paper presents it as motivation for studying these graphs; no resolution is supplied in the given text.

Sources & referencesView supporting material

Primary source

John Machacek, “Unique maximum independent sets in graphs on monomials of a fixed degree”, arXiv:2010.11112 (2021).

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.