Struct Matroid 

pub struct Matroid {
    pub ground_set_size: usize,
    pub bases: BTreeSet<BTreeSet<usize>>,
    pub rank: usize,
}

A matroid on a ground set {0, …, n-1}.

Represented by its collection of bases, which must satisfy the basis exchange axiom: for any two bases B₁, B₂ and any x ∈ B₁ \ B₂, there exists y ∈ B₂ \ B₁ such that (B₁ \ {x}) ∪ {y} is a basis.

Fields

ground_set_size: usize

Size of the ground set

bases: BTreeSet<BTreeSet<usize>>

Collection of bases (each a k-element subset)

rank: usize

Rank of the matroid (common size of all bases)

Implementations

impl Matroid

pub fn uniform(k: usize, n: usize) -> Self

Create the uniform matroid U_{k,n}: all k-subsets of [n] are bases.

Contract

requires: k <= n
ensures: result.bases.len() == C(n, k)
ensures: result.rank == k

pub fn from_bases( n: usize, bases: BTreeSet<BTreeSet<usize>>, ) -> Result<Self, String>

Create a matroid from an explicit collection of bases.

Validates the basis exchange axiom.

Contract

requires: all bases have the same cardinality
requires: basis exchange axiom holds
ensures: result.rank == bases[0].len()

pub fn from_plucker( k: usize, n: usize, coords: &[f64], tolerance: f64, ) -> Result<Self, String>

Create a matroid from Plücker coordinates.

The matroid is defined by the nonvanishing pattern of the Plücker coordinates: a k-subset I is a basis iff p_I ≠ 0 (within tolerance).

Contract

requires: coords.len() == C(n, k)
ensures: result represents the matroid of the point in Gr(k,n)

pub fn rank_of(&self, subset: &BTreeSet<usize>) -> usize

Rank of a subset S: max |B ∩ S| over all bases B.

Contract

ensures: result <= self.rank
ensures: result <= subset.len()

pub fn circuits(&self) -> BTreeSet<BTreeSet<usize>>

Compute all circuits (minimal dependent sets).

A circuit is a minimal subset C such that rank(C) < |C|.

Contract

ensures: forall C in result. rank_of(C) < |C|
ensures: forall C in result. forall e in C. rank_of(C \ {e}) == |C| - 1

pub fn dual(&self) -> Self

Dual matroid: bases are complements of original bases.

Contract

ensures: result.rank == self.ground_set_size - self.rank
ensures: result.bases.len() == self.bases.len()

pub fn direct_sum(&self, other: &Matroid) -> Self

Direct sum of two matroids (disjoint union of ground sets).

Contract

ensures: result.rank == self.rank + other.rank
ensures: result.ground_set_size == self.ground_set_size + other.ground_set_size

pub fn matroid_union(&self, other: &Matroid) -> Self

Matroid union: bases are maximal sets in B₁ ∨ B₂.

This is NOT the same as the direct sum — it uses the same ground set. A set I is independent in M₁ ∨ M₂ iff I = I₁ ∪ I₂ where I_j is independent in M_j. The rank is min(|E|, r₁ + r₂).

Contract

requires: self.ground_set_size == other.ground_set_size
ensures: result.rank <= self.rank + other.rank
ensures: result.ground_set_size == self.ground_set_size

pub fn is_loop(&self, e: usize) -> bool

Check if an element is a loop (in no basis).

Contract

ensures: result == !exists B in bases. e in B

pub fn is_coloop(&self, e: usize) -> bool

Check if an element is a coloop (in every basis).

Contract

ensures: result == forall B in bases. e in B

pub fn delete(&self, e: usize) -> Self

Delete element e: restrict to ground set \ {e}.

Contract

requires: e < self.ground_set_size
ensures: result.ground_set_size == self.ground_set_size - 1

pub fn contract(&self, e: usize) -> Self

Contract element e: bases containing e, with e removed.

Contract

requires: e < self.ground_set_size
ensures: result.ground_set_size == self.ground_set_size - 1
ensures: result.rank == self.rank - 1 (when e is not a loop)

pub fn tutte_polynomial(&self) -> BTreeMap<(usize, usize), i64>

Compute the Tutte polynomial T_M(x, y) via deletion-contraction.

Returns coefficients as a map (i, j) -> coefficient of x^i y^j.

Contract

ensures: T_M(1, 1) == number of bases
ensures: T_M(2, 1) == number of independent sets

pub fn intersection_cardinality(&self, other: &Matroid) -> usize

Matroid intersection cardinality via Edmonds’ augmenting path algorithm.

Finds the maximum cardinality common independent set of two matroids on the same ground set.

Contract

requires: self.ground_set_size == other.ground_set_size
ensures: result <= min(self.rank, other.rank)

pub fn schubert_matroid( partition: &[usize], k: usize, n: usize, ) -> Result<Self, String>

Schubert matroid: the matroid associated with a Schubert cell in Gr(k, n).

For a partition λ fitting in the k × (n-k) box, the Schubert matroid has bases corresponding to k-subsets I such that i_j ≤ λ_j + j (where λ is padded to length k).

Contract

requires: partition fits in k × (n-k) box
ensures: result is a valid matroid

impl Matroid

Combinatorial extensions for matroid theory.

pub fn characteristic_polynomial(&self) -> Vec<i64>

Characteristic polynomial χ_M(q) = Σ_{A ⊆ E} (−1)^|A| · q^(r − rank(A)).

Returns coefficients [c_0, c_1, …, c_r] where χ_M(q) = Σ cᵢ · q^i.

pub fn characteristic_polynomial_eval(&self, q: i64) -> i64

Evaluate the characteristic polynomial at an integer q.

pub fn beta_invariant(&self) -> i64

Beta invariant β(M) = (−1)^r · χ’_M(1).

pub fn closure(&self, subset: &BTreeSet<usize>) -> BTreeSet<usize>

Closure operator: cl(A) = smallest flat containing A.

pub fn is_flat(&self, subset: &BTreeSet<usize>) -> bool

Check if a subset is a flat.

pub fn flats(&self) -> Vec<Vec<BTreeSet<usize>>>

Lattice of flats grouped by rank: flats[i] = all flats of rank i.

pub fn mobius_values(&self) -> BTreeMap<BTreeSet<usize>, i64>

Möbius function μ(∅, F) for each flat F.

pub fn is_connected(&self) -> bool

Check if the matroid is connected (no direct sum decomposition).

pub fn connected_components(&self) -> Vec<Matroid>

Connected components of the matroid.

pub fn f_vector(&self) -> Vec<u64>

f-vector: f_i = number of independent sets of size i.

pub fn h_vector(&self) -> Vec<i64>

h-vector derived from f-vector.

h_i = Σ_j (-1)^{i-j} C(r-j, i-j) f_j

pub fn whitney_numbers_first_kind(&self) -> Vec<u64>

Whitney numbers of the first kind: |coefficient of q^i in χ_M(q)|.

pub fn whitney_numbers_second_kind(&self) -> Vec<u64>

Whitney numbers of the second kind: W_i = number of flats of rank i.

pub fn restrict(&self, subset: &BTreeSet<usize>) -> Matroid

Restriction M|A: matroid on subset A with inherited independence.

pub fn contraction_deletion(&self, e: usize) -> (Matroid, Matroid)

Contraction-deletion pair: returns (M/e, M\e).

pub fn has_excluded_minor(&self, name: &str) -> bool

Check for a specific excluded minor by name.

Supported: “U24” (uniform 2,4), “F7” (Fano), “F7*” (dual Fano).

Trait Implementations

impl Clone for Matroid

fn clone(&self) -> Matroid

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Matroid

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq for Matroid

fn eq(&self, other: &Matroid) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for Matroid

impl StructuralPartialEq for Matroid