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
Problem
Source: Czech-Polish-Slovak Match 2015, Problem 2
Tags: combinatorics, Sets
20.06.2015 12:13
We procced by strong induction on lUl=$u$.Assume all sets are non empty and we prove lFl<=lUl.Base case $u=1$ is clear. Pick a random subset $S$ and suppose it has $s$ elements.Divide the remaining sets in two groups $A$ and $B$,in $A$ are all subsets of $S$ and in $B$ are the remaining sets.Let $C$ be the family of intersections of all sets with $S$. Lemma $1$:In $C$ we can't have two non empty sets $X$ and $Y$ such that both $(X/Y)$ and $(Y/X)$ are non empty. Proof:Just consider sets $G$ and $D$ wich contain $X$ and $Y$.Now,just apply the problem condition on $G,D,S$. This means that if we pick any two sets from $C$,one is a subset of another,which means $C$ has at most $s$ elements. Lemma $2$:We can't have two sets such that they have the same elements that aren't in $S$(nonzero number). Proof:Let their common non $S$ set be $H$ and their intersections with $S$ be $X$ and $Y$.WLOG,$Y$ is a subset of $X$.Now,this easy follows from the problem statement(let X1=S,X2=HUY and X3=HUX). Now,from these lemmas we have that $A$ has at most $s$ elements and $B$ contains af most $u-s$ elements by induction hypothesis on $B$(we can do this since no two have same non $S$ elements),so we have at most $u-s+s=u$ non empy sets.
07.12.2017 07:17
Let exclude the empty subset. Then we need to prove that $|F| \leq |U|=n$. If every two sets don't have the same elements, then the result is trivial. Or otherwise we can suppose that there exist $X_1,X_2$ such that $|X_1 \cap X_2|$ is the largest among all. Then it's easy to check that for $X\in F$. $X \cap X_1 \subset X_2$ and $X \cap X_2 \subset X_1$, which means $X \subset X_1 \cap X_2$, and for all $X,Y \in F$(and not $X_1,X_2$). We have $X \subset Y$ or $Y \subset X$. Then the final result is easy.