2
$\begingroup$

Would it be reasonable to conjecture what follows : there is a real constant $c > 1/2$ such that, for every natural number $n$, if $X_{1}, \ldots , X_{n}$ is a union-stable family of distinct finite sets with at least two elements in their union $U$, then there is at least one subset of $U$ with two elements that intersects at least $cn - 1$ sets $X_{i}$ ? Thanks in advance.

$\endgroup$
8
  • 1
    $\begingroup$ While this is a reasonable (but not great) question for MathOverflow, you might go to gowers.wordpress.com where some Polymath discussion covers questions similar to (and maybe exactly) this. If this question isn't there already, add it. Gerhard "Go In,The Water's Fine" Paseman, 2016.02.21. $\endgroup$ Feb 21, 2016 at 20:01
  • $\begingroup$ Also, it is known that c=1/2 works when U is one of the X_i. You might be able to bring c down to exactly 1/2 by looking at those cases where U is a member of the family. Gerhard "Maybe Do The Hottub First" Paseman, 2016.02.21. $\endgroup$ Feb 21, 2016 at 20:06
  • $\begingroup$ I don't understand. It is not interesting to bring c down to exactly 1/2, a value c > 1/2 is better than 1/2. And how could it be possible that U was not a member of the family ? (By the way, it could be interesting to look at the hypothetical value c = 2/3.) $\endgroup$
    – Panurge
    Feb 22, 2016 at 6:29
  • $\begingroup$ Sorry, I misread U as being a two element subset of the universe. My contention ( and I may be wrong ) is that there will be for every epsilon a union closed family with a two element set V as part of the family such that V intersects (1/2 + epsilon)n - 1 sets of the family and every other two element set intersects in strictly fewer sets of the family. So I think c= 2/3 will not work for all families. Gerhard " Union Closed Sets Are Tricky" Paseman, 2016.02.21. $\endgroup$ Feb 22, 2016 at 6:59
  • 1
    $\begingroup$ Well, if you speak about this family with 17 sets indicated by Alec Edgington, the set {0,1} intersects 13 sets, which is in accordance with the value c = 2/3. $\endgroup$
    – Panurge
    Feb 22, 2016 at 10:33

1 Answer 1

2
$\begingroup$

As Miroslav Chlebik shows it here :

https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154441

the answer is yes with c = 3/4 if Frankl's conjecture is right.

$\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.