✦ LIBER ✦

Ordering of the elements of a matroid such that its consecutive w elements are independent

✍ Scribed by Yoji Kajitani; Shuichi Ueno; Hiroshi Miyano

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 480 KB
Volume: 72
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90209-9

No coin nor oath required. For personal study only.

✦ Synopsis

Let M be a matroid on set E, (El = m, with rank function r. For a positive integer w, M is said to be wth L-ind (C-ind) orderable if there exists an ordering 0 of E such that any consecutive (cyclically consecutive) w elements are independent.

It is proved that M is wth L-ind orderable if and only if [m/w] (w -r(E -S))< (S( < [m/w] r(S)

holds for any S c E. While, we conjecture that M is wth C-ind orderable if and only if (S( G r(S) (m/w) holds for any S c E.