What is the largest number of k-element subsets of a given n-element set S such that…

Question

Given a set S of n elements. What is the largest number of k-element subsets of S such that every pair of these subsets has at most one common element?

Answer 1

You're asking what the number of blocks of a maximum packing is.

An ordered pair $(S, \mathcal{B})$ of a finite set $S$ of cardinality $\vert S \vert = v$ and a finite set $\mathcal{B}$ of $k$-subsets of $S$ is a packing of order $v$ and block size $k$ if any pair of elements of $S$ appears in at most one element of $\mathcal{B}$. The elements of $S$ are the points, and those of $\mathcal{B}$ are the blocks.

A maximum packing of order $v$ and block size $k$ is a packing with the most blocks among all packings of block size $k$ on $v$ elements. What you're asking is what the cardinality $\vert \mathcal{B} \vert$ of the block set of a maximum packing.

A corollary of the Johnson bound (which is proved by S.M. Johnson in A new upper bound for error-correcting codes, IRE Trans. IT-8 (1962) 203–207) states that a packing of order $v$ and block size $k$ has at most

$$\left\lfloor\frac{n}{k}\middle\lfloor\frac{n-1}{k-1}\middle\rfloor\right\rfloor$$

blocks. As Butch mentioned, a Steiner $2$-design attains the upper bound with equality. The existence of such perfectly packed designs is solved in the affirmative in the asymptotic sense:

There exists a constant $v_k$ that depends only on $k$ such that for all $v > v_k$ such that $\frac{{{n}\choose{2}}}{{{k}\choose{2}}}$ is an integer, there exists a Steiner $2$-design of order $v$ and block size $k$.

The above result is a corollary of Wilson's Fundamental Existence Theorem. So the problem is when a maximum packing is not a Steiner $2$-design because $\frac{{{n}\choose{2}}}{{{k}\choose{2}}}$ isn't an integer (and, of course, finitely many cases of small order $v$ for each $k$). For small $k$, the necessary and sufficient conditions on $v$ are known, e.g., for $k=3$, you can get a Steiner $2$-design whenever the integer condition is met. A comprehensive list of results like this can be found in the Handbook of Combinatorial Designs. A quick summary is that for $k \leq 5$, the integer condition is also sufficient. But for larger $k$, there are definite exceptions for the existence of Steiner $2$-designs even if the order $v$ meets the necessary condition.

So, the tougher problem is the packing case where a maximum one does miss some pairs. Some cases are easy to solve. For instance, take a Steiner $2$-design $(S, \mathcal{B})$ of order $v$ of block size $3$. In this case, we have $v \equiv 1, 3 \pmod{6}$ because of the integer condition. You delete one point, say $\infty$, from the point set $S$ and throw away all $2$-subsets resulted in from those blocks containing $\infty$. Then you get a packing on the point set $S\setminus\{\infty\}$ with triples $\mathcal{B}'$ in which exactly $\frac{v-1}{2}$ pairs don't appear anywhere. You can show that it is a maximum packing. So the case $v \equiv 0, 2 \pmod{6}$ is also completely solved. The remaining case $v \equiv 5 \pmod{6}$ is not as simple. But as Butch mentioned, we have the answer: it's one step behind the Johnson bound.

The best results for the general case is given in the paper I linked to in this answer to a recent MO question here:

Uniform 4-hypergraph avoiding 2-cycles

In fact, the question there is, if you translate it into the language of design theory, asking if a maximum packing can get $c\cdot v^2$ blocks for some positive constant $c$ when $v$ approaches infinity.

The result given in the paper is that for sufficiently large orders, you can always attain the Johnson bound minus some constant. The history of this problem and its generalizations are also given in the paper.