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

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

$\endgroup$
  • $\begingroup$ Sorry for not stating the problem clearly. $F$ is consisting of subsets of $[n]$ $\endgroup$ – xmchenhit Feb 12 at 12:32
  • 1
    $\begingroup$ So what? Enumerate the points from 1 to $n$. $\endgroup$ – Fedor Petrov Feb 12 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.

New contributor
LopiJ is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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