# Set system with prescribed intersection sizes

Questions: What is the asymptotic maximal size of a $4$-uniform (every set has 4 elements) set system $\mathcal{A}$ of subsets of $[n]$ such that, no two sets have size of their intersection $2$?

In general I would be interested in k-uniform set systems of size $\tilde{} n^3$ with intersection sizes one of {0,1,k-1}.

Some background: The Ray-Chaudhuri-Wilson theorem states that such a system can not have more than $\tilde{}n^3$ elements. For the second question, from the Frankl-Wilson theorem it follows that if there is a prime $p \neq 2$ such that $k-2 \equiv 0 \mod p$ the size of the system can be at most $\tilde{}n^2$. Note that the Frankl-Wilson would give us $\tilde{}n^2$ at the first question if we would forbid disjoint sets! If there is a system with size $\tilde{}n^3$, by the Sauer-Shelah lemma it would shatter a lot of three element sets and by the condition, it can not shatter a four element set, thus has VC-dimension 3! If it shatters a three element set we can say something about the structure of the sets intersecting this triple. But I wouldn't describe it as one can work it out himself as fast as one can read it. :-)

You can also rephrase the first question as the independence number of a Kneser-like graph. The vertices are the 4-sets, there is an edge between two sets if the size of the intersection is exactly $2$. Then the maximal size of the required set system is exactly the independence number of this graph.

For the first question, Doesn't Frankl-Furedi give you a bound of $O(n)$?
• Yes it does! It also says that one can't achieve $\sim n^3$ in the second setting, as using the notation of the paper, there we have $l=2$ and $l'=1$ so the maixmal order of magnitude is $\sim n^2$. This can be achieved by dividing the ground set into two parts of size n/2: the left and the right part. We further divide the right part into disjoint "blocks" of size $k-1$. Then take every set that contains one element on the left side and one block on the right. – Daniel Soltész Feb 11 '17 at 11:57