Let $F$ be a set consisting of some subsets of $[n]$, and any two sets in $F$ have at least one element in common. I think I read a result stating as following: there exists an element $x$, such that at least half of $F$ include $x$. But I do not remember the related reference. Do anyone know the reference or some similar results?Thanks.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Frankl union-closed sets conjecture? $\endgroup$– SevaFeb 12, 2019 at 12:25
-
1$\begingroup$ You may be thinking of en.wikipedia.org/wiki/Union-closed_sets_conjecture $\endgroup$– bofFeb 12, 2019 at 12:28
-
$\begingroup$ In view of the given link to the Frankl conjecture and Fedor's answer, it seems that the missing assumption in your statement is that $F$ should be closed under taking unions. $\endgroup$– YCorFeb 12, 2019 at 17:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
This is completely false. Consider the lines of a finite projective plane.
-
$\begingroup$ Sorry for not stating the problem clearly. $F$ is consisting of subsets of $[n]$ $\endgroup$ Feb 12, 2019 at 12:32
-
1$\begingroup$ So what? Enumerate the points from 1 to $n$. $\endgroup$ Feb 12, 2019 at 12:44
$\begingroup$
$\endgroup$
Is such generality the result is false. If you have $n$ sets, you can always define ${n \choose 2}$ elements such that each of them is contained in a different couple of sets. This way all the sets have non-empty intersection and no element is contained in more than $2$ sets.