43:, and the restriction and contraction operations by which they are formed correspond to edge deletion and edge contraction operations in graphs. The theory of matroid minors leads to structural decompositions of matroids, and characterizations of matroid families by forbidden minors, analogous to the corresponding theory in graphs.
276:
also belongs to the family. In this case, the family may be characterized by its set of "forbidden matroids", the minor-minimal matroids that do not belong to the family. A matroid belongs to the family if and only if it does not have a forbidden matroid as a minor. Often, but not always, the set of
464:
can also be generalized to matroids, and plays a bigger role than branchwidth in the theory of graph minors, branchwidth has more convenient properties in the matroid setting. If a minor-closed family of matroids representable over a finite field does not include the graphic matroids of all planar
568:
with rank or corank one. However, if the problem is restricted to the matroids that are representable over some fixed finite field (and represented as a matrix over that field) then, as in the graph case, it is conjectured to be possible to recognize the matroids that contain any fixed minor in
456:
have different branchwidths, 2 and 1 respectively, but they both induce the same graphic matroid with branchwidth 1. However, for graphs that are not trees, the branchwidth of the graph is equal to the branchwidth of its associated graphic matroid. The branchwidth of a matroid always equals the
389:
that, for any finite field, the matroids representable over that field have finitely many forbidden minors. A proof of this conjecture was announced, but not published, by Geelen, Gerards, and
Whittle in 2014. The matroids that can be represented over the
409:
of the matroid elements, represented as an unrooted binary tree with the elements of the matroid at its leaves. Removing any edge of this tree partitions the matroids into two disjoint subsets; such a partition is called an e-separation. If
560:. Correspondingly, in matroid theory, it would be desirable to develop efficient algorithms for recognizing whether a given fixed matroid is a minor of an input matroid. Unfortunately, such a strong result is not possible: in the
385:, include both graphic and regular matroids. Tutte again showed that these matroids have a forbidden minor characterization: they are the matroids that do not have the four-point line as a minor.
260:
formed by the flats of a matroid, taking a minor of a matroid corresponds to taking an interval of the lattice, the part of the lattice lying between a given lower bound and upper bound element.
352:, matroids whose independent sets are the forest subgraphs of a graph, have five forbidden minors: the three for the regular matroids, and the two duals of the graphic matroids for the graphs
237:
489:. However, the example of the real-representable matroids, which have infinitely many forbidden minors, shows that the minor ordering is not a well-quasi-ordering on all matroids.
516:
states that all regular matroids can be built up in a simple way as the clique-sum of graphic matroids, their duals, and one special 10-element matroid. As a consequence,
441:. The width of a decomposition is the maximum width of any of its e-separations, and the branchwidth of a matroid is the minimum width of any of its branch-decompositions.
331:
556:
is allowed to vary). By combining this result with the
Robertson–Seymour theorem, it is possible to recognize the members of any minor-closed graph family in
465:
graphs, then there is a constant bound on the branchwidth of the matroids in the family, generalizing similar results for minor-closed graph families.
508:
is an important tool in the theory of graph minors, according to which the graphs in any minor-closed family can be built up from simpler graphs by
1000:
481:
matroids characterized by a list of forbidden minors can be characterized by a finite list. Another way of saying the same thing is that the
885:
871:
1064:
Mazoit, Frédéric; Thomassé, Stéphan (2007), "Branchwidth of graphic matroids", in Hilton, Anthony; Talbot, John (eds.),
513:
1256:
532:
One of the important components of graph minor theory is the existence of an algorithm for testing whether a graph
288:, matroids that are representable over all fields. Equivalently a matroid is regular if it can be represented by a
1104:
960:
897:
836:
804:
760:
405:
of matroids may be defined analogously to their definition for graphs. A branch-decomposition of a matroid is a
795:
474:
460:
Branchwidth is an important component of attempts to extend the theory of graph minors to matroids: although
278:
520:
defined by totally unimodular matrices may be solved combinatorially by combining the solutions to a set of
169:
162:
and defining a set to be independent in the contraction if its union with this basis remains independent in
1133:
1099:
1276:
1073:, London Mathematical Society Lecture Note Series, vol. 346, Cambridge University Press, p. 275
1065:
863:
549:
958:
Hicks, Illya V.; McMurray, Nolan B. Jr. (2007), "The branchwidth of graphs and their cycle matroids",
289:
1150:
296:
proved that a matroid is regular if and only if it does not have one of three forbidden minors: the
1025:
496:
are well-quasi-ordered. So far this has been proven only for the matroids of bounded branchwidth.
268:
Many important families of matroids are closed under the operation of taking minors: if a matroid
1281:
505:
406:
302:
1145:
916:
342:
281:
which states that the set of forbidden minors of a minor-closed graph family is always finite.
39:
by a sequence of restriction and contraction operations. Matroid minors are closely related to
985:
Proc. 28th
International Symposium on Mathematical Foundations of Computer Science (MFCS '03)
521:
1236:
1207:
1167:
1125:
1091:
783:
402:
386:
414:
denotes the rank function of the matroid, then the width of an e-separation is defined as
8:
486:
453:
367:
987:, Lecture Notes in Computer Science, vol. 2747, Springer-Verlag, pp. 470–479,
1195:
818:
492:
Robertson and
Seymour conjectured that the matroids representable over any particular
292:(a matrix whose square submatrices all have determinants equal to 0, 1, or −1).
1252:
1117:
257:
932:
512:
operations. Some analogous results are also known in matroid theory. In particular,
1224:
1187:
1155:
1113:
1050:
1015:
988:
969:
947:
906:
845:
813:
769:
798:; Whittle, Geoff (2003), "On the excluded minors for the matroids of branch-width
524:
problems corresponding to the graphic and co-graphic parts of this decomposition.
1232:
1203:
1163:
1121:
1087:
1079:
992:
779:
565:
557:
445:
349:
297:
285:
1228:
1159:
974:
911:
561:
517:
378:
1055:
1020:
1270:
1244:
482:
850:
774:
493:
382:
371:
338:
104:
983:
Hliněný, Petr (2003), "On matroid properties definable in the MSO logic",
1215:
Vámos, P. (1978), "The missing axiom of matroid theory is lost forever",
1175:
564:
model, the only minors that can be recognized in polynomial time are the
391:
40:
1041:
Hliněný, Petr; Whittle, Geoff (2009), "Addendum to matroid tree-width",
1199:
928:
881:
859:
827:
791:
751:
509:
449:
334:
1084:
Actes du Congrès
International des Mathématiciens (Nice, 1970), Tome 3
951:
461:
1191:
444:
The branchwidth of a graph and the branchwidth of the corresponding
20:
1247:(2010) , "4.4 Minors and their representation in the lattice",
602:
832:"Branch-width and well-quasi-ordering in matroids and graphs"
831:
790:
755:
728:
485:
on graphic matroids formed by the minor operation is a
864:"Towards a structure theory for matrices and matroids"
756:"The excluded minors for GF(4)-representable matroids"
263:
305:
172:
146:
whose independent sets are the sets whose union with
1136:; Walton, P. N. (1981), "Detecting matroid minors",
927:
880:
858:
826:
710:
706:
694:
690:
678:
608:
750:
87:whose independent sets are the independent sets of
1178:(1958), "A homotopy theorem for matroids. I, II",
341:of the Fano plane. For this he used his difficult
325:
231:
1180:Transactions of the American Mathematical Society
540:, taking an amount of time that is polynomial in
16:Matroid obtained by restrictions and contractions
1268:
931:; Gerards, Bert; Whittle, Geoff (Aug 17, 2014),
578:
154:. This definition may be extended to arbitrary
1251:, Courier Dover Publications, pp. 65–67,
1063:
1040:
998:
872:Proc. International Congress of Mathematicians
663:
647:
635:
381:, matroids representable over the two-element
284:An example of this phenomenon is given by the
277:forbidden matroids is finite, paralleling the
1132:
1102:(1980), "Decomposition of regular matroids",
1086:, Paris: Gauthier-Villars, pp. 229–233,
1082:(1971), "Combinatorial theory, old and new",
957:
734:
651:
940:Notices of the American Mathematical Society
527:
272:belongs to the family, then every minor of
253:by restriction and contraction operations.
1217:Journal of the London Mathematical Society
1138:Journal of the London Mathematical Society
166:. The rank function of the contraction is
1149:
1054:
1019:
973:
910:
849:
817:
773:
499:
448:may differ: for instance, the three-edge
345:. Simpler proofs have since been found.
884:; Gerards, Bert; Whittle, Geoff (2007),
862:; Gerards, Bert; Whittle, Geoff (2006),
830:; Gerards, Bert; Whittle, Geoff (2002),
754:; Gerards, A. M. H.; Kapoor, A. (2000),
1098:
982:
722:
674:
672:
477:implies that every matroid property of
394:have infinitely many forbidden minors.
142:, is the matroid on the underlying set
1269:
999:Hliněný, Petr; Whittle, Geoff (2006),
631:
629:
468:
232:{\displaystyle r'(A)=r(A\cup T)-r(T).}
1243:
1214:
1174:
620:
584:
293:
1078:
711:Geelen, Gerards & Whittle (2006)
707:Geelen, Gerards & Whittle (2002)
695:Geelen, Gerards & Whittle (2007)
691:Geelen, Gerards & Whittle (2006)
679:Geelen, Gerards & Whittle (2006)
669:
609:Geelen, Gerards & Whittle (2014)
596:
95:. Its circuits are the circuits of
626:
264:Forbidden matroid characterizations
13:
886:"Excluding a planar graph from GF(
14:
1293:
1043:European Journal of Combinatorics
1008:European Journal of Combinatorics
875:, vol. III, pp. 827–842
1105:Journal of Combinatorial Theory
961:Journal of Combinatorial Theory
898:Journal of Combinatorial Theory
837:Journal of Combinatorial Theory
805:Journal of Combinatorial Theory
761:Journal of Combinatorial Theory
716:
700:
514:Seymour's decomposition theorem
684:
657:
641:
614:
590:
397:
249:if it can be constructed from
223:
217:
208:
196:
187:
181:
46:
19:In the mathematical theory of
1:
1067:Surveys in Combinatorics 2007
819:10.1016/S0095-8956(02)00046-1
743:
370:are forbidden minors for the
1118:10.1016/0095-8956(80)90075-1
1039:. Addendum and corrigendum:
993:10.1007/978-3-540-45138-9_41
664:Hliněný & Whittle (2006)
648:Mazoit & Thomassé (2007)
636:Mazoit & Thomassé (2007)
536:is a minor of another graph
122:is an independent subset of
83:, is the matroid on the set
7:
933:"Solving Rota's conjecture"
735:Seymour & Walton (1981)
652:Hicks & McMurray (2007)
333:(the four-point line), the
326:{\displaystyle U{}_{4}^{2}}
10:
1298:
975:10.1016/j.jctb.2006.12.007
912:10.1016/j.jctb.2007.02.005
67:, then the restriction of
1056:10.1016/j.ejc.2008.09.028
1021:10.1016/j.ejc.2006.06.005
890:)-representable matroids"
550:fixed-parameter tractable
528:Algorithms and complexity
475:Robertson–Seymour theorem
457:branchwidth of its dual.
290:totally unimodular matrix
279:Robertson–Seymour theorem
111:restricted to subsets of
1229:10.1112/jlms/s2-18.3.403
1160:10.1112/jlms/s2-23.2.193
572:
544:for any fixed choice of
245:is a minor of a matroid
158:by choosing a basis for
55:is a matroid on the set
506:graph structure theorem
407:hierarchical clustering
851:10.1006/jctb.2001.2082
775:10.1006/jctb.2000.1963
500:Matroid decompositions
327:
233:
99:that are contained in
91:that are contained in
35:that is obtained from
522:minimum spanning tree
403:Branch-decompositions
328:
234:
126:, the contraction of
1001:"Matroid tree-width"
303:
170:
548:(and more strongly
487:well-quasi-ordering
469:Well-quasi-ordering
452:and the three-edge
322:
31:is another matroid
1277:Graph minor theory
323:
309:
229:
150:is independent in
1219:, Second Series,
1140:, Second Series,
794:; Gerards, Bert;
569:polynomial time.
258:geometric lattice
1289:
1261:
1239:
1210:
1170:
1153:
1128:
1094:
1080:Rota, Gian-Carlo
1074:
1072:
1059:
1058:
1049:(4): 1036–1044,
1038:
1037:
1036:
1030:
1024:, archived from
1023:
1014:(7): 1117–1128,
1005:
995:
978:
977:
954:
952:10.1090/noti1139
937:
923:
921:
915:, archived from
914:
894:
876:
868:
854:
853:
822:
821:
786:
777:
738:
732:
726:
720:
714:
704:
698:
688:
682:
676:
667:
661:
655:
645:
639:
633:
624:
618:
612:
606:
600:
594:
588:
582:
566:uniform matroids
440:
387:Rota conjectured
368:Wagner's theorem
350:graphic matroids
343:homotopy theorem
332:
330:
329:
324:
321:
316:
311:
286:regular matroids
256:In terms of the
238:
236:
235:
230:
180:
1297:
1296:
1292:
1291:
1290:
1288:
1287:
1286:
1267:
1266:
1265:
1259:
1245:Welsh, D. J. A.
1192:10.2307/1993244
1151:10.1.1.108.1426
1070:
1034:
1032:
1028:
1003:
935:
919:
892:
866:
796:Robertson, Neil
746:
741:
733:
729:
721:
717:
705:
701:
689:
685:
677:
670:
662:
658:
646:
642:
634:
627:
619:
615:
607:
603:
595:
591:
583:
579:
575:
558:polynomial time
552:if the size of
530:
518:linear programs
502:
471:
446:graphic matroid
415:
400:
379:binary matroids
365:
358:
317:
312:
310:
304:
301:
300:
298:uniform matroid
266:
173:
171:
168:
167:
63:is a subset of
49:
17:
12:
11:
5:
1295:
1285:
1284:
1282:Matroid theory
1279:
1264:
1263:
1257:
1249:Matroid Theory
1241:
1223:(3): 403–408,
1212:
1186:(1): 144–174,
1172:
1144:(2): 193–203,
1134:Seymour, P. D.
1130:
1112:(3): 305–359,
1100:Seymour, P. D.
1096:
1076:
1061:
996:
980:
968:(5): 681–692,
955:
946:(7): 736–743,
925:
905:(6): 971–998,
878:
856:
844:(2): 270–290,
824:
812:(2): 261–265,
788:
768:(2): 247–299,
747:
745:
742:
740:
739:
727:
723:Seymour (1980)
715:
699:
683:
668:
656:
640:
625:
613:
601:
589:
576:
574:
571:
562:matroid oracle
529:
526:
501:
498:
470:
467:
399:
396:
363:
356:
320:
315:
308:
265:
262:
228:
225:
222:
219:
216:
213:
210:
207:
204:
201:
198:
195:
192:
189:
186:
183:
179:
176:
48:
45:
15:
9:
6:
4:
3:
2:
1294:
1283:
1280:
1278:
1275:
1274:
1272:
1260:
1258:9780486474397
1254:
1250:
1246:
1242:
1238:
1234:
1230:
1226:
1222:
1218:
1213:
1209:
1205:
1201:
1197:
1193:
1189:
1185:
1181:
1177:
1173:
1169:
1165:
1161:
1157:
1152:
1147:
1143:
1139:
1135:
1131:
1127:
1123:
1119:
1115:
1111:
1107:
1106:
1101:
1097:
1093:
1089:
1085:
1081:
1077:
1069:
1068:
1062:
1057:
1052:
1048:
1044:
1031:on 2012-03-06
1027:
1022:
1017:
1013:
1009:
1002:
997:
994:
990:
986:
981:
976:
971:
967:
963:
962:
956:
953:
949:
945:
941:
934:
930:
926:
922:on 2010-09-24
918:
913:
908:
904:
900:
899:
891:
889:
883:
879:
874:
873:
865:
861:
857:
852:
847:
843:
839:
838:
833:
829:
825:
820:
815:
811:
807:
806:
801:
797:
793:
789:
785:
781:
776:
771:
767:
763:
762:
757:
753:
752:Geelen, J. F.
749:
748:
736:
731:
724:
719:
712:
708:
703:
696:
692:
687:
680:
675:
673:
665:
660:
653:
649:
644:
637:
632:
630:
622:
617:
610:
605:
598:
593:
586:
581:
577:
570:
567:
563:
559:
555:
551:
547:
543:
539:
535:
525:
523:
519:
515:
511:
507:
497:
495:
490:
488:
484:
483:partial order
480:
476:
466:
463:
458:
455:
451:
447:
442:
438:
434:
430:
426:
422:
418:
413:
408:
404:
395:
393:
388:
384:
380:
375:
373:
372:planar graphs
369:
362:
355:
351:
346:
344:
340:
336:
318:
313:
306:
299:
295:
291:
287:
282:
280:
275:
271:
261:
259:
254:
252:
248:
244:
239:
226:
220:
214:
211:
205:
202:
199:
193:
190:
184:
177:
174:
165:
161:
157:
153:
149:
145:
141:
137:
133:
129:
125:
121:
116:
114:
110:
106:
105:rank function
102:
98:
94:
90:
86:
82:
78:
74:
70:
66:
62:
58:
54:
44:
42:
38:
34:
30:
27:of a matroid
26:
22:
1248:
1220:
1216:
1183:
1179:
1176:Tutte, W. T.
1141:
1137:
1109:
1108:, Series B,
1103:
1083:
1066:
1046:
1042:
1033:, retrieved
1026:the original
1011:
1007:
984:
965:
964:, Series B,
959:
943:
939:
917:the original
902:
901:, Series B,
896:
887:
870:
841:
840:, Series B,
835:
809:
808:, Series B,
803:
799:
765:
764:, Series B,
759:
730:
718:
702:
686:
659:
643:
621:Vámos (1978)
616:
604:
592:
585:Welsh (2010)
580:
553:
545:
541:
537:
533:
531:
503:
494:finite field
491:
478:
472:
459:
443:
436:
432:
428:
424:
420:
416:
411:
401:
392:real numbers
383:finite field
376:
360:
353:
347:
339:dual matroid
294:Tutte (1958)
283:
273:
269:
267:
255:
250:
246:
242:
240:
163:
159:
155:
151:
147:
143:
139:
135:
131:
127:
123:
119:
117:
112:
108:
100:
96:
92:
88:
84:
80:
76:
72:
68:
64:
60:
56:
52:
50:
41:graph minors
36:
32:
28:
24:
18:
929:Geelen, Jim
882:Geelen, Jim
860:Geelen, Jim
828:Geelen, Jim
792:Geelen, Jim
597:Rota (1971)
398:Branchwidth
144:E − T
107:is that of
47:Definitions
1271:Categories
1035:2012-08-17
744:References
510:clique-sum
450:path graph
431:) −
335:Fano plane
241:A matroid
134:, written
75:, written
1146:CiteSeerX
462:treewidth
337:, or the
212:−
203:∪
366:that by
178:′
103:and its
21:matroids
1237:0518224
1208:0101526
1200:1993244
1168:0609098
1126:0579077
1092:0505646
784:1769191
479:graphic
79: |
1255:
1235:
1206:
1198:
1166:
1148:
1124:
1090:
782:
1196:JSTOR
1071:(PDF)
1029:(PDF)
1004:(PDF)
936:(PDF)
920:(PDF)
893:(PDF)
867:(PDF)
573:Notes
439:) + 1
25:minor
1253:ISBN
504:The
473:The
454:star
423:) +
377:The
359:and
348:The
59:and
23:, a
1225:doi
1188:doi
1156:doi
1114:doi
1051:doi
1016:doi
989:doi
970:doi
948:doi
907:doi
846:doi
814:doi
802:",
770:doi
364:3,3
130:by
118:If
71:to
51:If
1273::
1233:MR
1231:,
1221:18
1204:MR
1202:,
1194:,
1184:88
1182:,
1164:MR
1162:,
1154:,
1142:23
1122:MR
1120:,
1110:28
1088:MR
1047:30
1045:,
1012:27
1010:,
1006:,
966:97
944:61
942:,
938:,
903:97
895:,
869:,
842:84
834:,
810:88
780:MR
778:,
766:79
758:,
709:;
693:;
671:^
650:;
628:^
374:.
115:.
1262:.
1240:.
1227::
1211:.
1190::
1171:.
1158::
1129:.
1116::
1095:.
1075:.
1060:.
1053::
1018::
991::
979:.
972::
950::
924:.
909::
888:q
877:.
855:.
848::
823:.
816::
800:k
787:.
772::
737:.
725:.
713:.
697:.
681:.
666:.
654:.
638:.
623:.
611:.
599:.
587:.
554:H
546:H
542:G
538:G
534:H
437:M
435:(
433:r
429:B
427:(
425:r
421:A
419:(
417:r
412:r
361:K
357:5
354:K
319:2
314:4
307:U
274:M
270:M
251:M
247:M
243:N
227:.
224:)
221:T
218:(
215:r
209:)
206:T
200:A
197:(
194:r
191:=
188:)
185:A
182:(
175:r
164:M
160:T
156:T
152:M
148:T
140:T
138:/
136:M
132:T
128:M
124:E
120:T
113:S
109:M
101:S
97:M
93:S
89:M
85:S
81:S
77:M
73:S
69:M
65:E
61:S
57:E
53:M
37:M
33:N
29:M
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.