Eventual uniqueness of maximum independent sets in monomial graphs

About 6 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). Eventual uniqueness conjecture. For any n≥1n \geq 1, there exists some N≥0N \geq 0 such that an(d)=1\mathbf{a}_n(d)=1 whenever d≡0(modn)d\equiv 0\pmod n and d≥Nd\geq N.

The conjecture extends the paper's established uniqueness results in selected cases, particularly for n=3n=3 with dd divisible by 33 and for n=4n=4 with dd even. It predicts eventual uniqueness along the multiples of the number of variables for every nn.

References

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.