Eventual n-periodicity of maximum-independent-set counts

From papers

For positive integers nn and nonnegative integers dd, let Gn(d)G_n(d) be the graph whose vertices are the monomials of degree dd in nn variables, with two monomials adjacent exactly when their least common multiple has degree d+1d+1. Let an(d)\mathbf{a}_n(d) denote the number of maximum independent sets of Gn(d)G_n(d). Periodicity conjecture. For any n1n \geq 1, there exists some N0N \geq 0 such that the sequence {an(d)}dN\{\mathbf{a}_n(d)\}_{d \geq N} is nn-periodic.

This is the paper's second conjecture concerning the eventual behavior of maximum-independent-set counts. It is posed alongside the conjecture on eventual uniqueness at degrees divisible by nn; the supplied text gives no general proof or resolution.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Additional references

2 papers in this index state this conjecture (2011–2020). The statement above is taken from the most recent of them; the others are arXiv:1103.3309.

Solutions 0

No solutions have been posted yet.