Name
Abstract | ||
|---|---|---|
Tutte proved that a matroid is binary if and only if it does not contain a U2.4-minor. This provides a short proof for non-GF(2)-representability in that we can verify that a given minor is isomorphic to U2.4 in just a few rank evaluations. Using excluded-minor characterizations. short proofs can also be given of non-representablity over GF(3) and over GF(4). For GF(5), it is not even known whether the set of excluded minors is finite. Nevertheless, we show here that if a matroid is not representable over GF(5), then this can be verified by a short proof. Here a "short proof" is a proof whose length is bounded by some polynomial in the number of elements of the matroid. In contrast to these positive results, Seymour showed that we require exponentially many rank evaluations to prove GF(2)-representability, and this is in fact the case for any field. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.jctb.2003.11.001 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
rota's conjecture,matroids,positive result,rank evaluation,excluded-minor characterization,short proof,representation,05b35 | Matroid,Discrete mathematics,Combinatorics,Rota's conjecture,Matroid partitioning,Isomorphism,Mathematical proof,Graphic matroid,GF(2),Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
91 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
3 | 0.43 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jim Geelen | 1 | 241 | 29.49 |
| James Oxley | 2 | 194 | 24.39 |
| Dirk Vertigan | 3 | 331 | 32.14 |
| Geoff Whittle | 4 | 471 | 57.57 |