Check the two matroid axioms directly

Heredity: every subset of an independent set is independent. Exchange: if \(|A| < |B|\) with both independent, some element of \(B \setminus A\) can be added to \(A\) keeping it independent.

Usage

morie_is_matroid(ground, independent)

Arguments

ground

Integer vector of ground-set elements.

independent

List of integer vectors.

Value

A list with is_matroid, hereditary, exchange, heredity_violation, exchange_violation, warnings.

Details

Both are checked exhaustively and the first violating pair is returned, because "not a matroid" without a witness is not a useful answer.

References

Whitney H (1935) Amer J Math 57(3):509-533.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
morie_is_matroid(V, V)
#> $is_matroid
#> [1] FALSE
#> 
#> $hereditary
#> [1] FALSE
#> 
#> $exchange
#> NULL
#> 
#> $heredity_violation
#> [1] "the empty set is not independent"
#> 
#> $exchange_violation
#> NULL
#> 
#> $n_independent
#> [1] 8
#> 
#> $n
#> [1] 8
#> 
#> $warnings
#> [1] "the empty set is not independent"
#> 
#> $method
#> [1] "Matroid structure and greedy optimality"
#>