Ternary 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.5 Let F₃ be the set of (pairwise non-isomorphic) excluded minors for branch-width 3 that are ternary but not binary. Then F₃ contains no matroids on less than 9 elements, 18 matroids on 9 elements, 31 matroids on 10 elements, and no matroid on 11 or 12 elements.

The set F₃ on up to 12 elements is here, and a Macek procedure bw3tern here.

All non-binary matroids contain a U_2,4-minor. Unfortunately, U_2,4 (the 2-whirl) is one of the exceptions in the Seymour's Splitter Theorem, but an enhancement of this theorem presented in [Oxley, Matroid Theory, Section 11.3] implies that all ternary extensions of U_2,4 that are not whirls contain a single-element extension or coextension of W³ (the 3-whirl) as a minor. All whirls have branch-width at most 3. Therefore we perform a similar computation as above starting from the self-dual matroid W³. We must not forget to exclude those matroids having some ternary (i.e. regular) member of F₂ as a minor.

Firstly, make yourself familiar with the MACEK matroid computing package.
We do not describe the procedure bw3tern separately because it is very similar to the description of bw3bin. The only significant difference is that now we do not know the set of excluded minors, and so we collect the excluded minors we have found into a designated file.

Now we show how the above procedure is called to get the proposition. The whole file defining the procedure should be included in the Macek distribution under the name `bw3tern'. You need to first create the starting list of matroids `t6.' looking like:

{ Wh3 }

Moreover, you have to create an empty file `t6.-exc' for collecting the new excluded minors. Another file `bw3-reg-exc' with the regular excluded minors should be included with the package.

Then you call:

bash$ macek -pGF3 -g-1 '&bw3tern t6.'

The previous command performs one step of the search process. The next step starts with the file `t6.b' generated previously. Then the next step starts with `t6.bb', etc...

bash$ macek -pGF3 -g-1 '&bw3tern t6.b'
bash$ macek -pGF3 -g-1 '&bw3tern t6.bb'
bash$ macek -pGF3 -g-1 '&bw3tern t6.bbb'
bash$ macek -pGF3 -g-1 '&bw3tern t6.bbbb'
bash$ macek -pGF3 -g-1 '&bw3tern t6.bbbbb'

We have to execute six steps total to get to matroids on 12 elements. As you may see, computation time grows quite rapidly from step to step, and so we do not attempt to get past 12 elements. This computation remains unfinished, but it seems that no new excluded minors would be generated anyway.

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.