Matroiden

Matroiden are a class of combinatorial independence structures defined on a finite ground set E. They generalize the notion of a matroid by relaxing the single-element exchange axiom to allow exchanges in small batches. The central object is a family I of subsets of E called independent sets.

Axioms: The empty set is independent. The family I is hereditary (if A ∈ I and B ⊆ A, then B ∈ I). For a fixed integer k ≥ 1, the k-exchange property holds: for any A,B ∈ I with |A| < |B| there exists a nonempty subset X ⊆ B \ A with 1 ≤ |X| ≤ k such that A ∪ X ∈ I.

Remarks: When k = 1 the axioms define a matroid. For k > 1 the resulting structures are called Matroiden. They retain many features of matroids, including a well-behaved notion of independence and a greedy-amenable structure in restricted settings, but the exchange property no longer guarantees an immediate one-element augmentation.

Relation and examples: Matroiden sit among independence systems and share connections with greedoids and polymatroids. They appear in modeling problems where actions occur in small bundles, such as batch resource allocations or parallel task scheduling. In practice, many results for Matroiden depend on additional constraints or objective functions.

History and usage: The term Matroiden is used in some expository and theoretical discussions to study the spectrum between matroids and more general independence systems. It is not as widely standardized as the classic matroid theory, and definitions may vary in the literature.