Forbidden sequences in the sumset partition problem

A non-increasing sequence M = (m₁ ≥ ⋯ ≥ mₖ) of positive integers is realizable if there are pairwise disjoint subsets X₁, …, Xₖ ⊆ {1, …, m₁} with the sum of the elements of Xᵢ equal to mᵢ, and forbidden otherwise; this relaxes the classical sumset partition problem, where the sets must partition {1, …, n} exactly. Realizability is hereditary under subsequences, so forbidden sequences are generated by minimal ones. A universal singleton rule shows that sequences with distinct entries are always realizable and reduces the decision problem to a packing problem for repeated values — conjecturally, to a full rainbow matching problem over arithmetically structured color classes. We catalog all 2,668 minimal forbidden sequences with m₁ ≤ 12, exhibit an infinite extremal family, show that merging entries into their sum preserves realizability — whence a lone doubled maximum is the only repetition forbiddenness ever needs — and prove that no minimal forbidden sequence lies on the exact-partition boundary. Returning to exact n-realizability, tree search pruned by the relaxed oracle is a complete decision procedure, and its refutation depth defines an order on feasible sequences that are not n-realizable. The resulting hierarchy is unbounded: floor((n−1)/2) ≤ maxord(n) ≤ n−5, with equality on the right for all 8 ≤ n ≤ 31, and two horizon theorems show that no witness family with a fixed finite core can certify the equality for all n. The computational complexity of both realizability notions remains open; we isolate a structured rainbow matching problem whose resolution would settle the relaxed case.