Let be an integer greater than . For a positive integer , let . Suppose that there exists a -element set such that
(a) each element of is an -element subset of ;
(b) each pair of elements of shares at most one common element;
and
(c) each element of is contained in exactly two elements of .
Determine the maximum possible value of in terms of .
Solution
Let be an integer greater than 1. For a positive integer , let . Suppose that there exists a -element set such that:
(a) each element of is an -element subset of ;
(b) each pair of elements of shares at most one common element; and
(c) each element of is contained in exactly two elements of .
We aim to determine the maximum possible value of in terms of .
First, we show that . By condition (b), there are at most elements of which are in 2 sets in . However, by condition (c), every element of is in 2 sets in , so , and thus .
Now, to see that is achievable, consider a complete graph . Note that this has edges, so we label the edges with distinct elements of . Let be the family of sets formed by taking each vertex and creating the set of labels of incident edges. Any two sets in have exactly one element in common—the label of the edge between them—so condition (b) is satisfied. Each element of is in exactly two elements of : the two endpoints of the edge with the given label, satisfying condition (c). Condition (a) is also satisfied because every vertex in a has degree , so every element of has elements. Finally, since a has vertices, , as desired.
Thus, the maximum possible value of is: