Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: The number of overlapping subsets of a set
Replies: 2   Last Post: Jun 16, 1996 4:00 PM

 Messages: [ Previous | Next ]
 Yehouda Harpaz Posts: 2 Registered: 12/12/04
The number of overlapping subsets of a set
Posted: Jun 16, 1996 9:29 AM

Does anybody know how to compute the number of overlapping subsets in a set?
i.e. given a set of N items, how many sets of K items, such that the overlap
between each pair of sets is of L items or less.

for example, for N = 6 , K = 3, L = 1, there are four subsets, e.g.
(2 4 5) (1 3 5) (6 3 4) (6 1 2)

Realy, I want an analytic approximation for N >> K >> L >> 1,
though even a solution for L = 1 will be nice. The underlying
question is what the amount of data a network can hold, assuming
each item is a set of K nodes, and allowing overlap of L nodes.

Thanks

Yehouda Harpaz
http://www.azc.com/client/yeh/

Date Subject Author
6/16/96 Yehouda Harpaz
6/16/96 Greg Kuperberg