Abstract

For two subsets $A=\{a_1,\dots <!--FUNCTION\; APPLICATION-->,a_k\}$ and $B=\{b_1,\dots <!--FUNCTION\; APPLICATION-->,b_k\}$ of $[n]$ with $a_1<a_2<\cdots <a_k$ and $b_1<b_2<\cdots <b_k$, we define their coincidence by $|A\wedge B|=|\{i:a_i=b_i\}|$. A family $\mathcal{ℱ}\subset \left(\genfrac{}{}{0.0pt}{}{[n]}{k}\right)$ is called $t$-coinciding if $|F\wedge F^{\prime }|\ge t$ for all distinct $F,F^{\prime }\in \mathcal{ℱ}$. It is conjectured that for $n\ge k\ge t>0$ a $t$-coinciding family has size at most $\left(\genfrac{}{}{0.0pt}{}{n-t}{k-t}\right)$. The conjecture is confirmed for cases $t=1,k-1,k-2$, the case $n=k+1$, and the case $n=k+2$, $k\ge 3t-1$. The opposite problem, where $k$-subsets are forbidden to coincide in $t$ or more elements leads to new types of designs. We solve the new design problem completely for the $t=2$ case.

Keywords

Mathematical Subject Classification

Milestones

Authors