8
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

For the first question, Doesn't Frankl-Furedi give you a bound of $O(n)$?

http://www.sciencedirect.com/science/article/pii/0097316585900354

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniel Soltész Feb 11 '17 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.