Murota K. Matrices and Matroids for Systems Analysis
Подождите немного. Документ загружается.
292 5. Polynomial Matrix and Valuated Matroid
in addition to deg v = 1 for all v ∈ V
+
, since the general case can be obtained
as a composition of a series of such special cases. Let t
1
,t
2
∈ V
+
denote the
elements of V
+
such that (t
1
,t), (t
2
,t) ∈ A, and for v ∈ V
−
\{t} let ϕ(v)
denote the unique element of V
+
such that (ϕ(v),v) ∈ A.Putx = ϕ(u).
We consider the case where t ∈ B ∩B
, since otherwise the proof is easier.
We have
˜ω(B)=ω(
¯
B + t
k
), ˜ω(B
)=ω(
¯
B
+ t
l
)
with
¯
B = ϕ(B −t)and
¯
B
= ϕ(B
− t) for some k, l ∈{1, 2}.
Case 2(a) [k = l]: Since x = ϕ(u) ∈ (
¯
B + t
k
) \ (
¯
B
+ t
k
), there exist
y ∈
¯
B
\
¯
B such that
ω(
¯
B + t
k
)+ω(
¯
B
+ t
k
) ≤ ω(
¯
B + t
k
− x + y)+ω(
¯
B
+ t
k
+ x − y).
We can take v = ϕ
−1
(y) ∈ B
\ B in (5.32).
Case 2(b) [k = l]: We may assume k =1,l =2and
ω(
¯
B + t
1
) >ω(
¯
B + t
2
),ω(
¯
B
+ t
2
) >ω(
¯
B
+ t
1
). (5.34)
Since x = ϕ(u) ∈ (
¯
B + t
1
) \ (
¯
B
+ t
2
), there exists y ∈ (
¯
B
+ t
2
) \ (
¯
B + t
1
)
with
ω(
¯
B + t
1
)+ω(
¯
B
+ t
2
) ≤ ω(
¯
B + t
1
− x + y)+ω(
¯
B
+ t
2
+ x − y). (5.35)
If y = t
2
, RHS of (5.35) ≤ RHS of (5.32) with v = ϕ
−1
(y) ∈ B
\ B
(RHS=right hand side). If y = t
2
,
RHS of (5.35) = ω(
¯
B − x + t
1
+ t
2
)+ω(
¯
B
+ x)
≤ ω(
¯
B − x + t
2
+ z)+ω(
¯
B
+ x + t
1
− z)
for some z ∈ (
¯
B
+ x) \(
¯
B −x + t
1
+ t
2
). By (5.34) we must have z = x,and
therefore z ∈
¯
B
\
¯
B. Then (5.32) is satisfied with v = ϕ
−1
(z).
Remark 5.2.19. The present proof of Theorem 5.2.18 is elementary, as com-
pared with the original proof by Murota [227] and an alternative proof by
Shioura [297]. The present proof, if specialized to ω =0andw = 0, serves also
as an alternative proof of Theorem 2.3.38, showing that
˜
B satisfies (BM
±
).
2
Theorem 5.2.18 has important consequences. Let M
1
=(V,B
1
,ω
1
)and
M
2
=(V,B
2
,ω
2
) be valuated matroids. Denote by (V, B
1
∨B
2
) the union of
the underlying matroids (V,B
1
) and (V,B
2
), where, by definition, B
1
∨B
2
is the family of the maximal elements of {X
1
∪ X
2
| X
1
∈B
1
,X
2
∈B
2
}
(cf. §2.3.6). Define ω
1
∨ ω
2
: B
1
∨B
2
→ R by
(ω
1
∨ ω
2
)(X) = max{ω
1
(X
1
)+ω
2
(X
2
) | X
1
∪ X
2
= X, X
1
∈B
1
,X
2
∈B
2
},
X ∈B
1
∨B
2
.
We call M
1
∨ M
2
=(V, B
1
∨B
2
,ω
1
∨ ω
2
)theunion of M
1
and M
2
on the
basis of the following fact (Murota [227]).
5.2 Valuated Matroid 293
Theorem 5.2.20. M
1
∨ M
2
=(V,B
1
∨B
2
,ω
1
∨ ω
2
) is a valuated matroid.
Proof.LetV
1
and V
2
be disjoint copies of V ,andU be a set with |U| =
r
1
+ r
2
− r
12
, where r
1
, r
2
and r
12
denote the ranks of (V,B
1
), (V, B
2
)and
(V,B
1
∨B
2
). Consider a bipartite graph G =(V
+
,V
−
; A) with V
+
= V
1
∪V
2
,
V
−
= V ∪ U ,and
A = {(v
1
,v) | v ∈ V }∪{(v
2
,v) | v ∈ V }∪{(v
2
,u) | v ∈ V, u ∈ U},
where v
i
∈ V
i
is the copy of v ∈ V (i =1, 2). Let ˜ω be the valuation induced
on V
−
from the valuation ω on V
+
defined by ω(X
1
∪X
2
)=ω
1
(X
1
)+ω
2
(X
2
)
(X
i
∈B
i
(i =1, 2)) and weight function w =0onA. Then (ω
1
∨ ω
2
)(X)=
˜ω(X ∪ U)forX ⊆ V .
By showing the following lemma using Theorem 5.2.18 we can complete
the proof of Theorem 5.2.6 concerning truncation. For a valuated matroid
M =(V, B,ω)andk ≤ r =rankM, define B
k
⊆ 2
V
by (5.17) and ω
k
: B
k
→
R by
ω
k
(I) = max{ω(B) | I ⊆ B ∈B},I∈B
k
.
Lemma 5.2.21. M
k
=(V,B
k
,ω
k
) is a valuated matroid, where k ≤ r.
Proof.LetV
be a copy of V ,andU be a set with |U| = r − k. Consider a
bipartite graph G =(V
+
,V
−
; A) with V
+
= V
, V
−
= V ∪ U ,and
A = {(v
,v) | v ∈ V }∪{(v
,u) | v ∈ V, u ∈ U},
where v
∈ V
is the copy of v ∈ V . Let ˜ω be the valuation induced on V
−
from ω on V
+
( V )andw =0onA. Then ω
k
(I)=˜ω(I ∪ U )forI ⊆ V .
See also Murota [229] for the original proof that does not rely on Theorem
5.2.18.
Just as a matroid can be induced by a bimatroid (Theorem 2.3.57), a
valuated matroid can be induced by a valuated bimatroid, as follows. This
construction appears more general than the induction of a valuated matroid
by a bipartite graph, though the proof shows that it is just a variant thereof.
Theorem 5.2.22. For a valuated bimatroid (S, T, Λ, δ) and a valuated ma-
troid (T,B,ω), assume that
Λ ∗B= {X ⊆ S |∃Y ⊆ T :(X, Y ) ∈ Λ, Y ∈B}
is nonempty. Then (S, Λ ∗B,δ∗ω) with
(δ ∗ ω)(X) = max
Y
{δ(X, Y )+ω(Y ) | (X, Y ) ∈ Λ, Y ∈B},X∈ Λ ∗B
is a valuated matroid.
294 5. Polynomial Matrix and Valuated Matroid
Proof.LetS
be a copy of S,andT
and T
be copies of T . Consider a
bipartite graph G =(V
+
,V
−
; A) with V
+
= S
∪T
∪T
, V
−
= S ∪T ,and
A = {(x
,x) | x ∈ S}∪{(y
,y) | y ∈ T }∪{(y
,y) | y ∈ T },
where x
∈ S
is the copy of x ∈ S,andy
∈ T
[resp. y
∈ T
] is the copy of
y ∈ T . Define ω
:2
S
∪T
∪T
→ R ∪ {−∞} by ω
(X
∪ Y
1
∪ Y
2
)=δ(X, T \
Y
1
)+ω(Y
2
)forX
⊆ S
, Y
1
⊆ T
,andY
2
⊆ T
. Let ˜ω
be the valuation
induced on V
−
from ω
with w =0onA. Then (δ ∗ ω)(X)=˜ω
(X ∪ T )for
X ⊆ S.
Using a similar proof technique we can show that a product operation can
be defined for valuated bimatroids in a manner compatible with the bimatroid
product in Theorem 2.3.53.
Theorem 5.2.23. For two valuated bimatroids (S
i
,T
i
,δ
i
)(i =1, 2) with
T
1
= S
2
, define δ
1
∗ δ
2
:2
S
1
× 2
T
2
→ R ∪ {−∞} by
(δ
1
∗ δ
2
)(X, Z) = max{δ
1
(X, Y )+δ
2
(Y,Z) | Y ⊆ T
1
},X⊆ S
1
,Z ⊆ T
2
.
Then (S
1
,T
2
,δ
1
∗ δ
2
) is a valuated bimatroid.
Proof.LetS
i
be a copy of S
i
,andT
i
be a copy of T
i
(i =1, 2), where T
1
∩S
2
=
∅. Consider a bipartite graph G =(V
+
,V
−
; A) with V
+
= S
1
∪T
1
∪S
2
∪T
2
,
V
−
= S
1
∪ T
1
∪ T
2
,and
A = {(x
,x) | x ∈ S
1
}∪{(y
,y) | y ∈ T
1
}∪{(y
,y) | y ∈ T
1
}∪{(z
,z) | z ∈ T
2
},
where x
∈ S
1
is the copy of x ∈ S
1
, y
∈ T
1
[resp. y
∈ S
2
] is the copy of y ∈
T
1
,andz
∈ T
2
is the copy of z ∈ T
2
. Define ω
:2
S
1
∪T
1
∪S
2
∪T
2
→ R ∪{−∞}
by ω
(X
∪Y
1
∪Y
2
∪Z
)=δ
1
(S
1
\X, Y
1
)+δ
2
(S
2
\Y
2
,Z)forX
⊆ S
1
, Y
1
⊆ T
1
,
Y
2
⊆ S
2
,andZ
⊆ T
2
. Let ˜ω
be the valuation induced on V
−
from ω
with
w =0onA. Then (δ
1
∗ δ
2
)(X, Z)=˜ω
((S
1
\ X) ∪ T
1
∪ Z)forX ⊆ S
1
and
Z ⊆ T
2
.
Theorem 5.2.23 above implies as an immediate corollary that a union op-
eration can be defined for valuated bimatroids compatibly with the bimatroid
union in Theorem 2.3.51. It should be clear that S
1
∩S
2
= ∅ and T
1
∩T
2
= ∅
in general.
Theorem 5.2.24. For two valuated bimatroids (S
i
,T
i
,δ
i
)(i =1, 2), define
δ
1
∨ δ
2
:2
S
1
∪S
2
× 2
T
1
∪T
2
→ R ∪ {−∞} by
(δ
1
∨ δ
2
)(X, Y )
= max{δ
1
(X
1
,Y
1
)+δ
2
(X
2
,Y
2
) | X
1
∪ X
2
= X, Y
1
∪ Y
2
= Y,
X
1
∩ X
2
= ∅,Y
1
∩ Y
2
= ∅},X⊆ S
1
∪ S
2
,Y ⊆ T
1
∪ T
2
.
Then (S
1
∪ S
2
,T
1
∪ T
2
,δ
1
∨ δ
2
) is a valuated bimatroid.
5.2 Valuated Matroid 295
Proof.LetS
i
be a copy of S
i
,andT
i
be a copy of T
i
(i =1, 2), where S
1
∩S
2
=
∅ and T
1
∩T
2
= ∅. Consider a valuated bimatroid (S
1
∪S
2
,T
1
∪T
2
,δ
12
) defined
by δ
12
(X
1
∪X
2
,Y
1
∪Y
2
)=δ
1
(X
1
,Y
1
)+δ
2
(X
2
,Y
2
), where X
i
⊆ S
i
denotes the
copy of X
i
⊆ S
i
and similarly for Y
i
⊆ T
i
. Also consider valuated bimatroids
(S
1
∪S
2
,S
1
∪S
2
,δ
S
) and (T
1
∪T
2
,T
1
∪T
2
,δ
T
), where δ
S
(X, X
1
∪X
2
)isequal
to 0 if X
1
∪ X
2
= X and X
1
∩ X
2
= ∅,andto−∞ otherwise; and similarly,
δ
T
(Y
1
∪ Y
2
,Y) is equal to 0 if Y
1
∪ Y
2
= Y and Y
1
∩ Y
2
= ∅,andto−∞
otherwise. Then we have δ
1
∨δ
2
= δ
S
∗δ
12
∗δ
T
, which is a valuated bimatroid
by Theorem 5.2.23.
5.2.7 Characterizations
The objective of this section is to give other axioms that characterize a val-
uated matroid.
First we consider two seemingly weaker (but actually equivalent) exchange
axioms for ω : B→R or ω :2
V
→ R ∪ {−∞} with B = {B ⊆ V | ω(B) =
−∞}.
(VM
w
)ForB,B
∈Bwith B = B
, there exist u ∈ B \ B
and
v ∈ B
\ B such that B − u + v ∈B, B
+ u − v ∈B,and
ω(B)+ω(B
) ≤ ω(B −u + v)+ω(B
+ u − v),
(VM
loc
) B satisfies (BM
±
), and for B,B
∈Bwith |B \ B
| =2,
there exist u ∈ B \ B
and v ∈ B
\ B such that B − u + v ∈B,
B
+ u − v ∈B,and
ω(B)+ω(B
) ≤ ω(B −u + v)+ω(B
+ u − v).
Note that (VM
w
) is a quantitative generalization of the self-dual exchange
axiom (BM
±w
)of§2.3.4, and (VM
loc
) states a local exchange property.
These exchange axioms are in fact equivalent as follows (Dress–Wenzel
[56], Murota [228]).
Theorem 5.2.25. Forafunctionω :2
V
→ R ∪{−∞}, the three conditions
(VM), (VM
w
),and(VM
loc
) are equivalent, where B = {B ⊆ V | ω(B) =
−∞}.
Proof. Since (VM
w
) ⇒ (BM
±w
) and also (BM
±w
) ⇔ (BM
±
) by Theorem
2.3.14, we see (VM
w
) ⇒ (VM
loc
), whereas (VM) ⇒ (VM
w
) is obvious since
B \ B
= ∅ for distinct B,B
∈B.Toprove(VM
loc
) ⇒ (VM) we assume
(VM
loc
). For p : V → R we abbreviate ω[p] of (5.16) to ω
p
, and define
ω
p
(B,u, v)=ω
p
(B − u + v) − ω
p
(B)(B ∈B),
consistently with ω(B,u,v) of (5.21), where ω
p
(B,u, v)=−∞if B−u+v ∈B.
For B,B
∈Band u ∈ B \ B
, v ∈ B
\ B,wehave
296 5. Polynomial Matrix and Valuated Matroid
ω(B,u,v)+ω(B
,v,u)=ω
p
(B,u, v)+ω
p
(B
,v,u). (5.36)
If B ∈B, B \ B
= {u
0
,u
1
}, B
\ B = {v
0
,v
1
} (with u
0
= u
1
, v
0
= v
1
),
(VM
loc
) implies
ω
p
(B
) − ω
p
(B) ≤ max(ω
p
(B,u
0
,v
0
)+ω
p
(B,u
1
,v
1
),
ω
p
(B,u
0
,v
1
)+ω
p
(B,u
1
,v
0
)). (5.37)
Define
D = {(B,B
) | B,B
∈B, ∃u
∗
∈ B \ B
, ∀v ∈ B
\ B :
ω(B)+ω(B
) >ω(B − u
∗
+ v)+ω(B
+ u
∗
− v)},
which denotes the set of pairs (B,B
) for which the exchangeability in (VM)
fails. We want to show D = ∅.
Suppose, to the contrary, that D = ∅, and take (B, B
) ∈Dsuch that
|B
\B| is minimum and let u
∗
∈ B \B
be as in the definition of D.Wehave
|B
\ B| > 2. Define p : V → R by
p(v)=
⎧
⎨
⎩
−ω(B,u
∗
,v)(v ∈ B
\ B, B − u
∗
+ v ∈B)
ω(B
,v,u
∗
)+ε (v ∈ B
\ B, B − u
∗
+ v ∈B,B
+ u
∗
− v ∈B)
0 (otherwise)
with some ε>0 and consider ω
p
.
Claim 1:
ω
p
(B,u
∗
,v)=0 ifv ∈ B
\ B, B − u
∗
+ v ∈B, (5.38)
ω
p
(B
,v,u
∗
) < 0forv ∈ B
\ B. (5.39)
The inequality (5.39) can be shown as follows. If B − u
∗
+ v ∈B,wehave
ω
p
(B,u
∗
,v) = 0 by (5.38) and
ω
p
(B,u
∗
,v)+ω
p
(B
,v,u
∗
)=ω(B,u
∗
,v)+ω(B
,v,u
∗
) < 0
by (5.36) and the definition of u
∗
. Otherwise we have ω
p
(B
,v,u
∗
)=−ε or
−∞ according to whether B
+ u
∗
− v ∈Bor not.
Claim 2: There exist u
0
∈ B \ B
and v
0
∈ B
\ B such that u
0
= u
∗
,
B
+ u
0
− v
0
∈B,and
ω
p
(B
,v
0
,u
0
) ≥ ω
p
(B
,v,u
0
)(v ∈ B
\ B). (5.40)
Since |B \ B
| > 2, there exists u
0
∈ B \ B
distinct from u
∗
.By(BM
±
)we
have B
+ u
0
− v
0
∈Bfor some v
0
∈ B
\ B. We can further assume (5.40)
by redefining v
0
to be the element v ∈ B
\ B that maximizes ω
p
(B
,v,u
0
).
Claim 3: (B, B
) ∈Dwith B
= B
+ u
0
− v
0
.
5.2 Valuated Matroid 297
To prove this it suffices to show
ω
p
(B,u
∗
,v)+ω
p
(B
,v,u
∗
) < 0(v ∈ B
\ B).
We may restrict ourselves to v with B −u
∗
+ v ∈B, since otherwise the first
term ω
p
(B,u
∗
,v) is equal to −∞.Forsuchv the first term is equal to zero
by (5.38). For the second term it follows from (5.37), (5.39), and (5.40) that
ω
p
(B
,v,u
∗
)
= ω
p
(B
+ {u
0
,u
∗
}−{v
0
,v}) − ω
p
(B
+ u
0
− v
0
)
≤ max [ω
p
(B
,v
0
,u
0
)+ω
p
(B
,v,u
∗
),ω
p
(B
,v,u
0
)+ω
p
(B
,v
0
,u
∗
)]
−ω
p
(B
,v
0
,u
0
)
< max [ω
p
(B
,v
0
,u
0
),ω
p
(B
,v,u
0
)] − ω
p
(B
,v
0
,u
0
)=0.
Since |B
\B| = |B
\B|−1, Claim 3 contradicts our choice of (B,B
) ∈D.
Therefore we conclude D = ∅.
It is also mentioned that another exchange axiom
(VM
d
)ForB, B
∈Band u ∈ B \ B
, there exist v ∈ B
\ B and
u
∈ B \ B
such that B −u + v ∈B, B
+ u
− v ∈B,and
ω(B)+ω(B
) ≤ ω(B −u + v)+ω(B
+ u
− v)
is known to be equivalent to (VM) (see Murota [226]) .
A valuated matroid can be characterized as a family of matroids. For
p : V → R we define
B
p
= {B ∈B|ω[p](B) ≥ ω[p](B
)(∀B
∈B)},
which denotes the set of the maximizers of ω[p] (see (5.16) for the notation
ω[p]). It is immediate from (VM) that B
p
forms the basis family of a matroid,
whereas Murota [227, 228] points out that the converse is also true.
Theorem 5.2.26. Let (V,B) be a matroid. A function ω : B→R is a
valuation of (V, B) if and only if for any p : V → R the family B
p
of the
maximizers of ω[p] forms the basis family of a matroid. If ω is integer-valued,
we may restrict p to be integer-valued in the “if” part.
Proof. We abbreviate ω[p]toω
p
.
The “only if” part is easy to see. Take B,B
∈B
p
and u ∈ B \ B
. Since
ω
p
satisfies (VM), there exists v ∈ B
\ B such that
2 max ω
p
= ω
p
(B)+ω
p
(B
) ≤ ω
p
(B − u + v)+ω
p
(B
+ u − v),
which shows B −u + v ∈B
p
and B
+u −v ∈B
p
.Thatis,B
p
satisfies (BM
±
).
For the “if” part it suffices, by Theorem 5.2.25, to show the local exchange
axiom (VM
loc
). Under the assumption of (BM
±
)forB,(VM
loc
) is equivalent
to the following claim.
298 5. Polynomial Matrix and Valuated Matroid
Claim 1: If B, B
∈B, B \ B
= {u
0
,u
1
}, B
\ B = {v
0
,v
1
} (with u
0
= u
1
,
v
0
= v
1
), then
ω(B
) − ω(B) ≤ max(ω
00
+ ω
11
,ω
01
+ ω
10
), (5.41)
where ω
ij
= ω(B,u
i
,v
j
)fori, j =0, 1.
This claim can be proven as follows. Denote by γ and μ the left hand side
and the right hand side of (5.41), respectively. We consider a bipartite graph
G =({u
0
,u
1
}, {v
0
,v
1
}; E) with E = {(u
i
,v
j
) | B − u
i
+ v
j
∈B}. The graph
G has a perfect matching (of size 2) by (BM
±
). In addition we associate ω
ij
with edge (u
i
,v
j
) as the weight. Then μ is equal to the maximum weight of
a perfect matching in G and, by a variant of Theorem 2.2.36, there exists
ˆp : {u
0
,u
1
,v
0
,v
1
}→R such that
ˆp(u
i
)+ˆp(v
j
) ≥ ω
ij
((u
i
,v
j
) ∈ E),
i=0,1
ˆp(u
i
)+
j=0,1
ˆp(v
j
)=μ.
To show γ ≤ μ, suppose, to the contrary, that γ>μ. Then we can modify
ˆp to ¯p : {u
0
,u
1
,v
0
,v
1
}→R such that
¯p(u
i
)+¯p(v
j
) ≥ ω
ij
((u
i
,v
j
) ∈ E),
i=0,1
¯p(u
i
)+
j=0,1
¯p(v
j
)=γ.
Using ¯p we define p : V → R by
p(v)=
⎧
⎪
⎪
⎨
⎪
⎪
⎩
+¯p(v)(v ∈ B \ B
)
−¯p(v)(v ∈ B
\ B)
+M (v ∈ B ∩ B
)
−M (v ∈ V \ (B
∪ B))
where M>0 is a sufficiently large number.
For this p we have {B, B
}⊆B
p
, i.e., ω
p
(B)=ω
p
(B
) ≥ ω
p
(B
)(∀B
∈
B). In fact, this is immediate from the following relations:
ω
p
(B
) − ω
p
(B)=[ω(B
) − ω(B)] −
i=0,1
¯p(u
i
) −
j=0,1
¯p(v
j
)=0,
ω
p
(B − u
i
+ v
j
) − ω
p
(B)
=[ω(B − u
i
+ v
j
) − ω(B)] + [p(B − u
i
+ v
j
) − p(B)]
= ω
ij
− ¯p(u
i
) − ¯p(v
j
) ≤ 0,
ω
p
(B
) − ω
p
(B) ≤ ω(B
) − ω(B)+
i=0,1
|¯p(u
i
)| +
j=0,1
|¯p(v
j
)|−M ≤ 0
unless B ∩ B
⊆ B
⊆ B ∪ B
.
Since B,B
∈B
p
and (V,B
p
) satisfies (BM
±
) by the assumption, there exists
j ∈{0, 1} such that ω
p
(B − u
0
+ v
j
)=ω
p
(B
+ u
0
− v
j
)=ω
p
(B). Putting
k =1− j and noting B
+ u
0
− v
j
= B − u
1
+ v
k
, we obtain
5.2 Valuated Matroid 299
0=ω
p
(B − u
0
+ v
j
)+ω
p
(B − u
1
+ v
k
) − 2ω
p
(B)
= ω(B − u
0
+ v
j
)+ω(B − u
1
+ v
k
) − 2ω(B) −
i=0,1
¯p(u
i
) −
j=0,1
¯p(v
j
)
= ω
0j
+ ω
1k
− γ ≤ μ − γ,
a contradiction to γ>μ. This completes the proof of the claim.
If ω is integer-valued, we have ω
ij
∈ Z for all (i, j), and consequently, ˆp,
¯p and p can be chosen to be integer-valued.
Finally we consider “level sets” of ω : B→R defined by
L(ω, α)={B ∈B|ω(B) ≥ α} (5.42)
for α ∈ R. A level set of a matroid valuation does not necessarily form the
basis family of a matroid, as the following example shows.
Example 5.2.27. Consider a valuated matroid (V,B,ω) defined by V =
{1, 2, 3, 4}, B = {{1, 2}, {2, 3}, {3, 4}, {4, 1}},andω({1, 2})=1,ω({2, 3})=
2, ω({3, 4})=1,ω({4,
1}) = 0. Then L(ω, 1) = {{1, 2}, {2, 3}, {3, 4}} does
not satisfy the simultaneous basis exchange property (BM
±
). 2
It follows from (VM), however, that the family L = L(ω, α) satisfies the
following (weaker) exchange properties:
(BL) For B, B
∈Land for u ∈ B \B
, there exists v ∈ B
\B such
that B − u + v ∈Lor B
+ u − v ∈L,
(BL
w
) For distinct B,B
∈L, there exist u ∈ B \B
and v ∈ B
\B
such that B −u + v ∈Lor B
+ u − v ∈L.
To see this, observe that the inequality (5.14) for (VM) implies:
ω(B) ≥ α, ω(B
) ≥ α =⇒ max{ω(B − u + v),ω(B
+ u − v)}≥α.
For L⊆2
V
in general, it holds obviously that (BM
±
) ⇒ (BL) ⇒
(BL
w
), but the converse is not true. In fact, “(BM
±
) ⇐ (BL)” is demon-
strated by L = {{1, 2}, {2, 3}, {3, 4}} and “(BL) ⇐ (BL
w
)” is by L =
{{1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5, 6}}.
The following theorem of Shioura [299] characterizes a valuated matroid
in terms of the level sets of ω[p]. See (5.16) for the notation ω[p].
Theorem 5.2.28. Let (V, B) be a matroid. For a function ω : B→R, the
following three conditions are equivalent:
(i) ω : B→R is a valuation of (V,B),
(ii) For any p : V → R and for any α ∈ R, L(ω[p],α) satisfies (BL),
(iii) For any p : V → R and for any α
∈ R, L(ω[p],α) satisfies (BL
w
).
300 5. Polynomial Matrix and Valuated Matroid
Proof. [(i) ⇒ (ii) ⇒ (iii)] If ω is a valuation, so is ω[p]. Hence the claim
follows from the observations above.
[(iii) ⇒ (i)] By Theorem 5.2.25 it suffices to show the local exchange axiom
(VM
loc
). Suppose that {B, B
}⊆B, B \ B
= {u
0
,u
1
}, B
\ B = {v
0
,v
1
}
with u
0
= u
1
, v
0
= v
1
.PutB
ij
= B − u
i
+ v
j
for i, j =0, 1. By (BM
±
)for
B it holds that {B
00
,B
11
}⊆Bor {B
01
,B
10
}⊆B. Hence we may assume
{B
00
,B
11
}⊆Bwithout loss of generality. Define p by
p(u
0
)=[ω(B
) − ω(B)+ω(B
00
) − ω(B
11
)]/2,
p(u
1
)=[ω(B
) − ω(B) − ω(B
00
)+ω(B
11
)]/2+t,
p(v
1
)=t,
p(v)=0 (v ∈ V \{u
0
,u
1
,v
1
}),
so that ω[p](B
)=ω[p](B)andω[p](B
00
)=ω[p](B
11
), where t ∈ R is a
parameter. Since {B,B
}⊆L(ω[p],α)forα = ω[p](B
)=ω[p](B), the proof
of (VM
loc
) is completed if
{B
00
,B
11
}⊆L(ω[p],α)or{B
01
,B
10
}⊆L(ω[p],α) (5.43)
is shown for some t.If{B
01
,B
10
}⊆B, take
t =[ω(B
00
) − ω(B
11
)+ω(B
10
) − ω(B
01
)]/2
so that ω[p](B
01
)=ω[p](B
10
). Then (5.43) follows from (BL
w
). If B
01
∈
B, we can take t large enough for ω[p](B
10
) <α, and then (BL
w
) implies
{B
00
,B
11
}⊆L(ω[p],α). In the remaining case where B
10
∈B, we can take
t small enough for ω[p](B
01
) <α, and then (BL
w
) implies {B
00
,B
11
}⊆
L(ω[p],α).
5.2.8 Further Exchange Properties
We shall establish a number of lemmas concerning basis exchange in a single
valuated matroid. They will play key roles for the valuated matroid intersec-
tion problem, to be explained later.
For B ∈Band B
⊆ V we consider the exchangeability graph G(B,B
)
introduced in §2.3.4. G(B, B
)=(B\B
,B
\B; A) is a bipartite graph having
(B \ B
,B
\ B) as the vertex bipartition and
A = {(u, v) | u ∈ B \ B
,v ∈ B
\ B, B − u + v ∈B} (5.44)
as the arc set. The key properties of the exchangeability in a matroid have
been formulated as the perfect-matching lemma (Lemma 2.3.16) and the
unique-matching lemma (Lemma 2.3.18).
To capture the exchangeability with valuations, we need quantitative ex-
tensions of the perfect-matching lemma and the unique-matching lemma. To
5.2 Valuated Matroid 301
this end we attach the exchange gain ω(B,u,v) of (5.21) to each arc (u, v)
as “arc weight,” and denote by 6ω(B, B
) the maximum weight of a perfect
matching in G(B, B
) with respect to the arc weight ω(B,u, v), i.e.,
6ω(B, B
) = max{
(u,v)∈M
ω(B,u,v) | M: perfect matching in G(B,B
)}.
(5.45)
The perfect-matching lemma is generalized as follows (Murota [224]).
Lemma 5.2.29 (Upper-bound lemma). For B, B
∈B,
ω(B
) ≤ ω(B)+6ω(B,B
). (5.46)
Proof. For any u
1
∈ B \ B
there exists v
1
∈ B
\ B with
ω(B)+ω(B
) ≤ ω(B −u
1
+ v
1
)+ω(B
+ u
1
− v
1
),
which can be rewritten as
ω(B
) ≤ ω(B, u
1
,v
1
)+ω(B
2
)
with B
2
= B
+ u
1
−v
1
. By the same argument applied to (B,B
2
) we obtain
ω(B
2
) ≤ ω(B, u
2
,v
2
)+ω(B
3
)
for some u
2
∈ (B \B
)−u
1
and v
2
∈ (B
\B)−v
1
, where B
3
= B
2
+u
2
−v
2
=
B
+ {u
1
,u
2
}−{v
1
,v
2
}. Hence
ω(B
) ≤ ω(B
3
)+
2
i=1
ω(B,u
i
,v
i
).
Repeating this process we arrive at
ω(B
) ≤ ω(B)+
m
i=1
ω(B,u
i
,v
i
) ≤ ω(B)+6ω(B,B
),
where m = |B \B
| = |B
\B|, B \B
= {u
1
, ···,u
m
}, B
\B = {v
1
, ···,v
m
}.
Remark 5.2.30. For a trivial valuation ω :2
V
→{0, −∞}, the upper-
bound lemma guarantees 6ω(B, B
) = −∞, which shows the existence of a
perfect matching in G(B,B
). Thus, the perfect-matching lemma is a special
case of the upper-bound lemma. 2
Remark 5.2.31. The upper-bound lemma gives an alternative proof for the
optimality condition given in Theorem 5.2.7. The necessity of (5.22) is ob-
vious. For sufficiency take any B
∈Band consider G(B,B
). The condi-
tion (5.22) is equivalent to all the arcs having nonpositive weights. Hence
6ω(B, B
) ≤ 0. Then the upper-bound lemma implies ω(B
) ≤ ω(B). 2