An independent set in a graph is a set of vertices with no edges between them. A maximum independent set is one that can't be enlarged. A local maximum independent set is one that's maximum in its neighborhood — no nearby vertex can be swapped in to improve it. The collection of all local maximum independent sets of a graph is a set system, and Levit and Mandrescu (arXiv: 2603.22688) prove it has the structure of an augmentoid.
An augmentoid is an algebraic structure on set systems that generalizes matroids. In a matroid, any two independent sets of different sizes can be “augmented” — an element from the larger can be added to the smaller while maintaining independence. This exchange property is what makes matroids computationally tractable. An augmentoid relaxes this: the exchange is more structured, with specific conditions on which elements can be exchanged.
The proof is constructive. Given two local maximum independent sets S and T, the authors identify the “free parts” — A = S minus the closed neighborhood of T, and B = T minus the closed neighborhood of S — and show these satisfy the augmentation property with equal cardinality. This yields a canonical bijection and a decomposition formula: the independence number of the graph equals |S| plus the independence number of what's left after removing S's neighborhood.
The through-claim: the set of locally optimal solutions has global algebraic structure. Each local maximum independent set looks unrelated to every other — they're local optima, found by different greedy paths, seemingly independent. But collectively, they form an augmentoid: there are exchange rules governing how one local optimum relates to another. The local solutions are not isolated points in solution space; they're nodes in an algebraic lattice. The structure is in the collection, not in any individual element.
Levit & Mandrescu, 2603.22688. Discrete mathematics / graph theory / independent sets / augmentoids / matroid generalization.