{*------------------------------------------------------------------------------- M2 code to accompany "Divisors on matroids and their volumes" (upload to web) Author: Christopher Eur Last update: 8/5/2018 --------------------------------------------------------------------------------*} needsPackage "Matroids" {*------------------------------ New methods -----------------------------------*} --evaluates the volume polynomial of the matroid at t_F => rank(F) using Groebner bases matVol = method(); matVol(Matroid) := ZZ => M -> ( I := idealChowRing M; r := rank M; R := ring I; L := sum(gens R, r -> rank(M, set last baseName r)*r); V := factor ((-1)^r* L^(rank M -1) % I ); if rank(M,set last baseName first support value V#0) == r-1 then sub(value V#1,ZZ) else V ) --computes the volume of a matroid M using the combinatorial formula. combMatVol = method(); combMatVol(Matroid) := RingElement => M -> ( M = simpleMatroid M; rkM := hashTable apply(flats M, f -> (f,rank(M,f))); r := rank M;-- store rank information LMbar := dropElements(latticeOfFlats M,{{},toList M.groundSet}); -- reduced lattice of flats supp := drop(chains LMbar,1); -- the chains of the reduced lattice (i.e. supports of volPol) --compute all the relevant reduced characteristic polynomial and store it in hash table mus := hashTable apply(select(supp, C -> #C == 2) | (LMbar.GroundSet)/(e -> {e, toList M.groundSet}), C -> ( N := minor(M, set C_0, M.groundSet - set C_1); Lp := (flatten entries last coefficients characteristicPolynomial N)/(i -> sub(i,ZZ)); L := apply(#Lp-1, i -> abs sum(i+1, j -> Lp_j)); {C,L} )); sum(supp, C -> ( -- R is the rank sequence of the chain, Cp is the chain augmented to goundSet R := C/set/(s -> rkM#s); k := #C; Cp := C | {toList M.groundSet}; -- get all possible sequences of the consecutive sum degree sequence (wtD's) wtDs := toList((apply(k-1, i -> R_i) | {r-1})..(apply(k-1, i -> R_(i+1)-1) | {r-1})); (-1)^(r - 1 - k) * sum(wtDs, wtD -> ( D := {wtD_0} | apply(k-1, i -> wtD_(i+1) - wtD_i); --the degree sequence Vars := product(#D, i -> rkM#(set C_i)^(D_i)); muPart := product(k, i -> binomial(D_i - 1, wtD_i - R_i) * (mus#{Cp_i, Cp_(i+1)})_(wtD_i - R_i)); multinomial(r-1, D) * Vars * muPart )) )) ) -- Computes the intersection numbers of the divisors on a matroid M {* Given a monomial m = x_{F_1}^{d_1}...x_{F_k}^{d_k} of degree rk M - 1, computes the degree of m (in the Chow ring of M). Input is a triple (F,D,M) where F is a chain F_1 < F_2 < ... < F_k of flats of M, D is the degree list {d_1, ... , d_k}, and M is the matroid*} degMat = method(); degMat(List,List,Matroid) := ZZ => (F,D,M) -> ( k := #F; if not k == #D then << "#flats not #degrees" << return error; r := rank M; if not sum D == r-1 then << "wrong total degree" << return error; if not all(k-1, i -> isSubset(F_i, F_(i+1))) then << "not a chain" << return error; LM := flats M; if not all(F, f -> member(f,LM)) then << "not flats" << return error; F = append(F, M.groundSet); (-1)^(r - 1 - k) * product(k, i -> ( l := sum(i+1, j -> D_j) - rank(M,F_i); binomial(D_i -1, l) * mu(minor(M,F_i,(M.groundSet - F_(i+1))),l) )) ) --multinomial coefficient multinomial = (n,L) -> sub(n! / product(L, l -> l!),ZZ); -- computes the volume polynomial of a matroid via the combinatorial formula combVolPol = method(); combVolPol(Matroid) := RingElement => M -> ( M = simpleMatroid M; rkM := hashTable apply(flats M, f -> (f,rank(M,f))); r := rank M;-- store rank information LMbar := dropElements(latticeOfFlats M,{{},toList M.groundSet}); -- reduced lattice of flats t := symbol t; S := QQ[LMbar.GroundSet/(f -> t_f)]; supp := drop(chains LMbar,1); -- the chains of the reduced lattice (i.e. supports of volPol) --compute all the relevant reduced characteristic polynomial and store it in hash table mus := hashTable apply(select(supp, C -> #C == 2) | (LMbar.GroundSet)/(e -> {e, toList M.groundSet}), C -> ( N := minor(M, set C_0, M.groundSet - set C_1); Lp := (flatten entries last coefficients characteristicPolynomial N)/(i -> sub(i,ZZ)); L := apply(#Lp-1, i -> abs sum(i+1, j -> Lp_j)); {C,L} )); sum(supp, C -> ( -- R is the rank sequence of the chain, Cp is the chain augmented to goundSet R := C/set/(s -> rkM#s); k := #C; Cp := C | {toList M.groundSet}; -- get all possible sequences of the consecutive sum degree sequence (wtD's) wtDs := toList((apply(k-1, i -> R_i) | {r-1})..(apply(k-1, i -> R_(i+1)-1) | {r-1})); (-1)^(r - 1 - k) * sum(wtDs, wtD -> ( D := {wtD_0} | apply(k-1, i -> wtD_(i+1) - wtD_i); --the degree sequence Vars := product(#D, i -> (first select(gens S, s -> last baseName s == C_i))^(D_i)); muPart := product(k, i -> binomial(D_i - 1, wtD_i - R_i) * (mus#{Cp_i, Cp_(i+1)})_(wtD_i - R_i)); multinomial(r-1, D) * Vars * muPart )) )) ) --input: matroid M, a function T on the flats (as a function from 2^E) --output: the evaluation of the volume polynomial of M with t_F => T(F). combVolPol(Matroid,Function) := RingElement => (M,T) -> ( M = simpleMatroid M; rkM := hashTable apply(flats M, f -> (f,rank(M,f))); r := rank M;-- store rank information LMbar := dropElements(latticeOfFlats M,{{},toList M.groundSet}); -- reduced lattice of flats supp := drop(chains LMbar,1); -- the chains of the reduced lattice (i.e. supports of volPol) --compute all the relevant reduced characteristic polynomial and store it in hash table mus := hashTable apply(select(supp, C -> #C == 2) | (LMbar.GroundSet)/(e -> {e, toList M.groundSet}), C -> ( N := minor(M, set C_0, M.groundSet - set C_1); Lp := (flatten entries last coefficients characteristicPolynomial N)/(i -> sub(i,ZZ)); L := apply(#Lp-1, i -> abs sum(i+1, j -> Lp_j)); {C,L} )); sum(supp, C -> ( -- R is the rank sequence of the chain, Cp is the chain augmented to goundSet R := C/set/(s -> rkM#s); k := #C; Cp := C | {toList M.groundSet}; -- get all possible sequences of the consecutive sum degree sequence (wtD's) wtDs := toList((apply(k-1, i -> R_i) | {r-1})..(apply(k-1, i -> R_(i+1)-1) | {r-1})); (-1)^(r - 1 - k) * sum(wtDs, wtD -> ( D := {wtD_0} | apply(k-1, i -> wtD_(i+1) - wtD_i); --the degree sequence Vars := product(#D, i -> (T set C_i)^(D_i)); muPart := product(k, i -> binomial(D_i - 1, wtD_i - R_i) * (mus#{Cp_i, Cp_(i+1)})_(wtD_i - R_i)); multinomial(r-1, D) * Vars * muPart )) )) ) {*------------------------------- Experiments ----------------------------------*} --< testing combVolPol >-- restart load "volumeMatroid.m2" F = time combVolPol uniformMatroid(4,5); G = time cogeneratorChowRing uniformMatroid(4,5); --test that F and G are the same up to a sign member((map(ring G, ring F, gens ring G)) F , {G, - G}) F = time combVolPol matroid completeGraph 5; -- 3.5 seconds (!) G = time cogeneratorChowRing matroid completeGraph 5; -- 17 seconds member((map(ring G, ring F, gens ring G)) F , {G, - G}) F = time combVolPol uniformMatroid(5,5); -- 1.5 seconds (!) G = time cogeneratorChowRing uniformMatroid(5,5); -- 18 seconds member((map(ring G, ring F, gens ring G)) F , {G, - G}) time combMatVol uniformMatroid(4,5) == 5^3 time combMatVol uniformMatroid(6,7) == 7^5 -- 15 seconds --< Vol(M) numerology experiments >-- restart load "volumeMatroid.m2" --auxiliary commands U = (r,n) -> uniformMatroid(r,n); isConn = M -> #(components M) == 1; minVol = (r,n) -> r^(r-2)*((n-r+1)*(r-1)+1); --< matroid volume and the characteristic polynomial >-- -- equal matroid volume does not imply that the characteristic polynomials are the same L = select(allMatroids 7, M -> rank M == 4 and isGeom M); LVol = hashTable apply(L, M -> (M, combMatVol M)); -- 77 seconds T = tally values LVol RL = unique select(values LVol, i -> T#i > 1) apply(RL, v -> select(keys LVol, k -> LVol#k == v)) oo/(l -> l/characteristicPolynomial) -- equal characteristic polynomial does not imply that the volumes are the same S = ZZ[t]; LChar = hashTable apply(L, M -> (Chi := characteristicPolynomial M; (M, (map(S,ring Chi, gens S))Chi ))) T = tally values LChar RL = unique select(values LChar, i -> T#i > 1) apply(RL, p -> select(keys LChar, k -> LChar#k == p)) oo/combMatVol --< two matroids not isomorphic but has same Tutte polynomial >-- 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}}) -- combMatVol M1 == 1533457 -- 20 min on appsa 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}}) -- combMatVol M2 == 1534702 -- 20 min on appsa --< Vol(M) and the matroid polytope >-- restart load "volumeMatroid.m2" needsPackage "Polyhedra" --Same matroid volumes does not imply that volumes of matroid polytopes are same ML36 = select(allMatroids 6, M -> rank M == 3 and isGeom M and isConn M) time ML36/combMatVol -- 5 sec time ML36/(M -> volume convexHull basisIndicatorMatrix M) -- 9 sec L = ML36_{5,6} L/combMatVol L/(M -> volume convexHull basisIndicatorMatrix M) --Same volumes of matroid polytopes does not imply same matroid volume ML37 = select(allMatroids 7, M -> rank M == 3 and isGeom M and isConn M) L = ML37_{16,17} L/combMatVol time L/polyVol -- 27 sec: {221/720, 211/720} --< M -> Vol(M) is a matroid valuation >-- restart load "volumeMatroid.m2" -- U_{2,4} example (the octahedron one). Figure 3 in LdMRS17-CSM Section 4. M = uniformMatroid(2,4); M1 = matroid({0,1,2,3},{{0,1},{1,2},{1,3},{0,3},{0,2}}); M2 = matroid({0,1,2,3},{{0,3},{0,2},{1,2},{1,3},{2,3}}); M12 = matroid({0,1,2,3},{{1,2},{1,3},{0,2},{0,3}}); V = matVol M; V1 = matVol M1; V2 = matVol M2; V12 = matVol M12; (V,V1,V2,V12) V == V1+V2-V12 --Schubert matroid subdivision of U_{3,6} example. (Example 2.8 in AFR10-ValMatroid) --set up the bases sigma := L -> sort apply(L, l -> position({4,5,0,1,2,3}, i -> i==l)) --sigma is 234501 B1 = toList select({0,0,0}..{5,5,5}, l -> l_0 <2 and l_1<4 and l_2<6 and l_0-- restart load "volumeMatroid.m2" M = uniformMatroid(2,3) idealChowRing M LM = latticeOfFlats M; combVolPol M M = uniformMatroid(3,4) idealChowRing M LM = latticeOfFlats M; VP = combVolPol M L = {0,0,0,3,-1,-1,2,-1,2,2}; SL = apply(#L, i -> (gens ring VP)_i => L_i) L = {3,3,3,3,2,2,2,2,2,2}; SL = apply(#L, i -> (gens ring VP)_i => L_i) L = {6,6,6,6,9,9,9,9,9,9}; SL = apply(#L, i -> (gens ring VP)_i => L_i) sub(VP,SL) M = uniformMatroid(1,1)++uniformMatroid(2,3) LM = latticeOfFlats M; combVolPol M combMatVol M M = matroid({0,1,2,3,4},{{0,1,2,4},{0,1,3,4},{0,1,2,3}}) LM = latticeOfFlats M; combVolPol M combMatVol M