Specified intersections

Abstract:

Let $M \subset [n]:=\{0, \ldots , n\}$ and ${\mathcal {A}}$ be a family of subsets of an $n$ element set such that $|A \cap B| \in M$ for every $A, B \in \mathcal {A}$. Suppose that $l$ is the maximum number of consecutive integers contained in $M$ and $n$ is sufficiently large. Then \[ |\mathcal {A}|< \min \{1.622^n 10^{2l+5} ,\quad 2^{n/2+l\log ^2 n}\}.\] The first bound complements the previous bound of roughly $(1.99)^n$ due to Frankl and the second author which was proved under the assumption that $M=[n]\setminus \{n/4\}$. For $l=o(n/\log ^2 n)$, the second bound above becomes better than the first bound. In this case, it yields $2^{n/2+o(n)}$, and this can be viewed as a generalization (in an asymptotic sense) of the famous Eventown theorem of Berlekamp (1969) and Graver (1975). We conjecture that our bound $2^{n/2+o(n)}$ remains valid as long as $l<n/10$.

Our second result complements the result of Frankl and the second author in a different direction. Fix $\varepsilon >0$ and $\varepsilon n < t<n/5$ and let $M=[n]\setminus (t, t+n^{0.525})$. Then, in the notation above, we prove that for $n$ sufficiently large, \[ |\mathcal {A}| \le n{n \choose (n+t)/2}.\] This is essentially sharp, aside from the multiplicative factor of $n$. The short proof uses the Frankl-Wilson theorem and results about the distribution of prime numbers. We conjecture that a similar bound holds for $M=[n]\setminus \{t\}$ whenever $\varepsilon n < t < n/3$. A similar conjecture when $t$ is fixed and $n$ is large was made earlier by Frankl (1977) and proved by Frankl and Füredi (1984).