Independent Sets in Multiset Profile Graphs via Weighted Local Covers

Abstract

Let $G_q(d)$ be the unit-transfer graph on the nonnegative integer vectors whose $q$ coordinates sum to $d$, equivalently on the multiplicity profiles of size-$d$ multisets over $q$ symbols. The prime-checksum conjecture predicts that, for prime $q$ and all sufficiently large $d$, a largest independent set is a fiber of the natural cyclic checksum. We develop a finite-state weighted local-cover method for $G_q(d)$: translated induced subgraphs give local independence inequalities, while capped anchor profiles reduce the covering conditions for infinitely many degrees to a finite rational linear system. This method gives new proofs of the known cases $q=3$ and $q=4$ and determines $\alpha (G_q(d))$ exactly for $q=5$ and $q=7$ in every degree, thereby proving the next two odd-prime cases of the conjecture. In the complementary regime where $d$ is fixed and $q$ grows, the same method gives an explicit upper bound for $\alpha (G_q(5))$ for every $q\ge 7$, determines $\alpha (G_q(d))$ exactly when $q$ is a power of two and $d\in \{6,8,10\}$, and yields an asymptotically sharp upper bound through three terms for every fixed $d\ge 7$. The finite systems arising in these arguments are verified in exact arithmetic and supported by independently checkable certificates.

arXiv comment38 pages, 5 figures. Revised exposition; clarified that the fixed-degree $d=5$ result for $q\ge 7$ is an explicit upper bound; expanded the weighted-cover intuition; synchronized the mathematical content with the journal version