Given a universe U of cardinal number N find N subsets of cardinal number N/2 that cover U so as to minimize the cardinal number of pairwise intersections between subsets. We assume N is even.
Example:
U = {1, 2, 3, 4, 5, 6}
Subsets:
{1, 2, 3}
{3, 4, 5}
{2, 4, 6}
{4, 5, 6}
{1, 5, 6}
{2, 3, 6}
Pairwise Intersections:
{1, 2, 3} ^ {3, 4, 5} = {3}
{1, 2, 3} ^ {2, 4, 6} = {2}
{1, 2, 3} ^ {4, 5, 6} = {}
{1, 2, 3} ^ {1, 5, 6} = {1}
{1, 2, 3} ^ {2, 3, 6} = {2, 3}
{3, 4, 5} ^ {2, 4, 6} = {4}
{3, 4, 5} ^ {4, 5, 6} = {4, 5}
{3, 4, 5} ^ {1, 5, 6} = {5}
{3, 4, 5} ^ {2, 3, 6} = {3}
{2, 4, 6} ^ {1, 5, 6} = {6}
{2, 4, 6} ^ {2, 3, 6} = {2, 6}
{4, 5, 6} ^ {1, 5, 6} = {5, 6}
{4, 5, 6} ^ {2, 3, 6} = {6}
{1, 5, 6} ^ {2, 3, 6} = {6}
The cardinal number of all pairwise intersections is at most 2. I would like to get a lower value than 2 and in general, find a method to select the subsets so as to minimize the cardinal number of the pairwise intersections.