Eventual n-periodicity of maximum-independent-set counts

About 15 years old · traced to

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 n≥1n \geq 1, there exists some N≥0N \geq 0 such that the sequence {an(d)}d≥N\{\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.

References

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.

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.