Browse Prior Art Database

A Note on Common Systems of Distinct Representatives

IP.com Disclosure Number: IPCOM000128288D
Original Publication Date: 1977-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 6 page(s) / 17K

Publishing Venue

Software Patent Institute

Related People

Robert R. Korfhage: AUTHOR [+3]

Abstract

For the case of two collections of n sets, each partitioning the base set, a necessary and . sufficient condition for the existence of a common system of distinct representatives is given. It is shown that as n increases, the tiumber of cases to be tested for this condition is an arbitrarily small fraction of the number needed for the classical Ford and Fulkerson condition. Let {S S } and fS be collections of sets, each [Equation ommitted] ' S2n n collection partitioning the base set U S Let X 1 and X2 denote non-empty j=l subcollections of the two given collections, and let c 1 and e 2 denote the set of elements in X, and X2 respectively, [Equation ommitted] Ford and Fulkerson [1] established that without the partition condition, a necessary and sufficient condition for the existence of a common system of dis-tinct representatives is that [Equation ommitted]

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A Note on Common Systems of Distinct Representatives

Robert R. Korfhage

Department of Computer Science Southern Methodist University Dallas, Texas

September, 1977

Abstract

For the case of two collections of n sets, each partitioning the base set, a necessary and . sufficient condition for the existence of a common system of distinct representatives is given. It is shown that as n increases, the tiumber of cases to be tested for this condition is an arbitrarily small fraction of the number needed for the classical Ford and Fulkerson condition.

Let {S S } and fS be collections of sets, each

(Equation Omitted)

' S2n n collection partitioning the base set U S Let X 1 and X2 denote non-empty j=l subcollections of the two given collections, and let c 1 and e 2 denote the set of elements in X, and X2 respectively,

(Equation Omitted)

Ford and Fulkerson [1] established that without the partition condition, a necessary and sufficient condition for the existence of a common system of dis-tinct representatives is that

(Equation Omitted)

for all possible choices of X I and X 2' It is our purpose to show that if the partition condition holds we need only choose X, and X 1 2 such that

(Equation Omitted)

Furthermore, calling the number of choices to be tested for the Ford and Fulkerson text T(n), and the number of choices for the restricted case R(n)-, we shall show

that

(Equation Omitted)

Throughout the remainder of this paper we assume that the sets in each collection partition the base set.

Theorem 1. If for all choices of X, and X2

Southern Methodist University Page 1 Dec 31, 1977

Page 2 of 6

A Note on Common Systems of Distinct Representatives

(Equation Omitted)

then an SDR exists. Proof. Since (1) holds for all choices of X 1 and

(Equation Omitted)

and

(Equation Omitted)

. Then

(Equation Omitted)

Choose an element of this intersection to represent

(Equation Omitted)

By the partition condition, as j is varied from 1 to n, these intersections are dis-joint. Hence we have specified a common SDR.

Theorem 2. Suppose that X 1 is fixed, and X 2 is an arbitrary subcollection of d sets. If

(Equation Omitted)

(2) then for the same X 1 and any

(Equation Omitted)

(Equation Omitted)

Proof. It suffices to prove the result for X' such that

(Equation Omitted)

over all X 2 such that

(Equation Omitted)

By (2), b > 0. Suppose that for some X' with

(Equation Omitted)

say' 2 2 we

(Equation Omitted)

If b > 1, suppose that two elements are in one of the S 2j$ say

(Equation Omitted)

Southern Methodist University Page 2 Dec 31, 1977

Page 3 of 6

A Note on Common Systems of Distinct Representatives

Letting

(Equation Omitted)

we contradict the

minimality of b. Hence for any b > 1, the elements a 1$ ab are distributed throughout b of the sets S 2j' Without loss of generality, we assume that a

(Equation Omitted)

. Since any d of the sets in

X' contain at least b elements of the intersection in question, b <...