Generating and counting subsets of $\{1,...,100 \}$ with limited pairwise intersection

156 Views Asked by At

Suppose we have the set $X = \{1,...,100\}$, and we want a family $\mathscr{A} \subset \mathcal{P}(X)$ where the following hold:

1.) For all $A \in \mathscr{A}$, $|A| = 50$.

2.) For all $A, B \in \mathscr{A}$, $|A \cap B| \leq 40$.

The question is, how to we generate a family of maximum cardinality, and what is the maximum cardinality?

A simple lower bound, and example of a family, can be created as follows: pick a partition of $\{1,..,100 \}$ where each set in the partition has a cardinality 10. Now form all possible unions of five sets from the partition. This gives a family with ${10}\choose{5}$ $= 252$ different sets of cardinality 50, and the intersection of any two distinct sets has a cardinality of $0, 10, 20, 30$, or $40$.

Thanks all.

2

There are 2 best solutions below

1
On

Each set of 50 numbers is surrounded by a cloud of similar sets, with up to 4 changes. These clouds won't intersect because chosen sets differ by at least 10 changes. The size of each cloud is $1+{50\choose1}^2+{50\choose2}^2+{50\choose3}^3+{50\choose4}^2=53$billion, so at most ${100\choose50}/53$billion, or fewer than 1.9 quintillion sets may be chosen.

0
On

This method gives 900 sets.
With a random search, I found 30 out of the 252 that each differ in two out of the five. For example, if they were all five of the letters from A to K, and ABCDE were included, then ABCDF would not be allowed.
Divide the numbers 1-50 into ten quintets. Use the letters below to pick 30 groups of five quintets, which all differ by two quintets or ten numbers.
Do the same with numbers 51-100.
Pick a set from 1-50 and a set from 51-100.

CFGHI
ABGIJ
ADEGJ
BCDEF
BCEGJ
AEFHI
BCFHJ
ACEFG
ABEFJ
BEFGH
DEFGI
BDEIJ
CDEHJ
BDFHI
ACDEI
BDGHJ
ABCGH
AFGHJ
CDGIJ
ABDEH
ABCFI
EGHIJ
ABCDJ
ADGHI
ABDFG
CEFIJ
ACDFH
BCEHI
ADFIJ
ACHIJ