Eventual uniqueness of maximum independent sets in monomial graphs

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 n1n \geq 1, there exists some N0N \geq 0 such that an(d)=1\mathbf{a}_n(d)=1 whenever d0(modn)d\equiv 0\pmod n and dNd\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.

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.