Another user asked the following question:

"How can I determine the size of the largest collection of $k$-element subsets of an $n$-element set such that each pair of subsets has at most $m$ elements in common?"

Link: Choosing subsets of a set with a specified amount of maximum overlap between them

The top answer to this question gives upper and lower bounds. Has anyone calculated the exact solutions to this problem for small values of the parameters? In particular, I am interested in $k=3$, $m=1$, and various values of $n$. Is there a table of solutions available anywhere?


This is similar to the orchard-planting problem. But you'll want something so that every pair of points defines a three point line. For that, you'll want a finite projective plane.

For example, with 15 points, there is a 35 line projective space.

These can be chosen as the triples from 1-15 with a BitXor sum of 0.

{1,2,3), (1,4,5), (1,6,7), (1,8,9), (1,10,11), (1,12,13),
(1,14,15), (2,4,6), (2,5,7), (2,8,10), (2,9,11), (2,12,14),
(2,13,15), (3,4,7), (3,5,6), (3,8,11), (3,9,10), (3,12,15),
(3,13,14), (4,8,12), (4,9,13), (4,10,14), (4,11,15), (5,8,13),
(5,9,12), (5,10,15), (5,11,14), (6,8,14), (6,9,15), (6,10,12),
(6,11,13), (7,8,15), (7,9,14), (7,10,13), (7,11,12)

With 81 points, you can play the Game of Set. There are 1080 lines.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.