Regular (2, 2)-systems |
| |
Authors: | Reinhardt Euler |
| |
Institution: | (1) Mathematisches Institut, Universität zu Köln, Weyertal 86, D-5 Köln 41, West Germany |
| |
Abstract: | Let (E,I) be an independence system over the finite setE = {e
1, ,e
n
}, whose elements are orderede
1 e
n
. (E,I) is called regular, if the independence of {e
l
, ,e
l
k
},l
1 < <l
k
, implies that of {e
m
l
, ,e
m
k
}, wherem
l
< ··· <m
k
andl
1 m
1, ,l
k
m
k
. (E,I) is called a 2-system, if for anyI I,e E I the setI {e } contains at most 2 distinct circuitsC, C I and the number 2 is minimal with respect to this property. If, in addition, for any two independent setsI andJ the family (C J, C
C
(J, I)), whereC(J, I) denotes {C C: e J I C
{e}}, can be partitioned into 2 subfamilies each of which possesses a transversal, then (E,I) is called a (2, 2)-system. In this paper we characterize regular 2-systems and we show that the classes of regular 2-systems resp. regular (2, 2)-systems are identical. |
| |
Keywords: | Independence System Matroid Regularity Knapsack Problem |
本文献已被 SpringerLink 等数据库收录! |
|