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).
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