Maximum number of subsets of the same size intersecting in at most one point

Question

Let 1 < m < n. What is the maximum size of a family F of subsets of [n], all having size m, for which any two distinct sets A e B in F intersect in at most one point? If there is no exact formula, is there any known lower bound to this maximum size?

Answer 1

So this is not exactly an answer, but too long for a comment.

This is a question in extremal set theory, which is mostly concerned with determining the maximum number of sets, often of equal size, that can be chosen while satisfying certain intersection properties.

For example, the famous Erdős-Ko-Rado theorem explains how to choose the maximum number of $k$-subsets from a fixed $n$-set with the property that no two of the subsets are disjoint.

One of the leading researchers in this area is Peter Frankl, who has written a number of surveys such as "Invitation to Intersection Problems for Finite Sets", Frankl and Tokushige, Journal of Combinatorial Theory Series A, 2016. (I could freely read the PDF for this, but I might be silently logged in to some university library system that grants me this access.) This invitation alone is $55$ pages long, which gives an idea of the size of the literature to which one is being invited.

They define a concept called an $L$-system - if $L$ is a set of integers, then an $(n,k,L)$ system is a set of $k$-subsets of an $n$-set where the size of the intersection of any pair of distinct $k$-subsets lies in $L$.

So your case is an $(n,k,\{0,1\})$ system, which may well be a case whose exact solution is known. In fact, I am surprised that this hasn't been answered yet, given the incredible breadth and depth of knowledge demonstrated daily by the regular MO question-answerers.

Most attention is focussed on upper bounds, with lower bounds coming from explicit constructions of large $L$-systems. In your case, lower bounds are likely to require several constructions depending on $n$ and $k$.

One construction that is likely to be useful is when there exists a $2$-$(n,k,1)$ design (aka Steiner system). As each pair of points of a Steiner system lies in a unique block, this means that two blocks meet in 0 or 1 points.

For $k=3$, we can consider a graph whose vertices are the $\binom{n}{3}$ triples in a fixed $n$-set, and where two vertices are adjacent if the corresponding triples intersect in $2$ points. Then a $\{0,1\}$-system is an independent set in this graph and so we need to determine the size of a maximum independent set, traditionally denoted $\alpha$.

Some standard counting and eigenvalue stuff tells us that this graph has valency $3(n-3)$ and smallest eigenvalue $-3$. So by Hoffman's bound $$ \alpha \leqslant \frac{\binom{n}{3}\cdot 3}{3(n-3)-3} $$ which simplifies to $\alpha \leqslant n(n-1)/6$.

This is exactly the number of blocks in a Steiner triple system, and so whenever a Steiner triple system exists, there is a precise answer to your question. An STS exists whenever $n \equiv 1, 3 \pmod{6}$.

For other values of $n$ (still with $k=3)$ the eigenvalue bound is not an integer, but fortunately coding theorists are interested in this value and the answer is known for all $n$.

If $n \equiv 5 \bmod{6}$ then the exact maximum size of a set of a $\{0,1\}$-system is $$ \lfloor(n/3) \lfloor(n-1)/2\rfloor -1 $$ and otherwise it is just one more, so $$ \lfloor(n/3) \lfloor(n-1)/2\rfloor. $$

There may be well be similar results for other values of $k$, perhaps even a solution to your entire question.