Four-vertex traces of finite sets

Abstract

Let $[n]=X_1\cup X_2\cup X_3$ be a partition with $\lfloor \frac{n}{3}\rfloor \le |X_i|\le \lceil \frac{n}{3}\rceil$ and define $\mathcal{G}=\{G\subset [n]:|G\cap X_i|\le 1,1\le i\le 3\}$. It is easy to check that the trace ${\mathcal{G}}_{\mid Y}:=\{G\cap Y:G\in \mathcal{G}\}$ satisfies $|{\mathcal{G}}_{\mid Y}|\le 12$ for all 4-sets $Y\subset [n]$. For $n\ge 25$ it is proven that whenever $\mathcal{F}\subset 2^{[n]}$ satisfies $|\mathcal{F}|>|\mathcal{G}|$ then $|{\mathcal{F}}_{\mid C}|\ge 13$ for some $C\subset [n]$, $|C|=4$. Several further results of a similar flavor are established as well.