0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Frankl union-closed sets conjecture? $\endgroup$
    – Seva
    Feb 12, 2019 at 12:25
  • 1
    $\begingroup$ You may be thinking of en.wikipedia.org/wiki/Union-closed_sets_conjecture $\endgroup$
    – bof
    Feb 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$
    – YCor
    Feb 12, 2019 at 17:00

2 Answers 2

3
$\begingroup$

This is completely false. Consider the lines of a finite projective plane.

$\endgroup$
2
  • $\begingroup$ Sorry for not stating the problem clearly. $F$ is consisting of subsets of $[n]$ $\endgroup$
    – xmchenhit
    Feb 12, 2019 at 12:32
  • 1
    $\begingroup$ So what? Enumerate the points from 1 to $n$. $\endgroup$ Feb 12, 2019 at 12:44
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.