9
$\begingroup$

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!

$\endgroup$
5
  • $\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$ Aug 5, 2013 at 8:10
  • $\begingroup$ I suppose if the example you ask for existed then that question would not be listed as open... $\endgroup$ Aug 5, 2013 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$ Aug 5, 2013 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$ Aug 5, 2013 at 8:20
  • 6
    $\begingroup$ IMHO a question should have explained all this - otherwise it's limited to a handful of people who know all the background... $\endgroup$ Aug 5, 2013 at 8:32

2 Answers 2

10
$\begingroup$

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

$A_1=\{1,2,3\}$
$A_2=\{1,2,3,6,7,8,9\}$
$A_3=\{1,2,3,4,6,7,8,9\}$
$A_4=\{1,2,3,4,5,6,7,8,9\}$
$A_5=\{1,2,3,4,5,8,9\}$
$A_6=\{1,2,3,4,5,6,8,9\}$
$A_7=\{1,2,3,4,5,6,7\}$
$A_8=\{1,2,3,4,5,6,7,8\}$
$A_9=\{6,7,8,9\}$
$A_{10}=\{4,6,7,8,9\}$
$A_{11}=\{4,5,6,7,8,9\}$
$A_{12}=\{4,5,8,9\}$
$A_{13}=\{4,5,6,8,9\}$
$A_{14}=\{4,5,6,7\}$
$A_{15}=\{4,5,6,7,8\}$
$A_{16}=\{1,6,7,8,9\}$
$A_{17}=\{1,4,6,7,8,9\}$
$A_{18}=\{1,4,5,6,7,8,9\}$
$A_{19}=\{2,4,5,8,9\}$
$A_{20}=\{2,4,5,6,8,9\}$
$A_{21}=\{2,4,5,6,7,8,9\}$
$A_{22}=\{3,4,5,6,7\}$
$A_{23}=\{3,4,5,6,7,8\}$
$A_{24}=\{3,4,5,6,7,8,9\}$
$A_{25}=\{1,2,4,5,6,7,8,9\}$
$A_{26}=\{1,3,4,5,6,7,8,9\}$
$A_{27}=\{2,3,4,5,6,7,8,9\}$

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.

$\endgroup$
5
$\begingroup$

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.)

$\endgroup$
2
  • $\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$ Aug 5, 2013 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$ Aug 5, 2013 at 23:55

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.