5609:
5593:
11295:
11333:
In the late 1960s matroid theorists asked for a more general notion that shares the different aspects of finite matroids and generalizes their duality. Many notions of infinite matroids were defined in response to this challenge, but the question remained open. One of the approaches examined by D.A.
11623:
In his seminal paper, Whitney provided two axioms for independence, and defined any structure adhering to these axioms to be "matroids". His key observation was that these axioms provide an abstraction of "independence" that is common to both graphs and matrices. Because of this, many of the terms
843:
The dependent sets, the bases, or the circuits of a matroid characterize the matroid completely: a set is independent if and only if it is not dependent, if and only if it is a subset of a basis, and if and only if it does not contain a circuit. The collections of dependent sets, of bases, and of
11162:
The theory of infinite matroids is much more complicated than that of finite matroids and forms a subject of its own. For a long time, one of the difficulties has been that there were many reasonable and useful definitions, none of which appeared to capture all the important aspects of finite
11174:
is finite. This theory is similar to that of finite matroids except for the failure of duality due to the fact that the dual of an infinite matroid of finite rank does not have finite rank. Finite-rank matroids include any subsets of finite-dimensional vector spaces and of
8911:. Both of them are open-sourced packages. "Oid" is an interactive, extensible software system for experimenting with matroids. "Macek" is a specialized software system with tools and routines for reasonably efficient combinatorial computations with representable matroids.
11342:, it solves the problem: Arriving at the same notion independently, they provided five equivalent systems of axiom—in terms of independence, bases, circuits, closure and rank. The duality of B-matroids generalizes dualities that can be observed in infinite graphs.
2687:
8873:
of two or more matroids on the same ground set is the family of sets that are simultaneously independent in each of the matroids. The problem of finding the largest set, or the maximum weighted set, in the intersection of two matroids can be found in
11776:, Gerards, Whittle, and others, has produced substantial advances in the structure theory of matroids. Many others have also contributed to that part of matroid theory, which (in the first and second decades of the 21st century) is flourishing.
5864:
with seven points (the seven elements of the matroid) and seven lines (the proper nontrivial flats of the matroid). It is a linear matroid whose elements may be described as the seven nonzero points in a three dimensional vector space over the
2995:
3398:
3324:
11911:
There is one technical difference: A column matroid can have distinct elements that are the same vector, but a vector matroid as defined above cannot. Usually this difference is insignificant and can be ignored, but by letting
11200:
10568:
9090:
9207:
11315:), and algebraic dependence in arbitrary subsets of field extensions of possibly infinite transcendence degree. Again, the class of finitary matroid is not self-dual, because the dual of a finitary matroid is not finitary.
2751:
10718:
3470:
9610:
3146:
4000:
1202:
7855:
6836:
A signed graph, whose edges are labeled by signs, and a gain graph, which is a graph whose edges are labeled orientably from a group, each give rise to a biased graph and therefore have frame and lift matroids.
10861:
9978:
8862:
is to find as many disjoint spanning sets as possible. Both can be solved in polynomial time, and can be generalized to the problem of computing the rank or finding an independent set in a matroid sum.
9481:
5560:
every element is a coloop (an element that belongs to all bases). The direct sum of matroids of these two types is a partition matroid in which every element is a loop or a coloop; it is called a
1753:
1891:
2872:
11076:
4521:
394:
11085:. The Tutte polynomial is the most general such invariant; that is, the Tutte polynomial is a Tutte-Grothendieck invariant and every such invariant is an evaluation of the Tutte polynomial.
347:
5620:
Matroid theory developed mainly out of a deep examination of the properties of independence and dimension in vector spaces. There are two ways to present the matroids defined in this way:
728:
10346:
8243:
465:
11447:
6129:
if it is representable over the real numbers. For instance, although a graphic matroid (see below) is presented in terms of a graph, it is also representable by vectors over any field.
1929:
11003:
is neither a loop nor a coloop. An invariant of matroids (i.e., a function that takes the same value on isomorphic matroids) satisfying this recursion and the multiplicative condition
9736:
4951:
1104:
12770:. 5th International Workshop. Lecture Notes in Computer Science. Vol. 2570 (revised papers ed.). Aussois, FR: Berlin, Heidelberg: Springer (published 2003). pp. 11–26.
4076:
1994:
4881:
2527:
1136:
596:
10042:
4397:
219:
2575:
4465:
3496:
for its rank, meaning that the addition of any other element to the set would increase the rank. The closed sets of a matroid are characterized by a covering partition property:
424:
10978:
10089:
4435:
898:
9885:
3826:
3640:
2926:
11979:
The
Matroid Minors Project is an attempt to duplicate, for matroids that are representable over a finite field, the success of the Robertson–Seymour Graph Minors Project (see
8665:
658:
11485:
3091:
4326:
4294:
4226:
2775:
1625:
1233:
1066:
997:
942:
271:
10260:
2185:
3927:
1661:
7024:
628:
5558:
5519:
2145:
1574:
11733:(named by Crapo). Their work has recently (especially in the 2000s) been followed by a flood of papers—though not as many as on the Tutte polynomial of a graph.
6648:
5425:
2393:
11152:
10754:
10151:
9843:
9787:
6775:
2233:
10402:
8842:
of sets, closed under taking subsets, has the property that, no matter how the sets are weighted, the greedy algorithm finds a maximum-weight set in the family, then
5118:
4817:
4574:
3589:
10899:
4907:
4843:
4361:
11595:
11566:
11540:
11514:
11409:
11383:
11116:
8784:
7727:
7670:
7611:
7584:
7531:
7500:
7417:
4785:
2034:
7377:
7157:
7127:
6330:
6253:
5671:
5080:
4133:
3729:
3256:
2922:
2829:
1808:
1535:
1345:
564:
9659:
8002:
7956:
7753:
7696:
7637:
7557:
7094:
6982:
6834:
6486:
5842:
5761:
5346:
4159:
3329:
2468:
2349:
2263:
1481:
1451:
1298:
965:
11930:
11001:
10369:
10171:
10115:
9807:
9767:
9679:
9633:
9390:
8812:
7976:
7926:
7902:
7882:
7464:
7344:
7324:
7301:
7281:
7261:
7241:
7221:
7201:
7064:
7044:
6956:
6936:
6916:
6896:
6876:
6808:
6737:
6717:
6668:
6596:
6576:
6546:
6526:
6506:
6456:
6436:
6416:
6396:
6376:
6293:
6273:
6224:
6150:
6123:
6101:
6077:
6057:
6034:
5995:
5972:
5952:
5924:
5900:
5812:
5792:
5731:
5711:
5691:
5642:
5582:
5469:
5449:
5386:
5366:
5314:
5292:
5271:
5247:
5227:
5199:
5175:
5155:
5054:
5034:
5014:
4994:
4974:
4753:
4728:
4708:
4683:
4658:
4634:
4614:
4594:
4270:
4250:
4191:
4099:
4023:
3898:
3874:
3854:
3789:
3769:
3749:
3703:
3683:
3660:
3614:
3563:
3543:
3518:
3261:
3230:
3210:
3190:
3170:
3059:
3039:
3019:
2896:
2803:
2567:
2547:
2488:
2445:
2417:
2323:
2303:
2283:
2094:
2074:
2054:
1782:
1501:
1425:
1405:
1385:
1365:
1319:
1265:
1042:
1022:
918:
862:
834:
814:
786:
762:
698:
538:
518:
498:
299:
239:
177:
11290:{\displaystyle x\in \operatorname {cl} (Y)\ \Leftrightarrow \ {\text{ there is a finite set }}Y'\subseteq Y{\text{ such that }}x\in \operatorname {cl} (Y').}
17:
5475:. A matroid is uniform if and only if it has no circuits of size less than one plus the rank of the matroid. The direct sums of uniform matroids are called
10410:
8974:
9105:
11963:
13317:
12875:
12658:
10262:
generalizes the characteristic polynomial to two variables. This gives it more combinatorial interpretations, and also gives it the duality property
2698:
11762:
13010:
Minty, George J. (1966). "On the axiomatic foundations of the theories of directed linear graphs, electrical networks and network-programming".
10587:
8581:. A cycle is therefore the complement of a flat of the dual matroid. (This usage conflicts with the common meaning of "cycle" in graph theory.)
3417:
9492:
3095:
3934:
12766:(5–9 March 2001). "Submodular functions, matroids, and certain polyhedra". In Jünger, Michael; Reinelt, Gerhard; Rinaldi, Giovanni (eds.).
1141:
13379:. Modern Analytic and Computational Methods in Science and Mathematics. Vol. 37. New York, NY: American Elsevier Publishing Company.
12434:
7762:
13394:
11163:
matroid theory. For instance, it seemed to be hard to have bases, circuits, and duality together in one notion of infinite matroids.
10762:
8692:
A matroid that cannot be written as the direct sum of two nonempty matroids, or equivalently that has no proper separators, is called
119:, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in
96:, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or
13788:
9893:
12835:; Gerards, A.M.H.; Whittle, Geoff (2007). "Towards a matroid-minor structure theory". In Grimmett, Geoffrey; et al. (eds.).
11665:
became the foremost figure in matroid theory, a position he retained for many years. His contributions were plentiful, including
12839:. Oxford Lecture Series in Mathematics and its Applications. Vol. 34. Oxford, UK: Oxford University Press. pp. 72–82.
8556:
by deleting all loops and deleting one element from each 2-element circuit until no 2 element circuits remain is called a
6005:. Column matroids are just vector matroids under another name, but there are often reasons to favor the matrix representation.
13850:
13541:
13506:
13467:
13436:
13290:
13180:
13133:
13095:
12954:
12793:
12741:
12639:
10901:
is the number of bases. This, which sums over fewer subsets but has more complicated terms, was Tutte's original definition.
4005:
The flats of this matroid correspond one-for-one with the elements of the lattice; the flat corresponding to lattice element
7159:
which equals the number of edges outside a maximal forest of that subgraph, and also the number of independent cycles in it.
13012:
12629:
11765:'s extension to ternary matroids of Tutte's characterization of binary matroids that are representable over the rationals (
1666:
3403:
The first three of these properties are the defining properties of a closure operator. The fourth is sometimes called the
1813:
13070:
12850:
8683:
is a non-empty separator that contains no other non-empty separator. The irreducible separators partition the ground set
2833:
5564:. An equivalent definition of a discrete matroid is a matroid in which every proper, non-empty subset of the ground set
4228:
of hyperplanes of a matroid has the following properties, which may be taken as yet another axiomatization of matroids:
844:
circuits each have simple properties that may be taken as axioms for a matroid. For instance, one may define a matroid
11750:) was the most significant and influential work of the late 1970s and the 1980s. Another fundamental contribution, by
10904:
There is a further definition in terms of recursion by deletion and contraction. The deletion-contraction identity is
10723:
From this definition it is easy to see that the characteristic polynomial is, up to a simple factor, an evaluation of
9398:
9213:
8548:
if it has no circuits consisting of 1 or 2 elements. That is, it has no loops and no parallel elements. The term
5926:
on its set of columns. The dependent sets of columns in the matroid are those that are linearly dependent as vectors.
5856:
An important example of a matroid defined in this way is the Fano matroid, a rank three matroid derived from the
4470:
8245:
In linear algebra, this corresponds to looking at the quotient space by the linear space generated by the vectors in
6168:(1950s), of ternary matroids (representable over the 3 element field) due to Reid and Bixby, and separately to
316:
13840:
11719:
which are so complicated that later theorists have gone to great trouble to eliminate the need for them in proofs.
703:
10866:
Another definition is in terms of internal and external activities and a sum over bases, reflecting the fact that
10268:
6342:. Not every matroid is graphic, but all matroids on three elements are graphic. Every graphic matroid is regular.
13630:
13568:
13415:
13238:
13167:. Algorithms and Combinatorics. Vol. 6. Berlin, DE & Budapest, HU: Springer-Verlag and Akademiai Kiado.
12981:
11815:
8823:
Several important combinatorial optimization problems can be solved efficiently on every matroid. In particular:
6353:
of a graph is defined by calling a set of edges independent if every connected subset contains at most one cycle.
4173:.) These are the maximal proper flats; that is, the only superset of a hyperplane that is also a flat is the set
356:
13038:
11414:
10185:
1896:
9684:
4912:
1071:
4031:
1934:
13715:
13536:. Encyclopedia of Mathematics and its Applications. Vol. 40. Cambridge, UK: Cambridge University Press.
13462:. Encyclopedia of Mathematics and its Applications. Vol. 26. Cambridge, UK: Cambridge University Press.
13221:
12803:
Geelen, J. F.; Gerards, A. M. H.; Kapoor, A. (2000). "The excluded minors for GF(4)-representable matroids".
11980:
11009:
6132:
A basic problem in matroid theory is to characterize the matroids that may be represented over a given field
5521:
every element is a loop (an element that does not belong to any independent set), and in the uniform matroid
4848:
2682:{\displaystyle \operatorname {cl} (A)={\Bigl \{}\ x\in E\mid r(A)=r{\bigl (}A\cup \{x\}{\bigr )}{\Bigr \}}~.}
836:– that is, a dependent set whose proper subsets are all independent. The term arises because the circuits of
8175:
2500:
1109:
768:. A maximal independent set – that is, an independent set that becomes dependent upon adding any element of
569:
429:
13229:
11857:
11743:
9986:
6169:
4366:
182:
7426:. The problem of characterizing algebraic matroids is extremely difficult; little is known about it. The
6176:. A proof of Rota's conjecture was announced, but not published, in 2014 by Geelen, Gerards, and Whittle.
2990:{\displaystyle \operatorname {cl} (X)=\operatorname {cl} \left(\operatorname {cl} \left(X\right)\right)~.}
13758:
13738:
13710:
13216:
12723:
12689:
11655:
9369:
4440:
677:
399:
10910:
10047:
4402:
867:
13882:
13829:
13498:
12026:
11187:
9848:
9319:
7169:
3798:
3619:
128:
11647:
noted similarities between algebraic and linear dependence in his classic textbook on Modern
Algebra.
8605:
6008:
A matroid that is equivalent to a vector matroid, although it may be presented differently, is called
633:
13887:
11452:
8956:
8878:, and provides a solution to many other important combinatorial optimization problems. For instance,
6790:
If every cycle belongs to the distinguished class, these matroids coincide with the cycle matroid of
3064:
12776:
11338:
and was studied by Higgs, Oxley, and others in the 1960s and 1970s. According to a recent result by
4299:
4275:
4207:
2756:
1579:
1214:
1047:
978:
923:
252:
13799:
12694:
10217:
9294:
2158:
3903:
1634:
13877:
12575:
11635:
Almost immediately after
Whitney first wrote about matroids, an important article was written by
7861:
7641:
The dual can be described equally well in terms of other ways to define a matroid. For instance:
6987:
6671:
5872:. However, it is not possible to provide a similar representation for the Fano matroid using the
5767:
601:
5524:
5485:
2099:
1553:
680:). Actually, assuming (I2), property (I1) is equivalent to the fact that at least one subset of
12916:
12771:
11708:
8093:
In linear algebra, this corresponds to restricting to the subspace generated by the vectors in
7347:
6609:
5815:
5391:
2354:
1244:
12979:(1936). "Some interpretations of abstract linear dependence in terms of projective geometry".
12917:
Applications of matroid theory and combinatorial optimization to information and coding theory
12569:
Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi; Wollan, Paul (2013).
11761:
By the 1980s there were many other important contributors, but one should not omit to mention
11121:
10726:
10120:
9812:
9772:
6742:
2193:
13777:
13705:
13211:
10374:
10197:
5085:
4790:
4541:
4193:
of all the elements of the matroid. An equivalent definition is that a coatom is a subset of
3829:
3568:
2148:
101:
11847:
10869:
9635:
is disconnected, or empty, or a loop. Otherwise it depends only on the lattice of flats of
8858:
is to partition the elements of a matroid into as few independent sets as possible, and the
4886:
4822:
4340:
3393:{\displaystyle b\in \operatorname {cl} (Y\cup \{a\})\smallsetminus \operatorname {cl} (Y)~.}
13769:
13607:
13348:
13300:
13190:
13143:
13105:
13046:
13025:
12964:
12910:. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. pp. 287–296.
12824:
12751:
12608:
11571:
11545:
11519:
11493:
11388:
11362:
11180:
11094:
9241:
8869:
8853:
8762:
8376:, and whose independent sets are those subsets that are the union of an independent set in
7705:
7648:
7589:
7562:
7509:
7478:
7386:
7380:
6153:
5880:
4758:
2007:
2004:
These properties can be used as one of the alternative definitions of a finite matroid: If
13689:
13551:
13516:
13477:
13446:
13384:
13271:
13151:
13113:
8904:
7353:
7136:
7103:
6306:
6229:
5650:
5059:
4112:
3708:
3319:{\displaystyle a\in \operatorname {cl} (Y\cup \{b\})\smallsetminus \operatorname {cl} (Y)}
3235:
2901:
2808:
1787:
1511:
1324:
543:
8:
12649:
11640:
11176:
9638:
7981:
7935:
7732:
7675:
7616:
7536:
7073:
6961:
6850:
6813:
6461:
6296:
6172:(1970s), and of quaternary matroids (representable over the 4 element field) due to
6037:
5903:
5821:
5740:
5734:
5325:
4138:
3877:
2450:
2328:
2242:
1756:
1460:
1430:
1277:
673:
85:
10180:
of the first and second kind, which are the
Whitney numbers of the cycle matroid of the
6001:
For instance, the Fano matroid can be represented in this way as a 3 × 7
947:
13803:
13595:
13530:
13491:
13456:
13336:
13194:
13161:
12998:
12936:
12894:
12711:
12677:
12612:
12584:
11915:
11323:
10986:
10354:
10156:
10100:
9792:
9752:
9664:
9618:
9375:
8797:
7961:
7911:
7887:
7867:
7449:
7329:
7309:
7286:
7266:
7246:
7226:
7206:
7186:
7049:
7029:
6941:
6921:
6901:
6881:
6861:
6793:
6722:
6702:
6653:
6581:
6561:
6531:
6511:
6491:
6441:
6421:
6401:
6381:
6361:
6350:
6278:
6258:
6209:
6135:
6108:
6086:
6062:
6042:
6019:
5980:
5957:
5937:
5909:
5885:
5797:
5777:
5716:
5696:
5676:
5627:
5567:
5454:
5434:
5371:
5351:
5299:
5277:
5256:
5232:
5212:
5184:
5160:
5140:
5039:
5019:
4999:
4979:
4959:
4738:
4713:
4693:
4668:
4643:
4619:
4599:
4579:
4255:
4235:
4176:
4084:
4008:
3883:
3859:
3839:
3774:
3754:
3734:
3688:
3668:
3645:
3599:
3548:
3528:
3503:
3215:
3195:
3175:
3155:
3044:
3024:
3004:
2881:
2788:
2552:
2532:
2473:
2430:
2402:
2308:
2288:
2268:
2079:
2059:
2039:
1997:
1767:
1486:
1410:
1390:
1370:
1350:
1304:
1250:
1027:
1007:
903:
847:
819:
799:
771:
747:
739:
683:
523:
503:
483:
284:
224:
162:
13726:
13856:
13846:
13677:
13537:
13502:
13463:
13432:
13286:
13252:
13233:
13198:
13176:
13129:
13091:
12976:
12950:
12860:
12845:
12789:
12737:
12731:
12715:
12635:
11792:
9217:
8887:
7423:
7130:
5476:
3663:
3405:
2152:
105:
12616:
11729:
generalized to matroids Tutte's "dichromate", a graphic polynomial now known as the
10563:{\displaystyle T_{M}(x,y)=\sum _{S\subseteq E}(x-1)^{r(M)-r(S)}\ (y-1)^{|S|-r(S)}~.}
9085:{\displaystyle p_{M}(\lambda ):=\sum _{S\subseteq E}(-1)^{|S|}\lambda ^{r(E)-r(S)},}
13734:
13685:
13667:
13639:
13585:
13577:
13555:
13547:
13520:
13512:
13481:
13473:
13442:
13403:
13380:
13326:
13267:
13257:
13247:
13202:
13168:
13147:
13109:
13083:
13055:
12990:
12968:
12942:
12884:
12855:
12812:
12781:
12755:
12703:
12667:
12594:
12116:
12014:
11755:
11730:
11654:
developed further theory under the name "independence systems" with an eye towards
11089:
10210:
9202:{\displaystyle p_{M}(\lambda ):=\sum _{A}\mu (\emptyset ,A)\lambda ^{r(E)-r(A)}\ ,}
8923:
8890:. However, finding the largest set in an intersection of three or more matroids is
8879:
8835:
8830:
8791:
8757:
6846:
2693:
1243:
It is a basic result of matroid theory, directly analogous to a similar theorem of
93:
55:
12768:
Combinatorial
Optimization — Eureka, You Shrink!: Papers dedicated to Jack Edmonds
7427:
6184:
5613:
13603:
13563:
13497:. Encyclopedia of Mathematics and its Applications. Vol. 29. Cambridge, UK:
13344:
13296:
13186:
13139:
13101:
13021:
12960:
12820:
12747:
12727:
12604:
12002:
11852:
11820:
11678:
11674:
11356:
10193:
10189:
10177:
8883:
8875:
8725:
to an irreducible separator is a component. A separator is a union of components.
8286:
7176:
6604:
6338:
6180:
5861:
5318:
4531:
3833:
3493:
3414:. These properties may be taken as another definition of matroid: every function
837:
8934:
There are two especially significant polynomials associated to a finite matroid
13407:
13034:
11802:
11670:
11625:
11613:
10181:
8748:
8334:
8137:
are precisely the results of a sequence of deletions: the order is irrelevant.
6810:. If no cycle is distinguished, the frame matroid is the bicircular matroid of
6187:
is the simplest example of a matroid that is not representable over any field.
6161:
6002:
5250:
4329:
3409:
274:
148:
132:
112:
13818:
13590:
13280:
13262:
13172:
13087:
12946:
12599:
12570:
11186:
The next simplest infinite generalization is finitary matroids, also known as
9983:
summed over flats of the right rank. These numbers alternate in sign, so that
8738:
if it, or a matroid that contains it, has a basis such that all the points of
8345:, and whose independent sets are the disjoint unions of an independent set of
2746:{\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\mapsto {\mathcal {P}}(E)}
13871:
13860:
13750:
13681:
13659:
13163:
Matroid Theory and its
Applications in Electric Network Theory and in Statics
13059:
12625:
11898:, pp. 298–302, for a list of matroid axiom systems that are equivalent.
11862:
11842:
11737:
11682:
11308:
8476:
8368:
is the matroid whose underlying set is the union (not the disjoint union) of
8265:
8021:
5766:
The validity of the independent set axioms for this matroid follows from the
136:
42:
13392:
Vámos, Peter (1978). "The missing axiom of matroid theory is lost forever".
13080:
A lost mathematician, Takeo
Nakasawa: The forgotten father of matroid theory
12785:
11303:
Examples are linear dependence of arbitrary subsets of infinite-dimensional
9337:
is any field), the characteristic polynomial of the arrangement is given by
13672:
13654:
13644:
13621:
12816:
12763:
11832:
11797:
11651:
11629:
11319:
11312:
11304:
7905:
7472:
6696:
6688:
6679:
6678:, and it is a special case of a gammoid. The transversal matroids are the
6300:
6196:
6157:
5866:
5645:
5178:
1505:
1269:
116:
89:
12846:"A short proof of Tutte's characterization of totally unimodular matrices"
11949:
did not include an axiom requiring at least one subset to be independent.
11624:
used in matroid theory resemble the terms for their analogous concepts in
10713:{\displaystyle R_{M}(u,v)=\sum _{S\subseteq E}u^{r(M)-r(S)}v^{|S|-r(S)}~.}
3465:{\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\to {\mathcal {P}}(E)}
13372:
13356:
13308:
13121:
12906:
Kingan, Robert; Kingan, Sandra (2005). "A software system for matroids".
12020:
11996:
11810:
11662:
9605:{\displaystyle \beta (M)=(-1)^{r(M)}\sum _{X\subseteq E}(-1)^{|X|}r(X)~.}
9220:
of the matroid and the sum is taken over all the flats A of the matroid.
8891:
8787:
6842:
6670:
of the bipartition, and the independent subsets are sets of endpoints of
6165:
5873:
4201:, but such that adding any other element to it does make a spanning set.
46:
11999: – Mathematical system of orderings or sets with antiexchange axiom
11772:
In the current period (since around 2000) the
Matroid Minors Project of
8908:
6650:, one may form a matroid in which the elements are vertices on one side
3141:{\displaystyle \operatorname {cl} (X)\subseteq \operatorname {cl} (Y)~.}
2036:
satisfies these properties, then the independent sets of a matroid over
353:(I2) Every subset of an independent set is independent, i.e., for each
13599:
13340:
13002:
12898:
12832:
12707:
12681:
12091:, pp. 21–22), Section 1.8, "Closed sets = Flats = Subspaces".
11885:
is a standard source for basic definitions and results about matroids;
11837:
11773:
7929:
6692:
6203:
5857:
5597:
3995:{\displaystyle \operatorname {cl} (S)=\{x\in E\mid x\leq \bigvee S\}~.}
242:
13743:— A large bibliography of matroid papers, matroid software, and links.
10196:. The name has been extended to the similar numbers for finite ranked
8004:
The dual of a transversal matroid is a strict gammoid and vice versa.
4081:
Thus, the lattice of flats of this matroid is naturally isomorphic to
672:
The first two properties define a combinatorial structure known as an
8919:
8011:
The cycle matroid of a graph is the dual matroid of its bond matroid.
2778:
1197:{\displaystyle (A\smallsetminus \{a\})\cup \{b\}\in {\mathcal {B}}~.}
310:
35:
13581:
13331:
13312:
12994:
12889:
12870:
12733:
On the
Foundations of Combinatorial Theory: Combinatorial geometries
12672:
12653:
12106:, pp. 38–39), Section 2.2, "The Hyperplanes of a Matroid".
8505:. Equivalently, an element is a coloop if it belongs to every basis.
8264:
by a sequence of restriction and contraction operations is called a
7422:
A matroid that is equivalent to a matroid of this kind is called an
12008:
11933:
11300:
Equivalently, every dependent set contains a finite dependent set.
9372:(1967), may be expressed in terms of the characteristic polynomial
8915:
8903:
Two standalone systems for calculations with matroids are Kingan's
8838:. This fact may even be used to characterize matroids: if a family
7958:
The dual of a vector matroid representable over a particular field
7850:{\displaystyle r^{*}(S)=|S|-r(M)+r\left(E\smallsetminus S\right)~.}
7438:
There are some standard ways to make new matroids out of old ones.
124:
120:
12589:
11936:
of vectors one brings the two definitions into complete agreement.
9240:, the characteristic polynomial is a slight transformation of the
8721:
to an irreducible separator, and contrariwise, the restriction of
8479:
of a matroid is the size of its smallest circuit or dependent set.
8285:. Many important families of matroids may be characterized by the
12837:
Combinatorics, Complexity, and Chance: A tribute to
Dominic Welsh
12079:, pp. 7–9), Section 1.2, "Axiom Systems for a Matroid".
11327:
8946:, which means that isomorphic matroids have the same polynomial.
6550:
6183:
is a matroid that is representable over all possible fields. The
1542:
31:
10856:{\displaystyle p_{M}(\lambda )=(-1)^{r(M)}T_{M}(1-\lambda ,0)~.}
8926:
has a package for dealing with matroids since the version 2024.
5608:
9615:
The beta invariant is non-negative, and is zero if and only if
8492:. Equivalently, an element is a loop if it belongs to no basis.
6295:
and consider a set of edges independent if and only if it is a
2265:
It is the minimum number of elements that must be removed from
278:
111:
Matroid theory borrows extensively from the terms used in both
12568:
11339:
8700:. A matroid is connected if and only if its dual is connected.
8552:
is also used. A simple matroid obtained from another matroid
73:
11166:
The simplest definition of an infinite matroid is to require
8742:
are contained in the lines that join pairs of basis elements.
5869:
5794:
is a matroid that can be defined in this way, we say the set
5601:
5592:
1893:
From the first inequality it follows more generally that, if
1541:(R1) The value of the rank function is always a non-negative
1267:
have the same number of elements. This number is called the
520:
are two independent sets (i.e., each set is independent) and
10573:
This expresses the Tutte polynomial as an evaluation of the
9973:{\displaystyle w_{i}(M)=\sum \{\mu (\emptyset ,A):r(A)=i\},}
8751:
if all of its circuits have size at least equal to its rank.
8289:
matroids that do not belong to the family; these are called
5177:
defines the independent sets of a matroid. It is called the
84:
is a structure that abstracts and generalizes the notion of
13566:(1935). "On the abstract properties of linear dependence".
11784:
Mathematicians who pioneered the study of matroids include
64:
12915:
Kashyap, Navin; Soljanin, Emina; Vontobel, Pascal (2009).
11740:
published the first comprehensive book on matroid theory.
11658:, where his name for the subject is still sometimes used.
10351:
which implies a number of dualities between properties of
8968:, although it does not count colorings – is defined to be
7066:
as its class of independent sets, is a matroid called the
11769:), perhaps the biggest single contribution of the 1990s.
12549:
12547:
7430:
provides an example of a matroid that is not algebraic.
6687:
Graphic matroids have been generalized to matroids from
5427:
All uniform matroids of rank at least 2 are simple (see
13622:"A characterization of the matroids representable over
13361:
Journal of Research of the National Bureau of Standards
12914:
12056:
12029: – Formulation of matroids using closure operators
9095:
or equivalently (as long as the empty set is closed in
6345:
Other matroids on graphs were discovered subsequently:
6195:
A second original source for the theory of matroids is
7502:
by taking the same underlying set and calling a set a
1427:
to be independent if and only if it is independent in
12544:
12435:"The Matroids and Hypergraphs Packages in Maple 2024"
11918:
11574:
11548:
11522:
11496:
11455:
11417:
11391:
11365:
11203:
11124:
11097:
11012:
10989:
10913:
10872:
10765:
10729:
10590:
10413:
10377:
10357:
10271:
10220:
10159:
10123:
10103:
10050:
9989:
9896:
9851:
9815:
9795:
9775:
9755:
9687:
9667:
9641:
9621:
9495:
9401:
9378:
9108:
8977:
8800:
8765:
8608:
8178:
8140:
The dual operation of restriction is contraction. If
7984:
7964:
7938:
7914:
7890:
7870:
7765:
7735:
7708:
7678:
7651:
7619:
7592:
7565:
7539:
7512:
7481:
7452:
7389:
7356:
7332:
7312:
7289:
7269:
7249:
7229:
7209:
7189:
7139:
7106:
7076:
7052:
7032:
6990:
6964:
6944:
6924:
6904:
6884:
6864:
6816:
6796:
6745:
6725:
6705:
6656:
6612:
6584:
6564:
6534:
6514:
6494:
6464:
6444:
6424:
6404:
6384:
6364:
6309:
6281:
6261:
6232:
6212:
6138:
6111:
6089:
6065:
6045:
6022:
5983:
5960:
5940:
5912:
5888:
5824:
5800:
5780:
5743:
5719:
5699:
5679:
5653:
5630:
5570:
5527:
5488:
5457:
5437:
5394:
5374:
5354:
5328:
5302:
5280:
5259:
5235:
5215:
5187:
5163:
5143:
5088:
5062:
5042:
5022:
5002:
4982:
4962:
4915:
4889:
4851:
4825:
4793:
4761:
4741:
4716:
4696:
4671:
4646:
4622:
4602:
4582:
4544:
4473:
4443:
4405:
4369:
4343:
4302:
4278:
4258:
4238:
4210:
4179:
4141:
4115:
4087:
4034:
4011:
3937:
3906:
3886:
3862:
3842:
3801:
3777:
3757:
3737:
3711:
3691:
3671:
3648:
3622:
3602:
3571:
3551:
3531:
3506:
3420:
3332:
3264:
3238:
3218:
3198:
3178:
3158:
3098:
3067:
3047:
3027:
3007:
2929:
2904:
2884:
2836:
2811:
2791:
2759:
2701:
2578:
2555:
2535:
2503:
2476:
2453:
2433:
2405:
2357:
2331:
2311:
2291:
2271:
2245:
2196:
2161:
2102:
2082:
2062:
2042:
2010:
1937:
1899:
1816:
1790:
1770:
1748:{\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)~.}
1669:
1637:
1582:
1556:
1514:
1489:
1463:
1433:
1413:
1393:
1373:
1353:
1327:
1307:
1280:
1253:
1217:
1144:
1112:
1074:
1050:
1030:
1010:
981:
950:
926:
906:
870:
850:
822:
802:
774:
750:
706:
686:
636:
604:
572:
546:
526:
506:
486:
432:
402:
359:
319:
287:
255:
227:
185:
165:
92:. There are many equivalent ways to define a matroid
12831:
11698:
and the tools he used to prove many of his results:
9789:
in the characteristic polynomial. Specifically, the
8846:
must be the family of independent sets of a matroid.
6160:. The main results so far are characterizations of
1886:{\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1~.}
1537:
of the matroid, which has the following properties:
76:
70:
67:
12802:
12634:. London, UK & New York, NY: Chapman and Hall.
11568:can be extended to a maximal independent subset of
8066:whose independent sets are the independent sets of
6418:be two distinguished sets of vertices. In the set
6173:
5036:are the circuit and cocircuit classes of a matroid
2867:{\displaystyle X\subseteq \operatorname {cl} (X)~.}
61:
58:
13529:
13490:
13455:
13431:. L.M.S. Monographs. Vol. 8. Academic Press.
13160:
13078:Nishimura, Hirokazu; Kuroda, Susumu, eds. (2009).
12005: – Group-theoretic generalization of matroids
11970:) of Tutte's characterization of regular matroids.
11924:
11589:
11560:
11534:
11508:
11479:
11441:
11403:
11377:
11352:Every subset of an independent set is independent.
11289:
11146:
11110:
11070:
10995:
10972:
10893:
10855:
10748:
10712:
10562:
10396:
10363:
10340:
10254:
10165:
10145:
10109:
10083:
10036:
9972:
9879:
9837:
9801:
9781:
9761:
9730:
9673:
9653:
9627:
9604:
9475:
9384:
9201:
9084:
8886:can be expressed as a problem of intersecting two
8806:
8778:
8659:
8497:An element that belongs to no circuit is called a
8484:An element that forms a single-element circuit of
8237:
7996:
7970:
7950:
7920:
7896:
7876:
7849:
7747:
7721:
7690:
7664:
7631:
7605:
7578:
7551:
7525:
7494:
7458:
7411:
7371:
7338:
7318:
7295:
7275:
7255:
7235:
7215:
7195:
7151:
7121:
7088:
7058:
7038:
7018:
6976:
6950:
6930:
6910:
6890:
6870:
6828:
6802:
6769:
6731:
6711:
6662:
6642:
6590:
6570:
6540:
6520:
6500:
6480:
6450:
6430:
6410:
6390:
6370:
6324:
6287:
6267:
6247:
6218:
6144:
6117:
6095:
6071:
6051:
6028:
5989:
5966:
5946:
5918:
5894:
5836:
5806:
5786:
5755:
5725:
5705:
5685:
5665:
5636:
5576:
5552:
5513:
5463:
5443:
5419:
5380:
5360:
5340:
5308:
5286:
5265:
5241:
5221:
5193:
5169:
5149:
5112:
5074:
5048:
5028:
5008:
4988:
4968:
4945:
4901:
4875:
4837:
4811:
4779:
4747:
4722:
4702:
4677:
4652:
4628:
4608:
4588:
4568:
4515:
4459:
4429:
4391:
4355:
4320:
4288:
4264:
4244:
4220:
4185:
4153:
4127:
4093:
4070:
4017:
3994:
3921:
3892:
3868:
3848:
3820:
3783:
3763:
3743:
3723:
3697:
3677:
3654:
3634:
3608:
3583:
3557:
3537:
3512:
3472:that obeys these properties determines a matroid.
3464:
3392:
3318:
3250:
3224:
3204:
3184:
3164:
3140:
3085:
3053:
3033:
3013:
2989:
2916:
2890:
2866:
2823:
2797:
2769:
2745:
2681:
2561:
2541:
2521:
2482:
2462:
2439:
2411:
2387:
2343:
2317:
2297:
2277:
2257:
2227:
2179:
2139:
2088:
2068:
2048:
2028:
1988:
1923:
1885:
1802:
1776:
1747:
1655:
1619:
1568:
1529:
1495:
1475:
1445:
1419:
1399:
1379:
1359:
1339:
1313:
1292:
1259:
1227:
1211:. It follows from this property that no member of
1196:
1130:
1098:
1060:
1036:
1016:
991:
959:
936:
912:
892:
856:
828:
808:
780:
756:
722:
692:
652:
622:
590:
558:
532:
512:
492:
459:
418:
388:
341:
293:
265:
233:
213:
171:
13318:Transactions of the American Mathematical Society
12876:Transactions of the American Mathematical Society
12659:Transactions of the American Mathematical Society
11190:. A matroid with possibly infinite ground set is
10176:The Whitney numbers of both kinds generalize the
7163:
3880:under the following closure operator: for a set
2668:
2599:
13869:
10117:are the numbers of flats of each rank. That is,
9476:{\displaystyle \beta (M)=(-1)^{r(M)-1}p_{M}'(1)}
8412:be a matroid with an underlying set of elements
8309:be a matroid with an underlying set of elements
6156:describes a possible characterization for every
4755:is represented as the disjoint union of subsets
4516:{\displaystyle (Y\cap Z)\cup \{x\}\subseteq X~.}
3480:A set whose closure equals itself is said to be
2151:, such a matroid structure is equivalent to the
13414:
13077:
12553:
11758:play such an important role in matroid theory.
11746:'s decomposition theorem for regular matroids (
11644:
11617:
5587:
13811:— Gives proofs for statements in this article.
12654:"A decomposition for combinatorial geometries"
12011: – Set system used in greedy optimization
8914:Both open source mathematics software systems
342:{\displaystyle \emptyset \in {\mathcal {I}}~.}
12623:
12017: – Abstraction of ordered linear algebra
11694:the theory of chain groups and their matroids
11600:With these axioms, every matroid has a dual.
8249:, together with the images of the vectors in
7729:if and only if its complement is a coatom in
7168:A third original source of matroid theory is
6190:
2661:
2639:
2285:to obtain an independent set. The nullity of
723:{\displaystyle {\mathcal {I}}\neq \emptyset }
104:, a finite simple matroid is equivalent to a
27:Abstraction of linear independence of vectors
13032:
12905:
12124:Notices of the American Mathematical Society
12045:
11689:the regular-matroid representability theorem
11516:of the base space, every independent subset
11471:
11465:
10341:{\displaystyle T_{M^{*}}(x,y)=T_{M}(y,x)\ ,}
9964:
9922:
8949:
8392:, but that assumption is not essential. If
7533:if and only if its complement is a basis in
4956:He proved that there is a matroid for which
4806:
4800:
4498:
4492:
4059:
4035:
3983:
3956:
3360:
3354:
3292:
3286:
2656:
2650:
1850:
1844:
1175:
1169:
1160:
1154:
617:
611:
13828:(academic personal site). Baton Rouge, LA:
12268:
12266:
9293:, the characteristic polynomial equals the
8400:are disjoint, the union is the direct sum.
8384:. Usually the term "union" is applied when
8333:is the matroid whose underlying set is the
7133:of the subgraph induced on the edge subset
6845:form the bases of the two dimensional
5157:be a finite set. The set of all subsets of
4996:is the class of cocircuits. Conversely, if
389:{\displaystyle A'\subseteq A\subseteq E\ ,}
159:In terms of independence, a finite matroid
13776:(academic personal site). Binghamton, NY:
13757:(academic personal site). Boca Raton, FL:
13395:Journal of the London Mathematical Society
13209:
12510:
12508:
12495:
12493:
12456:
12454:
12331:
12329:
12050:
11616:, whose work was forgotten for many years
11612:. It was also independently discovered by
11442:{\displaystyle \ x\in J\smallsetminus I\ }
11318:Finitary infinite matroids are studied in
10404:One definition of the Tutte polynomial is
9887:and is the sum of Möbius function values:
8573:A union of circuits is sometimes called a
1924:{\displaystyle A\subseteq B\subseteq E\ ,}
1407:can be defined by considering a subset of
13671:
13652:
13643:
13589:
13330:
13261:
13251:
12888:
12859:
12775:
12722:
12671:
12648:
12598:
12588:
12398:
12314:
12278:
11827:Some of the other major contributors are
11726:
9731:{\displaystyle \beta (M)=\beta (M^{*})~.}
9268:is the number of connected components of
6036:is equivalent to a vector matroid over a
5431:). The uniform matroid of rank 2 on
4946:{\displaystyle g\in Y\subseteq B\cup G~.}
3492:of the matroid. A set is closed if it is
1099:{\displaystyle a\in A\smallsetminus B\ ,}
13278:
12868:
12370:
12368:
12302:
12290:
12263:
12251:
12239:
12191:
12169:
12167:
12154:
12152:
12099:
12097:
11751:
11345:The independence axioms are as follows:
10192:, the (co)founder of matroid theory, by
8929:
8317:be another matroid on an underlying set
6164:(those representable over GF(2)) due to
5607:
5591:
4685:(called a "cocircuit") contains another,
4071:{\displaystyle \{x\in E\mid x\leq y\}~.}
1989:{\displaystyle r(A)\leq r(B)\leq r(E)~.}
840:are cycles in the corresponding graphs.
13798:(academic personal site). Seattle, WA:
13619:
13562:
13228:
13128:. Oxford, UK: Oxford University Press.
12975:
12871:"Varieties of combinatorial geometries"
12843:
12762:
12532:
12520:
12505:
12490:
12478:
12466:
12451:
12380:
12326:
12227:
12057:Kashyap, Soljanin & Vontobel (2009)
12039:
11967:
11946:
11766:
11754:, showed why projective geometries and
11747:
11636:
11609:
11071:{\displaystyle F(M\oplus M')=F(M)F(M')}
8168:, is the matroid on the underlying set
7466:is a finite matroid, we can define the
4876:{\displaystyle g\in X\subseteq R\cup G}
14:
13870:
13838:
13527:
13377:Introduction to the Theory of Matroids
13158:
12869:Kahn, Jeff; Kung, Joseph P.S. (1982).
12526:
12179:
12139:
12137:
12135:
12133:
12072:
12070:
12068:
12066:
12064:
11359:(under set inclusion) independent set
9769:are the coefficients of the powers of
8238:{\displaystyle r'(A)=r(A\cup T)-r(T).}
7433:
5122:self-dual cryptomorphic axiomatization
5120:is a graphoid. Thus, graphoids give a
4660:(called a "circuit") contains another,
4232:(H1) There do not exist distinct sets
2522:{\displaystyle \operatorname {cl} (A)}
1131:{\displaystyle b\in B\smallsetminus A}
591:{\displaystyle x\in A\smallsetminus B}
460:{\displaystyle A'\in {\mathcal {I}}~.}
13786:
13488:
13453:
13426:
13391:
13371:
13355:
13307:
13120:
13009:
12688:
12538:
12514:
12499:
12484:
12472:
12460:
12421:
12409:
12386:
12374:
12365:
12359:
12353:
12347:
12335:
12320:
12308:
12296:
12284:
12272:
12257:
12245:
12233:
12221:
12215:
12209:
12203:
12197:
12185:
12173:
12164:
12158:
12149:
12143:
12103:
12094:
12088:
12076:
12023: – Multiset analogue of matroids
11895:
11886:
11882:
11722:
11712:
11307:(but not infinite dependencies as in
10037:{\displaystyle (-1)^{i}w_{i}(M)>0}
7179:of a field gives rise to a matroid:
6849:, a matroid defined in the theory of
6739:of cycles, known as a "biased graph"
5428:
4730:intersect in exactly one element, and
4392:{\displaystyle Y,Z\in {\mathcal {H}}}
1235:can be a proper subset of any other.
733:
214:{\displaystyle (E,{\mathcal {I}})\ ,}
18:Characteristic polynomial of matroids
13613:
13013:Journal of Mathematics and Mechanics
12934:
12631:Independence Theory in Combinatorics
12415:
12403:
12341:
11157:
8829:maximum-weight independent set in a
8717:. A component is the restriction of
8705:A maximal irreducible submatroid of
8074:. Its circuits are the circuits of
7884:is a graphic matroid if and only if
7672:if and only if its complement spans
6358:In any directed or undirected graph
6299:; that is, if it does not contain a
5316:to be a basis. This is known as the
3836:. Conversely, every matroid lattice
2422:
1457:and about the rank of any subset of
13234:"Decomposition of regular matroids"
13071:Mathematical Association of America
12851:Linear Algebra and Its Applications
12130:
12061:
11118:of a graph is the Tutte polynomial
10203:
9392:as an evaluation of the derivative
8898:
8510:Loop and coloops are mutually dual.
8403:
7559:It is not difficult to verify that
6336:. Matroids derived in this way are
6174:Geelen, Gerards & Kapoor (2000)
5596:The Fano matroid, derived from the
5204:
4616:are classes of nonempty subsets of
4460:{\displaystyle X\in {\mathcal {H}}}
419:{\displaystyle A\in {\mathcal {I}}}
154:
151:ways to define a (finite) matroid.
24:
13767:
13724:
13655:"Frame matroids and biased graphs"
10973:{\displaystyle F(M)=F(M-e)+F(M/e)}
10095:Whitney numbers of the second kind
10084:{\displaystyle 0\leq i\leq r(M)~.}
9931:
9740:
9147:
8431:. Its elements may be called the
8300:
7860:According to a matroid version of
7586:is a matroid and that the dual of
6719:with a distinguished linear class
5713:by taking the independent sets of
4819:(a singleton set), then either an
4452:
4430:{\displaystyle x\notin Y\cup Z\ ,}
4384:
4281:
4213:
3804:
3448:
3429:
2762:
2729:
2710:
1247:, that any two bases of a matroid
1220:
1183:
1053:
984:
929:
893:{\displaystyle (E,{\mathcal {B}})}
882:
764:that is not independent is called
717:
709:
639:
446:
411:
328:
320:
258:
197:
25:
13899:
13816:
13748:
13698:
11945:Although it was perhaps implied,
11894:See the appendix by Brylawski in
11608:Matroid theory was introduced by
11236: there is a finite set
9880:{\displaystyle \lambda ^{r(M)-i}}
9747:Whitney numbers of the first kind
9359:
8082:and its rank function is that of
7759:The rank function of the dual is
5848:Matroids of this kind are called
3821:{\displaystyle {\mathcal {L}}(M)}
3642:is in precisely one of the flats
3635:{\displaystyle E\smallsetminus S}
2781:, with the following properties:
1238:
1207:This property (B2) is called the
971:, with the following properties:
816:is a minimal dependent subset of
666:independent set exchange property
305:) with the following properties:
13359:(1965). "Lectures on matroids".
13082:. Basel, CH: Birkhäuser Verlag.
12692:(1969). "The Tutte polynomial".
8660:{\displaystyle r(S)+r(E-S)=r(M)}
7864:, the dual of a graphic matroid
4328:That is, the hyperplanes form a
3616:is a flat, then each element of
2187:partially ordered by inclusion.
2056:can be defined as those subsets
653:{\displaystyle {\mathcal {I}}~.}
54:
13631:Journal of Combinatorial Theory
13569:American Journal of Mathematics
13239:Journal of Combinatorial Theory
12982:American Journal of Mathematics
12938:A Source Book in Matroid Theory
12935:Kung, Joseph P.S., ed. (1986).
12805:Journal of Combinatorial Theory
12736:. Cambridge, MA: M.I.T. Press.
12427:
12392:
11973:
11956:
11939:
11639:on the relation of matroids to
11480:{\displaystyle \ I\cup \{x\}\ }
8675:is a separator that is neither
6777:has two matroids, known as the
6674:of the graph. This is called a
6458:to be independent if there are
5132:
4165:. (Hyperplanes are also called
3086:{\displaystyle X\subseteq Y\ ,}
2155:whose elements are the subsets
13845:. Cambridge University Press.
13285:. Boston, MA: Academic Press.
12571:"Axioms for infinite matroids"
12109:
12082:
11905:
11876:
11779:
11281:
11270:
11228:
11222:
11216:
11139:
11133:
11065:
11054:
11048:
11042:
11033:
11016:
10967:
10953:
10944:
10932:
10923:
10917:
10888:
10876:
10844:
10826:
10811:
10805:
10798:
10788:
10782:
10776:
10699:
10693:
10683:
10675:
10664:
10658:
10649:
10643:
10613:
10601:
10549:
10543:
10533:
10525:
10520:
10507:
10499:
10493:
10484:
10478:
10471:
10458:
10436:
10424:
10329:
10317:
10301:
10289:
10243:
10231:
10140:
10134:
10072:
10066:
10025:
10019:
10000:
9990:
9955:
9949:
9940:
9928:
9913:
9907:
9866:
9860:
9832:
9826:
9719:
9706:
9697:
9691:
9681:has no loops and coloops then
9593:
9587:
9578:
9570:
9565:
9555:
9534:
9528:
9521:
9511:
9505:
9499:
9470:
9464:
9440:
9434:
9427:
9417:
9411:
9405:
9188:
9182:
9173:
9167:
9156:
9144:
9125:
9119:
9074:
9068:
9059:
9053:
9039:
9031:
9026:
9016:
8994:
8988:
8654:
8648:
8639:
8627:
8618:
8612:
8568:if its dual matroid is simple.
8229:
8223:
8214:
8202:
8193:
8187:
8030:is a matroid with element set
7813:
7807:
7797:
7789:
7782:
7776:
7399:
7391:
7366:
7360:
7164:Matroids from field extensions
7116:
7110:
7007:
7001:
6758:
6746:
6637:
6619:
6474:
6466:
6319:
6313:
6242:
6236:
5253:. One may define a matroid on
5107:
5089:
4563:
4545:
4486:
4474:
4321:{\displaystyle X\subseteq Y~.}
4289:{\displaystyle {\mathcal {H}}}
4221:{\displaystyle {\mathcal {H}}}
4104:
3950:
3944:
3815:
3809:
3459:
3453:
3443:
3440:
3434:
3381:
3375:
3363:
3345:
3313:
3307:
3295:
3277:
3129:
3123:
3111:
3105:
2942:
2936:
2855:
2849:
2770:{\displaystyle {\mathcal {P}}}
2740:
2734:
2724:
2721:
2715:
2628:
2622:
2591:
2585:
2516:
2510:
2382:
2376:
2367:
2361:
2222:
2216:
2206:
2198:
2127:
2119:
2112:
2106:
2023:
2011:
1977:
1971:
1962:
1956:
1947:
1941:
1868:
1862:
1853:
1835:
1826:
1820:
1736:
1730:
1721:
1715:
1706:
1694:
1685:
1673:
1620:{\displaystyle r(A)\leq |A|~.}
1607:
1599:
1592:
1586:
1524:
1518:
1228:{\displaystyle {\mathcal {B}}}
1163:
1145:
1061:{\displaystyle {\mathcal {B}}}
992:{\displaystyle {\mathcal {B}}}
944:is a collection of subsets of
937:{\displaystyle {\mathcal {B}}}
920:is a finite set as before and
887:
871:
266:{\displaystyle {\mathcal {I}}}
202:
186:
13:
1:
12561:
12554:Nishimura & Kuroda (2009)
11889:is an older standard source.
11618:Nishimura & Kuroda (2009)
11349:The empty set is independent.
10255:{\displaystyle T_{M}(x,y)\ ,}
8818:
6918:be the collection of subsets
6528:. This defines a matroid on
5673:then we can define a matroid
4976:is the class of circuits and
3856:forms a matroid over its set
2447:be a matroid on a finite set
2180:{\displaystyle A\subset M\ ,}
1453:This allows us to talk about
1106:then there exists an element
660:This is sometimes called the
467:This is sometimes called the
142:
13770:"Matroids and signed graphs"
13253:10.1016/0095-8956(80)90075-1
12861:10.1016/0024-3795(89)90461-8
12033:
11869:
11385:and maximal independent set
11194:if it has the property that
11083:Tutte-Grothendieck invariant
9368:of a matroid, introduced by
8062:, is the matroid on the set
7908:. In this case, the dual of
5604:-linear but not real-linear.
5588:Matroids from linear algebra
5348:A uniform matroid with rank
4526:
3922:{\displaystyle \bigvee S\ ,}
1656:{\displaystyle A,B\subset E}
7:
13759:Florida Atlantic University
13739:City University of New York
13711:Encyclopedia of Mathematics
13217:Encyclopedia of Mathematics
12117:"Solving Rota's conjecture"
11990:
10153:is the number of rank
8349:with an independent set of
7978:is also representable over
7019:{\displaystyle M^{*}(G)\ ,}
6578:is the whole vertex set of
6488:vertex-disjoint paths from
5930:This matroid is called the
5616:, not linear over any field
5127:
744:A subset of the ground set
678:abstract simplicial complex
623:{\displaystyle B\cup \{x\}}
10:
13904:
13839:White, Neil, ed. (1992b).
13830:Louisiana State University
13789:"A brief look at matroids"
13733:(academic personal site).
13731:userhome.brooklyn.cuny.edu
13653:Zaslavsky, Thomas (1994).
13528:White, Neil, ed. (1992a).
13499:Cambridge University Press
13210:Sapozhenko, A.A. (2001) .
12941:. Boston, MA: Birkhäuser.
12046:Neel & Neudauer (2009)
12027:Pregeometry (model theory)
11603:
10579:rank generating polynomial
10184:, and equivalently of the
8922:contain matroid packages.
8019:
7441:
6191:Matroids from graph theory
5644:is any finite subset of a
5553:{\displaystyle U_{n,n}\ ,}
5514:{\displaystyle U_{0,n}\ ,}
3832:by set inclusion, forms a
2140:{\displaystyle r(A)=|A|~.}
1569:{\displaystyle A\subset E}
737:
129:combinatorial optimization
29:
13863:– via Google Books.
13489:White, Neil, ed. (1987).
13454:White, Neil, ed. (1986).
13173:10.1007/978-3-662-22143-3
13088:10.1007/978-3-7643-8573-6
13039:"Matroids you have known"
12947:10.1007/978-1-4684-9199-9
12600:10.1016/j.aim.2013.01.011
11981:Robertson–Seymour theorem
9325:of linear hyperplanes in
8957:characteristic polynomial
8950:Characteristic polynomial
8086:restricted to subsets of
8015:
7348:algebraically independent
6984:is still connected. Then
6878:be a connected graph and
6643:{\displaystyle G=(U,V,E)}
6558:is one for which the set
5420:{\displaystyle U_{k,n}~.}
3500:(F1) The whole point set
2388:{\displaystyle r(E)-r(A)}
2325:is called the nullity of
1631:(R3) For any two subsets
13800:University of Washington
13493:Combinatorial Geometries
13408:10.1112/jlms/s2-18.3.403
13279:Truemper, Klaus (1992).
13060:10.4169/193009809x469020
12930:– via www.birs.ca.
12844:Gerards, A.M.H. (1989).
12695:Aequationes Mathematicae
12126:: 736–743. Aug 17, 2014.
11669:the characterization of
11147:{\displaystyle T_{M(G)}}
10749:{\displaystyle T_{M}\ ,}
10188:. They were named after
10146:{\displaystyle W_{i}(M)}
9838:{\displaystyle w_{i}(M)}
9782:{\displaystyle \lambda }
7645:A set is independent in
7283:be any finite subset of
6770:{\displaystyle (G,B)\ ,}
6275:the set of all edges in
6226:gives rise to a matroid
5906:gives rise to a matroid
3475:
2395:is sometimes called the
2228:{\displaystyle |A|-r(A)}
1044:are distinct members of
30:Not to be confused with
13620:Whittle, Geoff (1995).
13159:Recski, András (1989).
12786:10.1007/3-540-36478-1_2
12576:Advances in Mathematics
11170:; that is, the rank of
10397:{\displaystyle M^{*}~.}
8964:– sometimes called the
8860:matroid packing problem
8172:whose rank function is
8109:this may be termed the
7350:if the extension field
6682:to the strict gammoids.
6202:Every finite graph (or
5768:Steinitz exchange lemma
5482:In the uniform matroid
5429:§ Additional terms
5113:{\displaystyle (E,C,D)}
4812:{\displaystyle G=\{g\}}
4569:{\displaystyle (L,C,D)}
3584:{\displaystyle S\cap T}
1755:That is, the rank is a
1245:bases in linear algebra
1209:basis exchange property
540:has more elements than
13673:10.1006/eujc.1994.1034
13645:10.1006/jctb.1995.1052
13626:(3) and the rationals"
13427:Welsh, D.J.A. (1976).
12817:10.1006/jctb.2000.1963
11926:
11752:Kahn & Kung (1982)
11709:Tutte homotopy theorem
11645:van der Waerden (1937)
11591:
11562:
11536:
11510:
11481:
11443:
11405:
11379:
11334:Higgs became known as
11291:
11154:of its cycle matroid.
11148:
11112:
11072:
10997:
10974:
10895:
10894:{\displaystyle T(1,1)}
10857:
10750:
10714:
10564:
10398:
10365:
10342:
10256:
10198:partially ordered sets
10167:
10147:
10111:
10085:
10038:
9974:
9881:
9845:is the coefficient of
9839:
9803:
9783:
9763:
9732:
9675:
9655:
9629:
9606:
9477:
9386:
9203:
9086:
8808:
8780:
8747:A matroid is called a
8679:nor the empty set. An
8661:
8550:combinatorial geometry
8515:If a two-element set {
8260:that is obtained from
8239:
8078:that are contained in
8070:that are contained in
7998:
7972:
7952:
7928:is the matroid of the
7922:
7898:
7878:
7851:
7749:
7723:
7702:A set is a circuit of
7692:
7666:
7633:
7607:
7580:
7553:
7527:
7496:
7460:
7413:
7373:
7340:
7320:
7297:
7277:
7257:
7237:
7217:
7197:
7153:
7123:
7090:
7060:
7040:
7020:
6978:
6952:
6932:
6912:
6892:
6872:
6830:
6804:
6771:
6733:
6713:
6664:
6644:
6592:
6572:
6542:
6522:
6502:
6482:
6452:
6432:
6412:
6392:
6372:
6326:
6289:
6269:
6249:
6220:
6146:
6119:
6097:
6073:
6053:
6030:
5991:
5968:
5948:
5920:
5896:
5838:
5808:
5788:
5757:
5727:
5707:
5687:
5667:
5638:
5617:
5605:
5578:
5554:
5515:
5465:
5445:
5421:
5382:
5362:
5342:
5310:
5288:
5267:
5243:
5223:
5195:
5171:
5151:
5114:
5076:
5050:
5030:
5010:
4990:
4970:
4947:
4903:
4902:{\displaystyle Y\in D}
4877:
4839:
4838:{\displaystyle X\in C}
4813:
4781:
4749:
4724:
4704:
4679:
4654:
4630:
4610:
4590:
4570:
4517:
4461:
4431:
4393:
4357:
4356:{\displaystyle x\in E}
4322:
4290:
4266:
4246:
4222:
4187:
4155:
4129:
4095:
4072:
4019:
3996:
3923:
3894:
3870:
3850:
3822:
3785:
3765:
3745:
3725:
3699:
3679:
3656:
3636:
3610:
3585:
3559:
3539:
3514:
3466:
3394:
3320:
3252:
3226:
3206:
3186:
3166:
3152:(C4) For all elements
3142:
3087:
3055:
3035:
3015:
2991:
2918:
2892:
2868:
2825:
2799:
2771:
2747:
2683:
2563:
2543:
2523:
2484:
2464:
2441:
2413:
2389:
2345:
2319:
2299:
2279:
2259:
2229:
2181:
2149:partially ordered sets
2141:
2090:
2070:
2050:
2030:
1990:
1925:
1887:
1804:
1778:
1749:
1657:
1621:
1570:
1531:
1497:
1477:
1447:
1421:
1401:
1381:
1361:
1341:
1315:
1294:
1261:
1229:
1198:
1132:
1100:
1062:
1038:
1018:
993:
961:
938:
914:
894:
858:
830:
810:
782:
758:
724:
700:is independent, i.e.,
694:
654:
624:
592:
560:
534:
514:
494:
461:
420:
390:
343:
313:is independent, i.e.,
295:
267:
235:
215:
173:
102:partially ordered sets
13778:Binghamton University
13416:van der Waerden, B.L.
13313:"Matroids and graphs"
13282:Matroid Decomposition
11927:
11592:
11590:{\displaystyle \ X~.}
11563:
11561:{\displaystyle \ X\ }
11537:
11535:{\displaystyle \ I\ }
11511:
11509:{\displaystyle \ X\ }
11482:
11444:
11406:
11404:{\displaystyle \ J\ }
11380:
11378:{\displaystyle \ I\ }
11292:
11255: such that
11149:
11113:
11111:{\displaystyle T_{G}}
11073:
10998:
10975:
10896:
10858:
10751:
10715:
10565:
10399:
10366:
10343:
10257:
10168:
10148:
10112:
10086:
10039:
9975:
9882:
9840:
9804:
9784:
9764:
9733:
9676:
9656:
9630:
9607:
9478:
9387:
9244:, which is given by χ
9228:is the cycle matroid
9204:
9087:
8930:Polynomial invariants
8809:
8781:
8779:{\displaystyle P_{M}}
8681:irreducible separator
8673:non-trivial separator
8662:
8240:
8133:. The submatroids of
7999:
7973:
7953:
7923:
7899:
7879:
7852:
7750:
7724:
7722:{\displaystyle M^{*}}
7693:
7667:
7665:{\displaystyle M^{*}}
7634:
7608:
7606:{\displaystyle M^{*}}
7581:
7579:{\displaystyle M^{*}}
7554:
7528:
7526:{\displaystyle M^{*}}
7497:
7495:{\displaystyle M^{*}}
7461:
7414:
7412:{\displaystyle |S|~.}
7374:
7341:
7321:
7298:
7278:
7258:
7238:
7218:
7198:
7154:
7124:
7091:
7061:
7041:
7026:whose element set is
7021:
6979:
6953:
6933:
6913:
6898:be its edge set. Let
6893:
6873:
6831:
6805:
6772:
6734:
6714:
6665:
6645:
6593:
6573:
6543:
6523:
6503:
6483:
6453:
6433:
6413:
6393:
6373:
6327:
6290:
6270:
6250:
6221:
6147:
6120:
6098:
6074:
6054:
6031:
5992:
5969:
5949:
5921:
5897:
5839:
5809:
5789:
5758:
5728:
5708:
5688:
5668:
5639:
5611:
5595:
5579:
5555:
5516:
5466:
5451:points is called the
5446:
5422:
5383:
5363:
5343:
5311:
5289:
5268:
5244:
5224:
5196:
5172:
5152:
5115:
5077:
5051:
5031:
5011:
4991:
4971:
4948:
4904:
4878:
4840:
4814:
4782:
4780:{\displaystyle R,G,B}
4750:
4725:
4705:
4680:
4655:
4631:
4611:
4591:
4571:
4518:
4462:
4432:
4394:
4358:
4323:
4291:
4267:
4247:
4223:
4188:
4156:
4130:
4109:In a matroid of rank
4096:
4073:
4020:
3997:
3924:
3895:
3871:
3851:
3823:
3786:
3766:
3746:
3731:but there is no flat
3726:
3700:
3680:
3657:
3637:
3611:
3586:
3560:
3540:
3515:
3467:
3395:
3321:
3253:
3227:
3207:
3187:
3167:
3143:
3088:
3056:
3036:
3016:
3001:(C3) For all subsets
2992:
2919:
2893:
2878:(C2) For all subsets
2869:
2826:
2800:
2785:(C1) For all subsets
2772:
2748:
2684:
2564:
2544:
2524:
2485:
2470:, with rank function
2465:
2442:
2414:
2390:
2346:
2320:
2300:
2280:
2260:
2230:
2182:
2142:
2091:
2071:
2051:
2031:
2029:{\displaystyle (E,r)}
1991:
1926:
1888:
1805:
1779:
1750:
1658:
1622:
1571:
1532:
1498:
1483:The rank of a subset
1478:
1448:
1422:
1402:
1382:
1362:
1342:
1316:
1295:
1262:
1230:
1199:
1133:
1101:
1063:
1039:
1019:
994:
962:
939:
915:
895:
859:
831:
811:
783:
759:
725:
695:
662:augmentation property
655:
625:
593:
561:
535:
515:
495:
462:
421:
391:
344:
296:
268:
236:
216:
174:
100:. In the language of
13842:Matroid Applications
13819:"What is a matroid?"
13532:Matroid Applications
13303:– via emis.de.
13047:Mathematics Magazine
12908:Graphs and Discovery
12854:. 114–115: 207–212.
12650:Brylawski, Thomas H.
11916:
11816:B.L. van der Waerden
11572:
11546:
11520:
11494:
11453:
11415:
11389:
11363:
11326:with strong ties to
11201:
11181:transcendence degree
11122:
11095:
11010:
10987:
10911:
10870:
10763:
10727:
10588:
10411:
10375:
10355:
10269:
10218:
10157:
10121:
10101:
10048:
9987:
9894:
9849:
9813:
9793:
9773:
9753:
9685:
9665:
9639:
9619:
9493:
9399:
9376:
9281:is the bond matroid
9242:chromatic polynomial
9212:where μ denotes the
9106:
8975:
8966:chromatic polynomial
8870:matroid intersection
8854:matroid partitioning
8798:
8763:
8606:
8544:A matroid is called
8458:. A set is said to
8176:
7982:
7962:
7936:
7912:
7904:is the matroid of a
7888:
7868:
7862:Kuratowski's theorem
7763:
7733:
7706:
7676:
7649:
7617:
7590:
7563:
7537:
7510:
7479:
7450:
7387:
7381:transcendence degree
7372:{\displaystyle F(S)}
7354:
7330:
7310:
7287:
7267:
7247:
7227:
7207:
7187:
7152:{\displaystyle F\ ,}
7137:
7122:{\displaystyle r(F)}
7104:
7074:
7050:
7030:
6988:
6962:
6942:
6922:
6902:
6882:
6862:
6814:
6794:
6785:of the biased graph.
6743:
6723:
6703:
6654:
6610:
6582:
6562:
6532:
6512:
6492:
6462:
6442:
6422:
6402:
6382:
6362:
6325:{\displaystyle M(G)}
6307:
6279:
6259:
6255:as follows: take as
6248:{\displaystyle M(G)}
6230:
6210:
6136:
6109:
6087:
6063:
6043:
6020:
5981:
5958:
5938:
5910:
5886:
5822:
5798:
5778:
5741:
5735:linearly independent
5717:
5697:
5677:
5666:{\displaystyle V\ ,}
5651:
5628:
5568:
5525:
5486:
5455:
5435:
5392:
5388:elements is denoted
5372:
5352:
5326:
5300:
5278:
5257:
5233:
5229:be a finite set and
5213:
5185:
5161:
5141:
5086:
5075:{\displaystyle E\ ,}
5060:
5040:
5020:
5000:
4980:
4960:
4913:
4887:
4849:
4823:
4791:
4759:
4739:
4714:
4694:
4669:
4644:
4620:
4600:
4580:
4542:
4471:
4441:
4403:
4367:
4341:
4300:
4276:
4256:
4236:
4208:
4177:
4139:
4128:{\displaystyle r\ ,}
4113:
4085:
4032:
4009:
3935:
3904:
3884:
3860:
3840:
3799:
3775:
3755:
3735:
3724:{\displaystyle S\ ,}
3709:
3689:
3669:
3646:
3620:
3600:
3569:
3549:
3529:
3504:
3418:
3330:
3262:
3251:{\displaystyle E\ ,}
3236:
3216:
3196:
3176:
3156:
3096:
3065:
3045:
3025:
3005:
2927:
2917:{\displaystyle E\ ,}
2902:
2882:
2834:
2824:{\displaystyle E\ ,}
2809:
2789:
2757:
2699:
2576:
2553:
2533:
2501:
2474:
2451:
2431:
2403:
2355:
2329:
2309:
2289:
2269:
2243:
2194:
2159:
2100:
2080:
2060:
2040:
2008:
1935:
1897:
1814:
1803:{\displaystyle x\ ,}
1788:
1768:
1667:
1635:
1580:
1554:
1550:(R2) For any subset
1530:{\displaystyle r(A)}
1512:
1487:
1461:
1431:
1411:
1391:
1387:, then a matroid on
1371:
1351:
1340:{\displaystyle E\ ,}
1325:
1305:
1278:
1251:
1215:
1142:
1110:
1072:
1048:
1028:
1008:
979:
948:
924:
904:
868:
848:
820:
800:
772:
748:
704:
684:
634:
602:
570:
559:{\displaystyle B\ ,}
544:
524:
504:
484:
430:
400:
357:
317:
285:
253:
225:
183:
163:
13796:math.washington.edu
13774:math.binghamton.edu
13751:"Greedy algorithms"
11641:projective geometry
11340:Bruhn et al. (2013)
9654:{\displaystyle M~.}
9463:
8834:can be solved by a
8097:. Equivalently if
7997:{\displaystyle F~.}
7951:{\displaystyle G~.}
7748:{\displaystyle M~.}
7691:{\displaystyle M~.}
7632:{\displaystyle M~.}
7552:{\displaystyle M~.}
7434:Basic constructions
7089:{\displaystyle G~.}
6977:{\displaystyle G-F}
6851:structural rigidity
6829:{\displaystyle G~.}
6676:transversal matroid
6481:{\displaystyle |U|}
5876:in place of GF(2).
5837:{\displaystyle M~.}
5756:{\displaystyle E~.}
5341:{\displaystyle k~.}
4665:(G2) no element of
4640:(G1) no element of
4197:that does not span
4154:{\displaystyle r-1}
3900:of atoms with join
2463:{\displaystyle E\ }
2344:{\displaystyle M~.}
2258:{\displaystyle A~.}
2147:In the language of
1996:That is, rank is a
1757:submodular function
1476:{\displaystyle E~.}
1446:{\displaystyle M~.}
1293:{\displaystyle M~.}
792:for the matroid. A
734:Bases and circuits
674:independence system
469:hereditary property
86:linear independence
13809:on 12 August 2010.
13768:Pagano, Steven R.
13591:10338.dmlcz/100694
13458:Theory of Matroids
13363:. Section B.
13263:10338.dmlcz/101946
13035:Neudauer, Nancy A.
12708:10.1007/BF01817442
12323:, pp. 146–147
11962:A fine example is
11922:
11807:Hirokazu Nishimura
11756:Dowling geometries
11702:the "Path theorem"
11656:transversal theory
11587:
11558:
11532:
11506:
11477:
11439:
11401:
11375:
11324:mathematical logic
11287:
11144:
11108:
11068:
10993:
10970:
10891:
10853:
10746:
10710:
10634:
10560:
10457:
10394:
10371:and properties of
10361:
10338:
10252:
10163:
10143:
10107:
10081:
10034:
9970:
9877:
9835:
9809:th Whitney number
9799:
9779:
9759:
9728:
9671:
9651:
9625:
9602:
9554:
9473:
9451:
9382:
9199:
9140:
9082:
9015:
8938:on the ground set
8888:partition matroids
8804:
8776:
8657:
8519:} is a circuit of
8466:if its closure is
8454:if its closure is
8423:may be called the
8235:
7994:
7968:
7948:
7918:
7894:
7874:
7847:
7745:
7719:
7688:
7662:
7629:
7603:
7576:
7549:
7523:
7492:
7456:
7409:
7369:
7336:
7316:
7293:
7273:
7253:
7233:
7213:
7193:
7149:
7119:
7100:The rank function
7086:
7056:
7036:
7016:
6974:
6948:
6928:
6908:
6888:
6868:
6826:
6800:
6767:
6729:
6709:
6660:
6640:
6588:
6568:
6538:
6518:
6498:
6478:
6448:
6438:, define a subset
6428:
6408:
6388:
6368:
6351:bicircular matroid
6322:
6285:
6265:
6245:
6216:
6142:
6127:real representable
6115:
6093:
6081:representable over
6069:
6049:
6026:
5987:
5964:
5944:
5916:
5902:with entries in a
5892:
5834:
5804:
5784:
5753:
5723:
5703:
5683:
5663:
5634:
5618:
5606:
5574:
5550:
5511:
5477:partition matroids
5461:
5441:
5417:
5378:
5358:
5338:
5306:
5284:
5263:
5239:
5219:
5191:
5167:
5147:
5110:
5072:
5046:
5026:
5006:
4986:
4966:
4943:
4899:
4873:
4835:
4809:
4777:
4745:
4720:
4700:
4675:
4650:
4626:
4606:
4586:
4566:
4513:
4457:
4427:
4389:
4353:
4318:
4286:
4262:
4242:
4218:
4183:
4151:
4125:
4091:
4068:
4015:
3992:
3919:
3890:
3866:
3846:
3818:
3781:
3761:
3741:
3721:
3705:properly contains
3695:
3675:
3652:
3632:
3606:
3581:
3555:
3535:
3510:
3462:
3390:
3316:
3248:
3222:
3202:
3182:
3162:
3138:
3083:
3051:
3031:
3011:
2987:
2914:
2888:
2864:
2821:
2795:
2767:
2743:
2679:
2559:
2539:
2519:
2480:
2460:
2437:
2423:Closure operators
2409:
2385:
2341:
2315:
2295:
2275:
2255:
2225:
2177:
2137:
2086:
2066:
2046:
2026:
1998:monotonic function
1986:
1921:
1883:
1800:
1774:
1745:
1653:
1617:
1566:
1527:
1493:
1473:
1443:
1417:
1397:
1377:
1357:
1337:
1311:
1290:
1257:
1225:
1194:
1128:
1096:
1058:
1034:
1014:
989:
960:{\displaystyle E,}
957:
934:
910:
890:
854:
826:
806:
778:
754:
740:Basis of a matroid
720:
690:
650:
620:
588:
566:then there exists
556:
530:
510:
490:
457:
416:
386:
339:
291:
263:
231:
211:
169:
13883:Closure operators
13852:978-0-5213-8165-9
13787:Hubenthal, Mark.
13634:. Series B.
13543:978-0-521-38165-9
13508:978-0-521-33339-9
13469:978-0-521-30937-0
13438:978-0-12-744050-7
13292:978-0-12-701225-4
13242:. Series B.
13182:978-3-540-15285-9
13135:978-0-19-853563-8
13097:978-3-7643-8572-9
12977:MacLane, Saunders
12956:978-0-8176-3173-4
12795:978-3-540-36478-8
12743:978-0-262-53016-3
12641:978-0-412-22430-0
11925:{\displaystyle E}
11583:
11577:
11557:
11551:
11531:
11525:
11505:
11499:
11490:For every subset
11476:
11458:
11438:
11420:
11400:
11394:
11374:
11368:
11256:
11237:
11233:
11227:
11158:Infinite matroids
10996:{\displaystyle e}
10849:
10742:
10706:
10619:
10556:
10506:
10442:
10390:
10364:{\displaystyle M}
10334:
10248:
10186:partition lattice
10166:{\displaystyle i}
10110:{\displaystyle M}
10077:
9802:{\displaystyle i}
9762:{\displaystyle M}
9724:
9674:{\displaystyle M}
9647:
9628:{\displaystyle M}
9598:
9539:
9385:{\displaystyle p}
9264: (λ), where
9218:geometric lattice
9195:
9131:
9000:
8944:matroid invariant
8807:{\displaystyle M}
8792:indicator vectors
8404:Additional terms
7990:
7971:{\displaystyle F}
7944:
7921:{\displaystyle M}
7897:{\displaystyle M}
7877:{\displaystyle M}
7843:
7741:
7684:
7625:
7545:
7459:{\displaystyle M}
7424:algebraic matroid
7405:
7339:{\displaystyle E}
7319:{\displaystyle S}
7296:{\displaystyle K}
7276:{\displaystyle E}
7256:{\displaystyle F}
7236:{\displaystyle K}
7216:{\displaystyle K}
7196:{\displaystyle F}
7145:
7131:cyclomatic number
7082:
7059:{\displaystyle I}
7039:{\displaystyle E}
7012:
6951:{\displaystyle E}
6931:{\displaystyle F}
6911:{\displaystyle I}
6891:{\displaystyle E}
6871:{\displaystyle G}
6822:
6803:{\displaystyle G}
6763:
6732:{\displaystyle B}
6712:{\displaystyle G}
6663:{\displaystyle U}
6591:{\displaystyle G}
6571:{\displaystyle E}
6541:{\displaystyle E}
6521:{\displaystyle U}
6501:{\displaystyle F}
6451:{\displaystyle U}
6431:{\displaystyle E}
6411:{\displaystyle F}
6391:{\displaystyle E}
6371:{\displaystyle G}
6288:{\displaystyle G}
6268:{\displaystyle E}
6219:{\displaystyle G}
6154:Rota's conjecture
6145:{\displaystyle F}
6118:{\displaystyle M}
6096:{\displaystyle F}
6072:{\displaystyle M}
6052:{\displaystyle F}
6029:{\displaystyle M}
6003:(0,1) matrix
5990:{\displaystyle M}
5967:{\displaystyle A}
5947:{\displaystyle A}
5919:{\displaystyle M}
5895:{\displaystyle A}
5830:
5807:{\displaystyle E}
5787:{\displaystyle M}
5749:
5726:{\displaystyle M}
5706:{\displaystyle E}
5686:{\displaystyle M}
5659:
5637:{\displaystyle E}
5577:{\displaystyle E}
5546:
5507:
5464:{\displaystyle n}
5444:{\displaystyle n}
5413:
5381:{\displaystyle n}
5361:{\displaystyle k}
5334:
5309:{\displaystyle E}
5287:{\displaystyle k}
5266:{\displaystyle E}
5242:{\displaystyle k}
5222:{\displaystyle E}
5194:{\displaystyle E}
5170:{\displaystyle E}
5150:{\displaystyle E}
5068:
5049:{\displaystyle M}
5029:{\displaystyle D}
5009:{\displaystyle C}
4989:{\displaystyle D}
4969:{\displaystyle C}
4939:
4909:exists such that
4845:exists such that
4748:{\displaystyle L}
4723:{\displaystyle D}
4703:{\displaystyle C}
4678:{\displaystyle D}
4653:{\displaystyle C}
4629:{\displaystyle L}
4609:{\displaystyle D}
4589:{\displaystyle C}
4534:(1966) defined a
4509:
4423:
4314:
4265:{\displaystyle Y}
4245:{\displaystyle X}
4186:{\displaystyle E}
4121:
4094:{\displaystyle L}
4064:
4018:{\displaystyle y}
3988:
3915:
3893:{\displaystyle S}
3869:{\displaystyle E}
3849:{\displaystyle L}
3830:partially ordered
3784:{\displaystyle T}
3764:{\displaystyle S}
3744:{\displaystyle U}
3717:
3698:{\displaystyle T}
3678:{\displaystyle S}
3655:{\displaystyle T}
3609:{\displaystyle S}
3558:{\displaystyle T}
3538:{\displaystyle S}
3513:{\displaystyle E}
3412:exchange property
3386:
3244:
3225:{\displaystyle Y}
3205:{\displaystyle E}
3185:{\displaystyle b}
3165:{\displaystyle a}
3134:
3079:
3054:{\displaystyle E}
3034:{\displaystyle Y}
3014:{\displaystyle X}
2983:
2910:
2891:{\displaystyle X}
2860:
2817:
2798:{\displaystyle X}
2675:
2606:
2562:{\displaystyle E}
2542:{\displaystyle A}
2483:{\displaystyle r}
2459:
2440:{\displaystyle M}
2412:{\displaystyle A}
2337:
2318:{\displaystyle M}
2298:{\displaystyle E}
2278:{\displaystyle A}
2251:
2173:
2153:geometric lattice
2133:
2089:{\displaystyle E}
2069:{\displaystyle A}
2049:{\displaystyle E}
1982:
1917:
1879:
1796:
1777:{\displaystyle A}
1764:(R4) For any set
1741:
1613:
1496:{\displaystyle A}
1469:
1439:
1420:{\displaystyle A}
1400:{\displaystyle A}
1380:{\displaystyle E}
1360:{\displaystyle A}
1333:
1314:{\displaystyle M}
1286:
1260:{\displaystyle M}
1190:
1092:
1037:{\displaystyle B}
1017:{\displaystyle A}
913:{\displaystyle E}
857:{\displaystyle M}
829:{\displaystyle E}
809:{\displaystyle M}
781:{\displaystyle E}
757:{\displaystyle E}
693:{\displaystyle E}
646:
552:
533:{\displaystyle A}
513:{\displaystyle B}
493:{\displaystyle A}
453:
382:
335:
294:{\displaystyle E}
234:{\displaystyle E}
207:
172:{\displaystyle M}
155:Independent sets
106:geometric lattice
16:(Redirected from
13895:
13888:Families of sets
13864:
13833:
13823:
13810:
13808:
13802:. Archived from
13793:
13781:
13762:
13742:
13737:. Brooklyn, NY:
13735:Brooklyn College
13727:"Matroid theory"
13725:Kingan, Sandra.
13719:
13693:
13675:
13649:
13647:
13616:, pp. 55–79
13611:
13593:
13564:Whitney, Hassler
13559:
13556:Internet Archive
13535:
13524:
13521:Internet Archive
13496:
13485:
13482:Internet Archive
13461:
13450:
13423:
13411:
13388:
13368:
13352:
13334:
13304:
13275:
13265:
13255:
13230:Seymour, Paul D.
13225:
13206:
13203:Internet Archive
13166:
13155:
13117:
13074:
13068:
13066:
13043:
13033:Neel, David L.;
13029:
13006:
12972:
12969:Internet Archive
12931:
12929:
12927:
12921:
12911:
12902:
12892:
12865:
12863:
12840:
12828:
12799:
12779:
12759:
12756:Internet Archive
12728:Rota, Gian-Carlo
12719:
12685:
12675:
12645:
12624:Bryant, Victor;
12620:
12602:
12592:
12556:
12551:
12542:
12536:
12530:
12524:
12518:
12512:
12503:
12497:
12488:
12482:
12476:
12470:
12464:
12458:
12449:
12448:
12446:
12445:
12439:
12431:
12425:
12419:
12413:
12407:
12401:
12399:Zaslavsky (1994)
12396:
12390:
12384:
12378:
12372:
12363:
12357:
12351:
12345:
12339:
12333:
12324:
12318:
12312:
12306:
12300:
12294:
12288:
12282:
12276:
12270:
12261:
12255:
12249:
12243:
12237:
12231:
12225:
12219:
12213:
12207:
12201:
12200:, pp. 72–97
12195:
12189:
12188:, pp. 46–48
12183:
12177:
12171:
12162:
12156:
12147:
12141:
12128:
12127:
12121:
12113:
12107:
12101:
12092:
12086:
12080:
12074:
12059:
12054:
12048:
12043:
12015:Oriented matroid
11984:
11977:
11971:
11960:
11954:
11943:
11937:
11931:
11929:
11928:
11923:
11909:
11903:
11880:
11793:Saunders MacLane
11731:Tutte polynomial
11727:Brylawski (1972)
11643:. A year later,
11596:
11594:
11593:
11588:
11581:
11575:
11567:
11565:
11564:
11559:
11555:
11549:
11541:
11539:
11538:
11533:
11529:
11523:
11515:
11513:
11512:
11507:
11503:
11497:
11486:
11484:
11483:
11478:
11474:
11456:
11448:
11446:
11445:
11440:
11436:
11418:
11410:
11408:
11407:
11402:
11398:
11392:
11384:
11382:
11381:
11376:
11372:
11366:
11296:
11294:
11293:
11288:
11280:
11257:
11254:
11246:
11238:
11235:
11231:
11225:
11177:field extensions
11153:
11151:
11150:
11145:
11143:
11142:
11117:
11115:
11114:
11109:
11107:
11106:
11090:Tutte polynomial
11081:is said to be a
11077:
11075:
11074:
11069:
11064:
11032:
11002:
11000:
10999:
10994:
10979:
10977:
10976:
10971:
10963:
10900:
10898:
10897:
10892:
10862:
10860:
10859:
10854:
10847:
10825:
10824:
10815:
10814:
10775:
10774:
10755:
10753:
10752:
10747:
10740:
10739:
10738:
10719:
10717:
10716:
10711:
10704:
10703:
10702:
10686:
10678:
10668:
10667:
10633:
10600:
10599:
10569:
10567:
10566:
10561:
10554:
10553:
10552:
10536:
10528:
10504:
10503:
10502:
10456:
10423:
10422:
10403:
10401:
10400:
10395:
10388:
10387:
10386:
10370:
10368:
10367:
10362:
10347:
10345:
10344:
10339:
10332:
10316:
10315:
10288:
10287:
10286:
10285:
10261:
10259:
10258:
10253:
10246:
10230:
10229:
10211:Tutte polynomial
10204:Tutte polynomial
10178:Stirling numbers
10172:
10170:
10169:
10164:
10152:
10150:
10149:
10144:
10133:
10132:
10116:
10114:
10113:
10108:
10090:
10088:
10087:
10082:
10075:
10043:
10041:
10040:
10035:
10018:
10017:
10008:
10007:
9979:
9977:
9976:
9971:
9906:
9905:
9886:
9884:
9883:
9878:
9876:
9875:
9844:
9842:
9841:
9836:
9825:
9824:
9808:
9806:
9805:
9800:
9788:
9786:
9785:
9780:
9768:
9766:
9765:
9760:
9737:
9735:
9734:
9729:
9722:
9718:
9717:
9680:
9678:
9677:
9672:
9660:
9658:
9657:
9652:
9645:
9634:
9632:
9631:
9626:
9611:
9609:
9608:
9603:
9596:
9583:
9582:
9581:
9573:
9553:
9538:
9537:
9482:
9480:
9479:
9474:
9459:
9450:
9449:
9391:
9389:
9388:
9383:
9328:
9208:
9206:
9205:
9200:
9193:
9192:
9191:
9139:
9118:
9117:
9091:
9089:
9088:
9083:
9078:
9077:
9044:
9043:
9042:
9034:
9014:
8987:
8986:
8899:Matroid software
8884:bipartite graphs
8880:maximum matching
8836:greedy algorithm
8831:weighted matroid
8813:
8811:
8810:
8805:
8794:of the bases of
8785:
8783:
8782:
8777:
8775:
8774:
8758:matroid polytope
8666:
8664:
8663:
8658:
8244:
8242:
8241:
8236:
8186:
8003:
8001:
8000:
7995:
7988:
7977:
7975:
7974:
7969:
7957:
7955:
7954:
7949:
7942:
7927:
7925:
7924:
7919:
7903:
7901:
7900:
7895:
7883:
7881:
7880:
7875:
7856:
7854:
7853:
7848:
7841:
7840:
7836:
7800:
7792:
7775:
7774:
7754:
7752:
7751:
7746:
7739:
7728:
7726:
7725:
7720:
7718:
7717:
7697:
7695:
7694:
7689:
7682:
7671:
7669:
7668:
7663:
7661:
7660:
7638:
7636:
7635:
7630:
7623:
7612:
7610:
7609:
7604:
7602:
7601:
7585:
7583:
7582:
7577:
7575:
7574:
7558:
7556:
7555:
7550:
7543:
7532:
7530:
7529:
7524:
7522:
7521:
7501:
7499:
7498:
7493:
7491:
7490:
7465:
7463:
7462:
7457:
7418:
7416:
7415:
7410:
7403:
7402:
7394:
7378:
7376:
7375:
7370:
7345:
7343:
7342:
7337:
7325:
7323:
7322:
7317:
7306:Define a subset
7302:
7300:
7299:
7294:
7282:
7280:
7279:
7274:
7262:
7260:
7259:
7254:
7242:
7240:
7239:
7234:
7223:are fields with
7222:
7220:
7219:
7214:
7202:
7200:
7199:
7194:
7158:
7156:
7155:
7150:
7143:
7128:
7126:
7125:
7120:
7095:
7093:
7092:
7087:
7080:
7065:
7063:
7062:
7057:
7045:
7043:
7042:
7037:
7025:
7023:
7022:
7017:
7010:
7000:
6999:
6983:
6981:
6980:
6975:
6957:
6955:
6954:
6949:
6937:
6935:
6934:
6929:
6917:
6915:
6914:
6909:
6897:
6895:
6894:
6889:
6877:
6875:
6874:
6869:
6847:rigidity matroid
6835:
6833:
6832:
6827:
6820:
6809:
6807:
6806:
6801:
6776:
6774:
6773:
6768:
6761:
6738:
6736:
6735:
6730:
6718:
6716:
6715:
6710:
6669:
6667:
6666:
6661:
6649:
6647:
6646:
6641:
6597:
6595:
6594:
6589:
6577:
6575:
6574:
6569:
6547:
6545:
6544:
6539:
6527:
6525:
6524:
6519:
6507:
6505:
6504:
6499:
6487:
6485:
6484:
6479:
6477:
6469:
6457:
6455:
6454:
6449:
6437:
6435:
6434:
6429:
6417:
6415:
6414:
6409:
6397:
6395:
6394:
6389:
6377:
6375:
6374:
6369:
6339:graphic matroids
6331:
6329:
6328:
6323:
6294:
6292:
6291:
6286:
6274:
6272:
6271:
6266:
6254:
6252:
6251:
6246:
6225:
6223:
6222:
6217:
6151:
6149:
6148:
6143:
6124:
6122:
6121:
6116:
6104:
6102:
6100:
6099:
6094:
6078:
6076:
6075:
6070:
6058:
6056:
6055:
6050:
6035:
6033:
6032:
6027:
5996:
5994:
5993:
5988:
5973:
5971:
5970:
5965:
5953:
5951:
5950:
5945:
5925:
5923:
5922:
5917:
5901:
5899:
5898:
5893:
5843:
5841:
5840:
5835:
5828:
5813:
5811:
5810:
5805:
5793:
5791:
5790:
5785:
5762:
5760:
5759:
5754:
5747:
5732:
5730:
5729:
5724:
5712:
5710:
5709:
5704:
5692:
5690:
5689:
5684:
5672:
5670:
5669:
5664:
5657:
5643:
5641:
5640:
5635:
5584:is a separator.
5583:
5581:
5580:
5575:
5562:discrete matroid
5559:
5557:
5556:
5551:
5544:
5543:
5542:
5520:
5518:
5517:
5512:
5505:
5504:
5503:
5470:
5468:
5467:
5462:
5450:
5448:
5447:
5442:
5426:
5424:
5423:
5418:
5411:
5410:
5409:
5387:
5385:
5384:
5379:
5367:
5365:
5364:
5359:
5347:
5345:
5344:
5339:
5332:
5315:
5313:
5312:
5307:
5295:
5293:
5291:
5290:
5285:
5273:by taking every
5272:
5270:
5269:
5264:
5248:
5246:
5245:
5240:
5228:
5226:
5225:
5220:
5205:Uniform matroids
5200:
5198:
5197:
5192:
5176:
5174:
5173:
5168:
5156:
5154:
5153:
5148:
5119:
5117:
5116:
5111:
5081:
5079:
5078:
5073:
5066:
5056:with ground set
5055:
5053:
5052:
5047:
5035:
5033:
5032:
5027:
5015:
5013:
5012:
5007:
4995:
4993:
4992:
4987:
4975:
4973:
4972:
4967:
4952:
4950:
4949:
4944:
4937:
4908:
4906:
4905:
4900:
4882:
4880:
4879:
4874:
4844:
4842:
4841:
4836:
4818:
4816:
4815:
4810:
4786:
4784:
4783:
4778:
4754:
4752:
4751:
4746:
4729:
4727:
4726:
4721:
4709:
4707:
4706:
4701:
4684:
4682:
4681:
4676:
4659:
4657:
4656:
4651:
4635:
4633:
4632:
4627:
4615:
4613:
4612:
4607:
4595:
4593:
4592:
4587:
4575:
4573:
4572:
4567:
4522:
4520:
4519:
4514:
4507:
4466:
4464:
4463:
4458:
4456:
4455:
4436:
4434:
4433:
4428:
4421:
4398:
4396:
4395:
4390:
4388:
4387:
4362:
4360:
4359:
4354:
4327:
4325:
4324:
4319:
4312:
4295:
4293:
4292:
4287:
4285:
4284:
4271:
4269:
4268:
4263:
4251:
4249:
4248:
4243:
4227:
4225:
4224:
4219:
4217:
4216:
4192:
4190:
4189:
4184:
4160:
4158:
4157:
4152:
4134:
4132:
4131:
4126:
4119:
4100:
4098:
4097:
4092:
4077:
4075:
4074:
4069:
4062:
4024:
4022:
4021:
4016:
4001:
3999:
3998:
3993:
3986:
3928:
3926:
3925:
3920:
3913:
3899:
3897:
3896:
3891:
3875:
3873:
3872:
3867:
3855:
3853:
3852:
3847:
3827:
3825:
3824:
3819:
3808:
3807:
3790:
3788:
3787:
3782:
3770:
3768:
3767:
3762:
3750:
3748:
3747:
3742:
3730:
3728:
3727:
3722:
3715:
3704:
3702:
3701:
3696:
3684:
3682:
3681:
3676:
3661:
3659:
3658:
3653:
3641:
3639:
3638:
3633:
3615:
3613:
3612:
3607:
3590:
3588:
3587:
3582:
3565:are flats, then
3564:
3562:
3561:
3556:
3544:
3542:
3541:
3536:
3519:
3517:
3516:
3511:
3471:
3469:
3468:
3463:
3452:
3451:
3433:
3432:
3399:
3397:
3396:
3391:
3384:
3325:
3323:
3322:
3317:
3257:
3255:
3254:
3249:
3242:
3231:
3229:
3228:
3223:
3212:and all subsets
3211:
3209:
3208:
3203:
3191:
3189:
3188:
3183:
3171:
3169:
3168:
3163:
3147:
3145:
3144:
3139:
3132:
3092:
3090:
3089:
3084:
3077:
3060:
3058:
3057:
3052:
3040:
3038:
3037:
3032:
3020:
3018:
3017:
3012:
2996:
2994:
2993:
2988:
2981:
2980:
2976:
2975:
2923:
2921:
2920:
2915:
2908:
2897:
2895:
2894:
2889:
2873:
2871:
2870:
2865:
2858:
2830:
2828:
2827:
2822:
2815:
2804:
2802:
2801:
2796:
2776:
2774:
2773:
2768:
2766:
2765:
2752:
2750:
2749:
2744:
2733:
2732:
2714:
2713:
2694:closure operator
2688:
2686:
2685:
2680:
2673:
2672:
2671:
2665:
2664:
2643:
2642:
2604:
2603:
2602:
2568:
2566:
2565:
2560:
2548:
2546:
2545:
2540:
2528:
2526:
2525:
2520:
2489:
2487:
2486:
2481:
2469:
2467:
2466:
2461:
2457:
2446:
2444:
2443:
2438:
2418:
2416:
2415:
2410:
2394:
2392:
2391:
2386:
2350:
2348:
2347:
2342:
2335:
2324:
2322:
2321:
2316:
2304:
2302:
2301:
2296:
2284:
2282:
2281:
2276:
2264:
2262:
2261:
2256:
2249:
2234:
2232:
2231:
2226:
2209:
2201:
2186:
2184:
2183:
2178:
2171:
2146:
2144:
2143:
2138:
2131:
2130:
2122:
2095:
2093:
2092:
2087:
2075:
2073:
2072:
2067:
2055:
2053:
2052:
2047:
2035:
2033:
2032:
2027:
1995:
1993:
1992:
1987:
1980:
1930:
1928:
1927:
1922:
1915:
1892:
1890:
1889:
1884:
1877:
1809:
1807:
1806:
1801:
1794:
1783:
1781:
1780:
1775:
1754:
1752:
1751:
1746:
1739:
1662:
1660:
1659:
1654:
1626:
1624:
1623:
1618:
1611:
1610:
1602:
1575:
1573:
1572:
1567:
1536:
1534:
1533:
1528:
1503:is given by the
1502:
1500:
1499:
1494:
1482:
1480:
1479:
1474:
1467:
1452:
1450:
1449:
1444:
1437:
1426:
1424:
1423:
1418:
1406:
1404:
1403:
1398:
1386:
1384:
1383:
1378:
1366:
1364:
1363:
1358:
1346:
1344:
1343:
1338:
1331:
1321:is a matroid on
1320:
1318:
1317:
1312:
1300:
1299:
1297:
1296:
1291:
1284:
1266:
1264:
1263:
1258:
1234:
1232:
1231:
1226:
1224:
1223:
1203:
1201:
1200:
1195:
1188:
1187:
1186:
1137:
1135:
1134:
1129:
1105:
1103:
1102:
1097:
1090:
1067:
1065:
1064:
1059:
1057:
1056:
1043:
1041:
1040:
1035:
1023:
1021:
1020:
1015:
998:
996:
995:
990:
988:
987:
966:
964:
963:
958:
943:
941:
940:
935:
933:
932:
919:
917:
916:
911:
899:
897:
896:
891:
886:
885:
863:
861:
860:
855:
838:graphic matroids
835:
833:
832:
827:
815:
813:
812:
807:
787:
785:
784:
779:
763:
761:
760:
755:
729:
727:
726:
721:
713:
712:
699:
697:
696:
691:
659:
657:
656:
651:
644:
643:
642:
629:
627:
626:
621:
597:
595:
594:
589:
565:
563:
562:
557:
550:
539:
537:
536:
531:
519:
517:
516:
511:
499:
497:
496:
491:
466:
464:
463:
458:
451:
450:
449:
440:
425:
423:
422:
417:
415:
414:
395:
393:
392:
387:
380:
367:
348:
346:
345:
340:
333:
332:
331:
303:independent sets
300:
298:
297:
292:
272:
270:
269:
264:
262:
261:
240:
238:
237:
232:
220:
218:
217:
212:
205:
201:
200:
178:
176:
175:
170:
83:
82:
79:
78:
75:
72:
69:
66:
63:
60:
21:
13903:
13902:
13898:
13897:
13896:
13894:
13893:
13892:
13868:
13867:
13853:
13821:
13806:
13791:
13704:
13701:
13696:
13612:— Reprinted in
13582:10.2307/2371182
13544:
13509:
13470:
13439:
13420:Moderne Algebra
13332:10.2307/1993185
13293:
13183:
13136:
13098:
13064:
13062:
13041:
12995:10.2307/2371070
12957:
12925:
12923:
12919:
12890:10.2307/1998894
12796:
12777:10.1.1.454.4060
12744:
12724:Crapo, Henry H.
12690:Crapo, Henry H.
12673:10.2307/1996381
12642:
12564:
12559:
12552:
12545:
12537:
12533:
12525:
12521:
12513:
12506:
12498:
12491:
12483:
12479:
12471:
12467:
12459:
12452:
12443:
12441:
12437:
12433:
12432:
12428:
12420:
12416:
12408:
12404:
12397:
12393:
12385:
12381:
12373:
12366:
12358:
12354:
12346:
12342:
12334:
12327:
12319:
12315:
12307:
12303:
12295:
12291:
12283:
12279:
12271:
12264:
12256:
12252:
12244:
12240:
12232:
12228:
12220:
12216:
12208:
12204:
12196:
12192:
12184:
12180:
12172:
12165:
12157:
12150:
12142:
12131:
12119:
12115:
12114:
12110:
12102:
12095:
12087:
12083:
12075:
12062:
12055:
12051:
12044:
12040:
12036:
12003:Coxeter matroid
11993:
11988:
11987:
11978:
11974:
11964:A.M.H. Gerards'
11961:
11957:
11944:
11940:
11917:
11914:
11913:
11910:
11906:
11881:
11877:
11872:
11867:
11853:Gian-Carlo Rota
11825:
11821:Hassler Whitney
11782:
11683:excluded minors
11606:
11573:
11570:
11569:
11547:
11544:
11543:
11521:
11518:
11517:
11495:
11492:
11491:
11487:is independent.
11454:
11451:
11450:
11416:
11413:
11412:
11390:
11387:
11386:
11364:
11361:
11360:
11273:
11253:
11239:
11234:
11202:
11199:
11198:
11160:
11129:
11125:
11123:
11120:
11119:
11102:
11098:
11096:
11093:
11092:
11057:
11025:
11011:
11008:
11007:
10988:
10985:
10984:
10959:
10912:
10909:
10908:
10871:
10868:
10867:
10820:
10816:
10801:
10797:
10770:
10766:
10764:
10761:
10760:
10756:specifically,
10734:
10730:
10728:
10725:
10724:
10682:
10674:
10673:
10669:
10639:
10635:
10623:
10595:
10591:
10589:
10586:
10585:
10575:co-rank-nullity
10532:
10524:
10523:
10519:
10474:
10470:
10446:
10418:
10414:
10412:
10409:
10408:
10382:
10378:
10376:
10373:
10372:
10356:
10353:
10352:
10311:
10307:
10281:
10277:
10276:
10272:
10270:
10267:
10266:
10225:
10221:
10219:
10216:
10215:
10206:
10194:Gian-Carlo Rota
10190:Hassler Whitney
10158:
10155:
10154:
10128:
10124:
10122:
10119:
10118:
10102:
10099:
10098:
10049:
10046:
10045:
10013:
10009:
10003:
9999:
9988:
9985:
9984:
9901:
9897:
9895:
9892:
9891:
9856:
9852:
9850:
9847:
9846:
9820:
9816:
9814:
9811:
9810:
9794:
9791:
9790:
9774:
9771:
9770:
9754:
9751:
9750:
9743:
9741:Whitney numbers
9713:
9709:
9686:
9683:
9682:
9666:
9663:
9662:
9640:
9637:
9636:
9620:
9617:
9616:
9577:
9569:
9568:
9564:
9543:
9524:
9520:
9494:
9491:
9490:
9486:or directly as
9455:
9430:
9426:
9400:
9397:
9396:
9377:
9374:
9373:
9362:
9354:
9345:
9326:
9310:is the matroid
9295:flow polynomial
9263:
9249:
9214:Möbius function
9163:
9159:
9135:
9113:
9109:
9107:
9104:
9103:
9049:
9045:
9038:
9030:
9029:
9025:
9004:
8982:
8978:
8976:
8973:
8972:
8952:
8932:
8901:
8876:polynomial time
8821:
8799:
8796:
8795:
8770:
8766:
8764:
8761:
8760:
8607:
8604:
8603:
8564:. A matroid is
8406:
8303:
8301:Sums and unions
8295:excluded minors
8179:
8177:
8174:
8173:
8144:is a subset of
8038:is a subset of
8024:
8018:
7983:
7980:
7979:
7963:
7960:
7959:
7937:
7934:
7933:
7913:
7910:
7909:
7889:
7886:
7885:
7869:
7866:
7865:
7826:
7822:
7796:
7788:
7770:
7766:
7764:
7761:
7760:
7734:
7731:
7730:
7713:
7709:
7707:
7704:
7703:
7677:
7674:
7673:
7656:
7652:
7650:
7647:
7646:
7618:
7615:
7614:
7597:
7593:
7591:
7588:
7587:
7570:
7566:
7564:
7561:
7560:
7538:
7535:
7534:
7517:
7513:
7511:
7508:
7507:
7486:
7482:
7480:
7477:
7476:
7451:
7448:
7447:
7444:
7436:
7398:
7390:
7388:
7385:
7384:
7355:
7352:
7351:
7331:
7328:
7327:
7311:
7308:
7307:
7288:
7285:
7284:
7268:
7265:
7264:
7248:
7245:
7244:
7228:
7225:
7224:
7208:
7205:
7204:
7188:
7185:
7184:
7166:
7138:
7135:
7134:
7105:
7102:
7101:
7075:
7072:
7071:
7051:
7048:
7047:
7031:
7028:
7027:
6995:
6991:
6989:
6986:
6985:
6963:
6960:
6959:
6943:
6940:
6939:
6923:
6920:
6919:
6903:
6900:
6899:
6883:
6880:
6879:
6863:
6860:
6859:
6815:
6812:
6811:
6795:
6792:
6791:
6744:
6741:
6740:
6724:
6721:
6720:
6704:
6701:
6700:
6655:
6652:
6651:
6611:
6608:
6607:
6605:bipartite graph
6583:
6580:
6579:
6563:
6560:
6559:
6533:
6530:
6529:
6513:
6510:
6509:
6493:
6490:
6489:
6473:
6465:
6463:
6460:
6459:
6443:
6440:
6439:
6423:
6420:
6419:
6403:
6400:
6399:
6383:
6380:
6379:
6363:
6360:
6359:
6308:
6305:
6304:
6280:
6277:
6276:
6260:
6257:
6256:
6231:
6228:
6227:
6211:
6208:
6207:
6193:
6181:regular matroid
6162:binary matroids
6137:
6134:
6133:
6110:
6107:
6106:
6105:in particular,
6088:
6085:
6084:
6083:
6064:
6061:
6060:
6044:
6041:
6040:
6021:
6018:
6017:
5982:
5979:
5978:
5959:
5956:
5955:
5939:
5936:
5935:
5911:
5908:
5907:
5887:
5884:
5883:
5862:finite geometry
5850:vector matroids
5823:
5820:
5819:
5799:
5796:
5795:
5779:
5776:
5775:
5742:
5739:
5738:
5718:
5715:
5714:
5698:
5695:
5694:
5678:
5675:
5674:
5652:
5649:
5648:
5629:
5626:
5625:
5590:
5569:
5566:
5565:
5532:
5528:
5526:
5523:
5522:
5493:
5489:
5487:
5484:
5483:
5456:
5453:
5452:
5436:
5433:
5432:
5399:
5395:
5393:
5390:
5389:
5373:
5370:
5369:
5353:
5350:
5349:
5327:
5324:
5323:
5319:uniform matroid
5301:
5298:
5297:
5279:
5276:
5275:
5274:
5258:
5255:
5254:
5234:
5231:
5230:
5214:
5211:
5210:
5207:
5186:
5183:
5182:
5162:
5159:
5158:
5142:
5139:
5138:
5135:
5130:
5087:
5084:
5083:
5061:
5058:
5057:
5041:
5038:
5037:
5021:
5018:
5017:
5001:
4998:
4997:
4981:
4978:
4977:
4961:
4958:
4957:
4914:
4911:
4910:
4888:
4885:
4884:
4850:
4847:
4846:
4824:
4821:
4820:
4792:
4789:
4788:
4760:
4757:
4756:
4740:
4737:
4736:
4715:
4712:
4711:
4695:
4692:
4691:
4690:(G3) no set in
4670:
4667:
4666:
4645:
4642:
4641:
4621:
4618:
4617:
4601:
4598:
4597:
4581:
4578:
4577:
4543:
4540:
4539:
4529:
4472:
4469:
4468:
4451:
4450:
4442:
4439:
4438:
4404:
4401:
4400:
4383:
4382:
4368:
4365:
4364:
4342:
4339:
4338:
4337:(H2) For every
4301:
4298:
4297:
4280:
4279:
4277:
4274:
4273:
4257:
4254:
4253:
4237:
4234:
4233:
4212:
4211:
4209:
4206:
4205:
4178:
4175:
4174:
4140:
4137:
4136:
4135:a flat of rank
4114:
4111:
4110:
4107:
4086:
4083:
4082:
4033:
4030:
4029:
4010:
4007:
4006:
3936:
3933:
3932:
3905:
3902:
3901:
3885:
3882:
3881:
3861:
3858:
3857:
3841:
3838:
3837:
3834:matroid lattice
3803:
3802:
3800:
3797:
3796:
3776:
3773:
3772:
3756:
3753:
3752:
3736:
3733:
3732:
3710:
3707:
3706:
3690:
3687:
3686:
3670:
3667:
3666:
3647:
3644:
3643:
3621:
3618:
3617:
3601:
3598:
3597:
3570:
3567:
3566:
3550:
3547:
3546:
3530:
3527:
3526:
3505:
3502:
3501:
3478:
3447:
3446:
3428:
3427:
3419:
3416:
3415:
3331:
3328:
3327:
3263:
3260:
3259:
3237:
3234:
3233:
3217:
3214:
3213:
3197:
3194:
3193:
3177:
3174:
3173:
3157:
3154:
3153:
3097:
3094:
3093:
3066:
3063:
3062:
3046:
3043:
3042:
3026:
3023:
3022:
3006:
3003:
3002:
2965:
2958:
2954:
2928:
2925:
2924:
2903:
2900:
2899:
2883:
2880:
2879:
2835:
2832:
2831:
2810:
2807:
2806:
2790:
2787:
2786:
2761:
2760:
2758:
2755:
2754:
2728:
2727:
2709:
2708:
2700:
2697:
2696:
2692:This defines a
2667:
2666:
2660:
2659:
2638:
2637:
2598:
2597:
2577:
2574:
2573:
2554:
2551:
2550:
2534:
2531:
2530:
2502:
2499:
2498:
2490:as above. The
2475:
2472:
2471:
2452:
2449:
2448:
2432:
2429:
2428:
2425:
2404:
2401:
2400:
2356:
2353:
2352:
2351:The difference
2330:
2327:
2326:
2310:
2307:
2306:
2290:
2287:
2286:
2270:
2267:
2266:
2244:
2241:
2240:
2205:
2197:
2195:
2192:
2191:
2190:The difference
2160:
2157:
2156:
2126:
2118:
2101:
2098:
2097:
2081:
2078:
2077:
2061:
2058:
2057:
2041:
2038:
2037:
2009:
2006:
2005:
1936:
1933:
1932:
1898:
1895:
1894:
1815:
1812:
1811:
1789:
1786:
1785:
1769:
1766:
1765:
1668:
1665:
1664:
1636:
1633:
1632:
1606:
1598:
1581:
1578:
1577:
1555:
1552:
1551:
1513:
1510:
1509:
1488:
1485:
1484:
1462:
1459:
1458:
1432:
1429:
1428:
1412:
1409:
1408:
1392:
1389:
1388:
1372:
1369:
1368:
1367:is a subset of
1352:
1349:
1348:
1326:
1323:
1322:
1306:
1303:
1302:
1279:
1276:
1275:
1273:
1252:
1249:
1248:
1241:
1239:Rank functions
1219:
1218:
1216:
1213:
1212:
1182:
1181:
1143:
1140:
1139:
1111:
1108:
1107:
1073:
1070:
1069:
1052:
1051:
1049:
1046:
1045:
1029:
1026:
1025:
1009:
1006:
1005:
983:
982:
980:
977:
976:
949:
946:
945:
928:
927:
925:
922:
921:
905:
902:
901:
881:
880:
869:
866:
865:
849:
846:
845:
821:
818:
817:
801:
798:
797:
773:
770:
769:
749:
746:
745:
742:
736:
708:
707:
705:
702:
701:
685:
682:
681:
638:
637:
635:
632:
631:
603:
600:
599:
571:
568:
567:
545:
542:
541:
525:
522:
521:
505:
502:
501:
485:
482:
481:
473:downward-closed
445:
444:
433:
431:
428:
427:
410:
409:
401:
398:
397:
360:
358:
355:
354:
327:
326:
318:
315:
314:
286:
283:
282:
257:
256:
254:
251:
250:
226:
223:
222:
196:
195:
184:
181:
180:
164:
161:
160:
157:
147:There are many
145:
57:
53:
39:
28:
23:
22:
15:
12:
11:
5:
13901:
13891:
13890:
13885:
13880:
13878:Matroid theory
13866:
13865:
13851:
13835:
13834:
13817:Oxley, James.
13813:
13812:
13783:
13782:
13764:
13763:
13745:
13744:
13721:
13720:
13700:
13699:External links
13697:
13695:
13694:
13666:(3): 303–307.
13650:
13638:(2): 222–261.
13617:
13576:(3): 509–533.
13560:
13558:(archive.org).
13542:
13525:
13523:(archive.org).
13507:
13486:
13484:(archive.org).
13468:
13451:
13437:
13429:Matroid Theory
13424:
13412:
13402:(3): 403–408.
13389:
13369:
13353:
13325:(3): 527–552.
13305:
13291:
13276:
13246:(3): 305–359.
13226:
13207:
13205:(archive.org).
13181:
13156:
13134:
13126:Matroid Theory
13118:
13096:
13075:
13030:
13007:
12989:(1): 236–240.
12973:
12971:(archive.org).
12955:
12932:
12912:
12903:
12883:(2): 485–499.
12866:
12841:
12829:
12811:(2): 247–299.
12800:
12794:
12760:
12758:(archive.org).
12742:
12720:
12702:(3): 211–229.
12686:
12646:
12640:
12626:Perfect, Hazel
12621:
12565:
12563:
12560:
12558:
12557:
12543:
12531:
12519:
12504:
12489:
12477:
12465:
12450:
12426:
12414:
12402:
12391:
12379:
12364:
12352:
12340:
12325:
12313:
12301:
12289:
12277:
12262:
12250:
12238:
12226:
12214:
12202:
12190:
12178:
12163:
12161:, pp. 115
12148:
12129:
12108:
12093:
12081:
12060:
12049:
12037:
12035:
12032:
12031:
12030:
12024:
12018:
12012:
12006:
12000:
11992:
11989:
11986:
11985:
11972:
11968:Gerards (1989)
11955:
11953:
11952:
11947:Whitney (1935)
11938:
11921:
11904:
11902:
11901:
11893:
11892:
11874:
11873:
11871:
11868:
11866:
11865:
11860:
11855:
11850:
11845:
11840:
11835:
11829:
11824:
11823:
11818:
11813:
11808:
11805:
11803:Takeo Nakasawa
11800:
11795:
11790:
11786:
11781:
11778:
11748:Seymour (1980)
11717:
11716:
11711:" (see, e.g.,
11704:
11703:
11696:
11695:
11691:
11690:
11686:
11685:
11637:MacLane (1936)
11626:linear algebra
11614:Takeo Nakasawa
11610:Whitney (1935)
11605:
11602:
11598:
11597:
11586:
11580:
11554:
11528:
11502:
11488:
11473:
11470:
11467:
11464:
11461:
11435:
11432:
11429:
11426:
11423:
11397:
11371:
11353:
11350:
11322:, a branch of
11298:
11297:
11286:
11283:
11279:
11276:
11272:
11269:
11266:
11263:
11260:
11252:
11249:
11245:
11242:
11230:
11224:
11221:
11218:
11215:
11212:
11209:
11206:
11159:
11156:
11141:
11138:
11135:
11132:
11128:
11105:
11101:
11079:
11078:
11067:
11063:
11060:
11056:
11053:
11050:
11047:
11044:
11041:
11038:
11035:
11031:
11028:
11024:
11021:
11018:
11015:
10992:
10981:
10980:
10969:
10966:
10962:
10958:
10955:
10952:
10949:
10946:
10943:
10940:
10937:
10934:
10931:
10928:
10925:
10922:
10919:
10916:
10890:
10887:
10884:
10881:
10878:
10875:
10864:
10863:
10852:
10846:
10843:
10840:
10837:
10834:
10831:
10828:
10823:
10819:
10813:
10810:
10807:
10804:
10800:
10796:
10793:
10790:
10787:
10784:
10781:
10778:
10773:
10769:
10745:
10737:
10733:
10721:
10720:
10709:
10701:
10698:
10695:
10692:
10689:
10685:
10681:
10677:
10672:
10666:
10663:
10660:
10657:
10654:
10651:
10648:
10645:
10642:
10638:
10632:
10629:
10626:
10622:
10618:
10615:
10612:
10609:
10606:
10603:
10598:
10594:
10571:
10570:
10559:
10551:
10548:
10545:
10542:
10539:
10535:
10531:
10527:
10522:
10518:
10515:
10512:
10509:
10501:
10498:
10495:
10492:
10489:
10486:
10483:
10480:
10477:
10473:
10469:
10466:
10463:
10460:
10455:
10452:
10449:
10445:
10441:
10438:
10435:
10432:
10429:
10426:
10421:
10417:
10393:
10385:
10381:
10360:
10349:
10348:
10337:
10331:
10328:
10325:
10322:
10319:
10314:
10310:
10306:
10303:
10300:
10297:
10294:
10291:
10284:
10280:
10275:
10251:
10245:
10242:
10239:
10236:
10233:
10228:
10224:
10214:of a matroid,
10205:
10202:
10182:complete graph
10162:
10142:
10139:
10136:
10131:
10127:
10106:
10080:
10074:
10071:
10068:
10065:
10062:
10059:
10056:
10053:
10033:
10030:
10027:
10024:
10021:
10016:
10012:
10006:
10002:
9998:
9995:
9992:
9981:
9980:
9969:
9966:
9963:
9960:
9957:
9954:
9951:
9948:
9945:
9942:
9939:
9936:
9933:
9930:
9927:
9924:
9921:
9918:
9915:
9912:
9909:
9904:
9900:
9874:
9871:
9868:
9865:
9862:
9859:
9855:
9834:
9831:
9828:
9823:
9819:
9798:
9778:
9758:
9742:
9739:
9727:
9721:
9716:
9712:
9708:
9705:
9702:
9699:
9696:
9693:
9690:
9670:
9650:
9644:
9624:
9613:
9612:
9601:
9595:
9592:
9589:
9586:
9580:
9576:
9572:
9567:
9563:
9560:
9557:
9552:
9549:
9546:
9542:
9536:
9533:
9530:
9527:
9523:
9519:
9516:
9513:
9510:
9507:
9504:
9501:
9498:
9484:
9483:
9472:
9469:
9466:
9462:
9458:
9454:
9448:
9445:
9442:
9439:
9436:
9433:
9429:
9425:
9422:
9419:
9416:
9413:
9410:
9407:
9404:
9381:
9366:beta invariant
9361:
9360:Beta invariant
9358:
9357:
9356:
9350:
9341:
9303:
9302:
9274:
9273:
9254:
9245:
9210:
9209:
9198:
9190:
9187:
9184:
9181:
9178:
9175:
9172:
9169:
9166:
9162:
9158:
9155:
9152:
9149:
9146:
9143:
9138:
9134:
9130:
9127:
9124:
9121:
9116:
9112:
9093:
9092:
9081:
9076:
9073:
9070:
9067:
9064:
9061:
9058:
9055:
9052:
9048:
9041:
9037:
9033:
9028:
9024:
9021:
9018:
9013:
9010:
9007:
9003:
8999:
8996:
8993:
8990:
8985:
8981:
8951:
8948:
8931:
8928:
8907:and Hlineny's
8900:
8897:
8896:
8895:
8864:
8863:
8848:
8847:
8820:
8817:
8816:
8815:
8803:
8773:
8769:
8753:
8752:
8749:paving matroid
8744:
8743:
8727:
8726:
8702:
8701:
8689:
8688:
8656:
8653:
8650:
8647:
8644:
8641:
8638:
8635:
8632:
8629:
8626:
8623:
8620:
8617:
8614:
8611:
8583:
8582:
8570:
8569:
8558:simplification
8541:
8540:
8512:
8511:
8507:
8506:
8494:
8493:
8481:
8480:
8472:
8471:
8441:
8440:
8405:
8402:
8335:disjoint union
8302:
8299:
8234:
8231:
8228:
8225:
8222:
8219:
8216:
8213:
8210:
8207:
8204:
8201:
8198:
8195:
8192:
8189:
8185:
8182:
8020:Main article:
8017:
8014:
8013:
8012:
8009:
7993:
7987:
7967:
7947:
7941:
7917:
7893:
7873:
7858:
7857:
7846:
7839:
7835:
7832:
7829:
7825:
7821:
7818:
7815:
7812:
7809:
7806:
7803:
7799:
7795:
7791:
7787:
7784:
7781:
7778:
7773:
7769:
7756:
7755:
7744:
7738:
7716:
7712:
7699:
7698:
7687:
7681:
7659:
7655:
7628:
7622:
7600:
7596:
7573:
7569:
7548:
7542:
7520:
7516:
7489:
7485:
7455:
7443:
7440:
7435:
7432:
7420:
7419:
7408:
7401:
7397:
7393:
7368:
7365:
7362:
7359:
7335:
7315:
7304:
7292:
7272:
7252:
7232:
7212:
7192:
7165:
7162:
7161:
7160:
7148:
7142:
7118:
7115:
7112:
7109:
7097:
7096:
7085:
7079:
7055:
7035:
7015:
7009:
7006:
7003:
6998:
6994:
6973:
6970:
6967:
6947:
6927:
6907:
6887:
6867:
6855:
6854:
6838:
6837:
6825:
6819:
6799:
6787:
6786:
6766:
6760:
6757:
6754:
6751:
6748:
6728:
6708:
6684:
6683:
6659:
6639:
6636:
6633:
6630:
6627:
6624:
6621:
6618:
6615:
6600:
6599:
6587:
6567:
6556:strict gammoid
6537:
6517:
6497:
6476:
6472:
6468:
6447:
6427:
6407:
6387:
6367:
6355:
6354:
6321:
6318:
6315:
6312:
6284:
6264:
6244:
6241:
6238:
6235:
6215:
6192:
6189:
6141:
6114:
6092:
6068:
6059:, then we say
6048:
6025:
5999:
5998:
5986:
5963:
5943:
5932:column matroid
5915:
5891:
5854:
5853:
5845:
5844:
5833:
5827:
5803:
5783:
5764:
5763:
5752:
5746:
5722:
5702:
5682:
5662:
5656:
5633:
5589:
5586:
5573:
5549:
5541:
5538:
5535:
5531:
5510:
5502:
5499:
5496:
5492:
5460:
5440:
5416:
5408:
5405:
5402:
5398:
5377:
5357:
5337:
5331:
5305:
5283:
5262:
5251:natural number
5238:
5218:
5206:
5203:
5190:
5166:
5146:
5134:
5131:
5129:
5126:
5109:
5106:
5103:
5100:
5097:
5094:
5091:
5071:
5065:
5045:
5025:
5005:
4985:
4965:
4954:
4953:
4942:
4936:
4933:
4930:
4927:
4924:
4921:
4918:
4898:
4895:
4892:
4872:
4869:
4866:
4863:
4860:
4857:
4854:
4834:
4831:
4828:
4808:
4805:
4802:
4799:
4796:
4776:
4773:
4770:
4767:
4764:
4744:
4735:(G4) whenever
4732:
4731:
4719:
4699:
4687:
4686:
4674:
4662:
4661:
4649:
4625:
4605:
4585:
4565:
4562:
4559:
4556:
4553:
4550:
4547:
4528:
4525:
4524:
4523:
4512:
4506:
4503:
4500:
4497:
4494:
4491:
4488:
4485:
4482:
4479:
4476:
4454:
4449:
4446:
4426:
4420:
4417:
4414:
4411:
4408:
4386:
4381:
4378:
4375:
4372:
4352:
4349:
4346:
4334:
4333:
4330:Sperner family
4317:
4311:
4308:
4305:
4283:
4261:
4241:
4215:
4182:
4150:
4147:
4144:
4124:
4118:
4106:
4103:
4090:
4079:
4078:
4067:
4061:
4058:
4055:
4052:
4049:
4046:
4043:
4040:
4037:
4014:
4003:
4002:
3991:
3985:
3982:
3979:
3976:
3973:
3970:
3967:
3964:
3961:
3958:
3955:
3952:
3949:
3946:
3943:
3940:
3918:
3912:
3909:
3889:
3865:
3845:
3828:of all flats,
3817:
3814:
3811:
3806:
3793:
3792:
3780:
3760:
3740:
3720:
3714:
3694:
3685:(meaning that
3674:
3651:
3631:
3628:
3625:
3605:
3593:
3592:
3580:
3577:
3574:
3554:
3534:
3522:
3521:
3509:
3477:
3474:
3461:
3458:
3455:
3450:
3445:
3442:
3439:
3436:
3431:
3426:
3423:
3401:
3400:
3389:
3383:
3380:
3377:
3374:
3371:
3368:
3365:
3362:
3359:
3356:
3353:
3350:
3347:
3344:
3341:
3338:
3335:
3315:
3312:
3309:
3306:
3303:
3300:
3297:
3294:
3291:
3288:
3285:
3282:
3279:
3276:
3273:
3270:
3267:
3247:
3241:
3221:
3201:
3181:
3161:
3149:
3148:
3137:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3110:
3107:
3104:
3101:
3082:
3076:
3073:
3070:
3050:
3030:
3010:
2998:
2997:
2986:
2979:
2974:
2971:
2968:
2964:
2961:
2957:
2953:
2950:
2947:
2944:
2941:
2938:
2935:
2932:
2913:
2907:
2887:
2875:
2874:
2863:
2857:
2854:
2851:
2848:
2845:
2842:
2839:
2820:
2814:
2794:
2764:
2742:
2739:
2736:
2731:
2726:
2723:
2720:
2717:
2712:
2707:
2704:
2690:
2689:
2678:
2670:
2663:
2658:
2655:
2652:
2649:
2646:
2641:
2636:
2633:
2630:
2627:
2624:
2621:
2618:
2615:
2612:
2609:
2601:
2596:
2593:
2590:
2587:
2584:
2581:
2558:
2538:
2518:
2515:
2512:
2509:
2506:
2479:
2456:
2436:
2424:
2421:
2408:
2399:of the subset
2384:
2381:
2378:
2375:
2372:
2369:
2366:
2363:
2360:
2340:
2334:
2314:
2294:
2274:
2254:
2248:
2239:of the subset
2235:is called the
2224:
2221:
2218:
2215:
2212:
2208:
2204:
2200:
2176:
2170:
2167:
2164:
2136:
2129:
2125:
2121:
2117:
2114:
2111:
2108:
2105:
2085:
2065:
2045:
2025:
2022:
2019:
2016:
2013:
2002:
2001:
1985:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1952:
1949:
1946:
1943:
1940:
1920:
1914:
1911:
1908:
1905:
1902:
1882:
1876:
1873:
1870:
1867:
1864:
1861:
1858:
1855:
1852:
1849:
1846:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1822:
1819:
1799:
1793:
1773:
1761:
1760:
1744:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1652:
1649:
1646:
1643:
1640:
1628:
1627:
1616:
1609:
1605:
1601:
1597:
1594:
1591:
1588:
1585:
1565:
1562:
1559:
1547:
1546:
1526:
1523:
1520:
1517:
1492:
1472:
1466:
1442:
1436:
1416:
1396:
1376:
1356:
1336:
1330:
1310:
1289:
1283:
1256:
1240:
1237:
1222:
1205:
1204:
1193:
1185:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1127:
1124:
1121:
1118:
1115:
1095:
1089:
1086:
1083:
1080:
1077:
1055:
1033:
1013:
1001:
1000:
986:
956:
953:
931:
909:
889:
884:
879:
876:
873:
853:
825:
805:
788:– is called a
777:
753:
738:Main article:
735:
732:
719:
716:
711:
689:
670:
669:
649:
641:
619:
616:
613:
610:
607:
587:
584:
581:
578:
575:
555:
549:
529:
509:
489:
477:
476:
456:
448:
443:
439:
436:
413:
408:
405:
385:
379:
376:
373:
370:
366:
363:
350:
349:
338:
330:
325:
322:
290:
260:
230:
210:
204:
199:
194:
191:
188:
168:
156:
153:
144:
141:
133:network theory
113:linear algebra
45:, a branch of
26:
9:
6:
4:
3:
2:
13900:
13889:
13886:
13884:
13881:
13879:
13876:
13875:
13873:
13862:
13858:
13854:
13848:
13844:
13843:
13837:
13836:
13831:
13827:
13820:
13815:
13814:
13805:
13801:
13797:
13790:
13785:
13784:
13779:
13775:
13771:
13766:
13765:
13760:
13756:
13752:
13747:
13746:
13740:
13736:
13732:
13728:
13723:
13722:
13717:
13713:
13712:
13707:
13703:
13702:
13691:
13687:
13683:
13679:
13674:
13669:
13665:
13662:
13661:
13660:Eur. J. Comb.
13656:
13651:
13646:
13641:
13637:
13633:
13632:
13627:
13625:
13618:
13615:
13609:
13605:
13601:
13597:
13592:
13587:
13583:
13579:
13575:
13571:
13570:
13565:
13561:
13557:
13553:
13549:
13545:
13539:
13534:
13533:
13526:
13522:
13518:
13514:
13510:
13504:
13500:
13495:
13494:
13487:
13483:
13479:
13475:
13471:
13465:
13460:
13459:
13452:
13448:
13444:
13440:
13434:
13430:
13425:
13421:
13417:
13413:
13409:
13405:
13401:
13397:
13396:
13390:
13386:
13382:
13378:
13374:
13370:
13366:
13362:
13358:
13354:
13350:
13346:
13342:
13338:
13333:
13328:
13324:
13320:
13319:
13314:
13310:
13306:
13302:
13298:
13294:
13288:
13284:
13283:
13277:
13273:
13269:
13264:
13259:
13254:
13249:
13245:
13241:
13240:
13235:
13231:
13227:
13223:
13219:
13218:
13213:
13208:
13204:
13200:
13196:
13192:
13188:
13184:
13178:
13174:
13170:
13165:
13164:
13157:
13153:
13149:
13145:
13141:
13137:
13131:
13127:
13123:
13119:
13115:
13111:
13107:
13103:
13099:
13093:
13089:
13085:
13081:
13076:
13072:
13061:
13057:
13053:
13049:
13048:
13040:
13036:
13031:
13027:
13023:
13019:
13015:
13014:
13008:
13004:
13000:
12996:
12992:
12988:
12984:
12983:
12978:
12974:
12970:
12966:
12962:
12958:
12952:
12948:
12944:
12940:
12939:
12933:
12918:
12913:
12909:
12904:
12900:
12896:
12891:
12886:
12882:
12878:
12877:
12872:
12867:
12862:
12857:
12853:
12852:
12847:
12842:
12838:
12834:
12830:
12826:
12822:
12818:
12814:
12810:
12806:
12801:
12797:
12791:
12787:
12783:
12778:
12773:
12769:
12765:
12764:Edmonds, Jack
12761:
12757:
12753:
12749:
12745:
12739:
12735:
12734:
12729:
12725:
12721:
12717:
12713:
12709:
12705:
12701:
12697:
12696:
12691:
12687:
12683:
12679:
12674:
12669:
12665:
12661:
12660:
12655:
12651:
12647:
12643:
12637:
12633:
12632:
12627:
12622:
12618:
12614:
12610:
12606:
12601:
12596:
12591:
12586:
12582:
12578:
12577:
12572:
12567:
12566:
12555:
12550:
12548:
12541:, p. 260
12540:
12535:
12529:, p. 188
12528:
12527:White (1992b)
12523:
12517:, p. 126
12516:
12511:
12509:
12502:, p. 124
12501:
12496:
12494:
12487:, p. 123
12486:
12481:
12475:, p. 120
12474:
12469:
12463:, p. 127
12462:
12457:
12455:
12436:
12430:
12423:
12418:
12411:
12406:
12400:
12395:
12389:, p. 110
12388:
12383:
12377:, p. 128
12376:
12371:
12369:
12362:, p. 347
12361:
12356:
12349:
12344:
12338:, p. 130
12337:
12332:
12330:
12322:
12317:
12311:, p. 150
12310:
12305:
12299:, p. 140
12298:
12293:
12287:, p. 139
12286:
12281:
12275:, p. 224
12274:
12269:
12267:
12260:, p. 131
12259:
12254:
12248:, p. 105
12247:
12242:
12235:
12230:
12224:, p. 216
12223:
12218:
12212:, p. 215
12211:
12206:
12199:
12194:
12187:
12182:
12176:, p. 100
12175:
12170:
12168:
12160:
12155:
12153:
12145:
12140:
12138:
12136:
12134:
12125:
12118:
12112:
12105:
12100:
12098:
12090:
12085:
12078:
12073:
12071:
12069:
12067:
12065:
12058:
12053:
12047:
12042:
12038:
12028:
12025:
12022:
12019:
12016:
12013:
12010:
12007:
12004:
12001:
11998:
11995:
11994:
11982:
11976:
11969:
11966:short proof (
11965:
11959:
11951:
11950:
11948:
11942:
11935:
11919:
11908:
11900:
11899:
11897:
11891:
11890:
11888:
11884:
11879:
11875:
11864:
11863:Dominic Welsh
11861:
11859:
11856:
11854:
11851:
11849:
11848:László Lovász
11846:
11844:
11843:Eugene Lawler
11841:
11839:
11836:
11834:
11831:
11830:
11828:
11822:
11819:
11817:
11814:
11812:
11809:
11806:
11804:
11801:
11799:
11796:
11794:
11791:
11789:Susumu Kuroda
11788:
11787:
11785:
11777:
11775:
11770:
11768:
11764:
11763:Geoff Whittle
11759:
11757:
11753:
11749:
11745:
11741:
11739:
11738:Dominic Welsh
11734:
11732:
11728:
11724:
11720:
11714:
11710:
11706:
11705:
11701:
11700:
11699:
11693:
11692:
11688:
11687:
11684:
11680:
11676:
11672:
11668:
11667:
11666:
11664:
11661:In the 1950s
11659:
11657:
11653:
11650:In the 1940s
11648:
11646:
11642:
11638:
11633:
11631:
11627:
11621:
11619:
11615:
11611:
11601:
11584:
11578:
11552:
11526:
11500:
11489:
11468:
11462:
11459:
11433:
11430:
11427:
11424:
11421:
11395:
11369:
11358:
11354:
11351:
11348:
11347:
11346:
11343:
11341:
11337:
11331:
11329:
11325:
11321:
11316:
11314:
11313:Banach spaces
11310:
11306:
11305:vector spaces
11301:
11284:
11277:
11274:
11267:
11264:
11261:
11258:
11250:
11247:
11243:
11240:
11219:
11213:
11210:
11207:
11204:
11197:
11196:
11195:
11193:
11189:
11188:pregeometries
11184:
11182:
11178:
11173:
11169:
11164:
11155:
11136:
11130:
11126:
11103:
11099:
11091:
11086:
11084:
11061:
11058:
11051:
11045:
11039:
11036:
11029:
11026:
11022:
11019:
11013:
11006:
11005:
11004:
10990:
10964:
10960:
10956:
10950:
10947:
10941:
10938:
10935:
10929:
10926:
10920:
10914:
10907:
10906:
10905:
10902:
10885:
10882:
10879:
10873:
10850:
10841:
10838:
10835:
10832:
10829:
10821:
10817:
10808:
10802:
10794:
10791:
10785:
10779:
10771:
10767:
10759:
10758:
10757:
10743:
10735:
10731:
10707:
10696:
10690:
10687:
10679:
10670:
10661:
10655:
10652:
10646:
10640:
10636:
10630:
10627:
10624:
10620:
10616:
10610:
10607:
10604:
10596:
10592:
10584:
10583:
10582:
10580:
10576:
10557:
10546:
10540:
10537:
10529:
10516:
10513:
10510:
10496:
10490:
10487:
10481:
10475:
10467:
10464:
10461:
10453:
10450:
10447:
10443:
10439:
10433:
10430:
10427:
10419:
10415:
10407:
10406:
10405:
10391:
10383:
10379:
10358:
10335:
10326:
10323:
10320:
10312:
10308:
10304:
10298:
10295:
10292:
10282:
10278:
10273:
10265:
10264:
10263:
10249:
10240:
10237:
10234:
10226:
10222:
10213:
10212:
10201:
10199:
10195:
10191:
10187:
10183:
10179:
10174:
10160:
10137:
10129:
10125:
10104:
10096:
10091:
10078:
10069:
10063:
10060:
10057:
10054:
10051:
10031:
10028:
10022:
10014:
10010:
10004:
9996:
9993:
9967:
9961:
9958:
9952:
9946:
9943:
9937:
9934:
9925:
9919:
9916:
9910:
9902:
9898:
9890:
9889:
9888:
9872:
9869:
9863:
9857:
9853:
9829:
9821:
9817:
9796:
9776:
9756:
9748:
9738:
9725:
9714:
9710:
9703:
9700:
9694:
9688:
9668:
9648:
9642:
9622:
9599:
9590:
9584:
9574:
9561:
9558:
9550:
9547:
9544:
9540:
9531:
9525:
9517:
9514:
9508:
9502:
9496:
9489:
9488:
9487:
9467:
9460:
9456:
9452:
9446:
9443:
9437:
9431:
9423:
9420:
9414:
9408:
9402:
9395:
9394:
9393:
9379:
9371:
9367:
9353:
9349:
9346: (λ) = λ
9344:
9340:
9336:
9332:
9324:
9321:
9317:
9313:
9309:
9305:
9304:
9300:
9296:
9292:
9289:) of a graph
9288:
9284:
9280:
9276:
9275:
9271:
9267:
9261:
9257:
9253:
9250: (λ) = λ
9248:
9243:
9239:
9236:) of a graph
9235:
9231:
9227:
9223:
9222:
9221:
9219:
9215:
9196:
9185:
9179:
9176:
9170:
9164:
9160:
9153:
9150:
9141:
9136:
9132:
9128:
9122:
9114:
9110:
9102:
9101:
9100:
9098:
9079:
9071:
9065:
9062:
9056:
9050:
9046:
9035:
9022:
9019:
9011:
9008:
9005:
9001:
8997:
8991:
8983:
8979:
8971:
8970:
8969:
8967:
8963:
8959:
8958:
8947:
8945:
8942:. Each is a
8941:
8937:
8927:
8925:
8921:
8917:
8912:
8910:
8906:
8893:
8889:
8885:
8881:
8877:
8872:
8871:
8866:
8865:
8861:
8857:
8855:
8850:
8849:
8845:
8841:
8837:
8833:
8832:
8826:
8825:
8824:
8801:
8793:
8789:
8771:
8767:
8759:
8755:
8754:
8750:
8746:
8745:
8741:
8737:
8736:frame matroid
8733:
8729:
8728:
8724:
8720:
8716:
8712:
8708:
8704:
8703:
8699:
8695:
8691:
8690:
8686:
8682:
8678:
8674:
8670:
8651:
8645:
8642:
8636:
8633:
8630:
8624:
8621:
8615:
8609:
8601:
8597:
8593:
8589:
8585:
8584:
8580:
8576:
8572:
8571:
8567:
8563:
8559:
8555:
8551:
8547:
8543:
8542:
8538:
8534:
8530:
8526:
8522:
8518:
8514:
8513:
8509:
8508:
8504:
8500:
8496:
8495:
8491:
8487:
8483:
8482:
8478:
8474:
8473:
8469:
8465:
8462:a closed set
8461:
8457:
8453:
8450:
8447:
8443:
8442:
8438:
8434:
8430:
8426:
8422:
8419:
8418:
8417:
8415:
8411:
8401:
8399:
8395:
8391:
8387:
8383:
8379:
8375:
8371:
8367:
8363:
8359:
8354:
8352:
8348:
8344:
8340:
8336:
8332:
8328:
8324:
8320:
8316:
8312:
8308:
8298:
8296:
8292:
8288:
8287:minor-minimal
8284:
8281:
8278:
8275:
8271:
8267:
8263:
8259:
8254:
8252:
8248:
8232:
8226:
8220:
8217:
8211:
8208:
8205:
8199:
8196:
8190:
8183:
8180:
8171:
8167:
8163:
8159:
8155:
8151:
8147:
8143:
8138:
8136:
8132:
8128:
8124:
8120:
8116:
8112:
8108:
8104:
8100:
8096:
8091:
8089:
8085:
8081:
8077:
8073:
8069:
8065:
8061:
8057:
8053:
8049:
8045:
8041:
8037:
8033:
8029:
8023:
8022:Matroid minor
8010:
8007:
8006:
8005:
7991:
7985:
7965:
7945:
7939:
7931:
7915:
7907:
7891:
7871:
7863:
7844:
7837:
7833:
7830:
7827:
7823:
7819:
7816:
7810:
7804:
7801:
7793:
7785:
7779:
7771:
7767:
7758:
7757:
7742:
7736:
7714:
7710:
7701:
7700:
7685:
7679:
7657:
7653:
7644:
7643:
7642:
7639:
7626:
7620:
7598:
7594:
7571:
7567:
7546:
7540:
7518:
7514:
7505:
7487:
7483:
7475:
7474:
7469:
7453:
7439:
7431:
7429:
7428:Vámos matroid
7425:
7406:
7395:
7382:
7363:
7357:
7349:
7333:
7313:
7305:
7290:
7270:
7250:
7230:
7210:
7190:
7182:
7181:
7180:
7178:
7173:
7171:
7146:
7140:
7132:
7113:
7107:
7099:
7098:
7083:
7077:
7069:
7053:
7033:
7013:
7004:
6996:
6992:
6971:
6968:
6965:
6945:
6925:
6905:
6885:
6865:
6857:
6856:
6852:
6848:
6844:
6840:
6839:
6823:
6817:
6797:
6789:
6788:
6784:
6780:
6779:frame matroid
6764:
6755:
6752:
6749:
6726:
6706:
6698:
6697:biased graphs
6694:
6690:
6689:signed graphs
6686:
6685:
6681:
6680:dual matroids
6677:
6673:
6657:
6634:
6631:
6628:
6625:
6622:
6616:
6613:
6606:
6602:
6601:
6585:
6565:
6557:
6553:
6552:
6535:
6515:
6495:
6470:
6445:
6425:
6405:
6385:
6365:
6357:
6356:
6352:
6348:
6347:
6346:
6343:
6341:
6340:
6335:
6334:cycle matroid
6316:
6310:
6302:
6298:
6282:
6262:
6239:
6233:
6213:
6205:
6200:
6198:
6188:
6186:
6185:Vámos matroid
6182:
6177:
6175:
6171:
6167:
6163:
6159:
6155:
6139:
6130:
6128:
6112:
6090:
6082:
6066:
6046:
6039:
6023:
6015:
6011:
6010:representable
6006:
6004:
5984:
5977:
5961:
5941:
5933:
5929:
5928:
5927:
5913:
5905:
5889:
5882:
5877:
5875:
5871:
5868:
5863:
5859:
5851:
5847:
5846:
5831:
5825:
5818:
5817:
5801:
5781:
5773:
5772:
5771:
5769:
5750:
5744:
5736:
5720:
5700:
5680:
5660:
5654:
5647:
5631:
5623:
5622:
5621:
5615:
5614:Vámos matroid
5610:
5603:
5599:
5594:
5585:
5571:
5563:
5547:
5539:
5536:
5533:
5529:
5508:
5500:
5497:
5494:
5490:
5480:
5478:
5474:
5458:
5438:
5430:
5414:
5406:
5403:
5400:
5396:
5375:
5355:
5335:
5329:
5321:
5320:
5303:
5281:
5260:
5252:
5236:
5216:
5202:
5188:
5180:
5164:
5144:
5125:
5124:of matroids.
5123:
5104:
5101:
5098:
5095:
5092:
5069:
5063:
5043:
5023:
5003:
4983:
4963:
4940:
4934:
4931:
4928:
4925:
4922:
4919:
4916:
4896:
4893:
4890:
4870:
4867:
4864:
4861:
4858:
4855:
4852:
4832:
4829:
4826:
4803:
4797:
4794:
4774:
4771:
4768:
4765:
4762:
4742:
4734:
4733:
4717:
4697:
4689:
4688:
4672:
4664:
4663:
4647:
4639:
4638:
4637:
4623:
4603:
4583:
4560:
4557:
4554:
4551:
4548:
4537:
4533:
4510:
4504:
4501:
4495:
4489:
4483:
4480:
4477:
4447:
4444:
4437:there exists
4424:
4418:
4415:
4412:
4409:
4406:
4379:
4376:
4373:
4370:
4363:and distinct
4350:
4347:
4344:
4336:
4335:
4331:
4315:
4309:
4306:
4303:
4259:
4239:
4231:
4230:
4229:
4202:
4200:
4196:
4180:
4172:
4168:
4164:
4148:
4145:
4142:
4122:
4116:
4102:
4088:
4065:
4056:
4053:
4050:
4047:
4044:
4041:
4038:
4028:
4027:
4026:
4012:
3989:
3980:
3977:
3974:
3971:
3968:
3965:
3962:
3959:
3953:
3947:
3941:
3938:
3931:
3930:
3929:
3916:
3910:
3907:
3887:
3879:
3863:
3843:
3835:
3831:
3812:
3778:
3758:
3738:
3718:
3712:
3692:
3672:
3665:
3649:
3629:
3626:
3623:
3603:
3595:
3594:
3578:
3575:
3572:
3552:
3532:
3524:
3523:
3507:
3499:
3498:
3497:
3495:
3491:
3487:
3483:
3473:
3456:
3437:
3424:
3421:
3413:
3411:
3407:
3387:
3378:
3372:
3369:
3366:
3357:
3351:
3348:
3342:
3339:
3336:
3333:
3310:
3304:
3301:
3298:
3289:
3283:
3280:
3274:
3271:
3268:
3265:
3245:
3239:
3219:
3199:
3179:
3159:
3151:
3150:
3135:
3126:
3120:
3117:
3114:
3108:
3102:
3099:
3080:
3074:
3071:
3068:
3048:
3028:
3008:
3000:
2999:
2984:
2977:
2972:
2969:
2966:
2962:
2959:
2955:
2951:
2948:
2945:
2939:
2933:
2930:
2911:
2905:
2885:
2877:
2876:
2861:
2852:
2846:
2843:
2840:
2837:
2818:
2812:
2792:
2784:
2783:
2782:
2780:
2737:
2718:
2705:
2702:
2695:
2676:
2653:
2647:
2644:
2634:
2631:
2625:
2619:
2616:
2613:
2610:
2607:
2594:
2588:
2582:
2579:
2572:
2571:
2570:
2556:
2536:
2513:
2507:
2504:
2497:
2493:
2477:
2454:
2434:
2420:
2406:
2398:
2379:
2373:
2370:
2364:
2358:
2338:
2332:
2312:
2292:
2272:
2252:
2246:
2238:
2219:
2213:
2210:
2202:
2188:
2174:
2168:
2165:
2162:
2154:
2150:
2134:
2123:
2115:
2109:
2103:
2083:
2063:
2043:
2020:
2017:
2014:
1999:
1983:
1974:
1968:
1965:
1959:
1953:
1950:
1944:
1938:
1918:
1912:
1909:
1906:
1903:
1900:
1880:
1874:
1871:
1865:
1859:
1856:
1847:
1841:
1838:
1832:
1829:
1823:
1817:
1797:
1791:
1771:
1763:
1762:
1758:
1742:
1733:
1727:
1724:
1718:
1712:
1709:
1703:
1700:
1697:
1691:
1688:
1682:
1679:
1676:
1670:
1650:
1647:
1644:
1641:
1638:
1630:
1629:
1614:
1603:
1595:
1589:
1583:
1563:
1560:
1557:
1549:
1548:
1544:
1540:
1539:
1538:
1521:
1515:
1508:
1507:
1506:rank function
1490:
1470:
1464:
1456:
1440:
1434:
1414:
1394:
1374:
1354:
1334:
1328:
1308:
1287:
1281:
1272:
1271:
1254:
1246:
1236:
1210:
1191:
1178:
1172:
1166:
1157:
1151:
1148:
1125:
1122:
1119:
1116:
1113:
1093:
1087:
1084:
1081:
1078:
1075:
1031:
1011:
1003:
1002:
974:
973:
972:
970:
954:
951:
907:
877:
874:
864:to be a pair
851:
841:
839:
823:
803:
796:in a matroid
795:
791:
775:
767:
751:
741:
731:
714:
687:
679:
675:
667:
663:
647:
614:
608:
605:
585:
582:
579:
576:
573:
553:
547:
527:
507:
487:
479:
478:
474:
470:
454:
441:
437:
434:
406:
403:
383:
377:
374:
371:
368:
364:
361:
352:
351:
336:
323:
312:
308:
307:
306:
304:
288:
280:
276:
248:
244:
228:
208:
192:
189:
166:
152:
150:
140:
138:
137:coding theory
134:
130:
126:
122:
118:
114:
109:
107:
103:
99:
95:
94:axiomatically
91:
90:vector spaces
87:
81:
52:
48:
44:
43:combinatorics
37:
33:
19:
13841:
13826:math.lsu.edu
13825:
13804:the original
13795:
13773:
13755:math.fau.edu
13754:
13749:Locke, S.C.
13730:
13709:
13663:
13658:
13635:
13629:
13623:
13573:
13567:
13554:– via
13531:
13519:– via
13492:
13480:– via
13457:
13428:
13419:
13399:
13393:
13376:
13364:
13360:
13322:
13316:
13281:
13243:
13237:
13215:
13201:– via
13162:
13125:
13122:Oxley, James
13079:
13069:– via
13063:. Retrieved
13054:(1): 26–41.
13051:
13045:
13017:
13011:
12986:
12980:
12967:– via
12937:
12924:. Retrieved
12907:
12880:
12874:
12849:
12836:
12808:
12807:. Series B.
12804:
12767:
12754:– via
12732:
12699:
12693:
12663:
12657:
12630:
12580:
12574:
12539:White (1986)
12534:
12522:
12515:White (1987)
12500:White (1987)
12485:White (1987)
12480:
12473:White (1987)
12468:
12461:White (1987)
12442:. Retrieved
12429:
12424:, p. 64
12422:Oxley (1992)
12417:
12412:, p. 26
12410:Oxley (1992)
12405:
12394:
12387:White (1986)
12382:
12375:Oxley (1992)
12360:Oxley (1992)
12355:
12350:, p. 52
12348:Oxley (1992)
12343:
12336:White (1986)
12321:White (1986)
12316:
12309:White (1986)
12304:
12297:White (1986)
12292:
12285:White (1986)
12280:
12273:White (1986)
12258:White (1986)
12253:
12246:White (1986)
12241:
12236:, p. 32
12234:White (1986)
12229:
12222:Oxley (1992)
12217:
12210:Oxley (1992)
12205:
12198:White (1987)
12193:
12186:Oxley (1992)
12181:
12174:Oxley (1992)
12159:Oxley (1992)
12146:, p. 13
12144:Oxley (1992)
12123:
12111:
12084:
12052:
12041:
11975:
11958:
11941:
11907:
11896:White (1986)
11887:Welsh (1976)
11883:Oxley (1992)
11878:
11858:P.D. Seymour
11833:Jack Edmonds
11826:
11798:Richard Rado
11783:
11771:
11767:Whittle 1995
11760:
11744:Paul Seymour
11742:
11735:
11723:Crapo (1969)
11721:
11718:
11713:Tutte (1965)
11697:
11681:matroids by
11660:
11652:Richard Rado
11649:
11634:
11630:graph theory
11622:
11607:
11599:
11344:
11335:
11332:
11320:model theory
11317:
11302:
11299:
11191:
11185:
11171:
11167:
11165:
11161:
11087:
11082:
11080:
10982:
10903:
10865:
10722:
10578:
10574:
10572:
10350:
10209:
10207:
10175:
10094:
10092:
9982:
9746:
9744:
9614:
9485:
9365:
9363:
9351:
9347:
9342:
9338:
9334:
9330:
9322:
9315:
9311:
9307:
9298:
9290:
9286:
9282:
9278:
9269:
9265:
9259:
9255:
9251:
9246:
9237:
9233:
9229:
9225:
9211:
9096:
9094:
8965:
8961:
8955:
8953:
8943:
8939:
8935:
8933:
8913:
8902:
8868:
8859:
8852:
8843:
8839:
8828:
8822:
8739:
8735:
8734:is called a
8731:
8722:
8718:
8714:
8710:
8709:is called a
8706:
8697:
8693:
8684:
8680:
8676:
8672:
8668:
8599:
8595:
8594:is a subset
8591:
8587:
8578:
8574:
8565:
8561:
8557:
8553:
8549:
8545:
8536:
8532:
8528:
8524:
8520:
8516:
8502:
8498:
8489:
8488:is called a
8485:
8467:
8463:
8459:
8455:
8451:
8448:
8445:
8444:A subset of
8436:
8432:
8428:
8424:
8420:
8413:
8409:
8407:
8397:
8393:
8389:
8385:
8381:
8377:
8373:
8369:
8365:
8361:
8357:
8355:
8350:
8346:
8342:
8338:
8330:
8326:
8325:of matroids
8322:
8318:
8314:
8310:
8306:
8304:
8294:
8290:
8282:
8279:
8276:
8273:
8269:
8261:
8257:
8255:
8250:
8246:
8169:
8165:
8161:
8157:
8153:
8149:
8145:
8141:
8139:
8134:
8130:
8126:
8122:
8118:
8114:
8110:
8106:
8102:
8098:
8094:
8092:
8087:
8083:
8079:
8075:
8071:
8067:
8063:
8059:
8055:
8051:
8047:
8043:
8039:
8035:
8031:
8027:
8025:
7906:planar graph
7859:
7640:
7503:
7473:dual matroid
7471:
7467:
7445:
7437:
7421:
7174:
7170:field theory
7167:
7068:bond matroid
7067:
6843:Laman graphs
6783:lift matroid
6782:
6778:
6675:
6555:
6549:
6344:
6337:
6333:
6332:is called a
6301:simple cycle
6201:
6197:graph theory
6194:
6178:
6158:finite field
6131:
6126:
6080:
6013:
6009:
6007:
6000:
5975:
5931:
5878:
5874:real numbers
5867:finite field
5855:
5849:
5814:
5765:
5646:vector space
5619:
5561:
5481:
5472:
5317:
5208:
5179:free matroid
5136:
5133:Free matroid
5121:
4955:
4538:as a triple
4535:
4530:
4203:
4198:
4194:
4170:
4166:
4162:
4161:is called a
4108:
4080:
4004:
3794:
3489:
3485:
3481:
3479:
3404:
3402:
2777:denotes the
2691:
2529:of a subset
2495:
2491:
2426:
2396:
2236:
2189:
2003:
1784:and element
1504:
1454:
1268:
1242:
1208:
1206:
999:is nonempty.
968:
842:
793:
789:
765:
743:
671:
665:
661:
472:
468:
302:
301:(called the
246:
245:(called the
158:
146:
117:graph theory
110:
97:
50:
40:
13614:Kung (1986)
13373:Tutte, W.T.
13357:Tutte, W.T.
13309:Tutte, W.T.
13020:: 485–520.
12833:Geelen, Jim
12666:: 235–282.
12440:. MapleSoft
12104:Welsh (1976
12089:Welsh (1976
12077:Welsh (1976
12021:Polymatroid
11997:Antimatroid
11780:Researchers
11411:, there is
11168:finite rank
9320:arrangement
8892:NP-complete
8788:convex hull
8698:irreducible
8380:and one in
8170:E − T
8150:contraction
8044:restriction
7243:containing
6699:. A graph
6693:gain graphs
5974:is said to
5737:subsets of
4710:and set in
4636:such that
4204:The family
4105:Hyperplanes
4025:is the set
2569:is the set
1663:, we have:
1455:submatroids
47:mathematics
13872:Categories
13690:0797.05027
13552:0742.00052
13517:0626.00007
13478:0579.00001
13447:0343.05002
13385:0231.05027
13272:0443.05027
13152:0784.05002
13114:1163.01001
13073:(maa.org).
12562:References
12444:2024-08-19
11838:Jim Geelen
11811:W.T. Tutte
11663:W.T. Tutte
11449:such that
11357:nonmaximal
11355:For every
11336:B-matroids
11179:of finite
9355: (λ).
8827:Finding a
8819:Algorithms
8730:A matroid
8602:such that
8425:ground set
8323:direct sum
8313:, and let
8283:as a minor
8272:. We say
8256:A matroid
8160:, written
8117:, written
8054:, written
7930:dual graph
7468:orthogonal
6958:such that
6204:multigraph
5858:Fano plane
5816:represents
5733:to be the
5598:Fano plane
5473:point line
5296:subset of
4163:hyperplane
3795:The class
3591:is a flat.
3520:is closed.
1576:, we have
1138:such that
598:such that
309:(I1) The
247:ground set
243:finite set
179:is a pair
149:equivalent
143:Definition
13861:0953-4806
13716:EMS Press
13706:"Matroid"
13682:0195-6698
13222:EMS Press
13212:"Matroid"
13199:117772439
13065:4 October
12926:4 October
12772:CiteSeerX
12716:119602825
12590:1003.3919
12583:: 18–46.
12034:Citations
11870:Footnotes
11463:∪
11431:∖
11425:∈
11268:
11262:∈
11248:⊆
11229:⇔
11214:
11208:∈
11023:⊕
10939:−
10836:λ
10833:−
10792:−
10780:λ
10688:−
10653:−
10628:⊆
10621:∑
10538:−
10514:−
10488:−
10465:−
10451:⊆
10444:∑
10384:∗
10283:∗
10061:≤
10055:≤
9994:−
9932:∅
9926:μ
9920:∑
9870:−
9854:λ
9777:λ
9715:∗
9704:β
9689:β
9559:−
9548:⊆
9541:∑
9515:−
9497:β
9444:−
9421:−
9403:β
9177:−
9161:λ
9148:∅
9142:μ
9133:∑
9123:λ
9063:−
9047:λ
9020:−
9009:⊆
9002:∑
8992:λ
8920:Macaulay2
8711:component
8694:connected
8634:−
8588:separator
8566:co-simple
8291:forbidden
8218:−
8209:∪
7831:∖
7802:−
7772:∗
7715:∗
7658:∗
7599:∗
7572:∗
7519:∗
7488:∗
7383:equal to
7177:extension
7046:and with
6997:∗
6969:−
6672:matchings
6548:called a
5976:represent
5368:and with
4932:∪
4926:⊆
4920:∈
4894:∈
4868:∪
4862:⊆
4856:∈
4830:∈
4576:in which
4527:Graphoids
4502:⊆
4490:∪
4481:∩
4448:∈
4416:∪
4410:∉
4380:∈
4348:∈
4307:⊆
4146:−
4054:≤
4048:∣
4042:∈
3978:⋁
3975:≤
3969:∣
3963:∈
3942:
3908:⋁
3627:∖
3576:∩
3444:→
3373:
3367:∖
3352:∪
3343:
3337:∈
3305:
3299:∖
3284:∪
3275:
3269:∈
3121:
3115:⊆
3103:
3072:⊆
2963:
2952:
2934:
2847:
2841:⊆
2779:power set
2725:↦
2648:∪
2617:∣
2611:∈
2583:
2508:
2371:−
2211:−
2166:⊂
1966:≤
1951:≤
1910:⊆
1904:⊆
1857:≤
1842:∪
1830:≤
1810:we have:
1710:≤
1701:∩
1680:∪
1648:⊂
1596:≤
1561:⊂
1179:∈
1167:∪
1152:∖
1123:∖
1117:∈
1085:∖
1079:∈
766:dependent
718:∅
715:≠
609:∪
583:∖
577:∈
475:property.
471:, or the
442:∈
407:∈
375:⊆
369:⊆
324:∈
321:∅
311:empty set
36:Meteoroid
13718:. 2001 .
13418:(1937).
13375:(1971).
13311:(1959).
13232:(1980).
13124:(1992).
13037:(2009).
12922:(Report)
12730:(1970).
12652:(1972).
12628:(1980).
12617:10436077
12009:Greedoid
11991:See also
11934:multiset
11736:In 1976
11278:′
11244:′
11192:finitary
11062:′
11030:′
9461:′
9318:) of an
8533:parallel
8277:contains
8184:′
8111:deletion
7183:Suppose
6781:and the
5600:. It is
5322:of rank
5128:Examples
4536:graphoid
4171:copoints
4167:co-atoms
3751:between
3596:(F3) If
3525:(F2) If
3490:subspace
3410:Steinitz
3406:Mac Lane
1004:(B2) If
900:, where
480:(I3) If
438:′
365:′
125:topology
121:geometry
13608:1507091
13600:2371182
13367:: 1–47.
13349:0101527
13341:1993185
13301:1170126
13191:1027839
13144:1207587
13106:2516551
13026:0188102
13003:2371070
12965:0890330
12899:1998894
12825:1769191
12752:0290980
12682:1996381
12609:3045140
11679:graphic
11675:regular
11604:History
11328:algebra
11309:Hilbert
10173:flats.
9216:of the
8856:problem
8790:of the
8786:is the
8523:, then
8503:isthmus
8058: |
8008:Example
7442:Duality
7263:. Let
7129:is the
6551:gammoid
6303:. Then
6170:Seymour
5294:element
3494:maximal
3484:, or a
2492:closure
2237:nullity
1543:integer
967:called
794:circuit
664:or the
279:subsets
51:matroid
32:Metroid
13859:
13849:
13688:
13680:
13606:
13598:
13550:
13540:
13515:
13505:
13476:
13466:
13445:
13435:
13383:
13347:
13339:
13299:
13289:
13270:
13197:
13189:
13179:
13150:
13142:
13132:
13112:
13104:
13094:
13024:
13001:
12963:
12953:
12897:
12823:
12792:
12774:
12750:
12740:
12714:
12680:
12638:
12615:
12607:
11774:Geelen
11677:, and
11671:binary
11582:
11576:
11556:
11550:
11530:
11524:
11504:
11498:
11475:
11457:
11437:
11419:
11399:
11393:
11373:
11367:
11232:
11226:
10848:
10741:
10705:
10555:
10505:
10389:
10333:
10247:
10076:
9723:
9646:
9597:
9333:where
9194:
8669:proper
8546:simple
8499:coloop
8433:points
8321:. The
8148:, the
8042:, the
8034:, and
8016:Minors
7989:
7943:
7842:
7740:
7683:
7624:
7544:
7404:
7346:to be
7144:
7081:
7011:
6821:
6762:
6695:, and
6297:forest
6014:linear
5954:, and
5881:matrix
5829:
5748:
5658:
5545:
5506:
5471:
5412:
5333:
5067:
4938:
4508:
4422:
4313:
4120:
4063:
3987:
3914:
3716:
3482:closed
3385:
3243:
3133:
3078:
2982:
2909:
2859:
2816:
2753:where
2674:
2605:
2458:
2397:corank
2336:
2250:
2172:
2132:
1981:
1916:
1878:
1795:
1740:
1612:
1468:
1438:
1332:
1285:
1189:
1091:
645:
630:is in
551:
452:
381:
334:
275:family
249:) and
221:where
206:
135:, and
13822:(PDF)
13807:(PDF)
13792:(PDF)
13596:JSTOR
13337:JSTOR
13195:S2CID
13042:(PDF)
12999:JSTOR
12920:(PDF)
12895:JSTOR
12712:S2CID
12678:JSTOR
12613:S2CID
12585:arXiv
12438:(PDF)
12120:(PDF)
11932:be a
10983:when
9370:Crapo
9306:When
9277:When
9224:When
9099:) as
8924:Maple
8909:Macek
8575:cycle
8477:girth
8449:spans
8358:union
8266:minor
8251:E - T
7504:basis
6603:In a
6508:onto
6166:Tutte
6038:field
6016:. If
5904:field
5870:GF(2)
5602:GF(2)
5181:over
5082:then
4883:or a
4787:with
4532:Minty
4467:with
4399:with
4296:with
3878:atoms
3664:cover
3662:that
3476:Flats
3326:then
3192:from
3061:with
2096:with
1931:then
975:(B1)
969:bases
790:basis
426:then
273:is a
241:is a
98:flats
13857:ISSN
13847:ISBN
13678:ISSN
13538:ISBN
13503:ISBN
13464:ISBN
13433:ISBN
13287:ISBN
13177:ISBN
13130:ISBN
13092:ISBN
13067:2014
12951:ISBN
12928:2014
12790:ISBN
12738:ISBN
12636:ISBN
11725:and
11311:and
11088:The
10208:The
10093:The
10044:for
10029:>
9745:The
9364:The
9329:(or
8954:The
8918:and
8916:SAGE
8851:The
8756:The
8667:. A
8531:are
8527:and
8517:f, g
8490:loop
8475:The
8460:span
8408:Let
8396:and
8372:and
8364:and
8356:The
8341:and
8329:and
8305:Let
7379:has
7203:and
6858:Let
6841:The
6554:: a
6398:and
6378:let
6349:The
5860:, a
5612:The
5209:Let
5137:Let
5016:and
4596:and
4252:and
3771:and
3545:and
3486:flat
3172:and
3021:and
2496:span
2427:Let
1347:and
1270:rank
1068:and
1024:and
676:(or
500:and
115:and
49:, a
13686:Zbl
13668:doi
13640:doi
13586:hdl
13578:doi
13548:Zbl
13513:Zbl
13474:Zbl
13443:Zbl
13404:doi
13381:Zbl
13327:doi
13268:Zbl
13258:hdl
13248:doi
13169:doi
13148:Zbl
13110:Zbl
13084:doi
13056:doi
12991:doi
12943:doi
12885:doi
12881:271
12856:doi
12813:doi
12782:doi
12704:doi
12668:doi
12664:171
12595:doi
12581:239
11628:or
11542:of
10577:or
10097:of
9749:of
9661:If
9297:of
8960:of
8905:Oid
8882:in
8713:of
8696:or
8671:or
8598:of
8590:of
8577:of
8560:of
8535:in
8501:or
8435:of
8427:of
8360:of
8337:of
8293:or
8268:of
8156:by
8152:of
8125:or
8113:of
8050:to
8046:of
8026:If
7932:of
7613:is
7506:in
7470:or
7446:If
7326:of
7175:An
7070:of
6938:of
6125:is
6079:is
6012:or
5934:of
5774:If
5693:on
5624:If
4272:in
4169:or
3876:of
3488:or
3258:if
3232:of
3041:of
2898:of
2805:of
2549:of
2494:or
2305:in
2076:of
1301:If
1274:of
396:if
281:of
277:of
88:in
41:In
34:or
13874::
13855:.
13824:.
13794:.
13772:.
13753:.
13729:.
13714:.
13708:.
13684:.
13676:.
13664:15
13657:.
13636:65
13628:.
13624:GF
13604:MR
13602:.
13594:.
13584:.
13574:57
13572:.
13546:.
13511:.
13501:.
13472:.
13441:.
13400:18
13398:.
13365:69
13345:MR
13343:.
13335:.
13323:90
13321:.
13315:.
13297:MR
13295:.
13266:.
13256:.
13244:28
13236:.
13220:.
13214:.
13193:.
13187:MR
13185:.
13175:.
13146:.
13140:MR
13138:.
13108:.
13102:MR
13100:.
13090:.
13052:82
13050:.
13044:.
13022:MR
13018:15
13016:.
12997:.
12987:58
12985:.
12961:MR
12959:.
12949:.
12893:.
12879:.
12873:.
12848:.
12821:MR
12819:.
12809:79
12788:.
12780:.
12748:MR
12746:.
12726:;
12710:.
12698:.
12676:.
12662:.
12656:.
12611:.
12605:MR
12603:.
12593:.
12579:.
12573:.
12546:^
12507:^
12492:^
12453:^
12367:^
12328:^
12265:^
12166:^
12151:^
12132:^
12122:.
12096:^
12063:^
11983:).
11673:,
11632:.
11620:.
11330:.
11265:cl
11211:cl
11183:.
10581:,
10200:.
9285:*(
9129::=
8998::=
8867:A
8586:A
8416:.
8388:=
8353:.
8297:.
8253:.
8101:=
8090:.
7172:.
6691:,
6206:)
6199:.
6179:A
6152:;
5879:A
5770:.
5479:.
5249:a
5201:.
4101:.
3939:cl
3791:).
3422:cl
3370:cl
3340:cl
3302:cl
3272:cl
3118:cl
3100:cl
2960:cl
2949:cl
2931:cl
2844:cl
2703:cl
2580:cl
2505:cl
2419:.
730:.
139:.
131:,
127:,
123:,
108:.
74:ɔɪ
65:eɪ
13832:.
13780:.
13761:.
13741:.
13692:.
13670::
13648:.
13642::
13610:.
13588::
13580::
13449:.
13422:.
13410:.
13406::
13387:.
13351:.
13329::
13274:.
13260::
13250::
13224:.
13171::
13154:.
13116:.
13086::
13058::
13028:.
13005:.
12993::
12945::
12901:.
12887::
12864:.
12858::
12827:.
12815::
12798:.
12784::
12718:.
12706::
12700:3
12684:.
12670::
12644:.
12619:.
12597::
12587::
12447:.
11920:E
11715:)
11707:"
11585:.
11579:X
11553:X
11527:I
11501:X
11472:}
11469:x
11466:{
11460:I
11434:I
11428:J
11422:x
11396:J
11370:I
11285:.
11282:)
11275:Y
11271:(
11259:x
11251:Y
11241:Y
11223:)
11220:Y
11217:(
11205:x
11172:E
11140:)
11137:G
11134:(
11131:M
11127:T
11104:G
11100:T
11066:)
11059:M
11055:(
11052:F
11049:)
11046:M
11043:(
11040:F
11037:=
11034:)
11027:M
11020:M
11017:(
11014:F
10991:e
10968:)
10965:e
10961:/
10957:M
10954:(
10951:F
10948:+
10945:)
10942:e
10936:M
10933:(
10930:F
10927:=
10924:)
10921:M
10918:(
10915:F
10889:)
10886:1
10883:,
10880:1
10877:(
10874:T
10851:.
10845:)
10842:0
10839:,
10830:1
10827:(
10822:M
10818:T
10812:)
10809:M
10806:(
10803:r
10799:)
10795:1
10789:(
10786:=
10783:)
10777:(
10772:M
10768:p
10744:,
10736:M
10732:T
10708:.
10700:)
10697:S
10694:(
10691:r
10684:|
10680:S
10676:|
10671:v
10665:)
10662:S
10659:(
10656:r
10650:)
10647:M
10644:(
10641:r
10637:u
10631:E
10625:S
10617:=
10614:)
10611:v
10608:,
10605:u
10602:(
10597:M
10593:R
10558:.
10550:)
10547:S
10544:(
10541:r
10534:|
10530:S
10526:|
10521:)
10517:1
10511:y
10508:(
10500:)
10497:S
10494:(
10491:r
10485:)
10482:M
10479:(
10476:r
10472:)
10468:1
10462:x
10459:(
10454:E
10448:S
10440:=
10437:)
10434:y
10431:,
10428:x
10425:(
10420:M
10416:T
10392:.
10380:M
10359:M
10336:,
10330:)
10327:x
10324:,
10321:y
10318:(
10313:M
10309:T
10305:=
10302:)
10299:y
10296:,
10293:x
10290:(
10279:M
10274:T
10250:,
10244:)
10241:y
10238:,
10235:x
10232:(
10227:M
10223:T
10161:i
10141:)
10138:M
10135:(
10130:i
10126:W
10105:M
10079:.
10073:)
10070:M
10067:(
10064:r
10058:i
10052:0
10032:0
10026:)
10023:M
10020:(
10015:i
10011:w
10005:i
10001:)
9997:1
9991:(
9968:,
9965:}
9962:i
9959:=
9956:)
9953:A
9950:(
9947:r
9944::
9941:)
9938:A
9935:,
9929:(
9923:{
9917:=
9914:)
9911:M
9908:(
9903:i
9899:w
9873:i
9867:)
9864:M
9861:(
9858:r
9833:)
9830:M
9827:(
9822:i
9818:w
9797:i
9757:M
9726:.
9720:)
9711:M
9707:(
9701:=
9698:)
9695:M
9692:(
9669:M
9649:.
9643:M
9623:M
9600:.
9594:)
9591:X
9588:(
9585:r
9579:|
9575:X
9571:|
9566:)
9562:1
9556:(
9551:E
9545:X
9535:)
9532:M
9529:(
9526:r
9522:)
9518:1
9512:(
9509:=
9506:)
9503:M
9500:(
9471:)
9468:1
9465:(
9457:M
9453:p
9447:1
9441:)
9438:M
9435:(
9432:r
9428:)
9424:1
9418:(
9415:=
9412:)
9409:M
9406:(
9380:p
9352:M
9348:p
9343:A
9339:p
9335:F
9331:F
9327:ℝ
9323:A
9316:A
9314:(
9312:M
9308:M
9301:.
9299:G
9291:G
9287:G
9283:M
9279:M
9272:.
9270:G
9266:c
9262:)
9260:G
9258:(
9256:M
9252:p
9247:G
9238:G
9234:G
9232:(
9230:M
9226:M
9197:,
9189:)
9186:A
9183:(
9180:r
9174:)
9171:E
9168:(
9165:r
9157:)
9154:A
9151:,
9145:(
9137:A
9126:)
9120:(
9115:M
9111:p
9097:M
9080:,
9075:)
9072:S
9069:(
9066:r
9060:)
9057:E
9054:(
9051:r
9040:|
9036:S
9032:|
9027:)
9023:1
9017:(
9012:E
9006:S
8995:)
8989:(
8984:M
8980:p
8962:M
8940:E
8936:M
8894:.
8844:F
8840:F
8814:.
8802:M
8772:M
8768:P
8740:M
8732:M
8723:M
8719:M
8715:M
8707:M
8687:.
8685:E
8677:E
8655:)
8652:M
8649:(
8646:r
8643:=
8640:)
8637:S
8631:E
8628:(
8625:r
8622:+
8619:)
8616:S
8613:(
8610:r
8600:E
8596:S
8592:M
8579:M
8562:M
8554:M
8539:.
8537:M
8529:g
8525:f
8521:M
8486:M
8470:.
8468:K
8464:K
8456:E
8452:M
8446:E
8439:.
8437:M
8429:M
8421:E
8414:E
8410:M
8398:F
8394:E
8390:F
8386:E
8382:N
8378:M
8374:F
8370:E
8366:N
8362:M
8351:N
8347:M
8343:F
8339:E
8331:N
8327:M
8319:F
8315:N
8311:E
8307:M
8280:N
8274:M
8270:M
8262:M
8258:N
8247:T
8233:.
8230:)
8227:T
8224:(
8221:r
8215:)
8212:T
8206:A
8203:(
8200:r
8197:=
8194:)
8191:A
8188:(
8181:r
8166:T
8164:/
8162:M
8158:T
8154:M
8146:E
8142:T
8135:M
8131:T
8129:−
8127:M
8123:T
8121:\
8119:M
8115:T
8107:S
8105:−
8103:M
8099:T
8095:S
8088:S
8084:M
8080:S
8076:M
8072:S
8068:M
8064:S
8060:S
8056:M
8052:S
8048:M
8040:E
8036:S
8032:E
8028:M
7992:.
7986:F
7966:F
7946:.
7940:G
7916:M
7892:M
7872:M
7845:.
7838:)
7834:S
7828:E
7824:(
7820:r
7817:+
7814:)
7811:M
7808:(
7805:r
7798:|
7794:S
7790:|
7786:=
7783:)
7780:S
7777:(
7768:r
7743:.
7737:M
7711:M
7686:.
7680:M
7654:M
7627:.
7621:M
7595:M
7568:M
7547:.
7541:M
7515:M
7484:M
7454:M
7407:.
7400:|
7396:S
7392:|
7367:)
7364:S
7361:(
7358:F
7334:E
7314:S
7303:.
7291:K
7271:E
7251:F
7231:K
7211:K
7191:F
7147:,
7141:F
7117:)
7114:F
7111:(
7108:r
7084:.
7078:G
7054:I
7034:E
7014:,
7008:)
7005:G
7002:(
6993:M
6972:F
6966:G
6946:E
6926:F
6906:I
6886:E
6866:G
6853:.
6824:.
6818:G
6798:G
6765:,
6759:)
6756:B
6753:,
6750:G
6747:(
6727:B
6707:G
6658:U
6638:)
6635:E
6632:,
6629:V
6626:,
6623:U
6620:(
6617:=
6614:G
6598:.
6586:G
6566:E
6536:E
6516:U
6496:F
6475:|
6471:U
6467:|
6446:U
6426:E
6406:F
6386:E
6366:G
6320:)
6317:G
6314:(
6311:M
6283:G
6263:E
6243:)
6240:G
6237:(
6234:M
6214:G
6140:F
6113:M
6103:;
6091:F
6067:M
6047:F
6024:M
5997:.
5985:M
5962:A
5942:A
5914:M
5890:A
5852:.
5832:.
5826:M
5802:E
5782:M
5751:.
5745:E
5721:M
5701:E
5681:M
5661:,
5655:V
5632:E
5572:E
5548:,
5540:n
5537:,
5534:n
5530:U
5509:,
5501:n
5498:,
5495:0
5491:U
5459:n
5439:n
5415:.
5407:n
5404:,
5401:k
5397:U
5376:n
5356:k
5336:.
5330:k
5304:E
5282:k
5261:E
5237:k
5217:E
5189:E
5165:E
5145:E
5108:)
5105:D
5102:,
5099:C
5096:,
5093:E
5090:(
5070:,
5064:E
5044:M
5024:D
5004:C
4984:D
4964:C
4941:.
4935:G
4929:B
4923:Y
4917:g
4897:D
4891:Y
4871:G
4865:R
4859:X
4853:g
4833:C
4827:X
4807:}
4804:g
4801:{
4798:=
4795:G
4775:B
4772:,
4769:G
4766:,
4763:R
4743:L
4718:D
4698:C
4673:D
4648:C
4624:L
4604:D
4584:C
4564:)
4561:D
4558:,
4555:C
4552:,
4549:L
4546:(
4511:.
4505:X
4499:}
4496:x
4493:{
4487:)
4484:Z
4478:Y
4475:(
4453:H
4445:X
4425:,
4419:Z
4413:Y
4407:x
4385:H
4377:Z
4374:,
4371:Y
4351:E
4345:x
4332:.
4316:.
4310:Y
4304:X
4282:H
4260:Y
4240:X
4214:H
4199:M
4195:E
4181:E
4149:1
4143:r
4123:,
4117:r
4089:L
4066:.
4060:}
4057:y
4051:x
4045:E
4039:x
4036:{
4013:y
3990:.
3984:}
3981:S
3972:x
3966:E
3960:x
3957:{
3954:=
3951:)
3948:S
3945:(
3917:,
3911:S
3888:S
3864:E
3844:L
3816:)
3813:M
3810:(
3805:L
3779:T
3759:S
3739:U
3719:,
3713:S
3693:T
3673:S
3650:T
3630:S
3624:E
3604:S
3579:T
3573:S
3553:T
3533:S
3508:E
3460:)
3457:E
3454:(
3449:P
3441:)
3438:E
3435:(
3430:P
3425::
3408:–
3388:.
3382:)
3379:Y
3376:(
3364:)
3361:}
3358:a
3355:{
3349:Y
3346:(
3334:b
3314:)
3311:Y
3308:(
3296:)
3293:}
3290:b
3287:{
3281:Y
3278:(
3266:a
3246:,
3240:E
3220:Y
3200:E
3180:b
3160:a
3136:.
3130:)
3127:Y
3124:(
3112:)
3109:X
3106:(
3081:,
3075:Y
3069:X
3049:E
3029:Y
3009:X
2985:.
2978:)
2973:)
2970:X
2967:(
2956:(
2946:=
2943:)
2940:X
2937:(
2912:,
2906:E
2886:X
2862:.
2856:)
2853:X
2850:(
2838:X
2819:,
2813:E
2793:X
2763:P
2741:)
2738:E
2735:(
2730:P
2722:)
2719:E
2716:(
2711:P
2706::
2677:.
2669:}
2662:)
2657:}
2654:x
2651:{
2645:A
2640:(
2635:r
2632:=
2629:)
2626:A
2623:(
2620:r
2614:E
2608:x
2600:{
2595:=
2592:)
2589:A
2586:(
2557:E
2537:A
2517:)
2514:A
2511:(
2478:r
2455:E
2435:M
2407:A
2383:)
2380:A
2377:(
2374:r
2368:)
2365:E
2362:(
2359:r
2339:.
2333:M
2313:M
2293:E
2273:A
2253:.
2247:A
2223:)
2220:A
2217:(
2214:r
2207:|
2203:A
2199:|
2175:,
2169:M
2163:A
2135:.
2128:|
2124:A
2120:|
2116:=
2113:)
2110:A
2107:(
2104:r
2084:E
2064:A
2044:E
2024:)
2021:r
2018:,
2015:E
2012:(
2000:.
1984:.
1978:)
1975:E
1972:(
1969:r
1963:)
1960:B
1957:(
1954:r
1948:)
1945:A
1942:(
1939:r
1919:,
1913:E
1907:B
1901:A
1881:.
1875:1
1872:+
1869:)
1866:A
1863:(
1860:r
1854:)
1851:}
1848:x
1845:{
1839:A
1836:(
1833:r
1827:)
1824:A
1821:(
1818:r
1798:,
1792:x
1772:A
1759:.
1743:.
1737:)
1734:B
1731:(
1728:r
1725:+
1722:)
1719:A
1716:(
1713:r
1707:)
1704:B
1698:A
1695:(
1692:r
1689:+
1686:)
1683:B
1677:A
1674:(
1671:r
1651:E
1645:B
1642:,
1639:A
1615:.
1608:|
1604:A
1600:|
1593:)
1590:A
1587:(
1584:r
1564:E
1558:A
1545:.
1525:)
1522:A
1519:(
1516:r
1491:A
1471:.
1465:E
1441:.
1435:M
1415:A
1395:A
1375:E
1355:A
1335:,
1329:E
1309:M
1288:.
1282:M
1255:M
1221:B
1192:.
1184:B
1176:}
1173:b
1170:{
1164:)
1161:}
1158:a
1155:{
1149:A
1146:(
1126:A
1120:B
1114:b
1094:,
1088:B
1082:A
1076:a
1054:B
1032:B
1012:A
985:B
955:,
952:E
930:B
908:E
888:)
883:B
878:,
875:E
872:(
852:M
824:E
804:M
776:E
752:E
710:I
688:E
668:.
648:.
640:I
618:}
615:x
612:{
606:B
586:B
580:A
574:x
554:,
548:B
528:A
508:B
488:A
455:.
447:I
435:A
412:I
404:A
384:,
378:E
372:A
362:A
337:.
329:I
289:E
259:I
229:E
209:,
203:)
198:I
193:,
190:E
187:(
167:M
80:/
77:d
71:r
68:t
62:m
59:ˈ
56:/
38:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.