I was wondering if someone could give me a specific example of union closed family with a three element set, none of whose elements are in half the members of the family.

Thanks in advance!

  • $\begingroup$ Are you talking about Conjecture/Question: If F is a finite non-trivial union-closed family of finite sets, then some element appears in at least half the members of F. (from math.uiuc.edu/~west/openp/unionclos.html) $\endgroup$ – Dima Pasechnik Aug 5 '13 at 8:10
  • $\begingroup$ I suppose if the example you ask for existed then that question would not be listed as open... $\endgroup$ – Dima Pasechnik Aug 5 '13 at 8:11
  • $\begingroup$ I can't, but such an example has been published (before 1994). If Poonen's paper doesn't have it, a citation search should help locate the paper. $\endgroup$ – The Masked Avenger Aug 5 '13 at 8:16
  • $\begingroup$ Dima, the poster is asking for a counterexample of a different kind. It is known that if a finite union closed collection contains a singleton set or a doubleton, at least one member of that set appears in half the elements of the collection. This is not the case in general for a finite union closed family with smallest set having three elements. $\endgroup$ – The Masked Avenger Aug 5 '13 at 8:20
  • 5
    $\begingroup$ IMHO a question should have explained all this - otherwise it's limited to a handful of people who know all the background... $\endgroup$ – Dima Pasechnik Aug 5 '13 at 8:32

This example with minimal size $3$ is from D. G. Sarvate and J-C. Renaud, "Improved bounds for the union-closed sets conjecture", Ars Combinatoria 29 (1990), pp. 181-185:

$\mathcal A=\{A_1,\dots,A_{27}\},$ with


Here $A_1=\{1,2,3\}$ is the unique set of minimal size, and each of the elements $1,2,3$ is in exactly $13$ of the $27$ sets.

| cite | improve this answer | |

This type of example was first provided by Sarvate and Renaud, but I can't access that paper.

The paper 'The graph formulation of the union-closed conjecture' by Bruhn, Charbit, Schaudt, Arne Telle contains a very similar example for their graph reformulation, which is presumably converted from the Sarvate-Renaud example. Reconverting into the set language, this is:

The family generated by the empty set, 1, 2, 3, 125, 136, 237, 567. This is a family containing 25 sets. The elements 1, 2 and 3 are each in 16 sets. The elements 5, 6 and 7 are each in 12 sets.

Thus the set 567 is a three element set, none of whose elements are in at least half of the sets.

(Note in case people are curious about the motivation - there is an easy argument to show that if the family contains a set with two elements then at least one of those elements is in at least half the sets. This shows the same is not true for sets of three elements.)

| cite | improve this answer | |
  • $\begingroup$ I believe the paper referred to is Sarvate and Renaud, Improved bounds for the union-closed sets conjecture, Ars Combin. 29 (1990) 181–185, MR1046106 (91i:05006). According to the review, in their counterexample, the smallest set in the family has 3 elements, which is not the case in the example given above. $\endgroup$ – Gerry Myerson Aug 5 '13 at 23:39
  • $\begingroup$ I'm not sure whether the Bruhn et al. paper has appeared in print. It's available at arxiv.org/abs/1212.4175 $\endgroup$ – Gerry Myerson Aug 5 '13 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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