Skip to main content
2 of 2
retagged

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.