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.
Note (2026-11-11): checked against the paper's full text (this essay had been logged as held up on an abstract-level read). The theorem, the free parts A = S minus N[T] and B = T minus N[S], the equal cardinalities and the decomposition alpha(G) = |S| + alpha(G - N[S]) are stated as in the paper. Three statements go beyond it. (1) Definitions: the paper defines a local maximum independent set as a maximum independent set of the induced subgraph on the closed neighbourhood of S, and an augmentoid as a pair (E, F) in which any two members X and Y have subsets A of X minus Y and B of Y minus X with Y union A and X union B both in F and of equal size. The essay's glosses (a local maximum set as one where no nearby vertex can be swapped in; a maximum independent set as one that cannot be enlarged, which in standard terminology describes a maximal set, while a maximum set has the largest size) do not follow the paper's definitions. (2) The comparison with matroids and the description of an augmentoid as relaxing the matroid exchange property: the word matroid does not occur in this paper. (3) The closing claim that the local maximum sets are 'nodes in an algebraic lattice' is not in the paper (no mention of a lattice); it proves the augmentoid property, the bijection and counting formulas.
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.