restart:matroids.mv v1.061110Here are a few matroid operations.
Although it is not the most compact way of representing a matroid,
I have chosen to let matroids be defined by their bases. Therefore, each matroid M here is of the form
M=[E,B] where E is an (unordered) set
and B is an (unordered) set of (unordered) bases.
The functions are:SuperSets(F,T) := the members of F that contain T
UpperCone(E,F) := the subsets of E that contain some member of F
LowerCone(F) := the sets that are contained in some member of F
MinimalSets(F) := the minimal sets of F, a family of sets MaximalSets(F) := the maximal sets of F, a family of sets
Complements(E,F) := the complements in a set E of the members of a family F
CycleMatroid(G) := the cycle matroid M(G) of a graf G=[V,E] VectorMatroid(A,p) := the vector matroid M[A] of a matrix A over the field Z_p where p is prime.
If A is real or complex, then set p=0.
Uniform(r,n) := the uniform matroid U_{r,n}Wheel(r) := the wheel graph on r+1 vertices, i.e., an r-cycle with an extra vertex adjacent to all r vertices
Matroid(M,fam) := the basis form [E,B] of the matroid M=[E,F] where F is a family of type given by fam: fam = bases, independentset, dependentsets, circuits, hyperplanes, opensets, flats, (=)closedsets, spanningsets, cobases, coindependentsets, codependentsets, cocircuits, (=)bonds, cohyperplanes, coopensets, coflats, (=)coclosedsets, cospanningsets
IsMatroid(M) := checks whether M is a matroid, by verifying that axiom (I3) is satisfiedIsEquivalent(M,N) := checks whether M and N are isomorphic
IsMinor(M,N) := checks whether M contains N as a minor
IsRepresentable(M,p) := checks whether M is representable over GF(p), p prime; if it is, then a representation is given
IsPMD(M) := checks whether M is a Perfect Matroid Design (i.e., a flat's rank determines its size)IsMD(M) := checks whether M is a Matroid Design (i.e., all hyperplanes have fixed size)Loops(M) := the loops of MColoops(M) := the coloops of MBases(M) := the bases of MIndependentSets(M) := the independent sets of M
DependentSets(M) := the dependent sets of M
Circuits(M) := the circuits of M
Cocircuits(M) := the cocircuits of M
Hyperplanes(M) := the hyperplanes of MOpenSets(M) := the open sets of MFlats(M) := the closed sets, or flats, of M MRank(M,X) := the rank of a set X in MClosure(M,X) := the closure of a set X in MFundCircuit(M,e,I) := the fundamental circuit C(e,I) in M, I independent
Relaxations(M) := the relaxations of M (if any) IsLoop(M,e) := checks whether e is a loop of MIsColoop(M,e) := checks whether e is a coloop of MParallelClasses(M) := the parallel classes of M (i.e., the partition of M's elements defined by the parallel elements; one class is the set of loops)
MSimple(M) := the simplification of M
MDual(M) := the dual matroid of MMDelete(M,X) := the deletion M\X of M by a set XMContract(M,X) := the contraction M/X of M by a set XTruncation(M) := the truncation of MMJoin(M,N) := the join, or union, of matroids M, N
DirectSum(M,N) := the direct sum of matroids M, N with disjoint ground sets (=MJoin(M,N) but quicker)
MSeries(M,N) := the series connection between matroids M and N whose ground sets meet in a single element
MParallel(M,N) := the parallel connection between matroids M and N whose ground sets meet in a single element
TwoSum(M,N) := the 2-sum of matroids M and N whose ground sets meet in a single (simple) elementRankgenpoly(M,x,y) := the rank generating polynomial of MMTuttepoly(M,x,y) := the Tutte polynomial of MMCharpoly(M,x) := the characteristic polynomial of M (= p(M;x))Coboundary(M,a,x,y) := the coboundary polynomial of M
CharSets(M,a) := the characteristic sets of M wrt. a (i.e., the sets T s.t. p(M.T;a)<>0)IsSeparation(M,X,Y,k) := checks whether (X,Y) is a k-separation of M
IsVSeparation(M,X,Y,k) := checks whether (X,Y) is a vertical k-separation of M
IsCSeparation(M,X,Y,k) := checks whether (X,Y) is a cyclic k-separation of M
IsSeparated(M,k) := checks whether M is k-separated
IsVSeparated(M,k) := checks whether M is vertically k-separated
IsCSeparated(M,k) := checks whether M is cyclically k-separated
Connectivity(M) := the (Tutte) connectivity of M
VConnectivity := the vertical connectivity of M
CConnectivity := the cyclic connectivity of M
dmin(M) := the minimum size of a cocircuit in MHigherWeights(M) := the weight heirarchy of MAMTest(M,a,t) := checks whether t<dmin(M) and the Assmus-Mattson criterium holds for M,a,tIsRelaxedDesign(F,t) := checks whether F is a relaxed t-design (the blocks needn't have constant size)
IsDesign(F,t) := checks whether F is a t-design
mplysupports(A,p,m) := returns the supports of codeword m-tuples of the code generated by A over F_p, listed by size.collectv(p,x,arg) := the function "collect" tweaked so as to be able handle polynomials p that do not contain x As well, a number of specific matroids have been defined (for more, see eg. the appendix in Matroid Theory by J. Oxley):P6, Q6, R6, W3, F7, F7m (=F7-), P7, W3p (=W^3+), F8, L8, P8, Q8, R8, S8, T8, V8,MJ(=J),MW4(=the 4-wheel matroid),W4(=the 4-whirl matroid), R9, R10, R12, AG32(=AG(3,2)), AG32r (=AG(3,2)'), AG23(=AG(2,3)), PG23(=PG(2,3)), S5612(=S(5,6,12)),Q3GF3(=Q_3(GF(3)^*)),Pappus, nonPappus (=non-Pappus), nonDesargues (=non-Desargues),
nonPappusi (=non-Pappus with i=0,1,2,3 lines; nonPappus0=nonPappus)I apologise for the messy coding; I'll improve this lot if my Maple skills get better.If you have any suggestions, improvements, additions, or applications, I would be very grateful to hear from you.Best regards,Thomas Britz :)+<with(combinat,powerset):with(combinat,choose):with(combinat,permute):with(combinat,cartprod):
with(LinearAlgebra):with(networks):
collectv := proc(p,x,arg)
if member(x,indets(p)) then return collect(p,x,arg) else return p fi; end proc:
SuperSets := proc(F,T) local X,G: G:={}:
for X in F do if T subset X then G:=G union {X} fi:od: return G: end proc:
UpperCone := proc(E,F) return `union`(seq(SuperSets(powerset(E),T),T=F)): end proc:
LowerCone := proc(F) return `union`(seq(powerset(T),T=F)): end proc:
Complements := proc(E,F) return {seq(E minus X,X=F)}; end proc:
MaximalSets := proc(F) local T,G: G:={}:
for T in F do if SuperSets(F,T)<>{T} then G:={T,seq(S,S=G)}: fi:od: return F minus G; end proc:
MinimalSets := proc(F) local U: U:=`union`(seq(X,X=F)):
return Complements(U,MaximalSets(Complements(U,F))); end proc:
Matroid := proc(M,f)
if f=`bases` then return M else
if f=`independentsets` then return [M[1],MaximalSets(M[2])] else
if f=`dependentsets` then return [M[1],MaximalSets(powerset(M[1]) minus M[2])] else
if f=`circuits` then return [M[1],MaximalSets(powerset(M[1]) minus UpperCone(M[1],M[2]))] else
if f=`hyperplanes` then return MDual([M[1],MaximalSets(powerset(M[1]) minus UpperCone(M[1],Complements(M[1],M[2])))]) else
if f=`opensets` then return MDual([M[1],MaximalSets(powerset(M[1]) minus UpperCone(M[1],M[2] minus {{}}))]) else
if f=`flats` or f=`closedsets` then return MDual([M[1],MaximalSets(powerset(M[1]) minus UpperCone(M[1],Complements(M[1],M[2]) minus {{}}))]) else
if f=`spanningsets` then return [M[1],MinimalSets(M[2])] else
if f=`cobases` then return MDual(M) else
if f=`coindependentsets` then return MDual([M[1],MaximalSets(M[2])]) else
if f=`codependentsets` then return MDual([M[1],MaximalSets(powerset(M[1]) minus M[2])]) else
if f=`cocircuits` or f=`bonds` then return MDual([M[1],MaximalSets(powerset(M[1]) minus UpperCone(M[1],M[2]))]) else
if f=`cohyperplanes` then return [M[1],MaximalSets(powerset(M[1]) minus UpperCone(M[1],Complements(M[1],M[2])))] else
if f=`coopensets` then return [M[1],MaximalSets(powerset(M[1]) minus SuperSets(M[1],M[2]))] else
if f=`coflats` or f=`coclosedsets` then return [M[1],MaximalSets(powerset(M[1]) minus UpperCone(M[1],Complements(M[1],M[2])))] else
if f=`cospanningsets` then return MDual([M[1],MinimalSets(M[2])]) fi:fi:fi:fi:fi:fi:fi:fi:fi:fi:fi:fi:fi:fi:fi:fi: end proc:
MRank := proc(M,X) return max(seq(nops(B intersect X),B=M[2])); end proc:
MDual := proc(M) return [M[1],Complements(M[1],M[2])]; end proc:
Loops := proc(M) return M[1] minus `union`(seq(B,B=M[2])); end proc:
Coloops := proc(M) return `intersect`(seq(B,B=M[2])); end proc:
MDelete := proc(M,X) return [M[1] minus X,MaximalSets({seq(B minus X,B=M[2])})];end proc:
MContract := proc(M,X) return MDual(MDelete(MDual(M),X)); end proc:
Relaxations := proc(M) return seq([M[1],M[2] union {B}],B=`intersect`(Hyperplanes(M),Circuits(M))); end proc:
Coboundary:= proc(M,a,x,y) local N,n: N:=MDual(M): n:=nops(M[1]):
return collectv(add(a^(-MRank(N,S))*(a*y)^nops(S)*(x-y)^(n-nops(S)), S=powerset(M[1])),y,factor); end proc:
Rankgenpoly := proc(M,x,y) local n,r: n:=nops(M[1]): r:=nops(M[2][1]):
return add(x^(r-MRank(M,S))*y^(nops(S)-MRank(M,S)),S=powerset(M[1])); end proc:
MTuttepoly := proc(M,x,y) return expand(Rankgenpoly(M,x-1,y-1)); end proc:
MCharpoly := proc(M,a) local r: r:=nops(M[2][1]):
return collectv(add((-1)^nops(S)*a^(r-MRank(M,S)),S=powerset(M[1])),a,factor); end proc:
CharSets := proc(M,a) local G,T: G:={}:
for T in powerset(M[1]) do if (MCharpoly(MContract(M,M[1] minus T),a)<>0) then G:=G union {T}: fi:od:
return G;end proc:
Bases := proc(M) return M[2]; end proc:
IndependentSets := proc(M) return LowerCone(M[2]); end proc:
DependentSets := proc(M) return powerset(M[1]) minus IndependentSets(M); end proc:
Circuits := proc(M) return MinimalSets(DependentSets(M)); end proc:
Cocircuits := proc(M) return Circuits(MDual(M)); end proc:
Hyperplanes := proc(M) return Complements(M[1],Cocircuits(M)); end proc:
OpenSets := proc(M) return {seq(`union`(seq(Y,Y=X)),X=powerset(Cocircuits(M)))}; end proc:
Flats := proc(M) return Complements(M[1],OpenSets(M)); end proc:
Closure := proc(M,X) return MinimalSets(SuperSets(Flats(M),X))[1]; end proc:
FundCircuit := proc(M,el,II) return seq(C,C=Circuits(M) intersect powerset(II union {el})); end proc:
IsLoop := proc(M,e) return evalb(MRank(M,{e})=0); end proc:
IsColoop := proc(M,e) return evalb(MRank(MDual(M),{e})=0); end proc:
PClasses := proc(M) local PC,eSets,e: PC := (Circuits(M) intersect choose(M[1],2)):
if Loops(M)<>{} then PC:=PC union {`union`(Loops(M))}:fi:
PC:=PC union {seq({e},e=M[1] minus `union`(seq(S,S=PC)))}:
for e in M[1] do eSets:=SuperSets(PC,{e}): PC:=(PC minus eSets) union {`union`(seq(S,S=eSets))}:od:
return PC; end proc:
MSimple := proc(M) local MM,PC,X: MM:=MDelete(M,`union`(Loops(M))):
PC:=PClasses(MM) minus {seq({e},e=MM[1])}: for X in PC do MM:=MDelete(MM,X minus {X[1]}):od:
return MM;end proc:
dmin := proc(M) if M[2]={{}} then print(`There are no cocircuits.`);
else return min(seq(nops(P),P=Cocircuits(M)));fi: end proc:
IsMatroid := proc(M) local Ind,I1,I2,X,q: q:=true: Ind:=IndependentSets(M):
for I1 in Ind do for I2 in Ind while nops(I2)=nops(I1)+1 do
q:=q and convert({seq(member(I1 union {X},Ind),X=I2 minus I1)},`or`): od:od: return q; end proc:
IsEquivalent := proc(M,N) local ii,ME,NE,PB:
if (nops(M[1])<>nops(N[1]) or nops(M[2])<>nops(N[2])) then return false fi:
if {seq(nops(PB),PB=IndependentSets(M))}<>{seq(nops(PB),PB=IndependentSets(N))} then return false fi:
if {seq(nops(PB),PB=IndependentSets(MDual(M)))}<>{seq(nops(PB),PB=IndependentSets(MDual(N)))} then return false fi:
if {seq(nops(PB),PB=Circuits(M))} <>{seq(nops(PB),PB=Circuits(N))} then return false fi:
if {seq(nops(PB),PB=Cocircuits(M))}<>{seq(nops(PB),PB=Cocircuits(N))} then return false fi:
ME:=[seq(ii,ii=M[1])]: NE:=[seq(ii,ii=N[1])]:
for PB in permute(NE) do
if N[2]={seq(subs([seq(ME[ii]=PB[ii],ii=1..nops(M[1]))],S),S=M[2])} then return true; fi:od:
return false;end proc:
IsMinor := proc(M,N) local SSet,CSet,DSet:
for SSet in choose(M[1],nops(M[1])-nops(N[1])) do
for CSet in powerset(SSet) do DSet := SSet minus CSet:
if IsEquivalent(MDelete(MContract(M,CSet),DSet),N) then return true; fi:od:od:
return false;end proc:
IsRepresentable := proc(M,p) local A,B,C,E,r,n,i,j,m,mm,en,EN:
B:=M[2][1]: E:=[seq(e,e=B),seq(e,e=M[1] minus B)]: n:=nops(E): r:=nops(B): en:=0:
if n=r then print(I); return true; fi:
A:=Matrix(r,n): A[1..r,1..r]:=IdentityMatrix(r): A[1..r,r+1..n]:=0:
for j from r+1 to n do C := FundCircuit(M,E[j],{seq(e,e=E[1..r])}):
for i from 1 to r do if {E[i]} subset C then A[i,j]:=1: fi:od:od:
if (r=1 or n-r=1) then print(evalm(A)); return true; fi:
i:=1: m:=0: for j from 1 to r do mm:=`add`(A[j,jj],jj=r+1..n): if mm>m then i:=j: m:=mm: fi:od:
if i>1 then A[[1,i],[r+1..n]]:=A[[i,1],[r+1..n]]: fi:
i:=r+1: m:=0: for j from r+1 to n do mm:=`add`(A[jj,j],jj=1..r): if mm>m then i:=j: m:=mm: fi: od:
if i>r+1 then A[[1..r],[r+1,i]]:=A[[1..r],[i,r+1]]: fi:
for i from 2 to r do for j from r+2 to n do if A[i,j]=1 then en:=en+1: EN[en]:=[i,j,1]: fi:od:od:
j := en: while j>0 do
for i from 1 to en do A[EN[i][1],EN[i][2]]:=EN[i][3]: od:
if IsEquivalent(M,VectorMatroid(A,p)) then print(evalm(A)); return true; fi:
j := en: while (j>0 and EN[j][3]=p-1) do EN[j][3]:=1: j:=j-1: od:
if j>0 then EN[j][3]:=EN[j][3]+1: fi:od:
return false;
end proc:
IsSeparation := proc(M,X,Y,k)
return (evalb(min(nops(X),nops(Y))>=k) and evalb(MRank(M,X)+MRank(M,Y)<nops(M[2][1])+k)); end proc:
IsVSeparation := proc(M,X,Y,k)
return (evalb(min(MRank(M,X),MRank(M,Y))>=k) and evalb(MRank(M,X)+MRank(M,Y)<nops(M[2][1])+k)); end proc:
IsCSeparation := proc(M,X,Y,k)
return (evalb(MRank(M,X)<nops(X)) and evalb(MRank(M,Y)<nops(Y)) and evalb(MRank(M,X)+MRank(M,Y)<nops(M[2][1])+k)); end proc:
IsSeparated := proc(M,k) local X,i:
for X in `union`(seq(choose(M[1] minus {M[1][1]},i),i=k..nops(M[1])-k)) do
if IsSeparation(M,X,M[1] minus X,k) then return true; fi:od: return false;end proc:
IsVSeparated := proc(M,k) local X,i:
for X in `union`(seq(choose(M[1] minus {M[1][1]},i),i=k..nops(M[1])-k)) do
if IsVSeparation(M,X,M[1] minus X,k) then return true; fi:od: return false;end proc:
IsCSeparated := proc(M,k) local X:
for X in powerset(M[1] minus {M[1][1]}) intersect DependentSets(M) do
if IsCSeparation(M,X,M[1] minus X,k) then return true; fi:od: return false;end proc:
Connectivity := proc(M) local k,i:
if nops(M[2])=binomial(nops(M[1]),nops(M[2][1])) then return infinity;fi: k:=infinity:
for i from floor(nops(M[1])/2) to 1 by -1 do if IsSeparated(M,i) then k:=i: fi:od: return k; end proc:
VConnectivity := proc(M) local k,i: k:=nops(M[2][1]): for i from floor(nops(M[1])/2) to 1 by -1 do
if IsVSeparated(M,i) then k:=i: fi:od: return k; end proc:
CConnectivity := proc(M) local k,i: k:=nops(M[1])-nops(M[2][1]):
for i from nops(M[1])-nops(M[2][1]) to 1 by -1 do if IsCSeparated(M,i) then k:=i:fi:od:return k; end proc:
IsMD := proc(M) return evalb(nops({seq(nops(X),X=Hyperplanes(M))})=1); end proc:
Truncation := proc(M) return [M[1],`union`(seq(choose(B,nops(M[2][1])-1),B=M[2]))]; end proc:
HigherWeights := proc(M) local N,hw: N:=M: hw:={}:
while nops(N[2])>1 do hw:={seq(X,X=hw),dmin(N)}: N:=Truncation(N): od: return hw; end proc:
IsPMD := proc(M) local N,S,T,i: S:=true: N:=M:
while nops(N[2])>1 do S:=S and evalb(nops({seq(nops(X),X=Hyperplanes(N))})=1): N:=Truncation(N): od:
return S; end proc:
CycleMatroid := proc(G) local E,S,ST,r: E:=edges(G): ST:={}: r:=rank(E,G):
for S in choose(edges(G),r) do if rank(S,G)=r then ST:={S,seq(X,X=ST)} fi:od: return [E,ST]; end proc:
VectorMatroid := proc(A,p) local AA,S,ST,k,r,n:
AA:= convert(A,Matrix): ST:={}: r := RowDimension(AA): n := ColumnDimension(AA):
if p=0 then k := Rank(AA):
for S in choose(n,k) do if Rank(SubMatrix(AA,[1..r],S))=k then ST := {seq(Y,Y=ST),convert(S,set)} fi:od
else Modular[RowReduce](p,Modular[Mod](p,A,integer[4]),r,n,0,0,0,'k',0,0,false):
if k=0 then return [{$1..n},{{}}] else for S in choose(n,k) do Modular[RowReduce](p,Modular[Mod](p,SubMatrix(A,[1..k],S),integer[4]),k,k,0,0,0,'rk',0,0,false):
if rk=k then ST:={seq(Y,Y=ST),convert(S,set)} fi:od:fi:fi:
return [{$1..n},ST]; end proc:
Uniform := proc(r,n) return [{$1..n},{seq(convert(X,set),X=choose(n,r))}]; end proc:
Wheel := proc(r) local v,G,r2: G:=networks[cycle](r): r2:=r+1:
networks[addvertex](r2,G):for v in (networks[vertices](G) minus {r2}) do networks[addedge]({v,r2},G): od:
return G; end proc:
MJoin := proc(M,N)
return [M[1] union N[1], MaximalSets({seq(seq(X union Y,Y=IndependentSets(N)),X=IndependentSets(M))})];
end proc:
DirectSum := proc(M,N) return [M[1] union N[1],{seq(seq(X union Y,Y=N[2]),X=M[2])}]; end proc:
MSeries := proc(M,N) local MM,B,P,p: P:=M[1] intersect N[1]:
if nops(P)<>1 then printf(`The two ground sets must share precisely one element.`); return;fi: p:=P[1]:
if (IsLoop(M,p) or IsColoop(N,p)) then MM:=DirectSum(MDelete(M,p),N) else
if (IsLoop(N,p) or IsColoop(M,p)) then MM:=DirectSum(M,MDelete(N,p)) else
B:={seq(seq(`if`((B1 intersect B2)={},B1 union B2,NULL), B2=N[2]), B1=M[2])}:
MM:=[M[1] union N[1],B]:fi:fi: return MM;end proc:
MParallel := proc(M,N) if nops(M[1] intersect N[1])<>1 then
printf(`The two ground sets must share precisely one element.`); return; fi:
return MDual(MSeries(MDual(M),MDual(N)));end proc:
TwoSum := proc(M,N) local P,p: P:=M[1] intersect N[1]:
if nops(P)<>1 then printf(`The two ground sets must share precisely one element.`); return;fi:p:=P[1]:
if (IsLoop(M,p) or IsLoop(N,p)) then printf(`p is a loop`); return; fi:
if (IsColoop(M,p) or IsColoop(N,p)) then printf(`p is a coloop`); return; fi:
return MContract(MSeries(M,N),P); end proc:
AMTest := proc(M,a,t) local d: d:=dmin(M):
return evalb((t<d) and (nops({seq(degree(X,y),X={op(Coboundary(MDual(M),a,1,y)-1)})} intersect {$1..(nops(M[1])-t)})<=d-t)); end proc:
IsRelaxedDesign := proc(F,t) local U: U:=`union`(seq(X,X=F)):
return evalb(nops({seq(nops(SuperSets(F,T)),T=choose(U,t))})=1); end proc:
IsDesign := proc(F,t) local U: U:=`union`(seq(X,X=F)):
return evalb(IsRelaxedDesign(F,t) and nops({seq(nops(T),T=F)})=1); end proc:
mplysupports := proc(A,p,m) local r,n,v,C,Cm,Supp,T:
r := RowDimension(convert(A,Matrix)):
n := ColumnDimension(convert(A,Matrix)):
C := [seq([seq(add(A[i,j],i=S) mod p, j=1..n)], S=powerset(r))]:
T := cartprod([seq(C,i=1..m)]):
Cm:= [seq(T[nextvalue](), i=1..p^(m*r))]:
Supp:= [seq({seq(`if`(0=add(w[j],w=S),NULL,j), j=1..n)}, S=Cm)]:
return [seq([seq(`if`(nops(S)=i,S,NULL),S=Supp)],i=0..n)]; end proc:
E:={$1..6}: B:=choose(E,3):
P6 := [E,B minus {{1,2,3}}]:
Q6 := [E,B minus {{1,2,3},{3,4,5}}]:
R6 := [E,B minus {{1,2,3},{4,5,6}}]:
W3 := [E,B minus {{1,2,3},{3,4,5},{5,6,1}}]:
E:={$1..7}: B:=choose(E,3):
F7m:= [E,B minus {{1,2,3},{3,4,5},{5,6,1},{1,7,4},{3,7,6},{5,7,2}}]:
F7 := [E,B minus {{1,2,3},{3,4,5},{5,6,1},{1,7,4},{3,7,6},{5,7,2},{2,4,6}}]:
P7 := [E,B minus {{1,2,3},{3,4,5},{5,6,1},{1,7,4},{2,7,6}}]:
W3p:= [E,B minus {{1,2,3},{1,7,3},{3,4,5},{5,6,1},seq({2,7,x},x={1,3,4,5,6})}]:
E:={$1..8}: B:=choose(E,4):
AG32 :=[E,B minus{{1,2,3,4},{1,2,5,6},{1,2,7,8},{1,3,5,7},{1,3,6,8},{1,4,5,8},{1,4,6,7},
{2,3,5,8},{2,3,6,7},{2,4,5,7},{2,4,6,8},{3,4,5,6},{3,4,7,8},{5,6,7,8}}]:
AG32r:=[E,B minus{{1,2,3,4},{1,2,5,6},{1,2,7,8},{1,3,5,7},{1,3,6,8},{1,4,5,8},{1,4,6,7},
{2,3,5,8},{2,3,6,7}, {2,4,6,8},{3,4,5,6},{3,4,7,8},{5,6,7,8}}]:
F8 := [E,B minus {{1,2,3,4},{1,2,5,6},{1,2,7,8},{1,3,5,7},{1,4,5,8},{1,4,6,7},
{2,3,5,8},{2,3,6,7},{2,4,6,8},{2,4,5,7},{3,4,7,8},{5,6,7,8}}]:
L8 := [E,B minus {{1,2,3,4},{1,2,5,6},{1,4,5,8},{2,3,6,7},{3,4,7,8},{5,6,7,8},
{1,3,6,8},{2,4,5,7}}]:
Q8 := [E,B minus {{1,2,3,4},{1,2,5,6},{1,2,7,8},{1,3,5,7},{1,4,5,8},{1,4,6,7},
{2,3,5,8},{2,3,6,7},{2,4,6,8},{3,4,7,8},{5,6,7,8}}]:
R8 := [E,B minus {{1,2,3,4},{1,2,5,6},{1,2,7,8},{1,3,5,7},{1,4,5,8},{1,4,6,7},
{2,3,5,8},{2,3,6,7},{2,4,6,8},{3,4,5,6},{3,4,7,8},{5,6,7,8}}]:
V8 := [E,B minus {{1,2,5,6},{1,3,5,7},{1,4,5,8},{2,3,6,7},{2,4,6,8}}]:
MJ := [E,B minus {{1,2,3,4},{1,2,5,6},{1,3,6,7},{2,3,5,7},{4,5,6,7},{4,5,6,8},{4,5,7,8},
seq({1,6,8,x},x={2,3,4,5,7}),seq({2,5,8,x},x={1,3,4,6,7}),seq({3,7,8,x},x={1,2,4,5,6})}]:
MW4:= CycleMatroid(Wheel(4)):
W4 := Relaxations(MW4):
E:={$1..9}: B:=choose(E,3):
R9 := [E,B minus {{1,2,3},{3,4,5},{3,4,6},{3,5,6},{4,5,6},{6,7,1},{1,4,9},{1,5,8},
{2,4,7},{2,5,9},{2,6,8},{3,7,8},{3,7,9},{3,8,9},{7,8,9}}]:
AG23:=[E,B minus {{1,2,3},{1,4,7},{1,5,9},{1,6,8},{2,4,9},{2,5,8},{2,6,7},
{3,4,8},{3,5,7},{3,6,9},{4,5,6},{7,8,9}}]:
Pappus :=
[E,B minus{{1,2,3},{7,8,9},{1,4,8},{1,5,9},{2,4,7},{2,6,9},{3,5,7},{3,6,8},{4,5,6}}]:
nonPappus := [E,B minus{{1,2,3},{7,8,9},{1,4,8},{1,5,9},{2,4,7},{2,6,9},{3,5,7},{3,6,8}}]:
nonPappus0 := nonPappus:
nonPappus1 := [E,B minus{{1,2,3},{7,8,9},{1,4,8},{1,5,9},{2,4,7},{2,6,9},{3,5,7},{3,6,8},
{2,5,8}}]:
nonPappus2 := [E,B minus{{1,2,3},{7,8,9},{1,4,8},{1,5,9},{2,4,7},{2,6,9},{3,5,7},{3,6,8},
{2,5,8},{1,6,7}}]:
nonPappus3 := [E,B minus{{1,2,3},{7,8,9},{1,4,8},{1,5,9},{2,4,7},{2,6,9},{3,5,7},{3,6,8},
{2,5,8},{1,6,7},{3,4,9}}]:
Q3GF3 := [E,(B minus `union`(seq(choose(X,3),X={{1,2,3,4},{1,5,6,7},{3,6,8,9}})))
minus{{2,5,9},{2,7,8},{4,5,8},{4,7,9}}]:
E:={$1..10}: B:=choose(E,3):
nonDesargues :=
[E,B minus{{1,2,4},{1,5,7},{1,8,10},{2,8,9},{2,6,7},{3,7,8},{3,5,10},{4,5,6},{4,9,10}}]:
#E:={$1..13}: B:=choose(E,3):
# PG23 :=
# [E,B minus `union`(seq(choose(X,3), X={{1,2,3,4},{1,5,6,7},{1,8,9,10},{1,11,12,13}, #{2,5,8,11},{2,6,9,12},{2,7,10,13},{3,5,9,13},{3,6,10,11},{3,7,8,12}, #{4,5,10,12},{4,6,8,13},{4,7,9,11}}))]:
P8 := VectorMatroid(Matrix([[1,0,0,0, 0,1,1,-1],
[0,1,0,0, 1,0,1, 1],
[0,0,1,0, 1,1,0, 1],
[0,0,0,1,-1,1,1, 0]]),3):
S8 := VectorMatroid(Matrix([[1,0,0,0,0,1,1,1],
[0,1,0,0,1,0,1,1],
[0,0,1,0,1,1,0,1],
[0,0,0,1,1,1,1,1]]),2):
T8 := VectorMatroid(Matrix([[1,0,0,0,0,1,1,1],
[0,1,0,0,1,0,1,1],
[0,0,1,0,1,1,0,1],
[0,0,0,1,1,1,1,0]]),3):
R10 := VectorMatroid(Matrix([[1,0,0,0,0,-1, 1, 0, 0, 1],
[0,1,0,0,0, 1,-1, 1, 0, 0],
[0,0,1,0,0, 0, 1,-1, 1, 0],
[0,0,0,1,0, 0, 0, 1,-1, 1],
[0,0,0,0,1, 1, 0, 0, 1,-1]]),0):
R12 := VectorMatroid(Matrix([[1,0,0,0,0,0,1,1,1,0,0,0],
[0,1,0,0,0,0,1,1,0,1,0,0],
[0,0,1,0,0,0,1,0,0,0,1,0],
[0,0,0,1,0,0,0,1,0,0,0,1],
[0,0,0,0,1,0,0,0,1,0,1,1],
[0,0,0,0,0,1,0,0,0,1,1,1]]),2):
S5612:=VectorMatroid(Matrix([[1,0,0,0,0,0,0, 1, 1, 1, 1, 1],
[0,1,0,0,0,0,1, 0, 1,-1,-1, 1],
[0,0,1,0,0,0,1, 1, 0, 1,-1,-1],
[0,0,0,1,0,0,1,-1, 1, 0, 1,-1],
[0,0,0,0,1,0,1,-1,-1, 1, 0, 1],
[0,0,0,0,0,1,1, 1,-1,-1, 1, 0]]),3):
PG23 :=VectorMatroid(Matrix([[1,0,0,1,1,0,1, 1, 1, 0, 1, 1, 1],
[0,1,0,1,0,1,1,-1, 0, 1, 1,-1,-1],
[0,0,1,0,1,1,1, 0,-1,-1,-1, 1,-1]]),3):
## Golay24: Note that this might take a bit of time to compute.
#
# A:=Matrix(
# [[1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,1,1,0,0,0,1,0],
# [0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,0,0,0,1],
# [0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,1,0,0,0],
# [0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,1,0,1,1,1,0,0],
# [0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,1,1,0,1,1,1,0],
# [0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,1,0,1,1,1],
# [0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,1,1,0,1,1],
# [0,0,0,0,0,0,0,1,0,0,0,0,1,1,1,0,0,0,1,0,1,1,0,1],
# [0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0],
# [0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,1,0,0,0,1,0,1,1],
# [0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,1,0,0,0,1,0,1],
# [0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1]]);
#
# G24 := VectorMatroid(A,2);
##E:={1,2,3,4}: M:=[E,{{1,2},{2,3},{1,3}}];X:={2,4}: MRank(M,X); MDelete(M,{1});MDual(M);Truncation(M); Hyperplanes(M);Rankgenpoly(V8,x,y);A:=Matrix([[1,2,3],[4,5,6]]); MA:=VectorMatroid(A,0); evalb(Uniform(2,3) = MA);with(networks): G:=complete(5): draw(G); Cocircuits(CycleMatroid(G));nops(%);IsRelaxedDesign(Circuits(F7),3);IsDesign(Circuits(F7),3);Cocircuits(F7) intersect convert(choose({$1..7},4),set);
IsDesign(%,2);
MF:=[P6,Q6,R6,W3,F7,F7m,P7,W3p,F8,AG32r,L8,Q8,R8,V8,R9,
P8,S8,T8,MJ,MW4,W4,R9,R10,R12,AG32,AG23,PG23,S5612,Q3GF3,
Pappus,nonPappus,nonPappus1,nonPappus2,nonPappus3,nonDesargues]:
Matroids:=[seq(N,N=MF),seq(MDual(N),N=MF)]:
seq(IsMatroid(N),N=Matroids);seq(IsMD(N),N=Matroids);IsMinor(F7,Uniform(2,4));FundCircuit(F7,7,{1,2,4});IsRepresentable(F8,2);Connectivity(R10);
VConnectivity(R10);
CConnectivity(R10);