newPackage("Matroids", AuxiliaryFiles => true, Version => "0.9.7", Date => "August 28, 2018", Authors => {{ Name => "Justin Chen", Email => "jchen@math.berkeley.edu", HomePage => "https://math.berkeley.edu/~jchen"}}, Headline => "a package for computations with matroids", HomePage => "https://github.com/jchen419/Matroids-M2", PackageExports => {"Graphs", "Posets"}, DebuggingMode => false ) export { "Matroid", "matroid", "ParallelEdges", "Loops", "groundSet", "indicesOf", "bases", "nonbases", "circuits", "fundamentalCircuit", "loops", "coloops", "isDependent", "closure", "hyperplanes", "flats", "latticeOfFlats", "restriction", "deletion", "contraction", "minor", "hasMinor", "relaxation", "representationOf", "quickIsomorphismTest", "getIsos", "tutteEvaluate", "chromaticPolynomial", "simpleMatroid", "uniformMatroid", "affineGeometry", "projectiveGeometry", "getCycles", "basisIndicatorMatrix", "maxWeightBasis", "idealChowRing", "cogeneratorChowRing", "specificMatroid", "allMatroids" } Matroid = new Type of HashTable Matroid.synonym = "matroid" globalAssignment Matroid net Matroid := M -> ( net ofClass class M | " of rank " | toString(M.rank) | " on " | toString(#M.groundSet) | " elements" ) Matroid == Matroid := (M, N) -> set bases M === set bases N and M.groundSet === N.groundSet matroid = method(Options => {EntryMode => "bases", ParallelEdges => {}, Loops => {}}) matroid (List, List) := Matroid => opts -> (E, L) -> ( if #L > 0 and not instance(L#0, Set) then L = indicesOf(E, L); G := set(0..<#E); B := if opts.EntryMode == "nonbases" then if #L == 0 then {G} else subsets(G, #(L#0)) - set L else if opts.EntryMode == "bases" then if #L == 0 then error "There must be at least one basis" else L else if opts.EntryMode == "circuits" then ( x := getSymbol "x"; R := QQ(monoid [x_0..x_(#E-1)]); I := monomialIdeal({0_R} | L/(c -> product(c/(i -> R_i)))); allVars := product gens R; (dual I)_* / (g -> set indices(allVars//g)) ); M := new Matroid from { symbol groundSet => G, symbol bases => B, symbol rank => #(B#0), cache => new CacheTable }; if opts.EntryMode == "circuits" then ( M.cache.ideal = I; M.cache.circuits = L; ) else if opts.EntryMode == "nonbases" then M.cache.nonbases = L; M.cache.groundSet = E; M.cache.rankFunction = new MutableHashTable; M ) matroid List := Matroid => opts -> B -> matroid(unique flatten B, B, opts) matroid Matrix := Matroid => opts -> A -> ( k := rank A; matroid(apply(numcols A, i -> matrix A_i), (select(subsets(numcols A, k), S -> rank A_S == k))/set) ) matroid Graph := Matroid => opts -> G -> ( P := opts.ParallelEdges; L := opts.Loops/(v -> set{v}); e := #edges G; E := hashTable apply(e, i -> (edges G)#i => i); C := getCycles G/(c -> set apply(#c-1, i -> E#(set{c#i, c#(i+1)}))); for i from 0 to #P - 1 do ( C = C | select(C, c -> member(E#(P#i), c))/(c -> c - set{E#(P#i)} + set{e+i}) | {set{E#(P#i), e + i}}; ); matroid(edges G | P | L, C | apply(#L, i -> set{e + #P + i}), EntryMode => "circuits") ) matroid (List, MonomialIdeal) := Matroid => opts -> (E, I) -> ( allVars := product gens ring I; M := matroid(E, (dual I)_* / (g -> set indices(allVars//g))); M.cache.ideal = I; M ) matroid Ideal := Matroid => opts -> I -> ( J := if instance(I, MonomialIdeal) then I else monomialIdeal I; -- The following is ~2x faster than isSquareFree if (J == I and isSubset(set flatten flatten(J_*/exponents), set{0,1})) then matroid(gens ring J, J) else error "Expected a squarefree monomial ideal" ) ideal Matroid := MonomialIdeal => M -> ( -- Stanley-Reisner ideal of independence complex if not M.cache.?ideal then ( x := getSymbol "x"; R := QQ(monoid [x_0..x_(#M.groundSet - 1)]); M.cache.ideal = dual monomialIdeal({0_R} | apply(bases M, b -> product(toList(M.groundSet - b) /(i -> R_i)))) ); M.cache.ideal ) isWellDefined Matroid := Boolean => M -> ( K := keys M; expectedKeys := set { symbol groundSet, symbol bases, symbol rank, symbol cache }; if set K =!= expectedKeys then ( if debugLevel > 0 then ( added := toList(K - expectedKeys); missing := toList(expectedKeys - K); if #added > 0 then << "-- unexpected key(s): " << toString added << endl; if #missing > 0 then << "-- missing keys(s): " << toString missing << endl; ); return false ); if not M.groundSet === set(0..<#M.groundSet) then ( if debugLevel > 0 then << "-- expected groundSet to be a set of integers" << endl; return false ); if not (instance(M.bases, List) and all(bases M, b -> instance(b, Set) and isSubset(b, M.groundSet))) then ( if debugLevel > 0 then << "-- expected bases to be a list of subsets of groundSet" << endl; return false ); if not all(M.bases, b -> #b === M.rank) then ( if debugLevel > 0 then << "-- expected rank to be the size of all bases" << endl; return false ); -- circuit elimination I := ideal dual M; if numgens ideal M < numgens I then I = ideal M; R := ring I; J := ideal flatten apply(subsets(I_*, 2), p -> (indices gcd(p#0,p#1))/(i -> p#0*p#1//(R_i^2))); numgens J == 0 or isSubset(J, I) ) Matroid _ ZZ := (M, i) -> M.cache.groundSet#i Matroid _ List := (M, S) -> (M.cache.groundSet)_S Matroid _ Set := (M, S) -> (M.cache.groundSet)_(keys S) Matroid _* := M -> M.cache.groundSet indicesOf = method() indicesOf (List, List) := List => (E, L) -> ( H := hashTable apply(#E, i -> E_i => i); L/(l -> set(l/(i -> H#i))) ) indicesOf (Matroid, List) := List => (M, L) -> ( if #L == 0 then return {}; if not M.cache.?indices then M.cache.indices = hashTable apply(#M.groundSet, i -> M_i => i); if not M.cache.indices#?(L#0) then ( if debugLevel > 0 then ( print("Warning: " | toString(L#0) | " is not a member of " | toString(M_*)); print("Treating " | toString(L#0) | " as an index (cf. 'help groundSet' for how to input subsets) ..."); ); L ) else L/(l -> M.cache.indices#l) ) bases = method() bases Matroid := List => M -> M.bases nonbases = method() nonbases Matroid := List => M -> ( if not M.cache.?nonbases then M.cache.nonbases = subsets(M.groundSet, rank M) - set M.bases; M.cache.nonbases ) circuits = method() circuits Matroid := List => M -> ( if not M.cache.?circuits then M.cache.circuits = (ideal M)_*/indices/set; M.cache.circuits ) fundamentalCircuit = method() fundamentalCircuit (Matroid, List, Thing) := Set => (M, I, e) -> fundamentalCircuit(M, set indicesOf(M, I), (indicesOf(M, {e}))#0) fundamentalCircuit (Matroid, Set, ZZ) := Set => (M, I, e) -> ( J := I + set{e}; for c in circuits M do if isSubset(c, J) then return c; error("Expected " | toString J | " to be dependent"); ) loops = method() loops Matroid := List => M -> toList(M.groundSet - flatten(bases M / toList)) coloops = method() coloops Matroid := List => M -> loops dual M independentSets Matroid := List => opts -> M -> unique flatten((bases M)/subsets) independentSets (Matroid, ZZ) := List => opts -> (M, r) -> unique flatten(bases M/(b -> subsets(b, r))) isDependent = method() isDependent (Matroid, List) := Boolean => (M, S) -> isDependent(M, set indicesOf(M, S)) isDependent (Matroid, Set) := Boolean => (M, S) -> ( if #S > rank M then return true; I := ideal M; product(S/(i -> (ring I)_i)) % I == 0 ) rank Matroid := ZZ => M -> M.rank rank (Matroid, List) := ZZ => (M, S) -> rank(M, set indicesOf(M, S)) rank (Matroid, Set) := ZZ => (M, S) -> ( if not M.cache.rankFunction#?S then ( currentRank := 0; if #bases M > 100 then ( I := ideal M; R := ring I; currentRank = dim (map((coefficientRing R)(monoid [(gens R)_(keys S)]), R))(I); ) else ( maxRank := min(#S, rank M); for b in bases M do ( currentRank = max(currentRank, #(b*S)); if currentRank == maxRank then return currentRank; ); ); M.cache.rankFunction#S = currentRank; ); M.cache.rankFunction#S ) closure = method() closure (Matroid, List) := List => (M, S) -> toList closure(M, set indicesOf(M, S)) closure (Matroid, Set) := Set => (M, S) -> ( r := rank(M, S); if r == rank M then return M.groundSet; limits := set{}; for s in toList(M.groundSet - S) do ( if r == rank(M, S + set{s}) then limits = limits + set{s}; ); S + limits ) hyperplanes = method() hyperplanes Matroid := List => M -> ( if not M.cache.?hyperplanes then M.cache.hyperplanes = (circuits dual M)/(c -> M.groundSet - c); M.cache.hyperplanes ) flats = method() flats (Matroid, ZZ) := List => (M, r) -> ( -- returns flats of rank r if r > rank M or r < 0 then return {}; if r == rank M then return {M.groundSet}; if r == 0 then return {set loops M}; if r == rank M - 1 then return hyperplanes M; unique (select(subsets(M.groundSet, r), s -> rank_M s == r)/closure_M) ) flats Matroid := List => M -> ( if not M.cache.?flats then ( H := hyperplanes M; flatList := H; numFlatsFound := 0; while numFlatsFound < #flatList do ( numFlatsFound = #flatList; flatList = unique flatten apply(flatList, F -> apply(H, h -> h*F)); ); M.cache.flats = append(sort(flatList, f -> #f), M.groundSet); ); M.cache.flats ) latticeOfFlats = method() latticeOfFlats Matroid := Poset => M -> poset(flats M/toList, (a, b) -> isSubset(a, b)) fVector Matroid := HashTable => M -> hashTable pairs tally(flats M/rank_M) dual Matroid := Matroid => {} >> opts -> M -> ( if not M.cache.?dual then ( D := matroid(M_*, (bases M)/(b -> M.groundSet - b)); D.cache.dual = M; M.cache.dual = D; ); M.cache.dual ) restriction = method() restriction (Matroid, List) := Matroid => (M, S) -> restriction(M, set indicesOf(M, S)) restriction (Matroid, Set) := Matroid => (M, S) -> ( -- assumes S is a subset of M.groundSet (not M_*) S0 := sort keys S; if #bases M > 100 then ( I := ideal M; R := ring I; return matroid(M_S0, monomialIdeal (map((coefficientRing R)(monoid [(gens R)_(S0)]), R))(I)); ); B := bases M/(b -> S*b); r := max sizes B; matroid(M_S0, indicesOf(S0, unique select(B, b -> #b == r) /toList)) ) Matroid | Set := (M, S) -> restriction(M, S) Matroid | List := (M, S) -> restriction(M, S) deletion = method() deletion (Matroid, List) := Matroid => (M, S) -> deletion(M, set indicesOf(M, S)) deletion (Matroid, Set) := Matroid => (M, S) -> restriction(M, M.groundSet - S) Matroid \ Set := (M, S) -> deletion(M, S) Matroid \ List := (M, S) -> deletion(M, S) contraction = method() contraction (Matroid, List) := Matroid => (M, S) -> contraction(M, set indicesOf(M, S)) contraction (Matroid, Set) := Matroid => (M, S) -> if #S == 0 then M else dual(deletion(dual M, S)) Matroid / Set := (M, S) -> contraction(M, S) Matroid / List := (M, S) -> contraction(M, S) minor = method() minor (Matroid, List, List) := Matroid => (M, X, Y) -> minor(M, set indicesOf(M, X), set indicesOf(M, Y)) minor (Matroid, Set, Set) := Matroid => (M, X, Y) -> ( if #(X*Y) > 0 then error "Expected disjoint sets"; N := M / X; N \ set((toList Y)/(y -> position(N_*, e -> M_y === e))) ) hasMinor = method() hasMinor (Matroid, Matroid) := Boolean => (M, N) -> ( n := #N.groundSet; m := #M.groundSet; if n > m or #bases N > #bases M then return false; for X in independentSets(M, rank M - rank N) do ( MX := M / X; for Y in independentSets(dual MX, m - n - rank M + rank N) do ( if areIsomorphic(N, MX \ Y) then ( if debugLevel > 0 then print("Contract "|toString X|", delete "|toString (Y/(y -> y + #select(toList X, x -> x <= y)))); return true; ); ); ); false ) Matroid + Matroid := (M, N) -> ( (E, B2) := (M_*, bases N); if not(E === N_*) then ( if #set(M_*) < #(M_*) or #set(N_*) < #(N_*) then error "Cannot have duplicate elements in M or N - cf. ``help (symbol +, Matroid, Matroid)\" for details"; E = unique(M_* | N_*); phi := hashTable apply(#N.groundSet, i -> i => position(E, e -> e === N_i)); B2 = bases N/(b -> b/(i -> phi#i)); ); H := partition(b -> #b, unique flatten table(bases M, B2, (b,c) -> b+c)); matroid(E, H#(max keys H)) ) Matroid ++ Matroid := (M, N) -> ( n := #M.groundSet; B := bases N/(b -> b/(i -> i + n)); E1 := (M_*)/(e -> (e, 0)); E2 := (N_*)/(e -> (e, 1)); matroid(E1 | E2, unique flatten table(bases M, B, (b, c) -> b + c)) ) getComponentsRecursive = method() getComponentsRecursive (List, List) := List => (S, C) -> ( if #S == 0 then return {} else if #(set S*set flatten(C/toList)) == 0 then return subsets(S, 1); comp0 := select(S, s -> any(C, c -> isSubset(set{s, S#0}, c))); C = select(C, c -> #(c*set comp0) == 0); join({comp0}, getComponentsRecursive(toList(set S - comp0), C)) ) components Matroid := List => M -> ( singles := join(loops M, coloops M); join(subsets(singles, 1), getComponentsRecursive(toList(M.groundSet - singles), circuits M))/set/restriction_M ) relaxation = method() relaxation (Matroid, List) := Matroid => (M, S) -> relaxation(M, set indicesOf(M, S)) relaxation (Matroid, Set) := Matroid => (M, S) -> ( if member(S, circuits M) and member(S, hyperplanes M) then matroid(M_*, append(bases M, S)) else error "Expected circuit-hyperplane" ) representationOf = method() representationOf Matroid := Thing => M -> ( if instance(M_0, Matrix) then transpose matrix((M_*)/(v -> flatten entries v)) else if all(M_*, c -> instance(c, Set) and #c <= 2) then ( graph(join(M_*, (flatten(select(M_*, c -> #c == 1)/toList))/(v -> {v,v}))) ) else error "No representation found" ) -- Recursively finds all permutations inducing a bijection on circuits (note: permutations(10) is already slow on a typical machine) getIsos = method() getIsos (Matroid, Matroid) := List => (M, N) -> ( (C, D, e) := (sort(circuits M, c -> #c), circuits N, #M.groundSet); if not tally sizes C === tally sizes D then return {}; if #C == 0 then return permutations e; local possibles, local c0, local shiftedIndices, local d1, local B, local candidate; possibles = {}; if e > 5 then ( c0 = toList C#0; shiftedIndices = apply(e, i -> i - #select(c0, j -> j < i)); for d0 in select(D, d -> #d == #c0)/toList do ( d1 = sort keys(N.groundSet - d0); B = apply(permutations d0, q -> hashTable apply(#q, i -> c0#i => q#i)); possibles = possibles | flatten apply(getIsos(M \ set c0, N \ set d0), p -> ( flatten apply(B, q -> ( candidate = apply(e, i -> if member(i, c0) then q#i else (d1)#(p#(shiftedIndices#i))); if all(C, c -> member(c/(i -> candidate#i), D)) then {candidate} else {} )) )); ); return possibles; ) else return select(permutations(e), p -> all(C, c -> member(c/(i -> p#i), D))); ) isomorphism (Matroid, Matroid) := HashTable => (M, N) -> ( -- assumes (M, N) satisfy "Could be isomorphic" by quickIsomorphismTest local coloopStore, local C, local D, local e, local C1, local c0slice; local coverCircuits, local H, local candidates, local extraElts, local F, local E; coloopStore = (M, N)/coloops/sort; -- sort is crucial! if #(coloopStore#0) > 0 then (M, N) = (M \ (coloopStore#0), N \ (coloopStore#1)); -- (M, N) are now both unions of circuits (C, D, e) = (sort(circuits M, c -> #c), circuits N, #M.groundSet); if #C == 0 then return hashTable pack(2, mingle coloopStore); C1 = C; c0slice = sliceBySize(C1#0, C1); coverCircuits = {(last values c0slice)#0} | while c0slice#?0 list ( C1 = sort(first values c0slice, c -> #c); c0slice = sliceBySize(C1#0, C1); (last values c0slice)#0 ); -- creates maximal list of disjoint circuits in M, covering as much of M.groundSet as possible H = apply(coverCircuits, c -> (c, select(D, d -> #d == #c and (pairs sliceBySize(c, C))/last/sizes/tally === (pairs sliceBySize(d, D))/last/sizes/tally))); -- creates list of ordered pairs: first element is member of coverCircuits, second element is list of circuits in N which have the same "intersection size pattern" as the first element if min sizes(H/last) == 0 then return; candidates = {H}; for i to #coverCircuits-1 do ( candidates = flatten apply(candidates, cand -> apply(#last(cand#i), j -> ( append(cand_{0.. (S#0, select(S#1, s -> #(s*((last(cand#i))#j)) == 0))) ))) ); -- "de-nests" second-element lists of H (i.e. each list member becomes its own item, but keeping only those which are disjoint from previously matched circuits of N extraElts = M.groundSet - flatten(coverCircuits/toList); E = flatten(append(coverCircuits, extraElts)/keys/sort); if #extraElts > 0 then candidates = apply(candidates, cand -> cand | {(extraElts, N.groundSet - flatten(cand/last/toList))}); for cand in candidates do ( for f in fold((a,b) -> flatten table(a,b,identity), cand/last/keys/permutations) /deepSplice/join do ( F = hashTable apply(e, i -> E#i => f#i); if all(C, c -> member(c/(i -> F#i), D)) then return ( if #(coloopStore#0) == 0 then F else ( F = pairs F; for i to #(coloopStore#0)-1 do F = apply(F, p -> (p#0 + (if p#0 >= coloopStore#0#i then 1 else 0), p#1 + (if p#1 >= coloopStore#1#i then 1 else 0))); hashTable(pack(2, mingle coloopStore) | F) ) ); ); ); ) quickIsomorphismTest = method() quickIsomorphismTest (Matroid, Matroid) := String => (M, N) -> ( (r, b, c, e) := (rank M, #bases M, #circuits M, #M.groundSet); if not (r == rank N and b == #bases N and c == #circuits N and e == #N.groundSet) then return "false"; if M == N then ( if debugLevel > 0 then print "Matroids are equal"; return "true" ); if min(b, c, binomial(e, r) - b) <= 1 then ( if debugLevel > 0 then print "At most 1 basis/nonbasis/circuit"; return "true" ); idealList := (M,N)/(m -> (m, dual m)/ideal); if idealList#0/res/betti === idealList#1/res/betti then "Could be isomorphic" else "false" ) areIsomorphic (Matroid, Matroid) := Boolean => (M, N) -> ( testResult := quickIsomorphismTest(M, N); if testResult == "Could be isomorphic" then not(isomorphism(M, N) === null) else value testResult ) tuttePolynomial Matroid := RingElement => M -> ( if not M.cache.?tuttePolynomial then M.cache.tuttePolynomial = tuttePolynomial(M, ZZ(monoid(["x","y"]/getSymbol))); M.cache.tuttePolynomial ) tuttePolynomial (Matroid, Ring) := RingElement => (M, R) -> ( a := coloops M; b := loops M; if #a + #b == #M.groundSet then R_0^#a*R_1^#b else ( c := set{(keys((bases M)#0 - a))#0}; tuttePolynomial(M \ c, R) + tuttePolynomial(M / c, R) ) ) tutteEvaluate = method() tutteEvaluate (Matroid, Thing, Thing) := Thing => (M, a, b) -> ( T := tuttePolynomial M; sub(T, {(ring T)_0 => a, (ring T)_1 => b}) ) characteristicPolynomial Matroid := RingElement => opts -> M -> ( T := tuttePolynomial M; R := ZZ(monoid([getSymbol "x"])); (map(R, ring T, {1 - R_0, 0}))((-1)^(rank M)*T) ) chromaticPolynomial = method() chromaticPolynomial Graph := RingElement => G -> ( P := characteristicPolynomial matroid G; (ring P)_0^(#connectedComponents G)*P ) isSimple Matroid := Boolean => M -> min sizes circuits M > 2 simpleMatroid = method() simpleMatroid Matroid := Matroid => M -> M \ set(select((ideal M)_*, m -> first degree m <= 2)/indices/last) uniformMatroid = method() uniformMatroid (ZZ, ZZ) := Matroid => (k, n) -> ( if 0 <= k and k <= n then matroid(toList(0.. (n, p) -> matroid affineMatrix(n, p) affineMatrix = (n, p) -> sub(transpose matrix toList((prepend(1,n:0)..prepend(1,n:p-1))/toList), ZZ/p) projectiveGeometry = method() projectiveGeometry (ZZ, ZZ) := Matroid => (n, p) -> matroid projectiveMatrix(n, p) projectiveMatrix = (n, p) -> ( if n == 0 then return matrix{{1_(ZZ/p)}}; affineMatrix(n, p) | (matrix{toList((p^n-1)//(p-1):0_(ZZ/p))} || projectiveMatrix(n-1, p)) ) getCycles = method() getCycles Graph := List => G -> ( if not isConnected G then return flatten((connectedComponents G)/(c -> getCycles inducedSubgraph(G, c))); G = graph edges G; -- removes loops if #edges G < #G.vertexSet then return {}; -- G is a tree possibleVertices := select(G.vertexSet, v -> #neighbors(G, v) > 1); if #possibleVertices < #G.vertexSet then G = inducedSubgraph(G, possibleVertices); cycles := {}; while #G.vertexSet > 2 do ( cycles = join(cycles, select(getClosedWalks(G, G.vertexSet#0, #G.vertexSet), p -> p#1 < p#(#p - 2))); G = deleteVertices(G, {G.vertexSet#0}); ); cycles ) getClosedWalks = method() getClosedWalks (Graph, Thing, ZZ) := List => (G, v, l) -> ( -- Returns walks at v of length <= l N := toList(neighbors(G, v)); paths := N/(n -> {v, n}); walks := {}; for i from 2 to l - 1 do ( paths = flatten(paths/(p -> (toList(neighbors(G, last p) - set{v} - set p))/(n -> append(p, n)))); walks = join(walks, (select(paths, p -> member(last p, N)))/(w -> append(w, v))); ); walks ) basisIndicatorMatrix = method() basisIndicatorMatrix Matroid := Matrix => M -> ( initVector := toList M.groundSet; transpose matrix(bases M/(b -> initVector/(i -> if member(i, b) then 1 else 0))) ) independenceComplex Matroid := SimplicialComplex => M -> simplicialComplex ideal M maxWeightBasis = method() maxWeightBasis (Matroid, List) := Set => (M, w) -> ( maxWeightSol := set{}; W := (rsort apply(#w, i -> (w#i, i)))/last; while not member(maxWeightSol, bases M) do ( for i from 0 to #W-1 do ( augmentedSol := maxWeightSol + set{W#i}; if not isDependent(M, augmentedSol) then ( maxWeightSol = augmentedSol; W = W_(delete(i, toList(0..<#W))); break; ); ); ); maxWeightSol ) idealChowRing = method() idealChowRing Matroid := Ideal => M -> ( x := symbol x; -- use symbol rather than getSymbol, in order to work with indices internally F := delete({}, delete(M.groundSet, flats M)/toList); R := QQ[F/(f -> x_f)]; I2 := ideal(select(subsets(F, 2), s -> #unique(s#0 | s#1) > max(#(s#0), #(s#1)))/(p -> x_(p#0)*x_(p#1))); L0 := sum(select(F, f -> member(0, f))/(f -> x_f)); I2 + ideal((1..#M.groundSet - 1)/(i -> sum(select(F, f -> member(i, f))/(f -> x_f)) - L0)) ) cogeneratorChowRing = method() cogeneratorChowRing Matroid := RingElement => M -> ( -- sorted flats makes this method 3x faster t := getSymbol "t"; I := trim idealChowRing M; R := ring I; W := R[apply(gens R, v -> t_(last baseName v))]; sub(value (factor((sum(#gens R, i -> W_i*R_i))^(rank M - 1) % sub(I, W)))#1, QQ[gens W]) ) specificMatroid = method() specificMatroid String := Matroid => name -> ( if name == "fano" then ( projectiveGeometry(2, 2) ) else if name == "nonfano" then ( relaxation(specificMatroid "fano", set{1,3,4}) ) else if name == "V8+" then ( matroid(toList(0..7), {{0,1,2,3},{0,3,4,5},{1,2,4,5},{0,3,6,7},{1,2,6,7},{4,5,6,7}}/set, EntryMode => "nonbases") ) else if name == "vamos" then ( relaxation(specificMatroid "V8+", set{4,5,6,7}) ) else if name == "pappus" then ( matroid(toList(0..8), {{0,1,2},{0,3,7},{0,4,8},{1,3,6},{1,5,8},{2,4,6},{2,5,7},{6,7,8}}/set, EntryMode => "nonbases") ) else if name == "nonpappus" then ( relaxation(specificMatroid "pappus", set{6,7,8}) ) else if name == "AG32" then ( affineGeometry(3, 2) ) else if name == "R10" then ( matroid(id_((ZZ/2)^5) | matrix{{-1_(ZZ/2),1,0,0,1},{1,-1,1,0,0},{0,1,-1,1,0},{0,0,1,-1,1},{1,0,0,1,-1}}) ) else error "Name string must be one of: fano, nonfano, V8+, vamos, pappus, nonpappus, AG32, R10" ) allMatroids = method() allMatroids ZZ := List => n -> ( if n > 8 then error "Can only return all matroids on <= 8 elements"; if n == 1 then return {uniformMatroid(0, 1), uniformMatroid(1, 1)}; startedReading := false; E := toList(0.. p | "Matroids/SmallMatroids.txt"), p -> fileExists p)) list ( if startedReading then ( if #l == 0 then break else if #l > binomial(n, r) then ( r = r + 1; PE := reverse sort subsets(set E, r); ); matroid(E, PE_(positions(characters l, c -> c === "*"))) ) else if l == ("-- " | n | " elements") then (startedReading = true;) ); matroidList = {uniformMatroid(0, n)} | delete(null, matroidList); L := toList(0..#matroidList - #select(matroidList, M -> 2*rank M == n) - 1); matroidList | (matroidList_L / dual)_(rsort L) ) -- Miscellaneous general purpose helper functions -- sorts L by values of f (note: L should not involve sequences at all, due to deepSplice) sort (List, Function) := opts -> (L, f) -> ( H := hashTable(identity, apply(L, l -> f(l) => l)); deepSplice join apply(sort keys H, k -> H#k) ) sizes = L -> L/(l -> #l) sliceBySize = (s, L) -> partition(l -> #(l*s), L) -- intersects a set against a list of sets, and records sizes beginDocumentation() -- Documentation -- -- < "circuits") M = matroid(B) M = matroid(A) M = matroid(G) M = matroid(I) Inputs E:List a ground set B:List a list of bases C:List a list of circuits A:Matrix whose column vectors form the ground set G:Graph whose edges form the ground set I:Ideal a squarefree monomial ideal defining the independence complex Outputs M:Matroid Description Text The default representation of a matroid in this package is by its ground set and list of bases. Example M = matroid({a,b,c,d}, {{a,b},{a,c}}) peek M Text One can create a matroid by specifying its @TO circuits@ or @TO nonbases@ instead, using the option @TO2{[matroid, EntryMode], "EntryMode"}@. Regardless of the value of EntryMode, the bases are automatically computed in the process of creation. Example M = matroid({a,b,c,d},{}, EntryMode => "nonbases") -- defaults to uniform matroid of full rank peek M N = matroid({a,b,c,d}, {{b,c}}, EntryMode => "circuits") peek N Text If no ground set is provided, the ground set is taken to be the union of the basis/nonbasis/circuit elements. Example M = matroid {{a,b},{a,c}} peek M Text If a matrix is provided, then the realizable matroid on the columns of the matrix is returned. The ground set consists of columns of the matrix, and independence is determined by the method @TO rank@ (to allow flexibility over general rings). Example M = matroid random(ZZ^3, ZZ^5) peek M Text If a graph is provided, then the graphic matroid is returned. The ground set consists of edges in the graph, and circuits are precisely the (minimal) cycles in the graph. Example M = matroid completeGraph 3 peek M Text One can use the optional arguments Loops and ParallelEdges to specify loops and parallel edges for the graph, respectively. These options are intended only for use with graphic matroids (since the Graphs package does not provide functionality for loops or parallel edges). ParallelEdges should be given as a list of edges (which are two-element sets of the form set$\{i,j\}$ where i, j are vertices in G), and Loops should be given as a list of vertices where the loops are based. Example M = matroid(completeGraph 3, ParallelEdges => {set{0,1},set{0,1},set{1,2}}, Loops => {0,2}) peek M circuits M Text If a squarefree monomial ideal is provided, corresponding to a simplicial complex Δ via the Stanley-Reisner correspondence, then the matroid with @TO2{(independenceComplex, Matroid), "independence complex"}@ Δ is returned. The ground set consists of the variables in the ring of the ideal. Example R = QQ[x_0..x_4] I = monomialIdeal (x_0*x_1*x_3,x_1*x_2*x_4,x_0*x_2*x_3*x_4) M = matroid I peek M Caveat This function does not check if (E,B) defines a matroid - see @TO2{(isWellDefined, Matroid), "isWellDefined"}@. The bases are not stored as subsets of the ground set - the indices (with respect to the ground set) are stored instead. For more, see @TO groundSet@. SeeAlso (isWellDefined, Matroid) bases indicesOf specificMatroid /// doc /// Key (symbol ==, Matroid, Matroid) Headline whether two matroids are equal Usage M == N Inputs M:Matroid N:Matroid Outputs :Boolean whether the two matroids are equal Description Text Two matroids are considered equal if they have the same set of (indexed) bases and same size grounds sets (in particular, the ground sets need not be identical). This happens iff the identity permutation is an isomorphism. The strong comparison operator === should not be used, as bases (and ground sets) are internally stored as lists rather than sets, so the same matroid with a different ordering on the list of bases (or ground set) will be treated as different under ===. (One might try to sort the list of bases, but this is potentially time-consuming, as the list of bases can grow rapidly with the size of the ground set.) Example M = matroid completeGraph 3 peek M N = uniformMatroid(2, 3) peek N M == N M === N AG32 = specificMatroid "AG32" -- identically self-dual AG32 == dual AG32 AG32 === dual AG32 V = specificMatroid "vamos" -- self-dual, but not identically so V == dual V areIsomorphic(V, dual V) SeeAlso (isomorphism, Matroid, Matroid) /// doc /// Key [matroid, EntryMode] Headline select method of specifying matroid Usage matroid(..., EntryMode => "bases") matroid(..., EntryMode => "nonbases") matroid(..., EntryMode => "circuits") Description Text A matroid is determined by its set of bases, i.e. maximal (with respect to inclusion) independent sets, which are all of the same size (namely, the rank of the matroid). However, many interesting matroids have relatively few dependencies, and thus it may be easier to specify the matroid by its @TO nonbases@, i.e. dependent subsets of the ground set, with size equal to the rank of the matroid. Similarly, a matroid can be specified by its @TO circuits@, i.e. minimal dependent sets. This is done e.g. when creating a graphical matroid. If EntryMode is not specified, then the default value is assumed, which is EntryMode => "bases". Example M = matroid({{0,1,2}, {3,4,5}}, EntryMode => "circuits") -- bowtie graph bases M F7 = matroid({{0,1,2},{2,3,4},{2,5,6},{0,4,5},{0,3,6},{1,3,5},{1,4,6}}, EntryMode => "nonbases") F7 == specificMatroid "fano" SeeAlso matroid nonbases circuits /// doc /// Key (isWellDefined, Matroid) Headline whether the input is a well-defined matroid Usage isWellDefined M Inputs M:Matroid Outputs :Boolean whether or not a set of subsets satisfies the circuit elimination axiom Description Text If E is a set and C is a collection of subsets of E such that (i) no two elements of C are comparable, and (ii): for C1, C2 in C and $e \in   C1 \cap C2$, there exists $C3 \in   C$ with $C \subseteq (C1 \cup C2) - e$, then C is the set of circuits of a matroid on E. Property (ii) is called the circuit elimination axiom, and these characterize the collections of subsets of E which can be circuits for a matroid on E. This method verifies if the circuit elimination axiom holds for the given input, and additionally whether the input has the correct keys and data types that an object of type Matroid has. Example isWellDefined matroid({a,b,c,d},{{a,b},{c,d}}) isWellDefined matroid({a,b,c,d},{{a,b},{a,c}}) isWellDefined matroid({{1,2,3},{1,4,5},{2,3,4,5},{2,3,6,7},{4,5,6,7}}, EntryMode =>"circuits") -- the Escher "matroid" isWellDefined matroid({{1,2,3},{1,4,5},{1,6,7},{2,3,4,5},{2,3,6,7},{4,5,6,7}}, EntryMode =>"circuits") isWellDefined matroid random(ZZ^3, ZZ^5) isWellDefined matroid completeGraph 4 isWellDefined uniformMatroid(4, 5) Text A theorem of Terai and Trung states that a monomial ideal is the Stanley-Reisner ideal for (the independence complex of) a matroid iff all symbolic powers is Cohen-Macaulay (indeed, this happens iff the 3rd symbolic power is Cohen-Macaulay). This can be verified as follows: Example R = QQ[x_0..x_3] I = monomialIdeal(x_0*x_1, x_0*x_2, x_3) isWellDefined matroid I symbolicCube = intersect apply(irreducibleDecomposition I, P -> P^3) (codim symbolicCube, pdim betti res symbolicCube) /// doc /// Key groundSet Headline (internal) ground set Usage M.groundSet Inputs M:Matroid Outputs :Set of integers starting from 0 Description Text Returns the internal representation of the ground set. Important: read the following if you encounter errors when specifying subsets of a matroid (e.g. restriction/deletion/contraction, rank of subset, etc.) For a matroid M, there are 2 important differences between M.groundSet and the elements of M (given by @TO2{(symbol _*, Matroid), "M_*"}@). First is data types: M.groundSet is a @TO Set@, and M_* is a @TO List@. Second, M.groundSet always consists of integers from 0 to n-1, where n is the number of elements of M: on the other hand, the elements of M themselves can be arbitrary (e.g. symbols, matrices, edges in a graph, etc.). Thus, one can think of M.groundSet as the set of indices of the elements in the list M_*: the first element of M has index 0, corresponding to the element 0 in M.groundSet; the second element of M has index 1, etc. The key point is that all sets associated to the structure of a matroid - bases, circuits, flats, etc. - are subsets of M.groundSet (not M_*). In particular, they are also of class @TO Set@ (although a collection of them is usually a @TO List@), and are also indexed from 0 to n-1. (An exception here is loops and coloops, which are given as a list of indices, rather than single-element sets). A recommended way to circumvent this distinction between indices and elements is to use $\{0, ..., n-1\}$ as the actual elements of M, in which case an element is equal to its index in M.groundSet. Most methods in this package will accept either a list of elements or a set of indices, and if the elements of M are $\{0, ..., n-1\}$, then functionally there will be no difference between inputting lists or sets. In summary: @TO2{List, "lists"}@ are used for elements in M, and given as sublists of M_*, while @TO2{Set, "sets"}@ are used for indices, and given as subsets of M.groundSet. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) peek M M.groundSet M_* bases M (bases M)#0 circuits M flats M loops M coloops M Text Note in particular the types of the various outputs above. The following illustrates how to perform operations with a specified subset of M.groundSet. In the final example, a list of indices is given, which goes against the conventions above, but the elements of the list are treated (correctly) as indices, and if debugLevel is greater than 0, then a warning is printed. Example N1 = M | {a,c,d} N2 = M | set{0,2,3} N1 == N2 debugLevel = 1 N3 = M | {0,2,3} -- gives a warning, but attempts to treat 0 as an index N3 == N2 SeeAlso (symbol _, Matroid, List) /// doc /// Key (symbol _, Matroid, List) (symbol _, Matroid, Set) (symbol _, Matroid, ZZ) (symbol _*, Matroid) Headline elements of matroid Usage M_S M_i M_* Inputs M:Matroid S:List or @TO2{Set, "set"}@, of indices in M.groundSet Outputs :List of elements of M Description Text Converts a list or set of indices to the list of elements of the matroid with those indices. The inverse of this function is @TO indicesOf@. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) M_2 M_{0,2,3} B = (bases M)#0 M_B Text If used with the operator @TO2{symbol _*, "_*"}@, then the list of all elements in M is returned. This is useful in conjunction with @TO apply@, to iterate over all elements in a matroid. Example F7 = specificMatroid "fano" M4 = matroid completeGraph 4 all(F7_*, x -> #getIsos(F7 \ {x}, M4) > 0) Caveat There are important differences between this method and @TO groundSet@: see that page for more details. SeeAlso groundSet indicesOf /// doc /// Key indicesOf (indicesOf, List, List) (indicesOf, Matroid, List) Headline indices of a sublist Usage indicesOf(E, L) indicesOf(M, L) Inputs E:List M:Matroid L:List a list of sublists of E, or a sublist of M_* Outputs :List of indices Description Text This method has two typical-use cases. The first case is to convert sublists of a list E to their corresponding indices. For technical reasons, the accepted input is a list L of sublists of E, and the output is a list of sets of indices, one set for each sublist in L. Note that the order of elements in the sublist is lost, when viewed as a set. Example indicesOf(toList(a..z) | toList(0..9), {{m,a,c,a,u,l,a,y,2},{i,s},{f,u,n}}) Text The second case is with a matroid as input. Here the ambient list E is taken as the ground set of the matroid (i.e. E = M_*), and L should be a list of elements of M (not a list of lists); in this case the inverse of this method is given by @TO2{(symbol _, Matroid, List), "taking subscripts"}@ with respect to M. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) B = {a, c} S = indicesOf(M, B) M_S == B Text In this case, if L is not a sublist of M_*, then a warning is printed, and L itself is returned. This is done so that if a user inputs a list of indices, then it will be interpreted as a set of indices. For more on this, cf. @TO groundSet@. SeeAlso (symbol _, Matroid, List) /// doc /// Key (ideal, Matroid) Headline Stanley-Reisner (circuit) ideal of matroid Usage ideal M Inputs M:Matroid Outputs :MonomialIdeal the Stanley Reisner ideal of the independence complex, also called the circuit ideal Description Text The @TO2{(independentSets, Matroid), "independent sets"}@ of a matroid M form a simplicial complex (i.e., are downward closed), called the @TO2{(independenceComplex, Matroid), "independence complex"}@ of M. Via the Stanley-Reisner correspondence, the independence complex of M corresponds uniquely to a squarefree monomial ideal, which is the output of this method. The minimal generators of the ideal correspond to minimal non-faces of the simplicial complex. As the faces of the independence complex are precisely the independent sets, the minimal non-faces are exactly the minimal dependent sets, i.e. the @TO circuits@ of M. The facets of the simplicial complex correspond to @TO bases@ of M, and thus also to irreducible components of the ideal of M; which are in bijection with the minimal generators of the Alexander dual ideal via taking complements. Internally, the ideal of the matroid is a fundamental complete invariant, and is heavily used in many algorithms in this package. Accordingly, once the ideal of a matroid is computed, it is cached in the @TO CacheTable@ of the matroid, which speeds up any algorithm which requires the ideal as part of the input. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) circuits M ideal M J = dual ideal M J_*/indices bases M SeeAlso circuits bases (independenceComplex, Matroid) /// doc /// Key bases (bases, Matroid) Headline bases of matroid Usage bases M Inputs M:Matroid Outputs :List of bases Description Text Returns a list of bases of the matroid. The basis elements are represented as sets of nonnegative integers, which are the indices of the elements in the ground set that make up a basis element. To get the subset of the ground set corresponding to a set of indices, use @TO2{(symbol _, Matroid, List), "subscripts"}@. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) bases M M_((bases M)#0) Text In this package, bases are the only structure that is always computed upon creation of a matroid. Additional invariants (such as the @TO2{(ideal, Matroid), "ideal"}@ or @TO circuits@) are not precomputed, but are cached after being computed once. This allows for maximum speed in methods that need to call the @TO2{matroid, "constructor function"}@ many, many times: e.g. @TO2{(tuttePolynomial, Matroid), "tuttePolynomial"}@ and @TO hasMinor@. SeeAlso nonbases (independentSets, Matroid) (symbol _, Matroid, List) /// doc /// Key nonbases (nonbases, Matroid) Headline nonbases of matroid Usage nonbases M Inputs M:Matroid Outputs :List of nonbases Description Text In any matroid, all basis elements have the same cardinality r (which is the rank of the matroid). The nonbases of a matroid are the subsets of the ground set of cardinality r that are dependent. Just as with @TO bases@ and @TO circuits@, nonbases are stored via their indices (rather than the elements of the ground set themselves). Example M = matroid({a,b,c,d},{{a,b},{a,c}}) nonbases M SeeAlso bases /// doc /// Key circuits (circuits, Matroid) Headline circuits of matroid Usage circuits M Inputs M:Matroid Outputs :List of circuits Description Text The circuits of a matroid are the minimal dependent subsets of the ground set. Just as with @TO bases@ and @TO nonbases@, circuits are stored via their indices (rather than the elements of the ground set themselves). Example M = matroid({a,b,c,d},{{a,b},{a,c}}) circuits M SeeAlso (ideal, Matroid) fundamentalCircuit loops /// doc /// Key fundamentalCircuit (fundamentalCircuit, Matroid, List, Thing) (fundamentalCircuit, Matroid, Set, ZZ) Headline fundamental circuit of independent set Usage fundamentalCircuit(M, I, e) Inputs M:Matroid I:Set of indices, or a @TO2{List, "list"}@ of elements in M, which is an independent set e:ZZ an index, or an element in M, such that $I \cup \{e\}$ is dependent Outputs :Set the fundamental circuit of e with respect to I Description Text If I is an independent set I, and e is an element such that $I \cup \{e\}$ is dependent (in particular e is not in I), then there is a unique circuit contained in $I \cup \{e\}$, called the fundamental circuit of e with respect to I, which moreover contains e. Every circuit is the fundamental circuit of some element with respect to some basis. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) circuits M fundamentalCircuit(M, {a,c}, b) fundamentalCircuit(M, set{0,2}, 1) fundamentalCircuit(M, set{0,2}, 3) Text This method does not perform any checks (e.g. whether $I$ is independent, or if $e$ is not in $I$). If $I \cup \{e\}$ is independent, then (if debugLevel is greater than 0) a warning is printed, and @TO null@ is returned. In the example below, the elements with indices 2 and 3 are parallel (indeed, both are equal to the column vector (1, 1)). Thus in general it is safer to refer to a subset by its indices, rather than its elements. Example M = matroid matrix{{1,0,1,1},{0,1,1,1}} circuits M M_2 M_2 == M_3 (try fundamentalCircuit (M, M_{1,2}, M_3)) === null fundamentalCircuit (M, set{1,2}, 3) SeeAlso circuits (independentSets, Matroid) isDependent /// doc /// Key loops (loops, Matroid) Headline loops of matroid Usage loops M Inputs M:Matroid Outputs :List the loops of M Description Text The loops of a matroid are the one-element @TO circuits@. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) loops M all(loops M, l -> member(set{l}, circuits M)) loops(M/(set loops M)) == {} SeeAlso coloops circuits /// doc /// Key coloops (coloops, Matroid) Headline coloops of matroid Usage coloops M Inputs M:Matroid Outputs :List Description Text The coloops of a matroid M are the loops of the @TO2{(dual, Matroid), "dual"}@ matroid. The set of coloops of M equals both the intersection of the @TO bases@ of M, and the complement of the union of the @TO circuits@ of M. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) circuits M C = set coloops M C === M.groundSet - fold(circuits M, (a, b) -> a + b) C === fold(bases M, (a, b) -> a*b) M_C D = dual M; peek D coloops matroid completeGraph 4 == {} SeeAlso loops (dual, Matroid) /// doc /// Key (independentSets, Matroid) (independentSets, Matroid, ZZ) Headline independent subsets of a matroid Usage independentSets M independentSets(M, s) Inputs M:Matroid Outputs :List the independent sets in M of size s Description Text A subset of the ground set is called independent if it is contained in a @TO2{bases, "basis"}@, or equivalently, does not contain a @TO2{circuits, "circuit"}@. This method returns all independent subsets of the ground set of a fixed size $s$. If no size $s$ is given, returns a list of all independent sets of M. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) independentSets(M, 2) netList independentSets M V = specificMatroid "vamos" I3 = independentSets(V, 3) #I3 SeeAlso bases isDependent (independenceComplex, Matroid) /// doc /// Key isDependent (isDependent, Matroid, Set) (isDependent, Matroid, List) Headline whether a subset is dependent Usage isDependent(M, S) Inputs M:Matroid S:Set of indices, or a @TO2{List, "list"}@ of elements in M Outputs :Boolean whether S is dependent in M Description Text This method checks if the given subset of the ground set is dependent, i.e. contains a @TO2{circuits, "circuit"}@. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) isDependent(M, {a,b}) isDependent(M, {d}) SeeAlso (independentSets, Matroid) /// doc /// Key (rank, Matroid) Headline rank of a matroid Usage rank M Inputs M:Matroid Outputs :ZZ Description Text The rank of a matroid is the common size of a(ny) basis of M. This is a basic numerical invariant of a matroid. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) rank M SeeAlso (rank, Matroid, Set) /// doc /// Key (rank, Matroid, Set) (rank, Matroid, List) Headline rank of a subset of a matroid Usage rank(M, S) Inputs M:Matroid S:Set of indices, or a @TO2{List, "list"}@ of elements in M Outputs :ZZ Description Text The rank of a subset S of a matroid is the size of a maximal independent subset of S. The map 2^E $\to \mathbb{N}$, S $\mapsto$ rank(S), is called the rank function, and completely determines the matroid. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) for s in subsets M_* do print(toString s | " has rank " | rank_M s) SeeAlso (rank, Matroid) /// doc /// Key closure (closure, Matroid, List) (closure, Matroid, Set) Headline closure of a subset of a matroid Usage closure(M, S) Inputs M:Matroid S:Set of indices, or a @TO2{List, "list"}@ of elements in M Outputs :List Description Text The closure of a subset S of a matroid (E, B) is the set cl(S) := \{x $\in$ E : rank(S) = rank(S $\cup$ \{x\}) \}. The closure operator 2^E -> 2^E, S $\mapsto$ cl(S), completely determines the matroid (indeed, the maximal proper closed sets - i.e. @TO2{(hyperplanes, Matroid), "hyperplanes"}@ - already determine the matroid). Example M = matroid({a,b,c,d},{{a,b},{a,c}}) for s in subsets M_* do print(toString s | " has closure " | toString closure_M s) F = flats M all(F, f -> closure_M f === f) SeeAlso flats /// doc /// Key flats (flats, Matroid, ZZ) (flats, Matroid) Headline flats of a matroid Usage flats(M, r) flats M Inputs M:Matroid r:ZZ the target rank (optional) Outputs :List Description Text A flat, or closed subset, of a matroid is a subset A of the ground set which equals its @TO closure@. The set of flats, partially ordered by inclusion, forms a lattice, called the @TO2{latticeOfFlats, "lattice of flats"}@. This is an important invariant of the matroid: one can recover the matroid from the lattice of flats, and for simple matroids (i.e. matroids whose circuits all have size >= 3), the isomorphism type of the lattice is already a complete invariant. If a target rank r is provided, then this method computes closures of independent sets of size r. This may be slower than simply computing all flats, and then selecting those of rank r. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) flats(M, 1) netList flats M Text If no target rank is provided, this method computes flats by iteratively intersecting @TO2{(hyperplanes, Matroid), "hyperplanes"}@ of M: every flat of corank k (i.e. of @TO2{(rank, Matroid), "rank"}@ = rank M - k) can be expressed as an intersection of k hyperplanes (cf. Oxley, Prop. 1.7.8). Thus if hyperplanes of M have been precomputed, then this function is typically much faster. CannedExample i4 : M = matroid completeGraph 7 o4 = a matroid of rank 6 on 21 elements o4 : Matroid i5 : time #hyperplanes M ‐‐ used 4.98437 seconds o5 = 63 i6 : time #flats M ‐‐ used 0.515625 seconds o6 = 877 SeeAlso closure (hyperplanes, Matroid) (fVector, Matroid) latticeOfFlats /// doc /// Key hyperplanes (hyperplanes, Matroid) Headline hyperplanes of a matroid Usage hyperplanes M Inputs M:Matroid Outputs :List Description Text The hyperplanes of a matroid are the flats of rank equal to rank M - 1. The complements of the hyperplanes are precisely the @TO circuits@ of the @TO2{(dual, Matroid), "dual"}@ matroid (which is indeed how this method computes hyperplanes), and thus a matroid is determined by its hyperplanes. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) hyperplanes M SeeAlso flats (rank, Matroid) /// doc /// Key latticeOfFlats (latticeOfFlats, Matroid) Headline lattice of flats of a matroid Usage latticeOfFlats M Inputs M:Matroid Outputs :Poset Description Text The lattice of flats of a matroid M is the set of flats of M, partially ordered by containment; i.e. F1 <= F2 if F1 is contained in F2. The lattice of flats of a matroid is a geometric lattice: i.e. it is atomic (every element is a join of atoms = rank 1 elements) and semimodular (h(x) + h(y) >= h(x ∨ y) + h(x ∧ y) for any x, y, where h is the height function = maximum length of a chain from 0). Conversely, every geometric lattice is the lattice of flats of a matroid. If M1 and M2 are @TO2{(isSimple, Matroid), "simple matroids"}@ (i.e. no loops or parallel classes) with isomorphic lattice of flats, then M1 and M2 are isomorphic. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) latticeOfFlats M Text One can also view the lattice of flats, using @TO displayPoset@ provided by the @TO Posets@ package (together with the option @TO SuppressLabels@ => false). SeeAlso flats (rank, Matroid) (fVector, Matroid) /// doc /// Key (fVector, Matroid) Headline f-vector of a matroid Usage fVector M Inputs M:Matroid Outputs :HashTable Description Text The f-vector of a matroid M is the invariant (f_0, f_1, ..., f_r), where f_i is the number of @TO2{(rank, Matroid, Set), "rank"}@ i @TO flats@ of M, and r is the @TO2{(rank, Matroid), "rank"}@ of M. Note that f_0 = f_r = 1, as the set of @TO loops@ is the unique flat of rank 0, and the ground set is the unique flat of maximal rank. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) fVector M fVector matroid completeGraph 4 Caveat This is not the same as the f-vector of the @TO2{(independenceComplex, Matroid), "independence complex"}@ of the matroid M, which counts the number of independent sets of a given size. To do this instead, use "fVector independenceComplex M". SeeAlso flats (rank, Matroid) latticeOfFlats /// doc /// Key (dual, Matroid) Headline dual matroid Usage dual M Inputs M:Matroid Outputs :Matroid the dual matroid of M Description Text The dual matroid of a matroid M has the same ground set as M, and bases equal to the complements of bases of M. Duality is a fundamental operation in matroid theory: for nearly any property/operation of matroids, there is a corresponding dual version, usually denoted with the prefix "co-". For instance, coloops are loops of the dual, and contraction is dual to deletion. In this package, every dual matroid is created as a matroid-dual matroid pair, and each is cached as the dual of the other. Often the ideal of the dual matroid has a significantly different number of generators, so many algorithms in this package will use an equivalent check for the ideal with fewer generators. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) D = dual M peek D M == dual D loops D == coloops M hyperplanes M === apply(circuits D, C -> D.groundSet - C) Text A matroid that is @TO2{(areIsomorphic, Matroid, Matroid), "isomorphic"}@ to its dual is called self-dual; and a matroid that is @TO2{(symbol ==, Matroid, Matroid), "equal"}@ to its dual is called identically self-dual. Example V8plus = specificMatroid "V8+" V8plus == dual V8plus V = relaxation(V8plus, set{4,5,6,7}) V == dual V areIsomorphic(V, dual V) /// doc /// Key restriction (restriction, Matroid, Set) (restriction, Matroid, List) (symbol |, Matroid, Set) (symbol |, Matroid, List) Headline restriction to subset of matroid Usage restriction(M, S) M | S Inputs M:Matroid S:Set of indices, or a @TO2{List, "list"}@ of elements in M Outputs :Matroid the restriction M | S Description Text The restriction of M to S, M | S, has ground set S and independent sets equal to the independent sets of M contained in S. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) N = M | {a,b,d} peek N N == M | set{0,1,3} SeeAlso deletion minor /// doc /// Key deletion (deletion, Matroid, Set) (deletion, Matroid, List) (symbol \, Matroid, Set) (symbol \, Matroid, List) Headline deletion of subset of matroid Usage deletion(M, S) M \ S Inputs M:Matroid S:Set of indices, or a @TO2{List, "list"}@ of elements in M Outputs :Matroid the deletion M \ S Description Text The deletion M \ S is obtained by restricting to the complement of S. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) N = M \ {a} peek N N == M \ set{0} SeeAlso restriction contraction minor /// doc /// Key contraction (contraction, Matroid, Set) (contraction, Matroid, List) (symbol /, Matroid, Set) (symbol /, Matroid, List) Headline contraction of subset of matroid Usage contraction(M, S) M / S Inputs M:Matroid S:Set of indices, or a @TO2{List, "list"}@ of elements in M Outputs :Matroid the contraction M / S Description Text The contraction of M by S is given by M/S := (M* \ S)*, where * stands for dual, and \ is deletion. Example M = matroid({a,b,c,d},{{a,b},{a,c}}) N = M / {c} peek N N == M / set{2} SeeAlso deletion (dual, Matroid) minor /// doc /// Key minor (minor, Matroid, List, List) (minor, Matroid, Set, Set) Headline minor of matroid Usage minor(M, X, Y) Inputs M:Matroid X:Set of indices, or a @TO2{List, "list"}@ of elements in M Y:Set of indices, or a @TO2{List, "list"}@ of elements in M, disjoint from X Outputs :Matroid the minor M / X \ Y Description Text The minor M / X \ Y of M is given by contracting X and deleting Y from M. The resulting matroid is independent of the order in which deletion and contraction is done. If X (or Y) is a set (of indices in M.groundSet), then X is identified with the sublist of elements of M with indices in X: cf. @TO groundSet@ for more on this package-wide convention. Example M = matroid random(ZZ^3,ZZ^6) M_* M.groundSet (X, Y) = (set{3}, set{0,1}) (X1, Y1) = (M_X, M_Y) N = minor(M, X, Y) peek N N == minor(M, X1, Y1) Text Note that there is potential ambiguity for the second argument - namely, whether or not Y is treated with respect to the ground set of M or M / X (which are different). This method assumes that the indices of Y (and X) are taken with respect to the ground set of M. If one already has the indices Y0 of Y in M / X (or the indices X0 of X in M \ Y), one can simply use the notation M @TO2{contraction, "/"}@ X @TO2{deletion, "\\"}@ Y0 (or (M \ Y) / X0). Thus this method serves purely as a convenience, to save the user the (trivial) task of computing Y0 from Y. If X and Y are not disjoint, then an error is thrown (thus one should @TO2{(symbol -, Set, Set), "subtract"}@ X from Y beforehand). Example M5 = matroid completeGraph 5 M5.groundSet N = minor(M5, set{8}, set{3,4,9}) areIsomorphic(N, matroid completeGraph 4) N == (M5 \ set{3,4,9}) / set{6} -- after deleting 3,4 (and 9), index 8 -> 6 N == M5 / set{8} \ set{3,4,8} -- after contracting 8, index 9 -> 8 (try minor(M5, set{8}, set{3,4,8,9})) === null minor(M5, set{8}, set{3,4,8,9} - set{8}) SeeAlso deletion contraction hasMinor /// doc /// Key hasMinor (hasMinor, Matroid, Matroid) Headline whether a matroid has a given minor Usage hasMinor(M, N) Inputs M:Matroid N:Matroid Outputs :Boolean whether N is a minor of M Description Text Determines if N is a minor of M, i.e. can be obtained from M by a contraction followed by a deletion. Since deletion and contraction by disjoint subsets commute, every sequence of deletion and contraction operations can be written as a single contraction and deletion. Many families of matroids can be defined by a list of forbidden minors: i.e. a matroid M is in the family iff M does not have any of the forbidden minors as a minor. For instance, a matroid is representable over F_2 iff it does not have U_{2,4} as a minor, i.e. U_{2,4} is the (sole) forbidden minor for binary matroids. If a minor is found that is @TO2{(areIsomorphic, Matroid, Matroid), "isomorphic"}@ to N, then the sets to be contracted and deleted are printed. Example (M4, M5, M6) = (4,5,6)/completeGraph/matroid hasMinor(M4, uniformMatroid(2,4)) time hasMinor(M6, M5) SeeAlso minor /// doc /// Key relaxation (relaxation, Matroid, Set) (relaxation, Matroid, List) Headline relaxation of matroid Usage relaxation(M, S) Inputs M:Matroid S:Set of indices, or a @TO2{List, "list"}@ of elements in M, which is a circuit-hyperplane of M Outputs :Matroid the relaxation of M by S Description Text Let M = (E, B) be a matroid with bases B. If there is a subset S of E that is both a @TO2{circuits, "circuit"}@ and a @TO2{(hyperplanes, Matroid), "hyperplane"}@ of M, then the set $B \cup \{S\}$ is the set of bases of a matroid on E, called the relaxation of M by S. Many interesting matroids arise as relaxations of other matroids: e.g. the non-Fano matroid is a relaxation of the @TO2{specificMatroid, "Fano matroid"}@, and the non-Pappus matroid is a relaxation of the Pappus matroid. Example P = specificMatroid "pappus" NP = specificMatroid "nonpappus" NP == relaxation(P, set{6,7,8}) Caveat Note that relaxation does not change the ground set. Thus e.g. @TO representationOf@ will return the same for both the Fano and non-Fano matroids. /// doc /// Key (symbol +, Matroid, Matroid) Headline union of matroids Usage M + N Inputs M:Matroid N:Matroid Outputs :Matroid the sum, or union, of M and N Description Text The union of M and N has ground set equal to the union of those of M and N, and independent sets given by pairwise unions of independent sets of M and N. Example M = uniformMatroid(2,4) + uniformMatroid(1,4) peek M M == uniformMatroid(3, 4) Text When the ground sets of M and N are disjoint, this is the @TO2{(symbol ++, Matroid, Matroid), "direct sum"}@ of M and N. Beware of order when using @TO2{(symbol ==, Matroid, Matroid), "=="}@ though: Example M1 = uniformMatroid(2, 4) + matroid completeGraph 4 M1 == uniformMatroid(2, 4) ++ matroid completeGraph 4 M2 = matroid completeGraph 4 ++ uniformMatroid(2, 4) M1 == M2 areIsomorphic(M1, M2) Text Matroid union is an important operation in combinatorial optimization, and via duality, is related to the problem of matroid intersection. With the operation of union, one can work with transversal matroids and gammoids. A matroid is transversal iff it is a union of rank 1 matroids; strict gammoids are precisely the duals of transversal matroids, and gammoids are restrictions of strict gammoids. In general the problem of determining if a given matroid is a gammoid is difficult. A union of two uniform matroids is again uniform, but a union of two graphic matroids need not be binary: Example M1 = matroid({a,b,c,d}, {{a},{b},{c}}) M2 = matroid({a,b,c,d}, {{b},{c},{d}}) M1 + M2 == uniformMatroid(2,4) F7 = specificMatroid "fano" NF = specificMatroid "nonfano" all({F7 + NF, F7 + F7, NF + NF}, M -> M == uniformMatroid(6, 7)) Text One potential caveat: the ground set of M must not have repeated elements. If this is not the case, the user MUST relabel elements of M so that they become distinct. Of course, this needs to be done for both M and N, and one should also keep track of which elements of M and N are meant to be the same after the relabelling (otherwise the entire point of taking unions, as opposed to direct sums, is lost). In the example below, M contains the vector {1,1} twice. Macaulay2 has no way of distinguishing the repeated vectors, so the second occurrence of {1,1} is relabelled to the symbol d (of course, if the symbol d also happened to be an element of N, then a different label would have to be chosen). Example A = matrix{{0,1,1,1},{0,0,1,1}} M = matroid A M_* unique M_* M1 = matroid(M_{0,1,2} | {d}, bases M) M == M1 B = matrix{{0,1,2},{0,1,2}} N = matroid B U = M1 + N peek U U_* SeeAlso (symbol ++, Matroid, Matroid) /// doc /// Key (symbol ++, Matroid, Matroid) Headline direct sum of matroids Usage M ++ N Inputs M:Matroid N:Matroid Outputs :Matroid the direct sum of M and N Description Text The direct sum of M and N has ground set equal to the disjoint union of those of M and N, and bases equal to the union of bases of M and N. Example S = uniformMatroid(2,3) ++ uniformMatroid(1,3) peek S S_* (S ++ uniformMatroid(1, 3))_* Caveat The elements of the ground set of the direct sum will receive placeholders to ensure disjointness (as evidenced by the elements of S being ordered pairs above). As this method is binary, repeated applications of this function will result in nested placeholders. Since the bases are stored as indices, the bases of M will not change, but those of N will be shifted up by the size of the ground set of M. SeeAlso (symbol +, Matroid, Matroid) (components, Matroid) /// doc /// Key (components, Matroid) Headline connected components of matroid Usage components M Inputs M:Matroid Outputs :List the connected components of M Description Text Define an equivalence relation ~ on the ground set of M by e ~ f if e = f or $\{e,f\}$ is contained in a circuit. The equivalence classes under ~ are the connected components of M. A matroid is the direct sum of its connected components. Example M = matroid graph({{0,1},{0,2},{1,2},{3,4},{4,5}}) C = components M areIsomorphic(M, fold(C, (a, b) -> a ++ b)) G = graph({{0,1},{0,2},{0,3},{0,4},{1,2},{3,4}}) isConnected G components matroid G Caveat As the examples above show, the connected components of the graphic matroid M(G) need not be the same as the connected components of the graph G (indeed, for any graph G, there exists a connected graph H with M(G) isomorphic to M(H)). SeeAlso circuits (symbol ++, Matroid, Matroid) /// doc /// Key representationOf (representationOf, Matroid) Headline represents a realizable/graphic matroid Usage representationOf M Inputs M:Matroid Outputs :Thing a representation of M (either a matrix or a graph) Description Text Given a realizable matroid whose ground set elements are vectors, returns the matrix with those column vectors. If the matroid is graphical, then the graph with edge set equal to the ground set is returned (without loops or parallel edges, since the Graphs package does not support these). Example A = random(ZZ^3,ZZ^5) M = matroid A A == representationOf M K4 = completeGraph 4 M4 = matroid K4 representationOf M4 === K4 SeeAlso matroid affineGeometry projectiveGeometry specificMatroid /// doc /// Key getIsos (getIsos, Matroid, Matroid) Headline all isomorphisms between two matroids Usage getIsos(M, N) Inputs M:Matroid N:Matroid Outputs :List of all isomorphisms between M and N Description Text This method computes all @TO2{(areIsomorphic, Matroid, Matroid), "isomorphisms"}@ between M and N: in particular, this method returns an empty list iff M and N are not isomorphic. To compute only a single isomorphism, use @TO2{(isomorphism, Matroid, Matroid), "isomorphism"}@. To test if two matroids are isomorphic, use @TO2{(areIsomorphic, Matroid, Matroid), "areIsomorphic"}@. To save space, the isomorphisms are given as lists (as opposed to hash tables). One way to interpret the output of this method is: given two isomorphic matroids, this method returns a permutation representation of the automorphism group of that matroid, inside the symmetric group on the ground set. Example M = matroid({a,b,c},{{a,b},{a,c}}) U23 = uniformMatroid(2,3) getIsos(M, U23) -- not isomorphic getIsos(M, M) getIsos(U23, U23) -- the full symmetric group S3 Text We can verify that the Fano matroid (the projective plane over the field of two elements) has automorphism group of order 168, and give a permutation representation for this nonabelian simple group (= PGL(3, F_2)) inside the symmetric group S_7: Example F7 = specificMatroid "fano" time autF7 = getIsos(F7, F7); #autF7 SeeAlso (isomorphism, Matroid, Matroid) quickIsomorphismTest (areIsomorphic, Matroid, Matroid) /// doc /// Key (isomorphism, Matroid, Matroid) Headline computes an isomorphism between isomorphic matroids Usage isomorphism(M, N) Inputs M:Matroid N:Matroid Outputs :HashTable an isomorphism between M and N Description Text This method computes a single @TO2{(areIsomorphic, Matroid, Matroid), "isomorphism"}@ between M and N, if one exists, and returns @TO null@ if no such isomorphism exists. The output is a @TO HashTable@, where the keys are elements of the @TO groundSet@ of M, and their corresponding values are elements of (the ground set of) N. To obtain all isomorphisms between two matroids, use @TO getIsos@. Example M = matroid({a,b,c},{{a,b},{a,c}}) isomorphism(M, uniformMatroid(2,3)) -- not isomorphic (M5, M6) = (5,6)/completeGraph/matroid minorM6 = minor(M6, set{8}, set{4,5,6,7}) time isomorphism(M5, minorM6) isomorphism(M5, M5) p = {8, 9, 13, 11, 7, 14, 0, 3, 2, 4, 6, 5, 1, 10, 12} -- random permutation of M6.groundSet N = matroid(M6.cache.groundSet, (circuits M6)/(c -> c/(i -> p#i)), EntryMode => "circuits") time phi = isomorphism(M6,N) values phi === p SeeAlso getIsos quickIsomorphismTest (areIsomorphic, Matroid, Matroid) /// doc /// Key quickIsomorphismTest (quickIsomorphismTest, Matroid, Matroid) Headline quick checks for isomorphism between matroids Usage quickIsomorphismTest(M, N) Inputs M:Matroid N:Matroid Outputs :String either "true" or "false" or "Could be isomorphic" Description Text This method performs relatively quick tests to determine whether or not two matroids are isomorphic. A result of "false" is definitive proof that the matroids are not isomorphic, a result of "true" is definitive proof that the matroids are isomorphic, and a result of "Could be isomorphic" is evidence that the matroids may be isomorphic (although there are nonisomorphic matroids which cannot be detected by this method). If "true" or "false" is returned, use @TO value@ to convert to a @TO Boolean@. Example M1 = matroid(toList(a..z)/toString,{{"m","a","t","r","o","i","d"}}) M2 = matroid(toList(0..25), {{random(ZZ),23,15,12,19,20,11}}) quickIsomorphismTest(M1, M2) quickIsomorphismTest(matroid random(ZZ^5,ZZ^8), uniformMatroid(5, 8)) quickIsomorphismTest(uniformMatroid(5, 9), uniformMatroid(4, 9)) M1 = matroid graph({{a,b},{b,c},{c,d},{d,e},{e,f},{f,g},{f,h},{c,h},{c,f},{a,g},{d,g}}) M2 = matroid graph({{a,b},{b,c},{c,d},{d,e},{e,f},{f,g},{f,h},{c,h},{c,f},{a,g},{a,h}}) R = ZZ[x,y]; tuttePolynomial(M1, R) == tuttePolynomial(M2, R) time quickIsomorphismTest(M1, M2) value oo === false SeeAlso (isomorphism, Matroid, Matroid) getIsos (areIsomorphic, Matroid, Matroid) /// doc /// Key (areIsomorphic, Matroid, Matroid) Headline whether two matroids are isomorphic Usage areIsomorphic(M, N) Inputs M:Matroid N:Matroid Outputs :Boolean true if the matroids are isomorphic, false otherwise Description Text Two matroids are isomorphic if there is a bijection between their ground sets which induces a bijection between bases, or equivalently, circuits (which is what this package actually checks, since there are often fewer circuits than bases). This method first runs @TO quickIsomorphismTest@, then @TO2{(isomorphism, Matroid, Matroid), "isomorphism"}@ if the tests are inconclusive. Example M = matroid({a,b,c},{{a,b},{a,c},{b,c}}) areIsomorphic(M, uniformMatroid(2,3)) M1 = matroid({a,b,c},{{a,b},{a,c}}) areIsomorphic(M, M1) Caveat Isomorphism of matroids should not be confused with equality: cf. @TO2{(symbol ==, Matroid, Matroid), "=="}@ for more details. SeeAlso (isomorphism, Matroid, Matroid) getIsos quickIsomorphismTest /// doc /// Key (tuttePolynomial, Matroid) (tuttePolynomial, Matroid, Ring) Headline Tutte polynomial of a matroid Usage tuttePolynomial M Inputs M:Matroid Outputs :RingElement the Tutte polynomial of M Description Text The Tutte polynomial is an invariant of a matroid that is universal with respect to satisfying a deletion-contraction recurrence. Indeed, one way to define the Tutte polynomial of a matroid is: if $M$ is a matroid consisting of $a$ loops and $b$ coloops, then T_M(x, y) = x^ay^b, and if $e \in M$ is neither a loop nor a coloop, then T_M(x, y) := T_{M/e}(x, y) + T_{M\e}(x, y), where M\e is the @TO deletion@ of M with respect to \{e\}, and M/e is the @TO contraction@ of M with respect to \{e\}. Many invariants of a matroid can be determined by substituting values into its Tutte polynomial - cf. @TO tutteEvaluate@. Example tuttePolynomial matroid completeGraph 4 tuttePolynomial specificMatroid "nonpappus" SeeAlso tutteEvaluate (characteristicPolynomial, Matroid) chromaticPolynomial /// doc /// Key tutteEvaluate (tutteEvaluate, Matroid, Thing, Thing) Headline evaluate Tutte polynomial Usage tutteEvaluate(M, a, b) Inputs M:Matroid a:Thing b:Thing Outputs :Thing the evaluation of the Tutte polynomial of M at (a, b) Description Text Provides a user-friendly method to evaluate the Tutte polynomial at given values (i.e. calls @TO sub@ with the correct variables in the ring of the Tutte polynomial). For example, if M has Tutte polynomial T, then T(1,1) is the number of bases of M. Example M = uniformMatroid(2, 4) tutteEvaluate(M, 1, 1) Text If M = M(G) is the graphic matroid of a graph G, then T(2, 1) counts the number of spanning forests of G, and T(2, 0) counts the number of acyclic orientations of G. Example M = matroid completeGraph 5 tutteEvaluate(M, 2, 1) tutteEvaluate(M, 2, 0) SeeAlso (tuttePolynomial, Matroid) /// doc /// Key (characteristicPolynomial, Matroid) Headline computes characteristic polynomial of a matroid Usage characteristicPolynomial M Inputs M:Matroid Outputs :RingElement the characteristic polynomial of M Description Text The characteristic polynomial is a particular specialization of the Tutte polynomial. If M is a matroid of rank r with Tutte polynomial T(x, y), then the characteristic polynomial of M is given by (-1)^r * T(1 - x, 0). This function computes the characteristic polynomial as an evaluation of the Tutte polynomial. If the Tutte polynomial of the matroid has already been computed, then this function should return the characteristic polynomial instantaneously. Example M = matroid completeGraph 4 T = tuttePolynomial M factor characteristicPolynomial M Caveat If M = M(G) is a graphic matroid, then the characteristic polynomial of M and the chromatic polynomial of G differ by a factor of x^k, where k is the number of connected components of the graph G. SeeAlso (tuttePolynomial, Matroid) chromaticPolynomial /// doc /// Key chromaticPolynomial (chromaticPolynomial, Graph) Headline computes chromatic polynomial of a graph Usage chromaticPolynomial G Inputs G:Graph Outputs :RingElement the chromatic polynomial of G Description Text The chromatic polynomial is an invariant of a graph that counts the number of vertex colorings. The value of this polynomial at a natural number n is the number of ways to color the vertices of G using at most n colors, such that no adjacent vertices have the same color. This method computes the chromatic polynomial as a multiple of the characteristic polynomial of the graphic matroid. Indeed, if M = M(G) is the graphic matroid corresponding to a graph G, then the chromatic polynomial of G equals the characteristic polynomial of M times x^k, where k is the number of connected components of G (which is distinct from the number of @TO2{(components, Matroid), "components"}@ of M). Example factor chromaticPolynomial cycleGraph 7 factor characteristicPolynomial matroid cycleGraph 7 Text The Four Color Theorem states that if G is a planar graph, then its chromatic polynomial has value > 0 at n = 4. In accordance with this, we see that K5 is not planar (on the other hand, note that K_{3,3} is bipartite, hence 2-colorable): Example factor chromaticPolynomial completeGraph 5 SeeAlso (tuttePolynomial, Matroid) (characteristicPolynomial, Matroid) /// doc /// Key (isSimple, Matroid) Headline whether a matroid is simple Usage isSimple M Inputs M:Matroid Outputs :Boolean whether M is a simple matroid Description Text A matroid is simple if it has no @TO loops@ or parallel classes; equivalently, it has no @TO circuits@ of size <= 2. Among the class of simple matroids, the @TO2{latticeOfFlats, "lattice of flats"}@ is a complete invariant. Every matroid has a unique @TO2{simpleMatroid, "simplification"}@ which has the same lattice of flats. Example isSimple matroid completeGraph 3 M = matroid(completeGraph 3, ParallelEdges => {set{0,1},set{0,1},set{1,2}}, Loops => {0,2}) isSimple M S = simpleMatroid M isSimple S latticeOfFlats M == latticeOfFlats S Text Note that the @TO2{(dual, Matroid), "dual"}@ of a simple matroid may not be simple: Example U = uniformMatroid(2, 2) isSimple U isSimple dual U SeeAlso simpleMatroid /// doc /// Key simpleMatroid (simpleMatroid, Matroid) Headline simple matroid associated to a matroid Usage S = simpleMatroid M Inputs M:Matroid Outputs :Matroid the simple matroid associated to M Description Text The simple matroid associated to a matroid M is obtained from M by deleting all @TO loops@, and all but one element from each parallel class. In a simple matroid, the @TO2{latticeOfFlats, "lattice of flats"}@ has the empty set as minimal element, and all atoms are singletons. Example M = uniformMatroid(0, 2) ++ uniformMatroid(1, 2) ++ uniformMatroid(2, 4) isSimple M S = simpleMatroid M latticeOfFlats M == latticeOfFlats S select(flats S, f -> rank(S, f) <= 1) AG32 = affineGeometry(3, 2) SeeAlso (isSimple, Matroid) /// doc /// Key uniformMatroid (uniformMatroid, ZZ, ZZ) Headline uniform matroid Usage U = uniformMatroid(k, n) Inputs k:ZZ n:ZZ Outputs :Matroid the uniform matroid of rank k on n elements Description Text The uniform matroid of rank k has as bases all size k subsets. The ground set is $\{0, ..., n-1\}$. Example U35 = uniformMatroid(3,5) peek U35 /// doc /// Key affineGeometry (affineGeometry, ZZ, ZZ) Headline affine geometry of rank n+1 over F_p Usage M = affineGeometry(n, p) Inputs n:ZZ the dimension of the ambient vector space p:ZZ a prime Outputs :Matroid the affine geometry of rank n+1 over F_p Description Text The affine geometry of rank n+1 over F_p is the matroid whose ground set consists of all vectors in a vector space over F_p of dimension n, where independence is given by affine independence, i.e. vectors are dependent iff there is a linear combination equaling zero in which the coefficients sum to zero (equivalently, the vectors are placed in the hyperplane x_0 = 1 in a vector space of dimension n+1, with ordinary linear independence in the larger space). Example M = affineGeometry(3, 2) M === specificMatroid "AG32" circuits M representationOf M SeeAlso projectiveGeometry /// doc /// Key projectiveGeometry (projectiveGeometry, ZZ, ZZ) Headline projective geometry of dimension n over F_p Usage M = projectiveGeometry(n, p) Inputs n:ZZ the dimension of the projective space p:ZZ a prime Outputs :Matroid the projective geometry of dimension n over F_p Description Text The projective geometry of dimension n over F_p is the matroid whose ground set consists of points in an n-dimensional projective space over F_p. The matroid structure is precisely the @TO2{simpleMatroid, "simple matroid"}@ associated to the realizable matroid of (F_p)^(n+1) (i.e. all vectors in an (n+1)-dimensional vector space over F_p) - the origin (being a loop) has been removed, and a representative is chosen for all parallel classes (= lines). Note that projective space has a stratification into affine spaces (one of each smaller dimension). In particular, deleting any hyperplane from PG(n, p) gives AG(n, p). Example PG22 = projectiveGeometry(2, 2) PG22 == specificMatroid "fano" A = transpose sub(matrix toList(((3:0)..(3:2-1))/toList), ZZ/2) -- all vectors in (ZZ/2)^3 areIsomorphic(PG22, simpleMatroid matroid A) PG32 = projectiveGeometry(3, 2) representationOf PG32 H = first hyperplanes PG32 areIsomorphic(affineGeometry(3, 2), PG32 \ H) SeeAlso affineGeometry /// doc /// Key getCycles (getCycles, Graph) Headline find cycles of graph Usage getCycles(G) Inputs G:Graph Outputs :List a list of (simple) cycles of G Description Text A cycle of G is a connected, 2-regular subgraph of G (i.e. every vertex has degree 2). This method returns all cycles of length at least 3, as ordered lists of vertices (for cycles of length 1 or 2, see the options Loops and ParallelEdges at @TO matroid@). This method is used to create the graphic matroid: the output is in bijection with the circuits of the graphic matroid (excluding loops and parallel edges). Example getCycles completeGraph 4 /// doc /// Key basisIndicatorMatrix (basisIndicatorMatrix, Matroid) Headline matrix of basis polytope Usage basisIndicatorMatrix M Inputs M:Matroid Outputs :Matrix Description Text The matroid (basis) polytope of a matroid on n elements lives in R^n, and is the convex hull of the indicator vectors of the bases. For uniform matroids, the basis polytope is precisely the hypersimplex: Example U24 = uniformMatroid(2, 4) A = basisIndicatorMatrix U24 Text In order to obtain an actual polytope, one must take the convex hull of the columns of the indicator matrix, which is provided by the Polyhedra package: Example needsPackage "Polyhedra" P = convexHull A vertices P Text The Gelfand-Goresky-MacPherson-Serganova characterizes which polytopes are basis polytopes for a matroid: namely, each edge is of the form $e_i - e_j$ for some $i, j$, where $e_i$ are the standard basis vectors. -- Example -- M = matroid({{0,1},{0,2},{0,3},{1,2},{2,3}}) -- n = #M.groundSet -- P = polytope M -- E = Polyhedra$faces(n - 2, P)/Polyhedra$vertices -- edges of P -- all(E, e -> sort flatten entries(e_0 - e_1) == ({-1} | toList(n-2:0) | {1})) -- GGMS criterion SeeAlso bases (independenceComplex, Matroid) /// doc /// Key (independenceComplex, Matroid) Headline independence complex of matroid Usage independenceComplex M Inputs M:Matroid Outputs :SimplicialComplex Description Text The independence complex of a matroid is the simplicial complex associated (via the Stanley-Reisner correspondence) to the circuit ideal of the matroid (which is a squarefree monomial ideal). This method uses the @TO SimplicialComplexes@ package to return an object of type @TO SimplicialComplex@. Example M = matroid({{0,1},{0,2},{0,3},{1,2},{2,3}}) independenceComplex M SeeAlso (independentSets, Matroid) (ideal, Matroid) (basisIndicatorMatrix, Matroid) /// doc /// Key maxWeightBasis (maxWeightBasis, Matroid, List) Headline maximum weight basis using greedy algorithm Usage maxWeightBasis(M, w) Inputs M:Matroid w:List a weight function Outputs :Set a maximum-weight basis obtained by the greedy algorithm Description Text For a matroid M on ground set E, a weight function on M is a function $w : E -> \mathbb{R}$, extended to all subsets of E by setting $w(X) := \sum_{x\in X} w(x)$. The greedy algorithm for finding a maximum-weight independent subset of E starts with the empty set, and proceeds by successively adding elements of E of maximum weight, which together with the elements already added, form an independent set. In this method, a weight function is specified by its list of values on E. Thus if $E = \{e_1, ..., e_n\}$, then w is represented as the list $\{w(e_1), ..., w(e_n)\}$. Matroids can be characterized via the greedy algorithm as follows: a set $\mathcal{I}$ of subsets of E is the set of independent sets of a matroid on E iff $\mathcal{I}$ is nonempty, downward closed, and for every weight function $w : E -> \mathbb{R}$, the greedy algorithm returns a maximal member of $\mathcal{I}$ of maximum weight. Example M = matroid completeGraph 4 bases M w1 = apply(M_*, e -> (toList e)#1) maxWeightBasis(M, w1) w2 = rsort w1 maxWeightBasis(M, w2) /// doc /// Key idealChowRing (idealChowRing, Matroid) Headline the defining ideal of the Chow ring Usage idealChowRing M Inputs M:Matroid Outputs :Ideal the defining ideal of the Chow ring of M Description Text The Chow ring of M is the ring R := QQ[x_F]/(I1 + I2), where $I1 = (\sum_{i_1\in F} x_F - \sum_{i_2\in F} x_F : i_1, i_2 \in M)$ and $I2 = (x_Fx_{F'} : F, F' incomparable)$, as $F$ runs over all proper nonempty flats of $M$. This is the same as the Chow ring of the toric variety associated to the Bergman fan of M. This ring is an Artinian standard graded Gorenstein ring, by a result of Adiprasito, Katz, and Huh: cf. https://arxiv.org/abs/1511.02888, Theorem 6.19. This method returns the defining ideal of the Chow ring, which lives in a polynomial ring with variable indices equal to the flats of M. To work with these subscripts, use "last baseName v" to get the index of a variable v, as shown below: Example M = matroid completeGraph 4 I = idealChowRing M basis comodule I (0.. hilbertFunction(i, I)) betti res minimalPresentation I apply(gens ring I, v -> last baseName v) SeeAlso latticeOfFlats cogeneratorChowRing /// doc /// Key cogeneratorChowRing (cogeneratorChowRing, Matroid) Headline cogenerator of the Chow ring of a matroid Usage cogeneratorChowRing M Inputs M:Matroid Outputs :RingElement the dual socle generator of the Chow ring of M Description Text If R is an Artinian Gorenstein k-algebra, then the Macaulay inverse system of R is generated by a single polynomial (in dual/differential variables), called the cogenerator (or dual socle generator) of R. By a result of Adiprasito, Katz, and Huh, the Chow ring of a matroid M is always Gorenstein. This function computes the cogenerator of the Chow ring of M, which is also called the volume polynomial of M. Note that this is a very fine invariant of M - indeed, this single polynomial can recover the entire Chow ring of M, and thus most of the lattice of flats of M. Example M = matroid completeGraph 4 I = idealChowRing M; betti I F = cogeneratorChowRing M T = ring F diff(gens((map(T, ring I, gens T)) I), F) SeeAlso latticeOfFlats idealChowRing /// doc /// Key specificMatroid (specificMatroid, String) Headline creates built-in matroid Usage specificMatroid(S) Inputs S:String the name of the matroid Outputs :Matroid Description Text Returns one of the named matroids below. Code UL { "fano", "nonfano", "V8+", "vamos", "pappus", "nonpappus", "AG32", "R10" } Text Many of these matroids are interesting for their non-representability or duality properties: Code UL { "The Fano matroid F7 is the matroid of the projective plane over F_2, and is representable only in characteristic 2. The non-Fano matroid is a relaxation of F7, and is representable only in characteristic not equal to 2.", "The Pappus matroid is an illustration of Pappus' theorem. By the same token, the non-Pappus matroid is a relaxation which is not representable over any field.", "The Vamos matroid V, which is a relaxation of V8+, is the smallest (size) matroid which is not representable over any field - indeed, it is not even algebraic. V8+ is identically self-dual, while V is isomorphic to its dual.", "AG32 is the affine geometry corresponding to a 3-dimensional vector space over F_2, and is identically self-dual, with circuits equal to its hyperplanes. A relaxation of AG32 is the smallest matroid not representable over any field, with fewer basis elements than V." } Example F7 = specificMatroid "fano" all(F7_*, x -> areIsomorphic(matroid completeGraph 4, F7 \ {x})) AG32 = specificMatroid "AG32" representationOf AG32 AG32 == dual AG32 R10 = specificMatroid "R10" representationOf R10 areIsomorphic(R10 \ set{0}, matroid completeMultipartiteGraph {3,3}) Caveat Notice that the ground set is a subset of \{0, ..., n-1\}   rather than \{1, ..., n\}. /// doc /// Key allMatroids (allMatroids, ZZ) Headline returns all n-element matroids Usage allMatroids n Inputs n:ZZ the size of the ground set Outputs :List of matroids on n elements Description Text This method returns a list of matroids on n elements, for small n (currently, n <= 8). This list is complete for isomorphism types of matroids on n elements, i.e. every matroid on n elements is @TO2{(areIsomorphic, Matroid, Matroid), "isomorphic"}@ to a unique matroid in this list. One can perform many verifications using this method: CannedExample i1 : L = allMatroids 5; #L o2 = 38 i3 : all(L, isWellDefined) o3 = true i4 : all(subsets(L, 2), S -> quickIsomorphismTest(S#0, S#1) == "false") o4 = true i5 : tally(L/fVector/values) o5 = Tally{{1, 1} => 5 } {1, 2, 1} => 6 {1, 3, 1} => 4 {1, 3, 3, 1} => 4 {1, 4, 1} => 2 {1, 4, 4, 1} => 3 {1, 4, 6, 1} => 2 {1, 4, 6, 4, 1} => 2 {1, 5, 1} => 1 {1, 5, 5, 1} => 1 {1, 5, 6, 1} => 1 {1, 5, 8, 1} => 1 {1, 5, 8, 5, 1} => 1 {1, 5, 10, 1} => 1 {1, 5, 10, 7, 1} => 1 {1, 5, 10, 10, 1} => 1 {1, 5, 10, 10, 5, 1} => 1 {1} => 1 o5 : Tally i6 : smallMatroids = flatten apply(6, i -> allMatroids i); -- all matroids on < 6 elements i7 : #smallMatroids o7 = 70 /// undocumented { (net, Matroid), Loops, ParallelEdges } TEST /// M = matroid({a, b, c, d}, {{a, b}, {a, c}}) assert(isWellDefined M and not isSimple M) assert(set bases M === set {set{0, 1}, set{0, 2}}) assert(set nonbases M === set {set {2, 3}, set {0, 3}, set {1, 3}, set {1, 2}}) assert(set circuits M === set {set {1, 2}, set {3}}) assert(M == matroid({a,b,c,d},{{b,c},{d}}, EntryMode => "circuits")) assert(not isDependent(M, {b})) assert(set independentSets_M 1 === set {set{0}, set{1}, set{2}}) assert(coloops M === {0}) assert(loops M === {3}) assert(rank_M {a,d} === 1) assert(closure_M {c,d} === {1, 2, 3}) assert(set hyperplanes M === set {set {0, 3}, set {1, 2, 3}}) assert(set flats M === set {set {3}, set {0, 3}, set {1, 2, 3}, set {0, 1, 2, 3}}) assert(values fVector M === {1, 2, 1}) D = dual M assert(D == dual M) N1 = M \ {d} assert((N1_*, set bases N1) === ({a, b, c}, set {set {0, 1}, set {0, 2}})) N2 = M / set{1} assert((N2_*, set bases N2) === ({a, c, d}, set {set {0}})) MA = matroid matrix{{0,4,-1,6},{0,2/3,7,1}} assert(areIsomorphic(MA, M)) /// TEST /// assert(not isWellDefined matroid({a,b,c,d}, {{b,c},{b,d}}, EntryMode=>"nonbases")) M = matroid({a,b,c,d}, {}, EntryMode => "nonbases") assert(isWellDefined M) assert(ideal M == 0) assert(M == matroid({a,b,c,d}, {}, EntryMode => "circuits")) assert(M == uniformMatroid(4,4)) assert(#bases M == 1) assert((try fundamentalCircuit(M, set{1,2}, 3)) === null) R = ZZ/101[x_0..x_3] assert(M == matroid monomialIdeal 0_R) assert((try matroid ideal 1_R) === null) assert((try matroid ideal()) === null) N = matroid({a,b,c,d}, {{}}) assert(rank N == 0 and isWellDefined N and N == dual M) M = matroid matrix{{1,0,1,1},{0,1,1,1}} assert(M \ set{0} == M \ set{1} and not M \ set{0} == M \ set{2}) assert(fundamentalCircuit (M, (bases M)#2, 3) === set{2, 3}) assert(fundamentalCircuit (M, M_{0,1}, M_3) === set{0,1,3}) assert(try fundamentalCircuit (M, M_{1,2}, M_3) else null === null) assert(toString tuttePolynomial M == "x^2+x*y+y^2+x+y") /// TEST /// S = uniformMatroid(2,4) ++ matroid completeGraph 3 assert(S == uniformMatroid(2,4) + matroid completeGraph 3) C = components S assert(S == C#0 ++ C#1) M = matroid(graph({{0,1},{1,2},{0,2},{3,4},{4,5},{3,5}}), Loops => {0,3,5}) assert(#loops M == 3 and #connectedComponents representationOf M == 2) C = components M assert(#C == 5 and #getIsos(M, fold(C, (a, b) -> a ++ b)) == 432) assert(characteristicPolynomial M == 0) M1 = matroid({a,b,c,d}, {{a},{b},{c}}) M2 = matroid({a,b,c,d}, {{b},{c},{d}}) assert(M1 + M2 == uniformMatroid(2,4)) F7 = specificMatroid "fano" NF = specificMatroid "nonfano" assert(all({F7 + NF, F7 + F7, NF + NF}, M -> M == uniformMatroid(6, 7))) /// TEST /// M5 = matroid completeGraph 5 U24 = uniformMatroid(2, 4) M4 = matroid completeGraph 4 assert(#bases M5 === 125 and #bases U24 == 6) assert(set getIsos(U24, dual U24) === set permutations 4) assert(hasMinor(M5, M4)) minorM5 = minor(M5, set{9}, set{3,5,8}) assert(areIsomorphic(minorM5, M4)) assert(not hasMinor(M5, U24)) /// TEST /// K4 = completeGraph 4 M4 = matroid K4 assert(toString tuttePolynomial M4 === "x^3+y^3+3*x^2+4*x*y+3*y^2+2*x+2*y") assert(tutteEvaluate(M4, 2, 1) === 38) assert(representationOf M4 === K4) A = random(ZZ^3,ZZ^5) assert(representationOf matroid A === A) /// TEST /// U34 = uniformMatroid(3,4) I = idealChowRing U34 assert((0.. numColumns basis(i, comodule I)) === (1,7,1)) F = cogeneratorChowRing U34 phi = map(ring F, ring I, gens ring F) assert(0 == diff(gens phi I, F)) /// TEST /// F7 = specificMatroid "fano" PG22 = projectiveGeometry(2,2) A = transpose sub(matrix toList(((3:0)..(3:2-1))/toList), ZZ/2) assert(PG22 == F7 and areIsomorphic(PG22, simpleMatroid matroid A)) M4 = matroid completeGraph 4 assert(all(F7_*, x -> areIsomorphic(M4, F7 \ {x}))) w = {0, log(2), 4/3, 1, -4, 2, pi_RR} assert(maxWeightBasis(F7, w) === set{2,5,6}) assert(maxWeightBasis(F7, rsort w) === set{0,1,2}) /// TEST /// M1 = matroid graph({{a,b},{b,c},{c,d},{d,e},{e,f},{f,g},{f,h},{c,h},{c,f},{a,g},{d,g}}) M2 = matroid graph({{a,b},{b,c},{c,d},{d,e},{e,f},{f,g},{f,h},{c,h},{c,f},{a,g},{a,h}}) T = ZZ[x,y] assert(isWellDefined M1 and isWellDefined M2) assert(tuttePolynomial(M1, T) === tuttePolynomial(M2, T)) F1 = set{0,1,2,3,7} F2 = F1 + set{5,8} assert(areIsomorphic(uniformMatroid(2,2), minor(M1, F1, M1.groundSet - F2))) assert(areIsomorphic(M1, matroid graph edges graph M1_*)) Delta = independenceComplex M1 F = fVector Delta assert(ideal Delta == ideal M1 and F === fVector independenceComplex M2) assert((sort keys F)/(k -> F#k) === {1,11,55,164,319,409,324,125}) assert(not areIsomorphic(M1, M2)) /// TEST /// R = QQ[x_0..x_6] M1 = matroid(graph(toList(0..4), {set{0,3},set{0,4},set{1,3},set{1,4},set{2,3},set{2,4}}), ParallelEdges => {set{2,4}}) M2 = matroid ideal(x_0*x_1*x_2*x_3,x_0*x_1*x_2*x_4,x_0*x_1*x_3*x_4,x_0*x_2*x_3*x_4,x_1*x_2*x_3*x_4,x_5*x_6) assert(betti res ideal M1 === betti res ideal M2) assert(areIsomorphic(M1, M2) == false) M3 = matroid ideal (x_0*x_1*x_2,x_0*x_3*x_4,x_1*x_2*x_3*x_4,x_0*x_1*x_3*x_5,x_0*x_2*x_3*x_5,x_1*x_2*x_3*x_5,x_0*x_1*x_4*x_5,x_0*x_2*x_4*x_5,x_1*x_2*x_4*x_5,x_1*x_3*x_4*x_5,x_2*x_3*x_4*x_5,x_0*x_1*x_3*x_6,x_0*x_2*x_3*x_6,x_1*x_2*x_3*x_6,x_0*x_1*x_4*x_6,x_0*x_2*x_4*x_6,x_1*x_2*x_4*x_6,x_1*x_3*x_4*x_6,x_2*x_3*x_4*x_6,x_1*x_5*x_6,x_0*x_2*x_5*x_6,x_0*x_3*x_5*x_6,x_2*x_3*x_5*x_6,x_0*x_4*x_5*x_6,x_2*x_4*x_5*x_6,x_3*x_4*x_5*x_6) M4 = matroid ideal (x_0*x_1*x_2,x_0*x_3*x_4,x_1*x_2*x_3*x_4,x_0*x_1*x_3*x_5,x_0*x_2*x_3*x_5,x_1*x_2*x_3*x_5,x_0*x_1*x_4*x_5,x_0*x_2*x_4*x_5,x_1*x_2*x_4*x_5,x_1*x_3*x_4*x_5,x_2*x_3*x_4*x_5,x_0*x_1*x_3*x_6,x_0*x_2*x_3*x_6,x_1*x_2*x_3*x_6,x_0*x_1*x_4*x_6,x_0*x_2*x_4*x_6,x_1*x_2*x_4*x_6,x_1*x_3*x_4*x_6,x_2*x_3*x_4*x_6,x_0*x_5*x_6,x_1*x_2*x_5*x_6,x_1*x_3*x_5*x_6,x_2*x_3*x_5*x_6,x_1*x_4*x_5*x_6,x_2*x_4*x_5*x_6,x_3*x_4*x_5*x_6) assert(betti res ideal M3 === betti res ideal M4 and betti res dual ideal M3 === betti res dual ideal M4) assert(betti res ideal dual M3 === betti res ideal dual M4 and betti res dual ideal dual M3 === betti res dual ideal dual M4) assert(areIsomorphic(M3, M4) == false) /// TEST /// G0 = graph(toList(0..5), {{0, 3}, {4, 0}, {0, 5}, {4, 1}, {5, 1}, {5, 2}, {4, 3}, {5, 3}, {4, 5}}) G1 = graph(toList(0..5), {{0, 3}, {4, 0}, {0, 5}, {1, 3}, {4, 1}, {5, 2}, {4, 3}, {5, 3}, {4, 5}}) G2 = graph(toList(0..5), {{0, 2}, {4, 0}, {0, 5}, {1, 3}, {4, 1}, {5, 1}, {4, 2}, {5, 2}, {4, 5}}) (M0, M1, M2) = (G0, G1, G2)/matroid assert(not(M0 == M1) and not(M1 == M2) and not(M0 == M2)) assert((#getIsos(M0,M1), #getIsos(M1,M0)) == (8,8)) T = ZZ[x,y] assert(tuttePolynomial(M0, T) == tuttePolynomial(M1, T) and tuttePolynomial(M1, T) == tuttePolynomial(M2, T)) G = graph({{0,1},{0,2},{1,2},{2,3},{3,4},{4,5},{4,6},{5,6}}) -- bowtie graph M = matroid G assert(set coloops M === set {4,3}) p = {6, 0, 5, 1, 4, 7, 2, 3} assert(values isomorphism (M, matroid(M_*, (circuits M)/(c -> c/(i -> p#i)), EntryMode => "circuits")) === p) /// TEST /// AG32 = specificMatroid "AG32" assert(AG32 == affineGeometry(3,2)) assert(set circuits AG32 === set hyperplanes AG32 and #circuits AG32 == 14) isos = getIsos(AG32, dual AG32) assert(#isos == 1344 and member(toList(0..7), isos)) V8plus = specificMatroid "V8+" assert(V8plus == dual V8plus) V = specificMatroid "vamos" assert(V == relaxation(V8plus, set{4,5,6,7})) isos = getIsos(V, dual V) assert(#isos == 64 and not member(toList(0..7), isos)) assert(hasMinor(V, uniformMatroid(2,4))) R10 = specificMatroid "R10" assert(#getIsos(R10 \ set{0}, matroid completeMultipartiteGraph {3,3}) == 72) /// TEST /// P8 = matroid(id_((ZZ/3)^4) | matrix{{0_(ZZ/3),1,1,-1},{1,0,1,1},{1,1,0,1},{-1,1,1,0}}) aut = getIsos (P8, P8) -- automorphism group is transitive assert(all(subsets(P8.groundSet,2)/toList, s -> any(aut, sigma -> sigma_(s#0) == s#1))) sigma1 = {7,6,5,4,0,1,2,3} sigma2 = {1,3,0,2,5,7,4,6} assert(member(sigma1, aut) and member(sigma2, aut)) S8 = matroid(id_((ZZ/2)^4) | matrix{{0_(ZZ/2),1,1,1},{1,0,1,1},{1,1,0,1},{1,1,1,1}}) F7 = specificMatroid "fano" assert(#select(S8_*, x -> areIsomorphic(S8 / {x}, F7)) == 1) assert(#select(S8_*, x -> areIsomorphic(S8 \ {x}, dual F7)) == 1) assert(#getIsos(F7, F7) == 168) /// TEST /// smallMatroids = apply(6, i -> allMatroids i) assert(smallMatroids/(l -> #l) == {1,2,4,8,17,38}) smallMatroids = flatten smallMatroids assert(all(smallMatroids, isWellDefined)) assert(not any(subsets(smallMatroids, 2), S -> areIsomorphic(S#0, S#1))) assert(all(smallMatroids_{1..69}, M -> areIsomorphic(M, fold(components M, (a, b) -> a ++ b)))) /// end-- restart loadPackage("Matroids", Reload => true) uninstallPackage "Matroids" installPackage "Matroids" installPackage("Matroids", RemakeAllDocumentation => true) viewHelp "Matroids" check "Matroids"