Matroids

This page, prepared by David C. Haws, is dedicated to the collection of software and data concerning matroids, related to:

De Loera, Jesús A.; Haws, David C.; Köppe, Matthias: Ehrhart Polynomials of Matroid Polytopes and Polymatroids, Discrete Comput. Geom., 42(4):670–702, 2009.

h^*-vectors and Ehrhart polynomials of the matroids in the appendix of Oxley:

U^{2,4} 1,2,1 1, 7/3, 2, 2/3
U^{2,5} 5,5,1 1, 35/12, 85/24, 25/12, 11/24
U^{3,5} 5,5,1 1, 35/12, 85/24, 25/12, 11/24
K_4 1, 10, 20, 10, 1 1, 107/30, 21/4, 49/12, 7/4, 7/20
W^3 1, 11, 24, 11, 10 1, 18/5, 11/2, 9/2, 2, 2/5
Q_6 1, 12, 28, 12, 1 1, 109/30, 23/4, 59/12, 9/4, 9/20
P_6 1, 13, 32, 13, 1 1, 11/3, 6, 16/3, 5/2, 1/2
U^{3,6} 1, 14, 36, 14, 1 1, 37/10, 25/4, 23/4, 11/4, 11/20
R_6 1, 12, 28, 12, 1 1, 109/30, 23/4, 59/12, 9/4, 9/20
F_7 21, 98, 91, 21, 1 1, 21/5, 343/45, 63/8, 91/18, 77/40, 29/90
F_7^ 21, 98, 91, 21, 1 1, 21/5, 343/45, 63/8, 91/18, 77/40, 29/90
F_7^- 21, 101, 97, 22, 1 1, 253/60, 2809/360, 33/4, 193/36, 61/30, 121/360
(F_7^-)^ 21, 101, 97, 22, 1 1, 253/60, 2809/360, 33/4, 193/36, 61/30, 121/360
P^7 21, 104, 103, 23, 1 1, 127/30, 479/60, 69/8, 17/3, 257/120, 7/20
(P^7)^ 21, 104, 103, 23, 1 1, 127/30, 479/60, 69/8, 17/3, 257/120, 7/20
AG(3,2) 1, 62, 561, 1014, 449, 48, 1 1, 209/42, 1981/180, 881/60, 119/9, 95/12, 499/180, 89/210
AG'(3,2) 1, 62, 562, 1023, 458, 49, 1 1, 299/60, 4007/360, 5401/360, 122/9, 2911/360, 1013/360, 77/180
R_8 1, 62, 563, 1032, 467, 50, 1 1, 524/105, 1013/90, 1379/90, 125/9, 743/90, 257/90, 136/315
F_8 1, 62, 563, 1032, 467, 50, 1 1, 524/105, 1013/90, 1379/90, 125/9, 743/90, 257/90, 136/315
Q_8 1, 62, 564, 1041, 476, 51, 1 1, 2099/420, 4097/360, 1877/120, 128/9, 337/40, 1043/360, 61/140
S_8 1, 44, 337, 612, 305, 40, 1 1, 1021/210, 377/36, 475/36, 193/18, 511/90, 65/36, 67/252
V_8 1, 62, 570, 1095, 530, 57, 1 1, 2117/420, 4367/360, 2107/120, 146/9, 1133/120, 1133/360, 193/420
T_8 1, 62, 564, 1041, 476, 51, 1 1, 2099/420, 4097/360, 1877/120, 128/9, 337/40, 1043/360, 61/140
V_8^+ 1, 62, 569, 1086, 521, 56, 1 1, 151/30, 2161/180, 3103/180, 143/9, 1669/180, 559/180, 41/90
L_8 1, 62, 567, 1068, 503, 54, 1 1, 527/105, 529/45, 83/5, 137/9, 134/15, 136/45, 47/105
J 1, 44, 339, 630, 323, 42, 1 1, 512/105, 193/18, 83/6, 205/18, 361/60, 17/9, 23/84
P_8 1, 62, 565, 1050, 485, 52, 1 1, 1051/210, 2071/180, 2873/180, 131/9, 1547/180, 529/180, 277/630
W_4 1, 38, 262, 475, 254, 37, 1 1, 135/28, 3691/360, 1511/120, 88/9, 39/8, 529/360, 89/420
W^4 1, 38, 263, 484, 263, 38, 1 1, 169/35, 467/45, 581/45, 91/9, 227/45, 68/45, 68/315
K_{3,3}^* 78, 1116, 3492, 3237, 927, 72, 1 1, 307/56, 137141/10080, 3223/160, 37807/1920, 211/16, 5743/960, 1889/1120, 8923/40320
K_{3,3} 78, 1116, 3492, 3237, 927, 72, 1 1, 307/56, 137141/10080, 3223/160, 37807/1920, 211/16, 5743/960, 1889/1120, 8923/40320
AG(2,3) 1, 147, 1230, 1885, 714, 63, 1 1, 1453/280, 41749/3360, 581/32, 34069/1920, 927/80, 4541/960, 239/224, 449/4480
Pappus 1, 147, 1230, 1915, 744, 66, 1 1, 729/140, 3573/280, 381/20, 1499/80, 243/20, 49/10, 153/140, 57/560
Non-Pappus 1, 147, 1230, 1925, 754, 67, 1 1, 4379/840, 25951/2016, 9287/480, 21967/1152, 987/80, 2855/576, 3701/3360, 275/2688
Q_3(GF(3)^*) 1, 147, 1098, 1638, 632, 59, 1 1, 433/84, 3079/252, 4193/240, 5947/360, 167/16, 601/144, 787/840, 149/1680
R_9 1, 147, 1142, 1717, 656, 60, 1 1, 723/140, 49/4, 88/5, 24217/1440, 1291/120, 625/144, 821/840, 133/1440

Software to compute the h^*-vector of uniform matroids.

An explicit formula to compute the h^*-vector of uniform matroids is given in Katzman, Modechai, "The Hilbert series of algebras of Veronese type", Communications in Algebra, pg1141-1146, Volume 3, 2005.

We implement this explicit equation in maple as well as recursive expressions developed in "Ehrhart Polynomials of Matroid Polytopes and Polymatroids".

The software can be found here.

Software to compute the Ehrhart polynomials of uniform matroids.

An explicit formula to compute the Ehrhart polynomial of uniform matroids is given in Katzman, Modechai, "The Hilbert series of algebras of Veronese type", Communications in Algebra, pg1141-1146, Volume 3, 2005.

The software which implements this can be found here as well as software to test positivity here.

We tested up to 75 elements, that the uniform matroids have positive coefficients in their Ehrhart polynomials using the above software.

Graphical matroids.

Here are five graphical matroids on which our computations show that the h^*-vectors are unimodal. The file with no extension are the adjacency description of each graph. The .ext files are the cdd input, and the .ine are their output. The .lat files are the Latte ready input and the .lat.rat.simp are h^*-vectors of each graphical matroid. Since we use Latte to compute the h^*-vectors, we are restricted to graphs with a low number of edges and spanning trees (matroid bases).

4wheel 6gon g1v4e4 grid3x3 K4
4wheel.ext 6gon.ext g1v4e4.ext grid3x3.ext K4.ext
4wheel.ine 6gon.ine g1v4e4.ine grid3x3.ine K4.ine
4wheel.lat 6gon.lat g1v4e4.lat grid3x3.lat K4.lat
4wheel.lat.rat.simp 6gon.lat.rat.simp g1v4e4.lat.rat.simp grid3x3.lat.rat.simp K4.lat.rat.simp

 

Random realizable matroids.

rmatroid.pl is a small perl program that uses maple, cddr+, Latte, and cplex which computes a random realizable matroid over a user defined characteristic, computes the h^*-vector, and verify if the h^*-vector is unimodal. These maple programs and perl programs are also necessary to properly run: rmatroid, unimodal, inetolat.pl. Here is a useful perl script to automatically run user defined number of tests: dormatroid.pl.

We used these programs to test 1500 matroids derived from random 3 x 9 matrices with characteristic 41. All matroids had unimodal h^*-vectors. The output from this test, which includes the matrices, can be found here.

We also used our programs to test 1000 matroids derived from random 3 x 7 matrices with characteristic 41. All matroids had unimodal h^*-vectors. The output from this test, which includes the matrices, can be found here.

Gordon Royle matroid.

Here you can find an excellent list, with many important properties, of all matroids with elements less than or equal to nine.

Unimodular Triangulations

We obtained data for all matroids with nine elements or less from Gordon Royle. From this, we were able to prove that all 1317 connected matroids with eight elements or less have a unimodular triangulation. The following link is a zipped text file which lists the matroid number, as indexed by Gordon Royle, the bases for the matroid and the unimodular triangulation. The line TRIANGULATION(1) indicates that the triangulation was the first found by TOPCOM which is the placing triangultion.

All_1317_Connected_Matroids_Unimodular_Triangulations_Eight_Elements_or_Less.txt.gz

We also computed as many possible unimodular and G-connected matroid triangulations. By G-connected we mean for each simplex its vertices are connected on the 1-skelton of the matroid polytope. We have found 68 such matroids which contains all matroids of six elements or less plus more. The following link to a text file lists the matroid number, as indexed by Gordon Royle, the bases for the matroid and the unimodular and G-connected triangulation. TRIANGULATION(<number>) indicates which the number of iterations/filps TOPCOM used to get the triangulation (using points2triangs).

Connected_Matroids_Unimodular_G_Connected_Triangulations.txt