Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Question: I am searching for a non-realizable matroid with few dependencies relative to the number of points. Precisely, I would like to find a non-realizable (over $\mathbb{R}$) oriented matroid $M$ on a set $A\cup B$ such that $A$ is a basis of $M$, and $B$ is independent in $M$. Can there be such an example? I would also be very interested to hear about any known results concerning the spaces of realizations of such oriented matroids.

Motivation and background: There are many known explicit non-realizable oriented matroids. However, all the examples I have found in the literature seem to rely on having a low rank relative to the number of points. For instance, here are depictions of two well-known (minimal) examples of non-realizable oriented matroids, both of rank three on nine points: the non-Pappus pseudo-line arrangement, and its perturbation given by Ringel's uniform oriented matroid. In both cases, the non-realizability amounts to the impossibility of straightening the curved lines.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

I believe you can take one of the low rank examples, such as Ringel's, and simply take the dual. Since Ringel's is on 9 points, with rank 3, the dual is on 9 points with rank 6.

@RicardoAndrade, I wrote some code to test this on a range of oriented matroids. My results are as follows:

ceva:            good =  31; not basis =  4; bad = 0
πάππος:          good =  75; not basis =  9; bad = 0
ringel:          good =  84; not basis =  0; bad = 0
tsukamoto13[+1]: good = 267; not basis = 19; bad = 0
tsukamoto13[0]:  good = 266; not basis = 20; bad = 0
tsukamoto13[-1]: good = 267; not basis = 19; bad = 0
circularsaw3:    good =  35; not basis =  0; bad = 0
Ω14[+1]:         good = 334; not basis = 30; bad = 0
Ω14[0]:          good = 333; not basis = 31; bad = 0
Ω14[-1]:         good = 334; not basis = 30; bad = 0
suvorov14:       good = 331; not basis = 33; bad = 0

For each of the dual oriented matroids, I took each r element subset of the n elements. If they were independent forming your A and the remaining set, your B, was also independent, I counted this as good; if the r element subset were dependent I added to the not basis count. The bad count, always 0, is when the A set was a basis, and the remainder was not independent.

So I conclude that while your observation that while every r element subset for a uniform oriented matroid will satisfy your conditions, the restriction to uniformity is pretty strong and unnecessary.

@Ricardo I am sorry to keep posting up here, but I want an image this time: a rank 3, order 12 OM This one is all bad ... i.e. wheel12: good = 0; not basis = 165; bad = 55 I think my main observation is that my interest is pseudoline stretching, i.e. rank 3 oriented matroids, typically 'interesting' ones. This wheel is not very interesting for me. Whenever a lot of pseudolines meet at a single point, then the dual of the rank 3 oriented matroid will tend to have small dependent sets, and so not have the property you are interested in. But the oriented matroids of interest to me, are rank 3, and typically at each vertex have only two or three lines, maybe four meeting, so that every convector has at least n-4 elements, and all sets of size 3 are independent (in the dual), so that your property is trivial for any basis of the dual. In summary I think the fact that the bad column is always 0 is just an artifact of my interest versus yours.

share|improve this answer
    
Dear @Jeremy: Very nice! So if we take any uniform oriented matroid with rank at most half the number of points (and there are lots of these), its dual will be an example as I requested. Then, further taking the direct sum with a free oriented matroid will give examples with arbitrarily high rank. Thank you very much, Jeremy. Welcome to MathOverflow! –  Ricardo Andrade Aug 24 '13 at 21:04
    
Thank you so much for the additional material, @Jeremy. That is very interesting, and quite unexpected to me! Do you happen to know or conjecture of a simple condition (more general than uniformity) which guarantees that every basis of the dual matroid is "good" in the sense you describe above? –  Ricardo Andrade Aug 25 '13 at 10:35
    
There is absolutely no need to apologize when you keep making your answer better. Thank you for clarifying the origin of the computational results you show in your answer. –  Ricardo Andrade Aug 28 '13 at 2:14
1  
The wheel picture shows a co-loop, being the line at infinity in the pseudoline diagram; dropping that line with all the pseudolines intersecting at a single point, gives two co-parallel-vectors. These are the only possible linear dependencies in the dual of a rank 3 oriented matroid. For a non-trivial example, take the dual of an arbitrary rank 3 matrix; then form another element in the dual matrix as a linear combination of two of the existing elements. Then take the set B to include that linear combination. The oriented matroid then has a basis A and a dependent B. Its dual has rank 4. –  Jeremy Carroll Aug 28 '13 at 15:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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