Regular (2, 2)-systems |
| |
Authors: | Reinhardt Euler |
| |
Affiliation: | (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 = {e1, ,en}, whose elements are orderede1 en. (E,I) is called regular, if the independence of {el, ,elk},l1 < <lk, implies that of {eml, ,emk}, whereml < ··· <mk andl1 m1, ,lk mk. (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 等数据库收录! |
|