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!
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityI 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!
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.
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.)