Independent Sets in Multiset Profile Graphs via Weighted Local Covers

The discrete simplex consists of the nonnegative integer vectors $a=(a_1,\ldots,a_q)$ whose coordinates sum to $d$.

Equivalently, its vertices are the multiplicity profiles of size-$d$ multisets over $q$ symbols.

Two vertices are adjacent when one is obtained from the other by decreasing one coordinate by one and increasing another coordinate by one.

We study the maximum size $\alpha_q(d)$ of an independent set in this graph.

Our upper bounds cover the graph by translated smaller graphs and assign them nonnegative weights.

For fixed $q$, the weights depend on only finitely many capped profiles, so one finite rational linear system can prove a bound for every sufficiently large $d$.

The method gives new proofs of the known cases $q=3$ and $q=4$ and determines $\alpha_q(d)$ exactly for $q=5$ and $q=7$ in every degree.

It also determines the largest classes of natural additive colorings for general $q$.

In the opposite regime, with $d$ fixed and $q$ growing, it solves degree five for $q\ge7$, gives exact power-of-two families in degrees six, eight, and ten, and gives an asymptotically sharp upper bound through three terms for every fixed $d\ge7$.

This last result improves the previously known asymptotic upper bound.