290:
If a matroid is regular, it must clearly be realizable over the two fields GF(2) and GF(3). The converse is true: every matroid that is realizable over both of these two fields is regular. The result follows from a forbidden minor characterization of the matroids realizable over these fields, part of
166:(and every co-graphic matroid) is regular. Conversely, every regular matroid may be constructed by combining graphic matroids, co-graphic matroids, and a certain ten-element matroid that is neither graphic nor co-graphic, using an operation for combining matroids that generalizes the
245:(a rank-three matroid in which seven of the triples of points are dependent) and its dual are also not regular: they can be realized over GF(2), and over all fields of characteristic two, but not over any other fields than those. As
47:
is defined to be a family of subsets of a finite set, satisfying certain axioms. The sets in the family are called "independent sets". One of the ways of constructing a matroid is to select a finite set of vectors in a
302:, a matrix in which every square submatrix has determinant 0, 1, or −1. The vectors realizing the matroid may be taken as the rows of the matrix. For this reason, regular matroids are sometimes also called
56:
in the vector space. Every family of sets constructed in this way is a matroid, but not every matroid can be constructed in this way, and the vector spaces over different
285:
228:
141:
121:
101:
81:
249:
showed, these three examples are fundamental to the theory of regular matroids: every non-regular matroid has at least one of these three as a
306:. The equivalence of regular matroids and unimodular matrices, and their characterization by forbidden minors, are deep results of
390:
362:
318:
later published an alternative and simpler proof of the characterization of unimodular matrices by forbidden minors.
610:
476:
521:
Maurer, Stephen B. (1976), "Matrix generalizations of some theorems on trees, cycles and cocycles in graphs",
431:
605:
471:
253:. Thus, the regular matroids are exactly the matroids that do not have one of the three forbidden minors
659:
Gerards, A. M. H. (1989), "A short proof of Tutte's characterization of totally unimodular matrices",
726:
256:
199:
311:
178:
28:
707:
633:
591:
542:
507:
457:
385:, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, p. 209,
330:
algorithm for testing whether a matroid is regular, given access to the matroid through an
292:
53:
8:
57:
32:
579:
126:
106:
86:
66:
698:
669:
624:
489:
386:
358:
299:
52:, and to define a subset of the vectors to be independent in the matroid when it is
693:
664:
619:
571:
530:
493:
485:
443:
703:
684:
Truemper, K. (1982), "On the efficiency of representability tests for matroids",
629:
587:
538:
503:
453:
327:
230:(the four-point line) is not regular: it cannot be realized over the two-element
194:
182:
163:
331:
238:
498:
720:
250:
156:
231:
152:
49:
448:
559:
378:
307:
174:
241:, although it can be realized over all other fields. The matroid of the
583:
242:
167:
60:
lead to different sets of matroids that can be constructed from them.
575:
534:
298:
The regular matroids are the matroids that can be defined from a
44:
24:
173:
The number of bases in a regular matroid may be computed as the
234:
357:, Annals of Discrete Mathematics, Elsevier, p. 24,
159:. Every direct sum of regular matroids remains regular.
436:
Journal of
Research of the National Bureau of Standards
259:
202:
129:
109:
89:
69:
562:(1958), "A homotopy theorem for matroids. I, II",
279:
222:
135:
115:
95:
75:
564:Transactions of the American Mathematical Society
718:
123:can be represented by a system of vectors over
16:Matroid that can be represented over all fields
608:(1979), "Matroid representation over GF(3)",
474:(1980), "Decomposition of regular matroids",
697:
668:
623:
497:
447:
352:
683:
658:
604:
470:
315:
719:
520:
177:of an associated matrix, generalizing
646:
558:
554:
552:
429:
417:
405:
377:
355:Submodular Functions and Optimization
348:
346:
310:, originally proved by him using the
246:
188:
661:Linear Algebra and Its Applications
523:SIAM Journal on Applied Mathematics
151:If a matroid is regular, so is its
13:
549:
343:
14:
738:
686:European Journal of Combinatorics
83:is regular when, for every field
291:a family of results codified by
677:
652:
640:
611:Journal of Combinatorial Theory
477:Journal of Combinatorial Theory
287:, the Fano plane, or its dual.
179:Kirchhoff's matrix-tree theorem
598:
514:
464:
423:
411:
399:
371:
1:
699:10.1016/s0195-6698(82)80039-5
337:
321:
155:, and so is every one of its
146:
38:
670:10.1016/0024-3795(89)90461-8
625:10.1016/0095-8956(79)90055-8
490:10.1016/0095-8956(80)90075-1
7:
280:{\displaystyle U{}_{4}^{2}}
223:{\displaystyle U{}_{4}^{2}}
10:
743:
353:Fujishige, Satoru (2005),
300:totally unimodular matrix
432:"Lectures on matroids"
312:Tutte homotopy theorem
281:
224:
137:
117:
97:
77:
449:10.6028/jres.069b.001
430:Tutte, W. T. (1965),
282:
225:
170:operation on graphs.
138:
118:
98:
78:
663:, 114/115: 207–212,
257:
200:
127:
107:
87:
67:
54:linearly independent
332:independence oracle
304:unimodular matroids
276:
219:
499:10338.dmlcz/101946
277:
263:
220:
206:
133:
113:
93:
73:
19:In mathematics, a
293:Rota's conjecture
237:, so it is not a
189:Characterizations
136:{\displaystyle F}
116:{\displaystyle M}
96:{\displaystyle F}
76:{\displaystyle M}
734:
712:
710:
701:
681:
675:
673:
672:
656:
650:
644:
638:
636:
627:
602:
596:
594:
556:
547:
545:
518:
512:
510:
501:
468:
462:
460:
451:
427:
421:
415:
409:
403:
397:
395:
375:
369:
367:
350:
286:
284:
283:
278:
275:
270:
265:
229:
227:
226:
221:
218:
213:
208:
183:graphic matroids
142:
140:
139:
134:
122:
120:
119:
114:
102:
100:
99:
94:
82:
80:
79:
74:
742:
741:
737:
736:
735:
733:
732:
731:
717:
716:
715:
682:
678:
657:
653:
645:
641:
603:
599:
576:10.2307/1993244
557:
550:
535:10.1137/0130017
519:
515:
469:
465:
428:
424:
416:
412:
404:
400:
393:
379:Oxley, James G.
376:
372:
365:
351:
344:
340:
328:polynomial time
324:
271:
266:
264:
258:
255:
254:
214:
209:
207:
201:
198:
197:
195:uniform matroid
191:
164:graphic matroid
149:
128:
125:
124:
108:
105:
104:
88:
85:
84:
68:
65:
64:
41:
21:regular matroid
17:
12:
11:
5:
740:
730:
729:
727:Matroid theory
714:
713:
692:(3): 275–291,
676:
651:
639:
618:(2): 159–173,
606:Seymour, P. D.
597:
570:(1): 144–174,
548:
529:(1): 143–148,
513:
484:(3): 305–359,
472:Seymour, P. D.
463:
422:
410:
398:
391:
383:Matroid Theory
370:
363:
341:
339:
336:
323:
320:
316:Gerards (1989)
274:
269:
262:
239:binary matroid
217:
212:
205:
190:
187:
148:
145:
132:
112:
92:
72:
40:
37:
15:
9:
6:
4:
3:
2:
739:
728:
725:
724:
722:
709:
705:
700:
695:
691:
687:
680:
671:
666:
662:
655:
648:
643:
635:
631:
626:
621:
617:
613:
612:
607:
601:
593:
589:
585:
581:
577:
573:
569:
565:
561:
555:
553:
544:
540:
536:
532:
528:
524:
517:
509:
505:
500:
495:
491:
487:
483:
479:
478:
473:
467:
459:
455:
450:
445:
441:
437:
433:
426:
419:
414:
407:
402:
394:
392:9780199202508
388:
384:
380:
374:
366:
364:9780444520869
360:
356:
349:
347:
342:
335:
333:
329:
319:
317:
313:
309:
305:
301:
296:
294:
288:
272:
267:
260:
252:
248:
244:
240:
236:
233:
215:
210:
203:
196:
186:
184:
180:
176:
171:
169:
165:
160:
158:
154:
144:
130:
110:
90:
70:
61:
59:
55:
51:
46:
36:
34:
30:
26:
22:
689:
685:
679:
660:
654:
647:Oxley (2006)
642:
615:
614:, Series B,
609:
600:
567:
563:
560:Tutte, W. T.
526:
522:
516:
481:
480:, Series B,
475:
466:
439:
435:
425:
418:Oxley (2006)
413:
406:Oxley (2006)
401:
382:
373:
354:
325:
303:
297:
289:
247:Tutte (1958)
232:finite field
192:
172:
161:
153:dual matroid
150:
62:
50:vector space
42:
27:that can be
20:
18:
326:There is a
308:W. T. Tutte
175:determinant
29:represented
338:References
322:Algorithms
243:Fano plane
168:clique-sum
147:Properties
63:A matroid
39:Definition
420:, p. 131.
408:, p. 112.
31:over all
721:Category
649:, p. 20.
442:: 1–47,
381:(2006),
708:0679212
634:0532586
592:0101526
584:1993244
543:0392635
508:0579077
458:0179781
45:matroid
25:matroid
706:
632:
590:
582:
541:
506:
456:
389:
361:
162:Every
157:minors
58:fields
33:fields
580:JSTOR
251:minor
235:GF(2)
23:is a
387:ISBN
359:ISBN
193:The
181:for
694:doi
665:doi
620:doi
572:doi
531:doi
494:hdl
486:doi
444:doi
440:69B
723::
704:MR
702:,
688:,
630:MR
628:,
616:26
588:MR
586:,
578:,
568:88
566:,
551:^
539:MR
537:,
527:30
525:,
504:MR
502:,
492:,
482:28
454:MR
452:,
438:,
434:,
345:^
334:.
314:.
295:.
185:.
143:.
103:,
43:A
35:.
711:.
696::
690:3
674:.
667::
637:.
622::
595:.
574::
546:.
533::
511:.
496::
488::
461:.
446::
396:.
368:.
273:2
268:4
261:U
216:2
211:4
204:U
131:F
111:M
91:F
71:M
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.