Problem

Source: Czech-Polish-Slovak Match 2015, Problem 2

Tags: combinatorics, Sets



A family of sets $F$ is called perfect if the following condition holds: For every triple of sets $X_1, X_2, X_3\in F$, at least one of the sets $$ (X_1\setminus X_2)\cap X_3,$$ $$(X_2\setminus X_1)\cap X_3$$ is empty. Show that if $F$ is a perfect family consisting of some subsets of a given finite set $U$, then $\left\lvert F\right\rvert\le\left\lvert U\right\rvert+1$. Proposed by MichaƂ Pilipczuk