Regular (2, 2)-systems

Mathematical P r o g r a m m i n g 24 (1982) 269-283 North-Holland Publishing C o m p a n y

REGULAR (2, 2 ) - S Y S T E M S Reinhardt EULER Mathematisches Institut der Universitiit zu K61n, Weyertal 86, D-5 K6ln 41, West Germany Received 27 April 1981 Revised manuscript received 25 N o v e m b e r 1981 L e t (E, 5~) be an independence s y s t e m over the finite set E = {e~. . . . . e~}, w h o s e elements are ordered el-< ""-< e~. (E, 3~) is called regular, if the independence of {et,. . . . . el~}, 11< "" < lk, implies that of {em~,..., emk}, where ml < "" < m k and I1 -< ml . . . . . lk "< rag. (E, .~) is called a 2-system, if for any I E ~, e E E ~ I the set I U {e} contains at m o s t 2 distinct circuits C, C' E q~ and the n u m b e r 2 is minimal with respect to this property. If, in addition, for any two independent sets I and J the family (C --- J, C E cO(j, i)), where ~(J, I) denotes {C E q~:3e E J ~ I C C_ I U {e}}, can be partitioned into 2 subfamilies each of which p o s s e s s e s a transversal, then (E, 3~) is called a (2, 2)-system. In this paper we characterize regular 2 - s y s t e m s and we s h o w that the classes of regular 2-systems resp. regular (2, 2)-systems are identical.

Key words: I n d e p e n d e n c e System, Matroid, Regularity, K n a p s a c k Problem.

1. I n t r o d u c t i o n L e t E = {e~. . . . . e,} be a finite set, w h o s e p o w e r set is d e n o t e d 2 ~ and w h o s e elements are o r d e r e d el-< " ' - < e,. It is u n d e r s t o o d that, w h e n e v e r a set X is m e n t i o n e d , X = {xl .... , Xlx/} with xl < x2 < "'" < XIxI. F o r X, Y C_ E, X = {xl . . . . . xk}, Y = {yt . . . . . Yk}, we define a relation ' F ' b y

X F Y :

holds. Proof. ' ~ ' . L e t

X A Y = {f~, ..., f~},

X ' : = ( X --- Y) U {f, . . . . . f,_,} = {x', . . . . . x IX'l},'

y i := ( y . _ . X ) U {fl . . . . . fi-1}= {Yli . . . . . ylv~l} and I, : = {j ~ { 1 , ... , I X ' l } : Y j' < f i < x } } = { i l

. . . . . jk~}, for i = 1 . . . . . p.

W e c o n s i d e r X i, Y~ and f/ for i E {1 . . . . . p} and (i) assign f~ to itself, if Ii = 0; (ii) assign f~ to YI,, x!j, to YI2, ..., xik_ ~ to YJk ~ and finally xJk~ ~ tofi, ifli#0. Via the a s s i g n m e n t and Definition 1.2 of the regular closure, we obtain X ~uf,~(YiUf~>

fori=l

..... p

yielding X E (Y>. ' ~ ' . Starting with X E (Y> the condition X - ~ Y E ( Y - ~ X > follows analogously to ' ~ ' : B y s u c c e s s i v e deletion of [i f r o m X ~÷1, Y~+~ and a s s i g n m e n t of xi,i to the c o r r e s p o n d i n g Ylt, l = 1. . . . . k~ and i = p . . . . . 1, w h e r e X p÷''.=X, YP+' := Y.

R. Euler/ Regular (2, 2)-systems Theorem

277

3.6. ff (E, # ) is a regular 2-system and B, B' are two bases, then

ItBI- IB'I] 2. T h e n let B'--. B = {g~, ..., gin+k}, k -> 2. Starting o u t - f r o m B and B ' we will c o n s t r u c t a b a s e B r such that [B r[ - ]B'[ and IB ~ Brl = 1. L o o k i n g b a c k at Case 1 this will p r o d u c e a contradiction. Case 2(a). g l < f , , . W e c o n s i d e r B'--.glUfm, which is i n d e p e n d e n t , and enlarge it to a b a s e B ~, which yields:

ml:=[B~.Bt[2. If m~ = 1, we refer to C a s e 1. If m~ > 1 and g] < f ~ , , we c o n t i n u e with B 1 -- g~ U f ~ as a l r e a d y indicated for B ' ~ g l U fro and so on, until for B and B * the following situation Occurs:

ml > 1 and gll > fL,. T h e n we pass to: Case 2(b). W e c o n s i d e r two bases B, B ~ such that B

B l

=

{ffl,

....

t

Bl

--

B

=

.... g,,l+kl},

m,

> 2, kl -> 2,

-

and f~, < g~l. S u p p o s e that B'+l := s ' ---. glt LJ f ~ ¢~ #. T h e n b y T h e o r e m 3.2(iii) l

where b~ := min{b ~ E Bt: b ~ > g]}. H o w e v e r , t~ ~ (B), h e n c e / ~ E #, a contradiction. Thus, B~+iE # and e v e n B~+IE ~ . M o r e o v e r IB ~ B'+'I < IB --- B' I.

Case 2(b) then applies until IB ~ Bvl = l, i.e., Case 1 p r o d u c e s a contradiction. W e add that due to L e m m a 3.5, B ~ B ' ~ ( B ' ~ B) and so our p r o c e d u r e ends at Case 1 after at m o s t m - 1 steps.

R. Euler/ Regular (2, 2)-systems

278

The converse of Theorem 3.6 is not true, even when the assumption is enlarged to all subsets X of E. It suffices to consider (E, N) given by E = {1, 2, 3, 4, 5}, Nr = {11, 2, 5}, {2, 3, 4}} resp. cg = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4, 5}}. What is the value of Theorem 3.6? First of all, the property

lIBI-IB'II ~ 1 for all B, B ' E is not only valid for the bases of (E, N) but also for the bases Nx of a set X C_E: since (E, 5~) is regular, the independence system (X, Nx), ~¢x := {I E N: I C_X}, is regular, too; - since (E, 3~) is a 2-system, (X, 5~x) is a 2-system or a 1-system (matroid). Our intention is to show that any regular 2-system is already a (2, 2)-system. If we suppose that there exists I, J E 5~, @ C_ cg(j, I) such that -

I~l > 2 U~'~ C

J,

(3.7)

then we can form

7:={eEJ~.I:3

CE~

r := ( c U { C ' J )

b'(I

CC_IUe}U(IAJ),

Obviously, I, J E ~. If IJI-< III, then by the 2-system-property

1~1~21J~I1~211 ~ J I

= 2 UCce~ ~.1 ,

a contradiction to (3.7). Hence, 171 > I~1 and by Theorem 3.6 we get:

171 = Irl + 1,

for [ is a base of [ U J.

In addition, 7 is a base of I U J, too. By (3.7) there can be at most one element e in J ~- I such that I U e contains exactly one circuit.

(3.8)

Consequently, if we can show that for any I, J E ~, I a base of I U J, IJl = III+ l, there exist at least two different elements e, e' E J -~ I satisfying (3.8), we have shown that (E, 5~) is a (2, 2)-system. Lemma 3.9. Let (E, ~) be a regular 2-system, L J E ~ such that IJI = III + 1 and I a base of I U J. Then for lm := max{j: j E J -- I}

I U Jm contains exactly one circuit C~(jm).

R. Euler/ Regular (2, 2)-systems

279

Proof. S u p p o s e that there exists a circuit C2(jm)~ Cl(jm) in I U Jm. T h e n let C2(Jm) be that circuit, w h i c h has a gap in I U jm, Cm=max{c:cEC2(jm)}

and

[:={i~I:i>Cm}.

Clearly, Cm > j~ and f o r (I U J) -~ [ we h a v e

(i) [J ~ [] _> ]I ~ I[ + l, since ]I n I] _> [J N [], (ii) C := C2(jm) ~ C~ is a base of (I U J ) -- [, since C U c~ ~ ~ and b y regularity U e ~ 5~ for all e E (I U J ) - ~ r such that e-< Cm. M o r e o v e r , C2(jm) has e x a c t l y one gap in I U Jm at s o m e c, Jm < C < Cm. T h u s

ICl = II--rl-1,

Is-. KI_>II. rl+ 1-- 1~1+2,

a contradiction to T h e o r e m 3.6 applied to the set (I U J ) -- I. L e m m a 3.10. L e t (E, # ) be a regular 2-system, I and J m e m b e r s o f ~ such that IJI =111+1 and I is a base of I U J . Then there exists j E J - - . I , j # j m = max{j : j E J --. I} with the property I U

j

contains exactly one circuit.

Proof. B y L e m m a 3.5, I - ~ J E (J ~. I), if and only if I E (J). Since {j C J : j > jm} is c o n t a i n e d in I A J,

I is a b a s e of I U J, thus I ~ (J} and, c o n s e q u e n t l y , I ~. S ~ ((J ~ I) -~ Jm). NOW let I = { i i . . . . . i1iI}, J - - 0 1 . . . . . Jlsh}, and {1 . . . . . ]I[}, for w h i c h it,--max{/r, Jm}-

T h e n we f o r m r := {i E I : i > ip} and in a n a l o g y to the p r o o f of L e m m a 3.9 we get a c o n t r a d i c t i o n to T h e o r e m 3.6 applied to (I U J ) ~ [ H e n c e , such a C2(jq) c a n n o t

exist, i.e., for all j ~ (J - ~ I ) "-Jm C2(j) = {i~ . . . . . j .... , ip} ~

(3.11) ip< m a x { i , jm}.

R. Euler/ Regular (2, 2)-systems

280

C h a n g e [ to {i ~ I :i > max{i, j~}} and c o n s i d e r (I U J ) ~ r. By (3.11), q~(J ~ I. I -- I ) = cO(j, I). If there exists e E - [ . ~ . J , then C ( j ~ ) - ~ , ~ = m a x { c : c E C ( j ~ ) } , is a base of (I U J ) -- I-, w h i c h is at least t w o e l e m e n t s smaller than J ~ i, in contradiction to T h e o r e m 3.6 applied to (I U J ) ~ [ So r C_ I n J and thus ]J ~ [I = ]I -~ r I + 1 and 1 ~ I is a b a s e of (I U J) --. [. W.l.o.g. we a s s u m e that C(j~) = I U J m and we c o n s i d e r [C(jm)

"N

{ill .....

i,~}1 U {J,1. . . . . . J~k}= : ~"

(I ~. J )

~-- {it,

We observe: ~. J =

. . . . . irk} E "'" -- a, -> 0,

x~ ~ {0, 1} for i = 1 . . . . . n. for n = 3, 4, 5 b y giving the c o r r e s p o n d i n g s y s t e m s q~ of circuits. Besides, they give a c o m p l e t e list of facets, i.e., a g e o m e t r i c description of the solution systems. Their results (enlarged b y the n u m b e r of 2-systems) can be s u m m a r i z e d in Table 1 (see also [16]). Example 4.3. The s y s t e m of solutions of 3x~ + 2x2 + 2x3 + x4 -~-x5 ~ 4 can be given b y q~ = {{1, 2}, {1, 3}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}}. T h e nontrivial facets to describe (E, q~) geometrically are as follows: x ~ + x 2