Binary 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].

Lemma 4.4 Let M be a 3-connected binary matroid on at most 14 elements with an F₇-minor. If M has branch-width 4, then M has an N-minor for some N in F₂.

Here F₂ = {grQ3, grO6, grK5, grK5*, grV8, grV8*, R10, ND11, ND14, ND23}.

Let us look at a 3-connected matroid M with an F₇-minor. By the Seymour's splitter Theorem, there is a sequence of 3-connected matroids N₀=F₇, ... , N_t=M such that N_i+1 is a single-element extension or coextension of N_i. Since binary matroids have unique representations up to matrix equivalence, we actually consider a one-row or one-column extension of the matrix of N_i in the search. At the t-th step of our computation, t=1,...,7, we generate all one-row or one-column extensions on 7+t elements from the branch-width-3 extensions on 6+t elements. Then we put aside the new extensions having branch-width bigger than 3, and verify that all of them contain a minor in the set F₂. We continue the next step with the remaining (branch-width-3) extensions.

Firstly, make yourself familiar with the MACEK matroid computing package.
The script used for the above computation, named bw3bin, is prepared as a procedure. One call to it performs one step of the whole computation. See below how to call this procedure step by step. The procedure takes one argument which contains a starting list of matroids for this step. The default value for the argument is "f7.".

# Call this as:  macek -g-1 -pGF2 '&bw3bin f7..'
# 
@subd-param1 "f7."

Next the procedure prepares its working subtree. (This is not neccessary in general, but we do so here to neatly organize the procedure.) Each node in the subtree is named and commented so that you see its purpose. Keep in mind that this part of the procedure is processed immediately when the file is read from the input. The known excluded minors are taken from the file bw3-bin-exc.

@sub-known-excluded "bw3-bin-exc"
@sub-excluded "(((S)))"
{
@name "bw3bin-w"
@comment "bw3bin working subframe:"
{
<${known-excluded}
}{
@name extens1
@comment "new b-extensions of $input [${param1}]..."
}{
@name e-bwidth4
@comment "those generated with bwidth 4 get here:"
}{
@name e-bwidth4n
@comment "those new excl-minors with bwidth 4 get here:"
}{
@name e-bwidth3
@comment "those next with bwidth 3 get here:"
}}
@sub-input "(()(S))"
{
<$param1
@comment "this is the starting set of matroids ${param1}:"
}

Here the computation part of the procedure starts. We first define macros for easy access to parts of the above subtree. Notice that we later close the parameter addresses that use these macros with `|', so that we do not have to bother with the proper number of brackets that must be closed. Then we decrease output verbosity level, and print the whole starting tree.

@sub-generto  "(((4)("
@sub-generall  "(((1)("
@sub-gener4bw  "(((2)("
@sub-gener4n  "(((3)("
!quiet
!prtree (T)

This part generates all one-element extensions and coextensions to the starting list of matroids. Then the generated extensions are copied to a storage, and they are as well separated by branch-width into generto and $gener4bw. Notice the way we separate the generated list --- we first mark those frames not having branch-width 3 by the command !rex-bwidth3, and then we move the marked frames away.

!extend b $input  >$generto(0t)|
!move ${generto}S|  >$generall(0t)|
!rex-bwidth3 ${generto}S|
!move ^1  >$gener4bw(0t)|

Finally, we store the results into several files. Out of those (co)extensions not having branch-width 3 we filter out ones having minor among already known excluded minors. The remaining ones are returned as possible new excluded minors (which do not actually exist as we see).

!writetreeto ${param1}b-all (T)
!writetreeto ${param1}b ${generto}T|
!writetreeto ${param1}b-4 ${gener4bw}T|
!move ${gener4bw}S|  >$gener4n(0t)|
!filx-minor ${gener4n}s| $excluded
!writetreeto ${param1}b-4n ${gener4n}T|
!prtree

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

{ F7 }

Recall that we are searching only through non-regular binary matroids, and hence we may assume, up to duality, that all matroids we need to generate contain an F₇ minor. We then call:

bash$ macek -pGF2 -g-1 '&bw3bin f7.'

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

bash$ macek -pGF2 -g-1 '&bw3bin f7.b'
bash$ macek -pGF2 -g-1 '&bw3bin f7.bb'
bash$ macek -pGF2 -g-1 '&bw3bin f7.bbb'
bash$ macek -pGF2 -g-1 '&bw3bin f7.bbbb'
bash$ macek -pGF2 -g-1 '&bw3bin f7.bbbbb'
bash$ macek -pGF2 -g-1 '&bw3bin f7.bbbbbb'

We have to execute seven steps total to get to matroids on 14 elements. You may easily check in the resulting files that no other excluded minors for branch-width 3 were found.

If you want to test the above obtained (partial) results yourself, you are welcome to play with the supplied script and the MACEK program. For example, you may try to start generating from the dual of F₇, which is a significant difference internally in the program, but all the result stays the same. (That is because all binary row-extensions of F₇ have an F₇*-minor.) You may also test the generated lists of branch-width-3 extensions of F₇ that they are closed on duality, and much more...
Remember that MACEK is a general-use package for structural computations with represented matroids, not a one-purpose special tool. Hence you may test the MACEK commands on other (similar) structural problems to which you know the correct solution, thus gaining more confidence in the presented results.

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.