Number of subsets of the same size and pairwise intersecting in at most one point

238 Views Asked by At

For any set $X$ of size $n \geqslant 4$, what is the maximum cardinality of a family $\mathscr F$ of subsets of $X$ such that $\vert A \vert =4$ for all $A \in \mathscr F$, and $\vert A \cap B \vert \leqslant 1$ for all distinct $A,B \in \mathscr F$? More generally, for any $1 \leqslant m \leqslant n$, what is the maximum size of a family $\mathscr F$ of subsets of $\{1,,\ldots,n\}$ such that $\vert A \vert = m$ for all $A \in \mathscr F$, and $\vert A \cap B \vert \leqslant m$ for all distinct $A,B \in \mathscr F$?

1

There are 1 best solutions below

3
On

On page number 190 (Section 13.6) of the book "Extremal Combinatorics, Second Edition" by Jukna, the following result, attributed to Frankl and Wilson, is proved:

If $L\subset \mathbb{N}$ is a finite set of integers and if $F$ is a family of subsets of an $n$ element set such that for all $A, B \in F$, $A \neq B$, $|A\cap B| \in L$, then $|F|\leq \sum_{i = 0}^{|L|}\binom{n}{i}$.