Fact-checked by Grok 2 weeks ago

Matroid

A matroid is a combinatorial structure in mathematics that abstracts and generalizes the concept of linear independence in vector spaces and the notion of acyclicity in graphs, providing a unified framework for studying dependence relations across diverse mathematical domains.^[1]^[2] Introduced independently by Hassler Whitney and Takeo Nakasawa in 1935, matroids were originally motivated by the desire to capture abstract properties of linear dependence without reference to specific vector spaces or fields.^[1]^[3] Formally, a matroid M = (E, \mathcal{I}) consists of a finite ground set E and a collection \mathcal{I} of independent subsets of E, satisfying three axioms: (I1) the empty set is independent; (I2) every subset of an independent set is independent (hereditary property); and (I3) for any two independent sets I, J \in \mathcal{I} with |J| > |I|, there exists an element e \in J \setminus I such that I \cup \{e\} \in \mathcal{I} (augmentation property).^[2] These axioms ensure the existence of bases (maximal independent sets, all of equal size called the rank of the matroid) and circuits (minimal dependent sets).^[2] Equivalent definitions exist using circuits, closures, or rank functions, highlighting the flexibility of the structure.^[1] Prominent examples include vector matroids, where independent sets are linearly independent subsets of column vectors from a matrix over a field, and graphic matroids, where the ground set is the edge set of a graph and independent sets are forests (acyclic subgraphs).^[2] Other classes encompass uniform matroids (all subsets of a fixed size are independent), transversal matroids (from bipartite matchings), and binary or regular matroids (representable over specific fields).^[1] Matroids exhibit duality, where the bases of the dual matroid complement those of the original, enabling connections between seemingly disparate structures like spanning trees in graphs and coboundaries in their cographic duals.^[2] Matroids play a central role in combinatorial optimization, where the greedy algorithm—selecting elements in decreasing order of weight while maintaining independence—yields an optimal maximum-weight basis in polynomial time.^[4] This extends to matroid intersection problems, which generalize bipartite matching and yield min-max theorems like the one for the size of maximum common independent sets across two matroids.^[4] Applications span graph theory (e.g., finding spanning trees), linear algebra (e.g., matrix rank computations), coding theory (e.g., error-correcting codes via binary matroids), and integer programming (e.g., testing total unimodularity of matrices).^[1]^[4]

Definitions

Axiomatic Approach

A matroid is defined axiomatically as a pair (E, \mathcal{I}), where E is a finite set known as the ground set and \mathcal{I} is a collection of subsets of E termed the independent sets, satisfying three fundamental axioms.^[5] The first axiom (I1) states that the empty set is independent: \emptyset \in \mathcal{I}. This ensures a starting point for building independent sets, mirroring the trivial linear independence of the zero subspace in vector spaces.^[5] The second axiom (I2), the hereditary or downward closed property, requires that every subset of an independent set is independent: if I \in \mathcal{I} and J \subseteq I, then J \in \mathcal{I}. This captures the idea that independence is preserved under taking subsets, analogous to subspaces generated by fewer vectors remaining linearly independent.^[5] The third axiom (I3), known as the augmentation or exchange axiom, states that if I, J \in \mathcal{I} with |I| < |J|, then there exists an element e \in J \setminus I such that I \cup \{e\} \in \mathcal{I}. This axiom ensures that smaller independent sets can be extended using elements from larger ones, embodying the absence of structural redundancy in the independence system—meaning no independent set is "stuck" at a smaller size due to inherent dependencies that cannot be bypassed. For instance, if I = \{a\} and J = \{b, c\} are independent with |I| < |J|, the axiom guarantees that either \{a, b\} or \{a, c\} is independent, allowing growth without violating the independence condition.^[5] This axiomatic framework was introduced by Hassler Whitney to abstract and unify the properties of linear dependence in vector spaces over fields and the acyclic dependence in graphs, where independent sets correspond to linearly independent vectors or forests, respectively. All other axiomatic characterizations of matroids, such as those based on bases, circuits, or rank functions, are equivalent to this independent sets definition.^[5]

Equivalent Characterizations

Matroids admit several equivalent axiomatic characterizations, each capturing the structure of independence in combinatorial and algebraic settings. These formulations demonstrate the robustness of the concept, allowing definitions via independent sets, rank functions, closure operators, or circuits, with equivalences established through mutual derivations. The original axiomatization by Whitney focused on independent sets and circuits, while subsequent work introduced the closure perspective.^[6] One equivalent definition uses a rank function r: 2^E \to \mathbb{N} \cup \{0\}, where E is the ground set. The function satisfies three axioms: (R1) monotonicity, so X \subseteq Y implies r(X) \leq r(Y); (R2) submodularity, so r(X \cup Y) + r(X \cap Y) \leq r(X) + r(Y) for all X, Y \subseteq E; and (R3) the single-element increment bound, so r(A \cup \{e\}) \leq r(A) + 1 for e \notin A. Additionally, $0 \leq r(X) \leq |X| holds for all X \subseteq E. These properties ensure the rank measures the size of the largest independent subset. Whitney introduced this formulation alongside independent sets.^[6] Another characterization employs a closure operator \mathrm{cl}: 2^E \to 2^E. It must satisfy: (CL1) extensivity, so X \subseteq \mathrm{cl}(X); (CL2) monotonicity, so X \subseteq Y implies \mathrm{cl}(X) \subseteq \mathrm{cl}(Y); (CL3) idempotence, so \mathrm{cl}(\mathrm{cl}(X)) = \mathrm{cl}(X); and (CL4) the exchange property, so if e, f \in E \setminus X and f \in \mathrm{cl}(X \cup \{e\}) \setminus \mathrm{cl}(X), then e \in \mathrm{cl}(X \cup \{f\}). The closure of a set X consists of all elements whose addition does not increase the rank of X. This axiomatization, linking matroids to projective geometry, was developed by Mac Lane.^[7] A third approach defines a matroid via its circuits, the minimal dependent sets forming a collection \mathcal{C} \subseteq 2^E \setminus \{\emptyset\}. The axioms are: (C1) no circuit properly contains another; and (C2) the circuit elimination property, so if C_1, C_2 \in \mathcal{C} are distinct with e \in C_1 \cap C_2, then there exists C_3 \in \mathcal{C} such that C_3 \subseteq (C_1 \cup C_2) \setminus \{e\}. Circuits capture the obstructions to independence, with dependent sets being those containing a circuit. Whitney established this as equivalent to the independent sets axioms.^[6] These characterizations are equivalent, as shown by explicit constructions and verifications of the axioms. Given a collection of independent sets satisfying the standard axioms (I1) the empty set is independent, (I2) subsets of independent sets are independent, and (I3) the augmentation property, the rank function is defined by r(A) = \max \{ |I| : I \subseteq A, I \text{ independent} \}; this satisfies (R1)–(R3) by induction on set sizes and submodularity from augmentation. Conversely, for a rank function, the independent sets are \{ X \subseteq E : r(X) = |X| \}, which verify (I1)–(I3) using monotonicity and the increment bound to ensure augmentation.^[6] The closure operator derives from the rank via \mathrm{cl}(X) = \{ e \in E : r(X \cup \{e\}) = r(X) \}, satisfying (CL1)–(CL4) through submodularity and the exchange property following from rank differences; idempotence holds since adding elements within the closure does not change the rank. In the reverse direction, the rank function is recovered as r(X) = \max \{ |I| : I \subseteq X, I \text{ is independent} \}, where a set I is independent if e \notin \mathrm{cl}(I \setminus \{e\}) for all e \in I, or more directly as the size of a basis of the closure of X. For circuits, they are the minimal nonempty sets C with r(C) < |C|, and the elimination axiom follows from submodularity applied to symmetric differences; conversely, circuits yield independent sets as those avoiding circuits, with augmentation via elimination to extend smaller independents. These mutual derivations confirm full equivalence.^[6]^[7]

Core Concepts

Independent Sets and Circuits

In a matroid M = (E, \mathcal{I}), where E is the finite ground set and \mathcal{I} is the family of independent sets, the independent sets satisfy the hereditary property: if A \in \mathcal{I} and B \subseteq A, then B \in \mathcal{I}.^[8] This downward-closed structure ensures that independence is preserved under taking subsets, mirroring the behavior in linear algebra where subspaces of independent vectors remain independent.^[9] The maximal elements of \mathcal{I} (under inclusion) are called bases of the matroid. A key property, established by the independence augmentation axiom, is that all bases have the same cardinality, denoted r(M) and called the rank of the matroid.^[10] This uniformity implies that the rank function provides a measure of the "dimension" of the matroid, with the size of any basis equal to r(M).^[8] A circuit of the matroid is a minimal dependent set: a nonempty subset C \subseteq E such that C \notin \mathcal{I} but every proper subset of C is in \mathcal{I}.^[9] Circuits represent the fundamental units of dependence, and every dependent set D \subseteq E (i.e., D \notin \mathcal{I}) contains at least one circuit as a subset.^[10] These minimal dependencies act as the obstructions to independence, analogous to linearly dependent relations in vector spaces that cannot be reduced further.^[9] A significant consequence of the matroid axioms is that for any independent set A \in \mathcal{I} and element x \in E \setminus A, the set A \cup \{x\} contains at most one circuit.^[8] When A is a basis B, this circuit is unique and termed the fundamental circuit of x with respect to B, denoted C(x, B); it is the unique minimal dependent subset of B \cup \{x\}.^[10] This uniqueness facilitates the exchange properties central to matroid theory, as originally explored in the axiomatic framework.^[6] A spanning set in a matroid is a subset S \subseteq E whose closure equals the entire ground set, i.e., \mathrm{cl}(S) = E, where the closure \mathrm{cl}(S) is the smallest subset of E containing S that is closed under the matroid's dependence relations (such that adding any further element would not increase the rank).^[8] Spanning sets generalize bases by allowing redundancy while covering the full structure of the matroid.^[9]

Bases and Rank Function

In a matroid M = (E, \mathcal{I}), a basis is a maximal independent set, meaning an independent set B \subseteq E such that no superset of B is independent. All bases of M have the same cardinality, denoted r(M), which is called the rank of the matroid and serves as a measure of its "dimension." This uniformity arises from the exchange property of independent sets: for distinct bases B_1 and B_2, and any e \in B_1 \setminus B_2, there exists f \in B_2 \setminus B_1 such that B_1 - \{e\} \cup \{f\} is also a basis. The rank function r: 2^E \to \mathbb{N} \cup \{0\} of M extends the notion of rank to arbitrary subsets, defined as r(A) = \max \{ |B| : B \subseteq A, B \in \mathcal{I} \} for any A \subseteq E, where |B| is the cardinality of B. Thus, r(E) = r(M), and the rank of any subset A equals the size of a basis for the submatroid induced by A. The rank function satisfies $0 \leq r(A) \leq |A| for all A \subseteq E, reflecting that no independent set exceeds the size of its ambient set. Key properties of the rank function include additivity over disjoint unions: if A \cap B = \emptyset, then r(A \cup B) = r(A) + r(B). This follows from the structure of independence and ensures that the matroid decomposes naturally along disjoint parts of the ground set. The rank function also exhibits submodularity, r(A \cup B) + r(A \cap B) \leq r(A) + r(B), which underpins many matroidal optimization techniques but is not exhaustive here. Circuits in a matroid relate directly to the rank: for any circuit C, the rank r(C) = |C| - 1, since C is minimally dependent and thus spans an independent set of size one less than its cardinality. Consequently, every circuit satisfies |C| \leq r(M) + 1, as r(C) \leq r(M). In particular, parallel elements are pairs e, f \in E such that \{e, f\} forms a circuit of size 2, meaning they are interchangeable in independent sets and represent the simplest form of dependence.

Closure Operators and Flats

In matroid theory, the closure operator \mathrm{cl} on the ground set E assigns to each subset A \subseteq E the smallest flat containing A, equivalently, A union all elements of E that are dependent on A.^[11] This operator satisfies the following axioms: for all X \subseteq E, X \subseteq \mathrm{cl}(X); if X \subseteq Y \subseteq E, then \mathrm{cl}(X) \subseteq \mathrm{cl}(Y); and if X \subseteq E and x, y \in E, then x \in \mathrm{cl}(X \cup \{y\}) \setminus \mathrm{cl}(X) implies y \in \mathrm{cl}(X \cup \{x\}) \setminus \mathrm{cl}(X).^[11] The third axiom embodies the exchange property, ensuring symmetric dependence relations analogous to those in linear algebra.^[11] A key consequence is that if e \in \mathrm{cl}(A), then \mathrm{cl}(A \cup \{e\}) = \mathrm{cl}(A), reflecting the idempotence and extensivity of the operator.^[11] For a flat F, the rank r(F) equals the dimension of F in the geometric sense of the matroid.^[11] Flats are the subsets F \subseteq E such that \mathrm{cl}(F) = F, forming the closed sets under this operator and generalizing subspaces.^[11] The collection of all flats constitutes a lattice ordered by inclusion, where the meet of two flats is their intersection (itself a flat) and the join is the closure of their union.^[11] Principal flats are the closures of singletons, \mathrm{cl}(\{e\}) for e \in E, which play a foundational role in the geometric structure by generating the lattice through iterative applications of the closure.^[11]

Hyperplanes and Graphoids

In matroid theory, a hyperplane is defined as a flat H of the matroid M on ground set E such that the corank r(E) - r(H) = 1, where r denotes the rank function. These hyperplanes represent the maximal proper flats, meaning no larger flat is properly contained within them while maintaining the corank property. They play a fundamental role in the geometry of matroids, analogous to codimension-one subspaces in linear algebra. A key structural property is that every flat in a matroid arises as the intersection of the hyperplanes that contain it. This intersection theorem underscores the generative power of hyperplanes in constructing the lattice of flats, ensuring that the entire flat structure can be recovered from these maximal elements.^[12] For representable matroids, particularly those over the reals, hyperplanes correspond directly to actual hyperplanes in the underlying vector space representation. In this context, the matroid arises from a hyperplane arrangement, where the ground set consists of the hyperplanes (or their defining linear forms), and independence is determined by the linear independence of their normal vectors. Such arrangements encode the combinatorial structure of the matroid, with the intersection lattice of the arrangement mirroring the flat lattice of the matroid.^[13] Matroids also admit an interpretation as models of conditional independence, aligning with the framework of graphoids in probabilistic reasoning. Here, the independence relation is recast as conditional independence I(X; Y \mid Z), meaning that subsets X and Y of the ground set are independent given Z if r(X \cup Y \cup Z) = r(X \cup Z) + r(Y \cup Z) - r(Z). Under this view, matroids satisfy the graphoid axioms, which include: symmetry (I(X; Y \mid Z) \iff I(Y; X \mid Z)); decomposition (I(X; Y \cup W \mid Z) \implies I(X; Y \mid Z) and I(X; W \mid Z)); weak union (I(X; Y \cup W \mid Z) \implies I(X; Y \mid Z \cup W)); and contraction (I(X; Y \mid Z) and I(X; W \mid Z \cup Y) \implies I(X; Y \cup W \mid Z)). This characterization distinguishes matroids from more general semigraphoids, which satisfy only the first four axioms (symmetry, decomposition, weak union, contraction) but may fail the intersection axiom. Matroids enforce the intersection axiom: if I(X; Y \mid Z) and I(X; Y \mid W), then I(X; Y \mid Z \cup W). This additional property captures the precise structure of linear or combinatorial independence, ensuring closure under conditioning in a way that semigraphoids do not.^[14]

Examples

Free and Uniform Matroids

The free matroid on a finite ground set E is the matroid in which every subset of E is independent.^[15] In this structure, the rank function satisfies r(A) = |A| for every subset A \subseteq E, reflecting the absence of any dependence relations among the elements.^[16] The bases of the free matroid are the maximal independent sets, which consist solely of the entire ground set E itself; thus, singletons serve as bases only when |E| = 1.^[17] This matroid exemplifies the extremal case of unrestricted independence, providing a baseline for understanding more constrained matroid structures. Uniform matroids generalize this concept by imposing a uniform size limit on independent sets. The uniform matroid U_{k,n} on a ground set E with |E| = n has independent sets precisely those subsets A \subseteq E satisfying |A| \leq k, assuming $0 \leq k \leq n.^[18] The rank function is then r(A) = \min(|A|, k) for any A \subseteq E, and the bases are all k-element subsets of E when k \leq n.^[19] Notably, the free matroid on E coincides with the uniform matroid U_{n,n}, as the size constraint becomes vacuous.^[15] Uniform matroids exhibit several key properties that highlight their simplicity and symmetry. They are simple matroids, containing neither loops (since singletons are independent for k \geq 1) nor parallel elements (as any two distinct elements form an independent set when k \geq 2).^[18] Additionally, U_{k,n} is self-dual when k = n - k, or equivalently n = 2k, in which case the matroid is isomorphic to its dual.^[20] The class of uniform matroids is closed under taking minors.^[19]

Linear and Representable Matroids

A linear matroid over a field F arises from the column vectors of a matrix A with entries in F; the independent sets of the matroid are precisely the subsets of columns that are linearly independent over F.^[21] The rank of such a matroid equals the rank of the matrix A over F.^[2] A matroid is representable (or linear) over F if it is isomorphic to the linear matroid defined by some matrix over F.^[21] The class of F-representable matroids is characterized by an infinite list of forbidden minors, which are the minor-minimal matroids not representable over F.^[22] Binary matroids are those representable over the finite field \mathrm{GF}(2).^[2] The uniform matroid U_{2,4} of rank 2 on 4 elements is the unique forbidden minor for binary matroids, meaning any matroid with no minor isomorphic to U_{2,4} is binary.^[23] Not all matroids are representable over any field; for example, the non-Pappus matroid of rank 3 on 9 elements is not representable over any field, though details of its structure are discussed elsewhere.^[24] In contrast, all uniform matroids U_{r,n} are representable over any field F with sufficiently large cardinality.^[22]

Graphic and Transversal Matroids

The graphic matroid of a finite undirected graph G = (V, E) is the matroid M(G) with ground set E whose independent sets are the acyclic subsets of edges, that is, the forests in G.^[1] The circuits of M(G) are the cycles of G.^[1] For any subset A \subseteq E, the rank function of M(G) is r(A) = |V| - c(A), where c(A) denotes the number of connected components in the subgraph (V, A).^[25] The cographic matroid of G is the dual of the graphic matroid M(G), with circuits consisting of the bonds of G, which are the minimal edge cutsets.^[1] The independent sets of the cographic matroid are the subsets of E that contain no bond as a subset.^[1] A transversal matroid arises from a bipartite graph G = (U \uplus V, E) with bipartition (U, V) and ground set U; its independent sets are the subsets U' \subseteq U for which there exists a matching in G that covers U'.^[26] Equivalently, these are the partial transversals of the family of neighborhoods \{N(u) \subseteq V \mid u \in U\}.^[27] Transversal matroids are representable over every field.^[28] Graphic matroids are binary, meaning they are representable over the field \mathrm{GF}(2).^[1] Moreover, graphic matroids are regular, as they are representable over every field.^[1] Transversal matroids are also regular.^[28]

Matroids from Combinatorial Structures

Matroids arise naturally from various combinatorial structures beyond linear algebra and graphs, capturing notions of independence in posets, directed graphs, algebraic extensions, geometric lattices, and generalized transversal systems. One prominent example is the partition matroid, where the ground set E is partitioned into disjoint subsets S_1, S_2, \dots, S_k, and a subset I \subseteq E is independent if |I \cap S_i| \leq r_i for prescribed bounds r_i \geq 0 on each part S_i; this structure ensures the independent sets satisfy the matroid axioms, with circuits being sets that exceed the bound in exactly one part.^[19] Such matroids model constraints in scheduling or resource allocation, and the rank function r(X) is the sum of \min(|X \cap S_i|, r_i) over the parts. For instance, if there is a single part (i.e., k=1), the partition matroid reduces to a uniform matroid of rank equal to the bound.^[19] The cycle matroid of a directed graph (digraph) extends the graphic matroid to oriented structures, where the ground set is the arc set A of a digraph D = (V, A), and the circuits are the arc sets of directed cycles in D. A subset C \subseteq A is a circuit if it forms a minimally dependent set corresponding to a directed cycle, meaning every proper subset is acyclic (no directed cycle), and the independent sets are the arc sets inducing no directed cycles (directed forests).^[29] The rank of a subset X \subseteq A equals |V| - c_w(X), where c_w(X) is the number of weakly connected components in the digraph induced by X. This matroid captures dependence in network flows or scheduling with directions, differing from the undirected case by restricting circuits to oriented cycles. Matroids from field extensions, known as algebraic matroids, arise when the ground set E is a finite subset of elements in a field extension L/K of a base field K, with independent sets defined as subsets algebraically independent over K. A subset I \subseteq E is independent if the elements of I satisfy no nontrivial polynomial relation with coefficients in K, generalizing linear independence to algebraic dependence; the rank r(I) of I is the transcendence degree of the subfield K(I) generated by I over K, measuring the "dimension" of the extension.^[30] Flats in this matroid are the intersections of L with the algebraic closures of subfields generated by subsets, providing a closure operator that aligns with algebraic varieties. For example, if E consists of algebraically independent elements over K = \mathbb{Q}, the matroid is uniform of rank |E|; dependencies arise when elements satisfy algebraic equations, such as \sqrt{2} and $2\sqrt{2} being algebraically dependent over \mathbb{Q}.^[30] Geometric lattices provide another combinatorial source for matroids, where the lattice itself is the structure of flats, corresponding to subspaces in projective geometries. A geometric lattice is a finite semimodular lattice in which every element is a join of atoms (rank-1 elements), and for a matroid M, its lattice of flats L(M) forms such a structure when ordered by inclusion, with the rank function preserved.^[11] In projective geometry over a finite field GF(q), the matroid PG(r-1, q) has ground set the 1-dimensional subspaces (points) of a rank-r vector space over GF(q), with flats being the projective subspaces: a flat of rank k corresponds to a (k+1)-dimensional vector subspace, satisfying the modular identity r(X) + r(Y) = r(X \cup Y) + r(X \cap Y) for flats X, Y.^[11] The number of rank-k flats in PG(r-1, q) is given by the Gaussian binomial coefficient \binom{r}{k+1}_q, emphasizing the geometric counting; for instance, in the Fano plane PG(2,2), there are 7 points and 7 lines as rank-2 flats.^[11]

Constructions

Direct Sums and Unions

The direct sum of two matroids M_1 = (E_1, \mathcal{I}_1) and M_2 = (E_2, \mathcal{I}_2), where E_1 and E_2 are disjoint finite sets, is the matroid M_1 \oplus M_2 with ground set E = E_1 \cup E_2 and independent sets \mathcal{I} = \{ I_1 \cup I_2 \mid I_1 \in \mathcal{I}_1, I_2 \in \mathcal{I}_2 \}.^[1] Equivalently, the circuits of M_1 \oplus M_2 are the disjoint union of the circuits of M_1 and M_2.^[1] The rank function of the direct sum satisfies r(A_1 \cup A_2) = r_1(A_1) + r_2(A_2) for subsets A_1 \subseteq E_1 and A_2 \subseteq E_2, reflecting the additive preservation of independence across the disjoint components.^[1] This operation is associative, meaning (M_1 \oplus M_2) \oplus M_3 \cong M_1 \oplus (M_2 \oplus M_3) for matroids M_1, M_2, M_3 with pairwise disjoint ground sets, allowing the extension to finite direct sums of multiple matroids.^[1] The direct sum decomposes a matroid into connected components, where a matroid is connected if it cannot be expressed as a nontrivial direct sum.^[1] Duality is preserved under direct sums, as the dual of M_1 \oplus M_2 is M_1^* \oplus M_2^*.^[31] The parallel connection provides a way to combine matroids by identifying distinguished elements. For matroids M_1 = (E_1, \mathcal{I}_1) and M_2 = (E_2, \mathcal{I}_2) with E_1 \cap E_2 = \emptyset and basepoints p_1 \in E_1, p_2 \in E_2 (neither loops nor coloops in their respective matroids), the parallel connection P((M_1; p_1), (M_2; p_2)) has ground set E = (E_1 \cup E_2) \setminus \{p_1, p_2\} \cup \{p\}, where p is a new element representing the identification of p_1 and p_2.^[20] The circuits consist of the circuits of M_1 / p_1 and M_2 / p_2, together with (C_1 \setminus \{p_1\}) \cup \{p\} for each circuit C_1 of M_1 containing p_1, (C_2 \setminus \{p_2\}) \cup \{p\} for each circuit C_2 of M_2 containing p_2, and (C_1 \setminus \{p_1\}) \cup (C_2 \setminus \{p_2\}) for circuits C_1, C_2 containing p_1, p_2 respectively such that no proper subset is dependent.^[20] The rank of this connection is r_1(M_1) + r_2(M_2) if p lies in a common circuit of both original matroids, and r_1(M_1) + r_2(M_2) - 1 otherwise.^[20] The series connection is analogous but defined dually. For the same setup as the parallel connection, the series connection S((M_1; p_1), (M_2; p_2)) has circuits comprising those of M_1 \setminus p_1 and M_2 \setminus p_2, along with (C_1 \setminus \{p_1\}) \cup (C_2 \setminus \{p_2\}) \cup \{p\} for circuits C_1, C_2 containing p_1, p_2 respectively, where minimality is ensured.^[20] Its rank is r_1(M_1) + r_2(M_2) - 1 if p is in a common circuit of the duals M_1^* and M_2^*, and r_1(M_1) + r_2(M_2) otherwise.^[20] Series connections arise naturally in cographic matroids, mirroring parallel connections in the graphic case due to the duality between graphs and their bond matroids.^[20]

Duality and Minors

In matroid theory, the dual matroid M^* of a matroid M on ground set E is defined such that the bases of M^* are the complements in E of the bases of M. This construction, introduced by Hassler Whitney in 1935, preserves the matroid axioms and ensures that the dual of the dual recovers the original matroid, i.e., (M^*)^* = M.^[32]^[20] The rank function r^* of M^* satisfies r^*(X) = |X| - r(E) + r(E \setminus X) for any subset X \subseteq E, where r is the rank function of M, highlighting how duality interchanges dimensions in the structure.^[33]^[12] Duality extends naturally to subclasses of matroids. For instance, if M is representable over a field F, then so is M^*, with a representing matrix for M^* obtained by transposing and complementing that of M. In graphic matroids, where M(G) arises from the edges of a graph G, the dual M(G)^* corresponds to the cographic matroid M^*(G), whose circuits are the minimal edge cuts of G. Self-dual matroids, where M \cong M^*, include examples like the matroid of the complete graph K_4 and the uniform matroid U_{2,4}.^[12]^[33] A key orthogonality property states that no circuit of M intersects a cocircuit (circuit of M^*) in exactly one element, generalizing incidence relations in vector spaces and graphs.^[20] Minors provide a way to derive simpler matroids from a given one through two fundamental operations: deletion and contraction. The deletion of a subset X \subseteq E, denoted M \setminus X, is the matroid on ground set E \setminus X whose independent sets are those independent in M and contained in E \setminus X; its rank function is r_{M \setminus X}(Y) = r_M(Y) for Y \subseteq E \setminus X. The contraction M / X on E \setminus X has independent sets I \subseteq E \setminus X such that I \cup B is independent in M for some basis B of M|_X, with rank r_{M / X}(Y) = r_M(Y \cup X) - r_M(X). These operations commute and are dual: (M \setminus X)^* = M^* / X and (M / X)^* = M^* \setminus X.^[33]^[20]^[34] A matroid N is a minor of M if N = (M \setminus X) / Y for some disjoint subsets X, Y \subseteq E. This minor relation is transitive and reflexive, forming a partial order on matroids up to isomorphism, and minors preserve representability: if M is F-representable, all its minors are as well. In graphic matroids, minors correspond to graph minors obtained by edge deletions and contractions, linking matroid theory to graph minor theorems. Forbidden minor characterizations, such as those excluding U_{2,4} for binary matroids, rely on this structure to classify matroid classes. Duality interacts with minors by ensuring that the minors of M^* are the duals of the minors of M.^[34]^[20]^[33]

Restrictions and Contractions

In matroid theory, the restriction of a matroid M on ground set E to a subset A \subseteq E, denoted M|A, is the matroid with ground set A whose independent sets are the sets I \cap A where I is independent in M.^[35] The rank function of M|A is the restriction of the rank function of M, so r_{M|A}(X) = r_M(X) for all X \subseteq A.^[35] This operation corresponds to deleting elements outside A while preserving the independence structure within A, and M|A inherits the matroid axioms from M.^[35] The contraction of M by a subset A \subseteq E, denoted M/A, has ground set E \setminus A and independent sets consisting of those J \subseteq E \setminus A such that J \cup B is independent in M for some basis B of A.^[35] Equivalently, the rank function of M/A is given by r_{M/A}(X) = r_M(X \cup A) - r_M(A) for X \subseteq E \setminus A.^[35] Contraction effectively identifies elements in A to a single point while adjusting dependencies, and like restriction, it produces a matroid that preserves key structural properties of M.^[35] Notably, contraction in M corresponds to restriction in the dual matroid M^*.^[35] A minor of M is any matroid obtained by a sequence of restrictions and contractions, such as M|A/B for disjoint subsets A, B \subseteq E, which can be computed as (M|B)|A or (M|A)/B.^[35] The rank of such a minor satisfies r_{M|A/B}(X) = r_M(X \cup B) - r_M(B) for X \subseteq A.^[35] Minors inherit independence from M, meaning the independent sets of a minor are subsets of independent sets in M, which ensures that matroid classes defined by forbidden minors are closed under these operations.^[35] Forbidden minor characterizations provide powerful tools for classifying matroids; for instance, a matroid is binary (representable over \mathrm{GF}(2)) if and only if it has no minor isomorphic to the uniform matroid U_{2,4}.^[36] This single forbidden minor suffices due to the structural constraints imposed by vector spaces over \mathrm{GF}(2), where rank-2 subspaces contain at most three nonzero vectors.^[23] Such characterizations extend to other representability classes, highlighting how restrictions and contractions generate the minor lattice to delineate these properties.^[36]

Properties and Algorithms

Optimization and Greedy Algorithms

One of the key strengths of matroid theory lies in its ability to characterize structures where greedy algorithms optimally solve weighted optimization problems. In a matroid M = (E, \mathcal{I}) equipped with a weight function w: E \to \mathbb{R}, the goal is often to find a basis B \in \mathcal{I} that maximizes the total weight \sum_{e \in B} w(e). The greedy algorithm achieves this by sorting the elements of the ground set E in non-increasing order of weight and iteratively adding an element to the current independent set if it maintains independence. This process yields a maximum-weight basis for any matroid, distinguishing matroids from more general independence systems where the greedy approach may fail.^[37] The correctness of the greedy algorithm relies on the defining axioms of matroids, particularly the augmentation and exchange properties. Suppose the algorithm produces a basis G, and let O be any other basis with higher total weight. By the augmentation property, there exists an element in O \setminus G that can be added to G while remaining independent, but the greedy selection ensures that no such higher-weight element was skipped without violating independence later. More formally, the exchange property guarantees that for any bases B_1 and B_2, and any e \in B_1 \setminus B_2, there exists f \in B_2 \setminus B_1 such that B_1 - e + f is a basis; this implies that the greedy choice cannot be suboptimal, as any deviation would contradict the weight ordering. This proof establishes that the greedy algorithm succeeds if and only if the independence system is a matroid.^[37] Beyond single matroids, optimization extends to the intersection of two matroids M_1 = (E, \mathcal{I}_1) and M_2 = (E, \mathcal{I}_2) on the same ground set, where the objective is to find a maximum-cardinality set I \subseteq E that is independent in both (i.e., I \in \mathcal{I}_1 \cap \mathcal{I}_2). Edmonds developed a polynomial-time algorithm for this problem using augmenting paths, analogous to those in bipartite matching. Starting from an initial common independent set, the algorithm repeatedly searches for an augmenting path in an auxiliary digraph that respects the independence oracles of both matroids, flipping along the path to increase the size of the common independent set until no such path exists. This yields the maximum common independent set and extends naturally to weighted versions via similar path-finding techniques.^[38] The greedy algorithm for a single matroid has time complexity O(n \log n) dominated by the initial sorting of n = |E| elements, assuming independence checks are performed efficiently via an oracle or explicit representation; subsequent additions require O(n) oracle queries in the worst case. For matroid intersection, the augmenting path algorithm runs in polynomial time, typically O(n^3) or better with optimized implementations, depending on the oracle model. A prominent application arises in graphic matroids, where the greedy algorithm corresponds to Kruskal's algorithm for computing a minimum spanning tree in an undirected graph, selecting edges in increasing weight order while avoiding cycles.^[37]^[38]^[39]

Intersection Theorems

In matroid theory, the union of two matroids M_1 = (E, \mathcal{I}_1) and M_2 = (E, \mathcal{I}_2) on the same ground set E, denoted M_1 \vee M_2, has independent sets consisting of those subsets I \subseteq E that can be partitioned as I = I_1 \cup I_2 where I_1 \in \mathcal{I}_1 and I_2 \in \mathcal{I}_2.^[40] The rank function of the union matroid r_{M_1 \vee M_2}(U) for any U \subseteq E is given by

r_{M_1 \vee M_2}(U) = \min_{T \subseteq U} \left[ |U \setminus T| + r_{M_1}(T) + r_{M_2}(T) \right],

which provides a min-max characterization reflecting the minimal covering by elements outside T plus the contributions from each matroid within T.^[40] Rado's theorem characterizes the existence of independent transversals in matroid structures, generalizing Hall's marriage theorem to arbitrary matroids. Specifically, for a matroid M = (E, \mathcal{I}) and a partition of E into subsets X_1, \dots, X_m, there exists a transversal T = \{x_1, \dots, x_m\} with x_i \in X_i that is independent in M if and only if for every subset J \subseteq , the rank satisfies r_M\left( \bigcup_{j \in J} X_j \right) \geq |J|.^[41] This rank-based Hall condition ensures that the substructure induced by any collection of parts admits sufficient independence to select one element per part without violating matroid axioms.^[41] The Nash-Williams theorem provides a matroid-theoretic criterion for decomposing graphs into forests, leveraging the union of graphic matroids. For an undirected graph G = (V, E), the edges can be partitioned into k forests if and only if for every subset U \subseteq V, the number of edges induced by U satisfies |E(U)| \leq k(|U| - 1).^[42] In terms of the cycle matroid M(G) of G, where the rank r_{M(G)}(F) = |V| - c(F) for F \subseteq E with c(F) denoting the number of connected components in the subgraph formed by F, this condition equates to the rank of the union of k copies of M(G) covering E.^[42] Edmonds' matroid intersection theorem establishes a min-max relation for the maximum common independent set in two matroids. For matroids M_1 = (E, \mathcal{I}_1) and M_2 = (E, \mathcal{I}_2), the size of the largest set I \in \mathcal{I}_1 \cap \mathcal{I}_2 equals

\min_{X \subseteq E} \left[ r_{M_1}(X) + r_{M_2}(E \setminus X) \right].

^[43] This theorem highlights the structural duality between common independence and the minimal rank covering across partitions of the ground set, enabling polynomial-time algorithms for finding such maximum intersections.^[43]

Matroid Software and Computation

SageMath provides comprehensive support for computational matroid theory through its built-in matroid classes, enabling the manipulation of linear and graphic matroids with efficient implementations for key operations such as minor deletion, contraction, and rank computation.^[44] Linear matroids are constructed from matrices over various fields, including finite fields, allowing users to verify independence via linear algebra routines, while graphic matroids are derived from Sage's graph structures, supporting cycle matroid extraction and connectivity tests.^[45] These features facilitate research in matroid optimization and structure testing, with rank queries running in time proportional to the matrix size for representable cases.^[44] MatroidDB, developed by Gordon Royle and collaborators, serves as a specialized database of small matroids essential for empirical research and property testing in matroid theory.^[46] It catalogs all matroids up to nine elements—totaling over 100,000 isomorphism classes across ranks—along with larger collections for binary, ternary, and quaternary matroids up to 12 elements, stored in compact formats like rank lines or circuit lists for easy querying.^[47] This resource supports investigations into representability, minors, and enumeration, enabling researchers to generate counterexamples or validate conjectures without exhaustive computation.^[46] Recognition of representable matroids over finite fields typically involves verifying the existence of a matrix representation where the rank of every subset matches the matroid's rank function, checked via determinant non-vanishing tests on submatrices.^[48] For a given finite field \mathbb{F}_q, an algorithm can attempt to construct such a matrix by solving systems ensuring that determinants of independent sets are non-zero and dependent sets have zero rank, though this is in NP and practical only for small instances due to the exponential number of subsets.^[48] Specialized cases, like regular matroids, use Seymour's decomposition theorem for polynomial-time recognition over all fields.^[49] Matroid isomorphism testing often relies on canonical forms to normalize structures for comparison, reducing the problem to checking equivalence under relabeling. For graphic matroids, algorithms reduce to graph isomorphism via tree decompositions and edge colorings with canonical labels of components, achieving polynomial-time solvability for planar cases.^[50] In oriented matroids, canonical labeling assigns unique identifiers to elements based on covector sequences, allowing isomorphism verification by comparing these labels without enumerating automorphisms.^[51] Computational challenges in matroid theory arise from non-constructive proofs, such as those in minor-closed structure theorems, which establish existence of decompositions but provide no efficient algorithms for finding them, limiting practical implementations for large matroids.^[52] For instance, proofs of colorability in matroid intersections guarantee solutions but resist algorithmic adaptation due to their existential nature.^[52] Recent advances in oracle models address these by introducing dynamic oracles that update incrementally during queries, yielding faster algorithms for basis finding and matching in O(m^{1+o(1)}) time, where m is the ground set size.^[53] Additionally, imprecise oracle models combine fast approximate queries with precise verifications to accelerate optimization, reducing clean oracle calls while bounding error.^[54]

Invariants and Generalizations

Polynomial Invariants

Polynomial invariants of matroids provide algebraic encodings of their combinatorial structure, particularly through generating functions that incorporate the rank function and subset properties. These polynomials facilitate the study of matroid isomorphism, connectivity, and enumeration problems by distilling complex rank behaviors into tractable expressions. The characteristic polynomial of a finite matroid M with ground set E and rank function r is defined as

\chi_M(\lambda) = \sum_{A \subseteq E} (-1)^{|A|} \lambda^{r(E) - r(A)}.

This polynomial can equivalently be expressed using the Möbius function \mu on the lattice of flats L(M) of M:

\chi_M(\lambda) = \sum_{F \in L(M)} \mu(\hat{0}, F) \lambda^{r(E) - r(F)}.

The coefficients of \chi_M(\lambda) are given by the Möbius function on the lattice of flats; specifically, the coefficient of \lambda^{r(E) - k} is \sum_{F: r(F)=k} \mu(\hat{0}, F).^[55] The Tutte polynomial of a finite matroid M is a two-variable invariant defined by

T_M(x, y) = \sum_{A \subseteq E} (x-1)^{r(E) - r(A)} (y-1)^{|A| - r(A)}.

It satisfies a deletion-contraction recurrence relation: for an element e \in E that is neither a loop nor a coloop in M, T_M(x, y) = T_{M \setminus e}(x, y) + T_{M / e}(x, y), with appropriate base cases for loops (T = y \cdot T') and coloops (T = x \cdot T''). This recursive structure mirrors the deletion-contraction relations in graph theory and enables efficient computation for small matroids.^[56] Key properties of the Tutte polynomial include its evaluation at specific points to yield combinatorial counts. For a graphic matroid M_G associated with a connected graph G, T_{M_G}(1, 1) equals the number of spanning trees of G. The beta invariant \beta(M) of a non-empty matroid M is given by \beta(M) = (-1)^{r(M)} \sum_{A \subseteq E(M)} (-1)^{|A|} r(A), measuring connectivity; \beta(M) = 0 if and only if M is disconnected or consists of a single loop (for matroids with at least two elements, \beta(M) > 0 if and only if M is connected).^[56]^[57]

Infinite Matroids

An infinite matroid is a combinatorial structure that generalizes finite matroids to allow ground sets of arbitrary cardinality, typically defined via a family of independent sets satisfying the standard axioms (I1)–(I3) along with a finitary condition (I4): every infinite set is independent if and only if all of its finite subsets are independent.^[58] This ensures that circuits—minimal dependent sets—are finite, distinguishing finitary infinite matroids from more general non-finitary variants that permit infinite circuits.^[59] The augmentation axiom (I3) applies only to finite differences in set sizes: if I and J are independent sets with |I| < |J| and this difference is finite, then there exists an element in J \setminus I that can be added to I while preserving independence.^[58] The rank function in an infinite matroid extends the finite case to possibly infinite cardinals. For a subset X \subseteq E, the rank r(X) is the cardinality of a maximum independent subset of X, or equivalently, the supremum of the cardinalities of finite independent subsets of X.^[60] The closure operator \mathrm{cl}(X) is defined analogously: x \in \mathrm{cl}(X) if and only if r(X \cup \{x\}) = r(X), yielding the smallest flat containing X.^[58] These definitions preserve key properties like submodularity of the rank function, though the infinite setting requires careful handling of cardinal arithmetic.^[61] Examples of finitary infinite matroids include the free matroid on an infinite ground set E, where every subset of E is independent, as all finite subsets satisfy the independence axioms and (I4) extends this to infinite subsets.^[60] Another class arises from restrictions of infinite graphs: the finitary cycle matroid of an infinite graph G = (V, E) has ground set E and independent sets as the edge sets of forests in G, with circuits corresponding to finite cycles.^[59] Similarly, the finitary bond (or cocycle) matroid uses finite minimal edge cuts as circuits.^[59] Duality in infinite matroids is well-defined and preserves the structure: the dual of a matroid M = (E, \mathcal{I}) has independent sets as the complements of maximal independent sets (cobases) of M, with rank function r^*(X) = |X| + r(E \setminus X) - r(E), adjusted for cardinals.^[58] However, the dual of a finitary matroid is generally non-finitary, as seen in the dual of the finitary cycle matroid of an infinite graph, whose circuits are the (possibly infinite) bonds.^[59] Minors are obtained via deletion and contraction over subsets, but to maintain finitary properties, these operations are often restricted to finite subsets of the ground set.^[58] A notable property concerns well-foundedness under exchange operations: Bruhn established that certain classes of infinite matroids, such as those arising from infinite graphs, exhibit well-quasi-ordering with respect to the minor relation, preventing infinite descending chains of exchanges and ensuring structural stability.^[62] This extends finite matroid theory by addressing challenges in infinite exchange properties through ordinal-ranked independence.^[63]

Oriented and Binary Matroids

An oriented matroid extends the combinatorial structure of a matroid by incorporating orientation information, modeling signed dependencies in geometric configurations such as point sets, vector arrangements, or hyperplane arrangements.^[64] It axiomatizes the signed circuits of the underlying matroid, where each circuit C is assigned a signing (C^+, C^-) with C^+ \cup C^- = C and C^+ \cap C^- = \emptyset, such that no proper subset of C^+ or C^- is dependent, preserving acyclicity in the positive and negative parts while satisfying composition and elimination axioms.^[64]^[65] These signed circuits encode relative orientations, ensuring that the structure captures topological and combinatorial aspects of oriented geometries without relying on coordinates.^[66] The chirotope of an oriented matroid is a function \chi: \binom{E}{r} \to \{+, -\} defined on the ordered r-tuples forming bases of the underlying matroid, where r is the rank, acting as an alternating orientation map that flips sign under transposition of adjacent elements and satisfies the Grassmann-Plücker relations for consistency across bases.^[64]^[67] This function fully determines the oriented matroid up to reorientation, which involves reversing signs on a subset of elements to yield an isomorphic structure.^[64] The underlying matroid of an oriented matroid is obtained by disregarding the signs, yielding the standard matroid whose independent sets and circuits match the unsigned supports.^[64] Oriented matroids are representable over the reals if they arise from a configuration of real vectors whose signed dependencies match the axioms, though determining realizability is NP-hard.^[64] Deletion and contraction operations extend those of matroids to the oriented setting by restricting or quotienting the sign assignments while preserving the circuit axioms.^[64] Binary matroids form the class of matroids representable over the finite field \mathrm{GF}(2), where elements correspond to columns of a matrix A over \mathrm{GF}(2), and a set is independent if the corresponding columns are linearly independent.^[23] They are precisely the matroids with no minor isomorphic to the uniform matroid U_{2,4}, which consists of four elements with rank two and any two elements independent.^[23]^[68] This forbidden minor characterization, established by Tutte, ensures that binary matroids close under minors and direct sums.^[23] The rank function of a binary matroid M on ground set E is given by r(S) = \rho(A_S), where A_S is the submatrix with columns indexed by S and \rho denotes the rank over \mathrm{GF}(2).^[69] Binary matroids include graphic matroids as a subclass, where the matroid of a graph's cycle space over \mathrm{GF}(2) has circuits corresponding to the graph's cycles, with rank |E| - |V| + c for c connected components.^[69] Binary matroids are linear matroids restricted to representations over \mathrm{GF}(2).^[68]

History and Applications

Historical Development

Matroid theory originated in 1935 with Hassler Whitney's and independently Takeo Nakasawa's introduction of abstract dependence structures to unify concepts from linear algebra and graph theory, as detailed in Whitney's paper "On the abstract properties of linear dependence."^[19]^[1] Whitney defined matroids through axioms capturing independence, closure, and rank, drawing parallels between linear varieties over fields and the cycle spaces of graphs.^[70] In the 1950s, W. T. Tutte advanced the field by developing the structural theory of graphic matroids, including a characterization of binary matroids representable over GF(2) in 1958.^[71] Tutte also introduced the Tutte polynomial in 1954 as a generating function for graphs, which was later generalized to arbitrary matroids as a key invariant.^[72] Concurrently, in the early 1960s, Jack Edmonds established foundational results in combinatorial optimization, proving that the greedy algorithm optimally solves the maximum-weight independent set problem for matroids.^[71] The 1940s saw Richard Rado's pioneering work on transversal matroids, generalizing Hall's marriage theorem to matroid independence in a 1942 paper.^[70] Building on this, the 1960s and 1970s brought characterizations of representability over finite fields, such as Tutte's binary case and the early 1970s characterization of ternary matroids (representable over GF(3)) by R. E. Reid, published by Bixby in 1979.^[73] From the 1980s onward, matroid theory expanded to infinite structures, with early explorations of infinite dependence by Brualdi in works on bases and exchange properties, followed by Wheeler's contributions to infinite combinatorial structures.^[60] Computational aspects gained prominence, including algorithms for matroid recognition and intersection, alongside deepening connections to hyperplane arrangements for studying realizability.^[74] Post-2000 developments include applications in theoretical computer science, such as the matroid secretary problem introduced by Babaioff, Immorlica, Kleinberg, and Slivkins in 2007, which extends online selection to matroid constraints.^[75]

Key Contributors

Hassler Whitney laid the foundations of matroid theory in his 1935 paper "On the Abstract Properties of Linear Dependence," where he introduced the abstract concept of linear dependence to unify properties observed in vector spaces and graphs.^[6] This work defined matroids through independent sets and established key axioms that capture the essence of dependence without reference to a specific underlying structure.^[6] W. T. Tutte advanced matroid theory in the 1950s by exploring connections between matroids and graph theory, particularly through enumeration techniques and structural characterizations.^[76] In his 1959 paper "Matroids and Graphs," Tutte provided a characterization of graphic matroids using excluded minors, bridging combinatorial enumeration with matroidal properties of graphs. His contributions also included early developments in the Tutte polynomial, which enumerates spanning trees and other graph invariants extendable to matroids.^[76] Jack Edmonds made pivotal contributions to matroid optimization in the 1960s, developing algorithms that exploit matroid structure for efficient solutions to combinatorial problems.^[77] In his 1965 paper "Matroid Partition," he introduced the matroid partition problem and proved that it can be solved using a greedy algorithm when weights satisfy certain conditions, laying groundwork for broader optimization techniques.^[78] Edmonds also formulated the matroid intersection theorem in the late 1960s, showing that the maximum common independent set of two matroids can be found via a polynomial-time algorithm, which has profound implications for network flows and matching problems.^[79] Gian-Carlo Rota revitalized matroid theory in the 1970s by integrating it with lattice theory and invariant methods from algebraic combinatorics.^[80] Co-authoring the 1970 book On the Foundations of Combinatorial Theory: Combinatorial Geometries with Henry Crapo, Rota developed the geometric lattice perspective on matroids, emphasizing their role in enumerative combinatorics and representation theory. His series of papers starting in 1964, including works on binomial enumeration and mobius functions over lattices, introduced invariants like the characteristic polynomial that quantify matroid structures and their symmetries. In more recent decades, James Oxley has been a leading figure through his comprehensive textbook Matroid Theory (second edition, 2011), which synthesizes decades of developments and serves as a standard reference for advanced study in the field. Federico Ardila has contributed significantly to the combinatorial aspects of matroids, notably in his 2013 ICM address "Matroid Theory, Old and New," where he explored connections to polytopes, tropical geometry, and inequalities for matroid structures.^[81] Ardila's work, including the 2006 exposition "The Geometry of Matroids," highlights applications in algebraic combinatorics and Lagrangian formulations.^[82] Rudi Pendavingh has advanced algorithmic aspects, particularly in counting and representing matroids; his 2013 paper "On the Number of Matroids" provides tight bounds and compression algorithms for enumerating matroids on n elements, improving prior estimates exponentially.^[83] Pendavingh's research also includes efficient methods for matroid representations over partial fields, enhancing computational tractability.^[84]

Applications in Optimization and Beyond

Matroids play a central role in combinatorial optimization, particularly through their connection to greedy algorithms that efficiently solve problems like finding minimum spanning trees (MSTs). In graphic matroids, where independent sets correspond to forests in an undirected graph, Kruskal's algorithm selects edges in increasing weight order while maintaining acyclicity, guaranteeing an optimal MST.^[85] This approach extends the greedy paradigm to matroids in general, enabling optimal solutions for weighted basis selection.^[86] Beyond MSTs, matroid partitioning addresses scheduling problems, such as assigning tasks to machines under capacity constraints modeled as partition matroids, where the goal is to partition elements into bases of multiple matroids to maximize total weight. Algorithms for optimal matroid partitioning, solvable in polynomial time via matroid intersection techniques, find applications in resource allocation and load balancing.^[87] In statistics, matroids underpin graphical models by formalizing conditional independence (CI) structures through graphoids, which are axiomatic systems capturing separation properties in probabilistic distributions. Semigraphoids, a subclass of graphoids, align closely with matroid axioms, allowing CI statements like "X is independent of Y given Z" to be represented as independence in a matroid derived from the model's joint distribution.^[14] This connection facilitates efficient inference in Bayesian networks and Markov random fields, where matroid minors help characterize embeddability of CI structures into graphs, aiding model selection and structure learning from data.^[14] Theoretical computer science leverages matroids in online algorithms, notably the matroid secretary problem, where elements arrive in random order and an algorithm must irrevocably select a maximum-weight independent set. Constant-competitive algorithms exist for special cases like partition and graphic matroids, while an O(log k)-competitive algorithm applies generally, with k the matroid rank; the conjecture for O(1)-competitiveness remains open.^[75]^[88] Matroids also appear in learning theory, where rank queries reveal the structure of an unknown matroid, enabling algorithms to learn partitions or bases with poly(log n) queries in query-complexity models.^[89] Emerging work in property testing explores sublinear algorithms to verify matroid properties like uniformity or representability over finite fields, though 2020s results remain sparse compared to graph testing.^[90] In database theory, acyclic conjunctive queries correspond to graphic matroids, where the query hypergraph's acyclicity ensures efficient evaluation via join trees, avoiding exponential blowup in result size. Yannakakis' algorithm exploits this structure to compute query outputs in linear time relative to input size, modeling joins as forest edges in the matroid.^[73] This matroidal view optimizes query planning in relational databases, particularly for tree-structured schemas. Recent extensions to quantum matroids generalize classical structures to quantum settings, defining independence via ranked posets satisfying quantum-inspired axioms like the Rota upper bound. These hypothetical constructs explore quantum automorphism groups, where permutations preserving bases extend to non-commutative operations, with potential applications in quantum error correction and cryptography.^[91]^[92]

References

[1]
[PDF] Briefly, what is a matroid? - LSU Math
In 1935, Hassler Whitney published a paper [18] entitled “On the abstract ... We defined a matroid to be regular if it is representable over all fields.
[2]
[PDF] Lecture 8: Matroids
Oct 8, 2009 · We defined matroids in terms of axioms for their independent sets, but we could also have defined them in terms of axioms for their bases, ...
[3]
Matroids: The Value of Abstraction - American Mathematical Society
The person generally credited with beginning the theory of matroids was Hassler Whitney (1907-1989). Whitney was a towering figure in American mathematics.
[4]
[PDF] Lecture 10 1 Matroid Optimization
Oct 20, 2009 · Many combinatorial optimization ... The following important examples illustrate some of the applications of the matroid intersection theorem.Missing: mathematics | Show results with:mathematics
[5]
[PDF] oxley-matroids.pdf - Cornell: Computer Science
The hereditary property, ( I 2) , means that a matroid is uniquely determined by its collection of maximal independent sets, which are called bases , or by its ...
[6]
on the abstract properties of linear dependence.1 - jstor
us call a system obeying (a) and (b) a " matroid." The present paper is devoted to a study of the elementary properties of matroids. The fundamental.Missing: pdf | Show results with:pdf
[7]
some interpretations of abstract linear dependence in terms of ... - jstor
Whitney, " On the abstract properties of linear dependence," American Journal of Mathematics, vol. 57 (1935), pp. 509-533. 236. Page 2. SOME INTERPRETATIONS ...
[8]
[PDF] 1 Matroids and their properties
A matroid is a pair M = (E,I), where E is a finite set and I is a nonempty family of subsets of E satisfying the conditions.
[9]
[PDF] Matroids - Brown Math Department
Apr 22, 2020 · The independent subsets of E are defined to be those which are linearly independent. In other words 1Vil is an independent set if, whenever we ...<|control11|><|separator|>
[10]
[PDF] MATROIDS
We call this the Independent Augmentation Axiom – IAA. Matroid independence is a generalisation of linear independence in vector spaces. Only Examples 2,4 and ...
[11]
[PDF] Matroid Theory, Second Edition, James Oxley
The main ideas in Chapter 1 are that matroids can be axiomatized in many equivalent ways and that the two fundamental classes of examples of matroids arise ...
[12]
Duality | Matroid Theory | Oxford Academic
One of the most attractive features of matroid theory is the existence of a theory of duality. This theory, which was introduced by Whitney (1935), ...<|separator|>
[13]
[PDF] An Introduction to Hyperplane Arrangements - UPenn CIS
We now come to the primary connection between hyperplane arrangements and matroid theory. If H is a hyperplane, write nH for some (nonzero) normal vector to H.Missing: representable | Show results with:representable
[14]
Conditional independence structures examined via minors
The notion of minor from matroid theory is adapted to examination of classes of conditional independence structures. For the classes of semigraphoids, ...
[15]
[PDF] 5. Matroid optimization 5.1 Definition of a Matroid
Apr 20, 2017 · A free matroid is one in which all sets are independent; it is Un,n. • Another is a partition matroid in which E is partitioned into ...
[16]
[PDF] Matroids
Such matroids are called cardinality matroids. If k = \E\, the matroid is called a free matroid. If. E = ∪Ei where Ei are disjoint, and T = {F : F = ∪Fi ...
[17]
[PDF] Matroids - Computer Science
If S n then Uns is called the free matroid on S. The n x n identity matrix is a matrix representation of the free matroid over any field F. For notational ...
[18]
[PDF] TROPICAL SCHEME THEORY 3. Matroids Matroids take “It's useful ...
Definition 3.1. A matroid on E is a collection I ⊂ 2E of independent sets satisfying (I1) ∅∈I, (I2) If S ∈ I and S0 ⊂ S then S0 ∈ I, and (I3) If S, T ∈ I and | ...
[19]
[PDF] What is a matroid? - LSU Math
Matroids were introduced to capture dependence in linear algebra and graph theory, and arise in combinatorial optimization. They are related to a matrix.
[20]
[PDF] Chapter 2 Dual Matroids and Minors
If I(M) = I(M∗), then M is an identically self- dual matroid. For example, the uniform matroid Ur,2r is an identically self-dual matroid, The matroid R8 ( see ( ...
[21]
[PDF] Matroids
Def: For a field F, a matroid M is repre- sentable over F if it is isomorphic to a linear matroid with matrix A and linear indepen- dence taken over F. Example: ...
[22]
[PDF] Chapter 4 Representations over a Field
This chapter discusses F-representable matroids, their properties, and methods of construction, including characterizations of binary and ternary matroids.
[23]
[PDF] U2,4–The only forbidden minor for binary matroids - Drexel University
Sep 23, 2014 · If M is a matroid on S and T Ç S, a matroid M/ on T is called a minor of M if M/ is obtained by any combination of deletion (<) and contraction.
[24]
[PDF] Chapter 6 Representability of matroids
Another example of a matroid that is not representable is the non-Pappus ... The non-Pappus matroid is not representable over any field. Page 4. 66. CHAPTER ...
[25]
[PDF] What is a Matroid? - Harvard Mathematics Department
After a lot of painful checking, we find that the M we defined above is actually a matroid. This matroid has another name: the uniform matroid U2,4. The 4 ...
[26]
Linear representation of transversal matroids and gammoids ...
May 24, 2020 · Let G = ( U ⊎ V , E ) be a bipartite graph, the transversal matroid M G on the ground set U has the following family of independent sets: U ′ ⊆ ...
[27]
Transversal matroids and Hall's theorem - MSP
It is then clear that a matroid M on a set X is a transversal matroid provided there is a bipartite graph (X, Δ, Y) such that M consists of those subsets of X.
[28]
[PDF] An Introduction to Transversal Matroids - Semantic Scholar
Geometrically, a (transversal) matroid is fundamental iff it has a simplex representation that has at least one element at each vertex. Each transversal matroid ...
[29]
[PDF] arXiv:2010.08988v1 [math.CO] 18 Oct 2020
Oct 18, 2020 · Note that the directed circuits of an oriented graphic matroid are exactly the edge-sets of the directed cycles of the corresponding digraph D.
[30]
[PDF] Algebraic Matroids in Applications - UC Berkeley
Algebraic matroids are combinatorial objects defined by the set of coordinates of an algebraic variety. These objects are of interest whenever coordinates ...
[31]
[PDF] DISCRETE POLYMATROIDS
The discrete poly- matroid is a multiset analogue of the matroid, closely related to the integral polymatroids. This paper is organized as follows. In Section 1 ...
[32]
https://graal.ens-lyon.fr/~abenoit/algo09/matroids.pdf
[33]
[PDF] On the Abstract Properties of Linear Dependence - GRAAL
Author(s): Hassler Whitney. Source: American Journal of Mathematics, Vol. 57, No. 3 (Jul., 1935), pp. 509-533. Published by: The Johns Hopkins University ...Missing: theory | Show results with:theory
[34]
[PDF] Chapter 2 Duality and minors
in the dual matroid: the matroid M/T obtained by contracting T is the matroid ... dependent set of. M∗(G). We now show that in general, it is not true that ...
[35]
Minors | Matroid Theory - Oxford Academic
This chapter begins by introducing the operation of contraction as the dual of the operation of deletion. It then derives a definition of contraction that does ...
[36]
[PDF] Restriction and Contraction of Matroids Theorem
(c) Restriction and contraction of matroids correspond to deletion and contraction. of edges in graphs, in the following sense. If M is the circuit matroid of ...
[37]
[PDF] The excluded minors for the matroids that are binary or ternary
The binary matroids and the ternary matroids are well known to have, respectively, one excluded minor and four excluded minors. In this case, the union of two ...
[38]
Matroids and the greedy algorithm
MATROIDS AND THE GREEDY ALGORITHM *. Jack EDMONDS. National Bureau of Standards, Washington, D.C., U.S.A. and. University of Waterloo, Ontario, Canada. Linear ...
[39]
Matroid intersection algorithms | Mathematical Programming
In this paper three matroid intersection algorithms are presented. One algorithm computes an intersection containing a maximum number of elements.
[40]
[PDF] On the Shortest Spanning Subtree of a Graph ... - Utah State University
384-409. HEBREW UNIVERSITY. ON THE SHORTEST SPANNING SUBTREE OF A GRAPH. AND THE TRAVELING SALESMAN PROBLEM. JOSEPH B. KRUSKAL, JR. Several years ago a ...
[41]
[PDF] Lecture 13 1 Matroid Union
Oct 29, 2009 · There are two main ways for checking if a given set is independent in the matroid union. ... From the rank function of a matroid union, we know ...
[42]
[PDF] 1 Applications of Matroid Intersection - Stanford CS Theory
Feb 16, 2017 · For the extension axiom, suppose we have I,J ∈ I with. |J| > |I|. So we can find I0,J0 ∈ I0 with f(I0) = I,f(J0) = J, and we might as well ...Missing: semigraphoid | Show results with:semigraphoid
[43]
[PDF] 1 Matroid Union
Apr 6, 2010 · Algorithmic results for M follow from an independence oracle or rank oracle for M. Recall that a set I ∈ I is independent in M iff I an be ...
[44]
[PDF] Lecture 10 — Matroid intersection - Stanford CS Theory
For matroids M1 = (E,I1) and M2 = (E,I2), define the matroid intersection polytope P(M1 ∩ M2) = conv{χI | I ∈ I1 ∩ I2}. Theorem 4 (Edmonds). P(M1 ∩ M2) ...
[45]
The abstract Matroid class - SageMath Documentation
Matroids are combinatorial structures that capture the abstract properties of (linear/algebraic/...) dependence.
[46]
Linear matroids - Matroid Theory - SageMath Documentation
A binary matroid is a linear matroid represented over the finite field with two elements. See LinearMatroid for a definition.
[47]
[PDF] Constructing and Using Databases of Small Matroids - SymOmega
Nov 29, 2010 · To make the database more than mildly useful, it is essential to capture the minor relationship between matroids, rather than just properties of ...Missing: MatroidDB | Show results with:MatroidDB
[48]
[math/0702316] Matroids with nine elements - arXiv
Feb 12, 2007 · We describe the computation of a catalogue containing all matroids with up to nine elements, and present some fundamental data arising from this cataogue.
[49]
[PDF] Representing Matroids over the Reals is ∃R-complete
Jul 11, 2024 · The presented verification algorithm shows that F-representability is in NP for each finite field F. A matrix over F as witness and the ...
[50]
Recent work in matroid representation theory - ScienceDirect.com
Crucially, Seymour's decomposition leads to a polynomial time algorithm for recognising a regular matroid. It is natural to ask if there are analogues of ...Missing: determinants | Show results with:determinants
[51]
[PDF] On the Complexity of Matroid Isomorphism Problem - arXiv
Nov 24, 2008 · Using this, we are able to show that graphic matroid isomorphism testing for planar graphs can be done in deterministic polynomial time.
[52]
Checking oriented matroid isomorphism by means of canonical ...
In this paper a method for establishing the structural equivalence of sets of planar geometric features composed by points and lines is presented.
[53]
[PDF] Efficiently Coloring the Intersection of a General Matroid and ... - arXiv
Aug 26, 2025 · However, most of the proofs of these results are nonconstructive, in that they are not readily adaptable to yield polynomial-time coloring ...
[54]
[2302.09796] Fast Algorithms via Dynamic-Oracle Matroids - arXiv
Feb 20, 2023 · We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic ...Missing: advances | Show results with:advances
[55]
Accelerating Matroid Optimization through Fast Imprecise Oracles
Feb 5, 2024 · We additionally equip algorithms with a fast but dirty oracle modelling an unknown, potentially different matroid. We design and analyze ...Missing: advances | Show results with:advances
[56]
[PDF] Combinatorial Geometries
In Crapo and Rota (1970) this is the definition ofr(X) and it is proved that this gives a rank function of a geometry on ( ~ ). Exercises. 6.1. Verify that ...
[57]
The Tutte polynomial
When calcu- lated for a graph, this generating function, properly called the Tutte polynomial, reveals more of the internal structure of the graph than is ...
[58]
[PDF] Convexity and the Beta Invariant - Webbox
If M is a matroid, then β(M) is a non-negative integer which gives information about whether M is connected and whether M is the matroid of a series-parallel ...
[59]
[PDF] Axioms for infinite matroids - arXiv
Feb 23, 2013 · We propose five equivalent sets of matroid axioms, in terms of independent sets, bases, circuits, closure and rank, that make duality possible.
[60]
[PDF] Infinite matroids in graphs - Uni Ulm
Abstract. It has recently been shown that infinite matroids can be axiomatized in a way that is very similar to finite matroids and permits duality.Missing: seminal | Show results with:seminal
[61]
[PDF] Infinite matroids - LSU Math
Circuit axioms for independence spaces. An independence space M(S) is a set S together with a collection of subsets (called circuits) such that C satisfies ( ...
[62]
[PDF] Axioms for infinite matroids - Universität Hamburg
We propose five equivalent sets of matroid axioms, in terms of independent sets, bases, circuits, closure and rank, that make duality possible. They will allow.Missing: seminal | Show results with:seminal
[63]
[PDF] Infinite Matroids
Dec 15, 2014 · The dual of U2,E, for example, cannot be finitary for any infinite set ... Williams [53] proved that infinite trees are well-quasi-ordered.
[64]
Mathematisches Forschungsinstitut Oberwolfach Graph Theory
... matroids are well-quasi-ordered as minors appears to be nearing completion. There is now a theory of infinite matroids that admits duality and is based on ...
[65]
[PDF] 6 ORIENTED MATROIDS - CSUN
Direct sum: An oriented matroid M = (E, L) has a direct sum decomposi- tion, denoted by M = M(E1)⊕M(E2), if E has a partition into nonempty sub- sets E1 ...
[66]
[PDF] Oriented Matroids : introduction - Université de Montpellier
Oriented matroids use signed sets (X+, X-) and circuits, which follow specific axioms. All matroid notions are also considered as oriented matroid notions.
[67]
[PDF] Oriented Matroids Today - The Electronic Journal of Combinatorics
Apr 15, 2024 · Oriented matroids model geometric situations, generalizing objects like point and vector configurations, and hyperplane arrangements.
[68]
[PDF] Basis orientations and Chirotopes of Oriented Matroids - Ethz
A basis orientation is a map from bases to {+,−} that is alternating, and for every basis B and e, f, χ(B:e→f) = Xe · Xf · χ(B) where X is a fundamental ...
[69]
[PDF] representations of matroids and the excluded minor theorems
In particular, we show that a matroid is binary if and only if it has no minor isomorphic to U2,4. We also give several additional characterizations of binary ...
[70]
[PDF] Chapter 6 Binary Matroid
Binary matroids can be characterized in many different way. Quite a few of the characterizations are expressed in terms of properties of circuits.
[71]
[PDF] The Coming of the Matroids - University of Waterloo
Whitney. Matroid theory starts with the paper [22] of Hassler Whitney in 1935. A matroid may be defined to be a family of “independent” subsets of a finite.
[72]
[PDF] Matroid Decomposition - D-MATH
In 1935, H. Whitney realized the mathematical importance of an abstrac- tion of linear dependence. His pioneering paper (Whitney (1935)) contains a number ...<|control11|><|separator|>
[73]
Introduction The Tutte polynomial of a matroid - EMS Press
introduced by W.T. Tutte in 1954 for graphs — is a self-dual form of the generating function for cardinality and rank in.
[74]
[PDF] 1 Lecture 10 Graphic Matroids
Definition 1 The Fano matroid is the matroid with ground set S = {A, B, C, D, E, F, G} whose bases are all subsets of S of size 3 except {A, D, B}, {B,E,C}, {A ...
[75]
[PDF] Lectures on matroids and oriented matroids
S. Mac Lane (1938) - abstract algebraic independence give matroids. • J. Edmonds and D.R. Fulkerson (1965) - partial matchings give matroids.
[76]
[PDF] Matroids, Secretary Problems, and Online Mechanisms
The matroid secretary problem involves selecting elements from a matroid in random order, where the selected elements must form an independent set, to maximize ...Missing: 2000 | Show results with:2000
[77]
[PDF] The contributions of W.T. Tutte to matroid theory - LSU Math
The last theorem was proved in two papers in the Transactions of the American. Mathematical Society called A homotopy theorem for matroids I, II. In a 1959 ...<|control11|><|separator|>
[78]
Jack Edmonds - INFORMS.org
During the 1960's, while working at the National Bureau of Standards, Edmonds explored the relationship between matroids and optimization. His beautiful theory ...
[79]
(PDF) Matroid Partition - ResearchGate
PDF | This article, “Matroid Partition”, which first appeared in the book edited by George Dantzig and Pete Veinott, is important to me for many.Missing: 1960s | Show results with:1960s
[80]
On matroid parity and matching polytopes - ScienceDirect.com
Sep 30, 2020 · In the late 1960s, Jack Edmonds proved that two important combinatorial optimization problems, the matching and matroid intersection ...
[81]
[PDF] The Contributions of Dominic Welsh to Matroid Theory - LSU Math
Oxley, Matroid Theory, Oxford University Press, New York, 1992. [52] J. G. Oxley and D. J. A. Welsh, The Tutte polynomial and percolation, Graph Theory and ...
[82]
[PDF] matroid theory, old and new - Federico Ardila
The theory of matroids or combinatorial geometries originated in linear algebra and graph theory, and has deep connections with many other areas, ...
[83]
[PDF] The geometry of matroids - Federico Ardila
A matroid (M = (E, I)) has a set E and independent subsets I. The geometric approach to matroid theory has grown deeper.
[84]
On the number of matroids - SIAM.org
Dec 18, 2013 · We consider the problem of determining mn, the number of matroids on n elements. The best known lower bound on mn is due to Knuth (1974) who ...
[85]
https://jeffe.cs.illinois.edu/teaching/algorithms/notes/E-matroids.pdf
[86]
[PDF] Matroids | Jeff Erickson
Many problems that can be correctly solved by greedy algorithms can be described in terms of an abstract combinatorial object called a matroid.
[87]
[PDF] Networks and Combinatorial Optimization
Kruskal's algorithm computes an MST. Proof. In fact, we will use the same ... Such matroids are called graphic matroids. We can also describe the rank ...
[88]
[PDF] Optimal Matroid Partitioning Problems - DROPS
These matroid partitioning problems are natural to study, and have many applications in various areas such as scheduling and combinatorial optimization. We.
[89]
Matroid Secretary Problems | Journal of the ACM
In this problem, the elements of a matroid are presented to an online algorithm in uniformly random order. When an element arrives, the algorithm observes its ...
[90]
Learning Partitions Using Rank Queries - DROPS - Schloss Dagstuhl
Dec 5, 2024 · We consider the problem of learning an unknown partition of an n element universe using rank queries. Such queries take as input a subset of the ...
[91]
[PDF] Query complexity of matroids ?
Our main technical result is that the Fourier spectrum of matroidal Boolean functions is dense. Theorem 1. If M is a bridgeless matroid on ground set [n] then.
[92]
[2312.13464] Quantum automorphisms of matroids - arXiv
Dec 20, 2023 · We define and study quantum automorphism groups of matroids. A key feature of quantum groups is that there are many quantizations of a classical group.
[93]
Quantum Matroids - Project Euclid
We define a quantum matroid to be any finite nonempty poset P P satisfying the conditions R, SL, M, AU below. R: P P is ranked.