On a Mutation Problem for Oriented Matroids

For uniform oriented matroids M with n elements, there is in the realizable case a sharp lower bound Lr(n) for the number mut(M) of mutations of M: Lr(n) = n ≤ mut(M), see Shannon [17]. Finding a sharp lower bound L(n) ≤ mut(M) in the non-realizable case is an open problem for rank d ≥ 4. Las Vergnas [9] conjectured that 1 ≤ L(n). We study in this article the rank 4 case. Richter-Gebert [11] showed thatL (4 k) ≤ 3 k + 1 for k ≥ 2. We confirm Las Vergnas’ conjecture for n < 13. We show that L(7k + c) ≤ 5 k + c for all integersk ≥ 0 and c ≥ 4, and we provide a 17 element example with a mutation free element.