MathDB
Maximal size of a perfect family of sets

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

June 19, 2015
combinatoricsSets

Problem Statement

A family of sets FF is called perfect if the following condition holds: For every triple of sets X1,X2,X3∈FX_1, X_2, X_3\in F, at least one of the sets (X1∖X2)∩X3, (X_1\setminus X_2)\cap X_3, (X2∖X1)∩X3(X_2\setminus X_1)\cap X_3 is empty. Show that if FF is a perfect family consisting of some subsets of a given finite set UU, then ∣F∣≤∣U∣+1\left\lvert F\right\rvert\le\left\lvert U\right\rvert+1.
Proposed by Michał Pilipczuk
Back to ProblemsView on AoPS