Eventual uniqueness of maximum independent sets in monomial graphs
Eventual uniqueness of maximum independent sets in monomial graphs
For positive integers and nonnegative integers , let be the graph whose vertices are the monomials of degree in variables, with two monomials adjacent exactly when their least common multiple has degree . Let denote the number of maximum independent sets of . Eventual uniqueness conjecture. For any , there exists some such that whenever and .
The conjecture extends the paper's established uniqueness results in selected cases, particularly for with divisible by and for with even. It predicts eventual uniqueness along the multiples of the number of variables for every .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.