Quaternary Excluded Minors for Branch-Width 3

We provide a computer-assisted proof for the following finite-case statement from the paper [Petr Hlineny, On the Excluded Minors for Matroids of Branch-Width Three, submitted 2002].

Proposition 4.6 Let F₄ be the set of (pairwise non-isomorphic) excluded minors for branch-width 3 that are quaternary but neither ternary nor binary. Then F₄ contains no matroids on less than 8 elements, 5 matroids on 8 elements, 90 matroids on 9 elements, and 32 matroids on 10 elements.

The set F₄ on up to 10 elements is here, and a Macek procedure bw3quat here.

Important! (posted 27.3.)
The previous numbers in Proposition 4.6 contained some pairs of isomorphic matroids in nonequivalent representations. That was an unfortunate error, and the duplicated pairs are now removed. Read below for more information.

We use the following result of [Semple, Whittle]: A non-binary non-ternary matroid representable over some field has a U_2,5- or U_3,5-minor. Clearly, such a matroid must contain a U_2,5-minor, unless it is isomorphic to U_n-2,n which has branch-width 3. The compuation is then analogous to the previous two. Again, we should exclude those matroids having some member of F₂ or some quaternary member of F₃ as a minor.

One new theoretical problem arises for quaternary matroids in general --- one matroid may have non-equivalent quaternary representations. Fortunately, this problem is manageable in the quaternary field, since 3-connected matroids may have at most two nonequivalent quaternary representations that arise from the automorphism w -> w+1 of GF(4). Read more in the MACEK documenation.

We refer to the previous one for more details.
The whole file defining the procedure should be included in the Macek distribution under the name `bw3quat'. You need to first create the starting list of matroids `q5.' looking like:

{ U25 }

Moreover, you have to create an empty file `q5.-exc' for collecting the new excluded minors. Another file `bw3-trqt-exc' with the ternary & quaternary excluded minors should be included with the package (up to 9 elements only). The two 9-element matroids in this file were found among the ternary excluded minors using the "6th root of unity" partial field.

Then you call:

bash$ macek -pGF4 -g-1 '&bw3quat q5.'
bash$ macek -pGF4 -g-1 '&bw3quat q5.b'
bash$ macek -pGF4 -g-1 '&bw3quat q5.bb'
bash$ macek -pGF4 -g-1 '&bw3quat q5.bbb'
bash$ macek -pGF4 -g-1 '&bw3quat q5.bbbb'

Finally, you call the next command to remove isomorphic nonequivalent pairs of matroids from the resulting list `q5.bbbbb-exc'. The cleaned list is stored in `q5.bbbbb-excnq'. (The idea behind this command is that nonequivalent pairs of isomorphic matroid representations over GF(4) arise from the automorphism w -> w+1. This automorphism is applied to the whole list, and the isomorphic pairs are then detected as usual matrix equivalence.) You need version >=0.8.1 of MACEK here.

bash$ macek '!filt-unique;!writetreeto q5.bbbbb-excnq ((T))' q5.bbbbb-exc '@replace w _w+1;<q5.bbbbb-exc'
--

We do not attempt to compute beyond 10 elements since the numbers of generated extensions are enormous. (Moreover, if you wanted to extend this computation further, you would first have to determine the 10-element memebrs of `bw3-trqt-exc' above!)
We provide this computation mainly to show that there are many excluded minors for branch-width 3, and much more matroids to search in general, and so it is probably not feasible to search through all abstract matroids on up to 14 elements.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.