# Renaud-Sarvate limitation on Frankl's Conjecture

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.

-
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) – Dima Pasechnik Aug 5 '13 at 8:10
I suppose if the example you ask for existed then that question would not be listed as open... – Dima Pasechnik Aug 5 '13 at 8:11
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. – The Masked Avenger Aug 5 '13 at 8:16
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. – The Masked Avenger Aug 5 '13 at 8:20
IMHO a question should have explained all this - otherwise it's limited to a handful of people who know all the background... – Dima Pasechnik Aug 5 '13 at 8:32

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

-
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. – Gerry Myerson Aug 5 '13 at 23:39
I'm not sure whether the Bruhn et al. paper has appeared in print. It's available at arxiv.org/abs/1212.4175 – Gerry Myerson Aug 5 '13 at 23:55

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.

-