Oakey1w

2022-06-19

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?

klemmepk

Beginner2022-06-20Added 16 answers

Let $L$ be a set of m integers and $F$ be an $L$-intersecting $k$-uniform family of subsets of a set of $n$ elements, where $m\le k$, then

$|F|\le {\textstyle (}\genfrac{}{}{0ex}{}{n}{m}{\textstyle )}$

$k$-uniform family is a set of subsets, each subset being of size $k$.

An $L$-intersecting family is such that the intersection size of any two distinct sets in the family is in $L$.

For every $k\ge m\ge 1$ and $n\ge 2{k}^{2}$ there exists a $\u043b$-uniform family $F$ of size $>(\frac{n}{2k}{)}^{m}$ on $n$ points such that $|A\cap B|\le m-1$ for any two distinct sets $A,B\in F$.

$|F|\le {\textstyle (}\genfrac{}{}{0ex}{}{n}{m}{\textstyle )}$

$k$-uniform family is a set of subsets, each subset being of size $k$.

An $L$-intersecting family is such that the intersection size of any two distinct sets in the family is in $L$.

For every $k\ge m\ge 1$ and $n\ge 2{k}^{2}$ there exists a $\u043b$-uniform family $F$ of size $>(\frac{n}{2k}{)}^{m}$ on $n$ points such that $|A\cap B|\le m-1$ for any two distinct sets $A,B\in F$.