1.2. EXTENSIONS. LEXICOGRAPHIC EXTENSIONS. 9
if the circuit is of the form ({p},B) for some B C A. If this is the case we have
two possibilities: if B ^ A, then p is in the convex hull of a proper face of A, and
thus not in relintM(A). If B = A, then the orthogonality between circuits and
covectors implies, with part (i), that p G relintM(A).
1.2. Extensions . Lexicographic extensions .
Let M and M' be two oriented matroids on sets E and E'. H E C E', and
every circuit of M. is a circuit in M1 then .M' is an extension of .A/f. Equivalently,
M! is an extension of Mi if A4 is a restriction of M! by deleting some elements.
We will only consider extensions which do not increase the rank, i.e., for which
rank(Ai) = rank{Ai'). If E' \ E {p} has one element we say that M1 is a
one-element extension, and use the notation Ai U p for .A/f. This will be usually
our case.
Let Ai Up be a one-element extension of Ai. For every cocircuit C = ( C + , C~)
of A4, exactly one of ( C + U {p}, C " ) , (C+, C " U {p}) and ( C + , C " ) is a cocircuit
of Ai. In other words, there is a unique way to extend each cocircuit of Ai into
a cocircuit of M. U p. This means that there is no ambiguity in considering C as
a cocircuit in Ai U p, and we can write C(p) + 1 , —1 and 0, respectively. The
function assigning to each cocircuit of Ai its value C(p) G { 1, 0, +1 } on the new
element p is called the signature of the extension AiU p.
Not every map from the set of cocircuits of M. to { —1, 0, +1 } is the signature
function of an extension. Also, not every cocircuit of an extension AA U p is the
extension of a cocircuit of A\. However, it is true that a valid signature function
on the cocircuits of At uniquely determines the extension. More information on
this can be found in [11, Section 7.1]. In particular, the way to obtain all the
cocircuits of At U p from the cocircuits of A\ and the signature function of Ai U p
is in Proposition 7.1.4. The conditions that a signature function has to satisfy to
be valid are in Theorem 7.1.8, which we reproduce below. Both results come from
the paper [22] by Las Vergnas.
L E M MA 1.3 (Las Vergnas). Let AA be an oriented matroid on a ground set E,
andC* its set of cocircuits. Let a : C* —• {+, —, 0} be a cocircuit signature satisfying
a(—C) = —a(C) for every C G C*. Then, the following conditions are equivalent:
(a) a is the cocircuit signature function of a single-element extension of Ai.
(b) For every subset A C E of corank 2, a restricted to the cocircuits not
intersecting A is the cocircuit signature function of an extension of Ai/A.
I.e., a defines a single-element extension on every corank 2 contraction.
(c) .M has no minor of rank 2 on three elements on which a induces one
of the three forbidden subconfigurations displayed in Figure 1.1. (The
figure should be read as follows: the three lines represent the complement
of cocircuits, i.e. flats of rank 1 of Ai. A plus or minus sign on one
side of a flat mean that p lies in this or the other part of the cocircuit,
respectively. A zero means that p lies on the flat).
D E F I N I T I ON 1.4. Let Ai Up be a one-element extension of an oriented matroid
Ai of rank r on a set E. We say that the extension is interior if p G COTIVMUP(E).
We say that the extension is in general position iiC(p) ^ 0, for every cocircuit C of
Ai; equivalently, if the support of every circuit of .M Up containing p is a spanning
subset.
Previous Page Next Page