5
$\begingroup$

I am wondering what is the (computationally) best way to tell if a matroid of size $n$ and rank $r$ is binary(or whether it has a $U^2_4$ minor) given either one of these: 1) An independence oracle 2) Its rank vector 3) A basis oracle

I want to implement $U^2_4$/binary detection(Most likely given a basis oracle which will be in form of the reverse-lexicographic encoding in [3]).

What I know(or what I think I know):

1) can't be solved by asking polynomial number of questions to the oracle which is due to Seymour[1].

2) and 3) One can write a brute force implementation which would compute and check all minors of size 4.

Also, I considered following ideas:

a) For problem (3), given a matroid $M$ one can start with an $r\times r$ Identity matrix and assign its columns to elements of some basis say $B^*$. Now we expand this matrix by adding columns that correspond to $e\in E(M)\setminus B^*$. We now fill r entries in this new column with $0$ or $1$. For filling $i^{th}$ entry in the column, we ask the basis oracle if $(B^*\setminus i)\cup e$ is a basis. If it is, we put a $1$ in that entry, $0$ otherwise. When we are done constructing all $n-r$ columns this way we have the only binary matrix that correctly reflects if an $r$-subset S of $E(M)$ with $|S\cap B^*|=r-1$ is a basis or not. As for other $r$-subsets, we can test their rank in the matrix and ask basis oracle whether each of them is a basis. If the two results don't match for any $r$-subset, we conclude that the matroid is not binary representable. This way seems better than the brute-force 'compute and check all minors' in terms of complexity.

b) One can compute all $r-1$ flats of $M$ from bases(Using an algorithm again due to Seymour [2]). Then compute all $r-2$ flats. Then use scum theorem(i.e. check if any $r-2$ flat is contained in more than three $r-1$ flats).

EDIT Some extra info: Here is what I am really trying to do: Much on the lines of [3] and [4] I am trying to enumerate(list) matroids, but only the binary ones using single element extensions(by simply not extending any non-binary matroids produced). This list(scalar binary codes) and more lists created after pairing of bits(vector binary codes) are then to be used for computer assisted achievability proofs of rate regions of multisource network coding problems. Matsumoto [3] was very generous to share his c++ code which I am parallelizing using OpenMPI(My C $U^2_4$ check which is currently brute-force seamlessly goes into this scheme). Since the binary matroids are so less in number[5] compared to all matroids, I am expecting to go much farther. I have to care about computational efficiency because there are millions of matroids to be tested just at ground set size 14.

Given all this, although I appreciate and have been following sage-matroid library, I am not much of a Python guy I am not very sure how sage's code will go into my OpenMPI-C++ code(well, I won't exclude the possibility of existence of some hack that will let me do this). Hence, what I am looking for is pointers to best algorithms around which Dr. Royle's answer does tell.

[1] Seymour, P. D.; Walton, P. N. (1981), "Detecting matroid minors", Journal of the London Mathematical Society, Second Series 23 (2): 193–203

[2] P.D. Seymour, A Note on Hyperplane Generation, Journal of Combinatorial Theory, Series B, Volume 61, Issue 1, May 1994, Pages 88-91

[3] Yoshitake Matsumoto, Sonoko Moriyama, Hiroshi Imai, and David Bremner. Matroid enumeration for incidence geometry. Discrete & Computational Geometry, 47(1):17–43, 2012

[4] Dillon Mayhew and Gordon F. Royle. Matroids with nine elements. Journal of Combinatorial Theory, Series B, 98(2):415 – 431, 2008

[5] Marcel Wild: The Asymptotic Number of Binary Codes and Binary Matroids. SIAM J. Discrete Math. 19(3): 691-699 (2005)

$\endgroup$
3
$\begingroup$

This is actually implemented (as well as a host of other features) in the latest version of Sage. This is the culmination of 2 and a half years of hard work by Stefan van Zwam and Rudi Pendavingh, together with help from Michael Welsh and Gordon Royle. See this page from the Matroid Union Blog to get started. For your particular question, it is easy to construct $U_{2,4}$ via the Sage command

Sage: N = matroids.Uniform(2,4)

To test if an input matroid M has an N-minor you can run the Sage command

Sage: M.has_minor(N)

As you can see, Stefan and Rudi have worked hard to make the syntax easy to understand. Of course this is a very generic approach, so I am not sure how optimal it will be. Feel free to contact Stefan if you have any questions, or (better yet) want to develop for the package (Sage is open-source).

$\endgroup$
  • 1
    $\begingroup$ In Sage you should use is_binary() rather than the general purpose minor routine. It uses an effective, though not asymptotically the most efficient method due to Geelen and Gerards and implemented by Rudi Pendavingh. $\endgroup$ – Gordon Royle Nov 18 '13 at 13:08
  • $\begingroup$ Thanks Gordon. Nice to hear this has been implemented. I guess this is probably the best routine available without having to reinvent the wheel. $\endgroup$ – Tony Huynh Nov 18 '13 at 14:41
  • 2
    $\begingroup$ Ack, except that I was talking through my chapeau. After a long day of marking exam scripts, I confused "binary" and "graphic" so in fact, the "is_graphic" routine is the one that is implemented and not the "is_binary" (although of course it should be). Sorry for that, and reminder to self never to post in the evening. $\endgroup$ – Gordon Royle Nov 19 '13 at 2:05
  • $\begingroup$ I did implement a M.has_line_minor(k) routine in Sage, which essentially enumerates the flats F of rank r-2 to see if the simplification of M/F has k or more elements. So M.has_line_minor(4) will test if M is nonbinary. This comes quite close to approach b) suggested by Jayant Apte above. $\endgroup$ – Rudi Pendavingh Feb 23 '14 at 9:53
  • $\begingroup$ Also, the single-element extension approach is generously supported in Sage right now. If M is a BinaryMatroid in sage, then M.linear_extensions(..) will generate the binary matroids extending M. The isomorphism test for binary matroids is fairly efficient as well. $\endgroup$ – Rudi Pendavingh Feb 23 '14 at 9:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.