S1-Frankl 猜想的6元素情形 (Ⅰ)

2020-01-10 03:17:18胡澤春李世倫

四川大學學報(自然科學版) 2020年1期

關鍵詞：數學

胡澤春，李世倫

(四川大學數學學院，成都 610064)

1 Introduction

A familyFof sets is union-closed ifA,B∈FimpliesA∪B∈F. For simplicity, denoten=|∪A∈FA| andm=|F|.

LetMn={1,2,…,n} andF?2Mn={A:A?Mn} with ∪A∈FA=Mn. Suppose thatFis union-closed. Without loss of generality, we assume that ?∈F. For anyk=1,2,…,n, define

Mk={A∈2Mn:|A|=k},

and

T(F)=inf{1≤k≤n:F∩Mk≠?}.

Then 1≤T(F)≤n. By virtue ofT(F), Ref.[17] introduced the following two stronger versions of Frankl’s conjecture:

S1-Frankl conjecture: Ifn≥2 andT(F)=k∈{2,…,n}, then there exist at leastkelements inMnwhich belong to at least half of the sets inF;

S2-Frankl conjecture: Ifn≥2 andT(F)=k∈{2,…,n}, then there exist at least two elements inMnwhich belong to at least half of the sets inF.

We need the following lemma, which has been used in some proofs in Ref.[17].

Lemma1.1Suppose thatMis a finite set with |M|≥2 andG?{A?M:|A|=|M|-1}. If |G|≥2, then all the elements inMbelong to at least |G|-1 set(s) inG.

ProofWithout loss of generality, we assume thatM=Mn={1,2,…,n} withn≥2. ThenGis a subset ofMn-1={A?Mn:|A|=n-1}. Notice that for anyi∈{1,2,…,n}, it belongs to all the sets inMn-1except the setMn{i}. Hence all the elements inMbelong to at least |G|-1 set(s) inG.

When we considerS1-Frankl conjecture for the case thatn=6, by section 2 of Ref.[17], we know that ifT(F)∈{4,5,6}, then there exist at leastT(F) elements inM6which belong to at least half of the sets inF. Thus we need only to consider the two casesT(F)=3 andT(F)=2. In next section, we will prove thatS1-Frankl conjecture holds whenn=6 andT(F)=3. The proof for the case thatn=6 andT(F)=2 will be given in a sister paper.LetM6={1,2,…,6} andF?2M6={A:A?M6} with ∪A∈FA=M6. Suppose thatFis union-closed and ?∈F. Fork=1,2,…,6, define

Mk={A∈2M6:|A|=k},nk=|F∩Mk|,

and

T(F)=inf{1≤k≤6:nk>0}.

Then 1≤T(F)≤6.

In the following, we assume thatT(F)=3, and will prove that there exist at least 3 elements inM6which belong to at least half of the sets inF. We have 4 cases:F={?,M6}∪G3,F={?,M6}∪G3∪G5,F={?,M6}∪G3∪G4andF={?,M6}∪G3∪G4∪G5, whereGiis a nonempty subset ofMifori=3,4,5.

2.1 F={?,M6}∪G3

We have two subcases:n3=1 andn3≥2. Throughout the rest of this paper, we omit the sentences of this type. DenoteG3={G1,…,Gn3}.

(1)n3=1. NowG3={G1}. Then all the 3 elements inG1belong to two sets among the three sets inF.

(2)n3≥2. For anyi,j=1,…,n3,i≠j, we must haveGi∪Gj=M6, which implies thatGi∩Gj=?. Hencen3=2. Now all the 6 elements inM6belong to two sets among the four sets inF.

2.2 F={?,M6}∪G3∪G5

DenoteG3={G1,…,Gn3} andG5={H1,…,Hn5}.

(1)n5=1. NowG5={H1}. Without loss of generality, we assume thatH1={1,2,3,4,5}.

(1.1)n3=1. NowG3={G1}. Notice that all the elements inG1∪{1,2,3,4,5} belong to at least one of the two setsG1and {1,2,3,4,5}. Then we know that all the elements inG1∪{1,2,3,4,5} belong to at least half of the sets inF.

(1.2)n3≥2. For anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj={1,2,3,4,5}.

(1.2.1)n3is an even number and there is a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-1∪Gin3=M6. Then all the 6 elements inM6belong to half of the sets inG3and thus all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(1.2.2)n3is an odd number and there is a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-2∪Gin3-1=M6. Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gin3-1} and thus all the elements inGin3∪{1,2,3,4,5} belong to at least half of the sets inF.

(1.2.3) We can decomposeG3into two disjoint parts {Gi1,…,Gi2k} (hereafter this part may be an empty set) and {Gi2k+1,…,Gin3}, where {i1,…,in3}={1,…,n3},n3-2k≥2, and

(i)Gi1∪Gi2=…=Gi2k-1∪Gi2k=M6;

(ii) for any two different indexes {i,j} from {i2k+1,…,in3},Gi∪Gj={1,2,3,4,5}.

Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gi2k}. Without loss of generality, we assume thatGi2k+1={1,2,3}. By (ii), we know that for anyj=i2k+2,…,in3,

Gj∈{{1,4,5},{2,4,5},{3,4,5}}.

Since |{1,4,5}∪{2,4,5}|=|{1,4,5}∪{3,4,5}|=|{2,4,5}∪{3,4,5}|=4, by (ii) again, we know that in this casen3-2k=2. Then we know that all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(2)n5≥2. By Lemma 1.1, we know that all the 6 elements inM6belong to at leastn5-1 set(s) inG5and thus belong to at least half of the sets inG5. Hence it is enough to show that there exist at least 3 elements inM6which belong to at least half of the sets inG3.

(2.1)n3=1. NowG3={G1}. Then all the 3 elements inG1satisfy the condition.

(2.2)n3≥2. For anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6or |Gi∪Gj|=5.

(2.2.1)n3is an even number and there is a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-1∪Gin3=M6. Then all the 6 elements inM6belong to half of the sets inG3.

(2.2.2)n3is an odd number and there is a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-2∪Gin3-1=M6. Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gin3-1} and thus all the 3 elements inGin3belong to at least half of the sets inG3.

(2.2.3) We can decomposeG3into two disjoint parts {Gi1,…,Gi2k} and {Gi2k+1,…,Gin3}, where {i1,…,in3}={1,…,n3},n3-2k≥2, and

(i)Gi1∪Gi2=…=Gi2k-1∪Gi2k=M6;

(ii) for any two different indexes {i,j} from {i2k+1,…,in3},|Gi∪Gj|=5.

Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gi2k}. Without loss of generality, we assume thatGi2k+1={1,2,3}. By (ii), we know that for anyj=i2k+2,…,in3,

Gj∈{{1,4,5},{2,4,5},{3,4,5},{1,4,6},

{2,4,6},{3,4,6},{1,5,6},{2,5,6},{3,5,6}}.

Since |{1,4,5}∪{2,4,5}|=|{1,4,5}∪{3,4,5}|=|{2,4,5}∪{3,4,5}|=4, by (ii) again, we know that |{Gi2k+1,…,Gin3}∩{{1,4,5},{2,4,5},{3,4,5}}|≤1. Similarly, we have that

Hence we need only to consider the following 3 cases.

(2.2.3.1)n3-2k=2. Take |{Gi2k+1,…,Gin3}∩{{1,4,5},{2,4,5},{3,4,5}}|=1 for example. Without loss of generality, we assume that {Gi2k+1,…,Gin3}={{1,2,3},{1,4,5}}. Now all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inG3.

(2.2.3.2)n3-2k=3. Take |{Gi2k+1,…,Gin3}∩{{1,4,5},{2,4,5},{3,4,5}}|=1=|{Gi2k+1,…,Gin3}∩{{1,4,6},{2,4,6},{3,4,6}}| for example. Without loss of generality, we assume that {Gi2k+1,…,Gin3}={{1,2,3},{1,4,5},{2,4,6}}. Now all the 3 elements in {1,2,4} belong to at least half of the sets inG3.

(2.2.3.3)n3-2k=4. Without loss of generality, we assume that {Gi2k+1,…,Gin3}={{1,2,3},{1,4,5},{2,4,6},{3,5,6}}. Now all the 6 elements inM6belong to at least half of the sets inG3.

2.3 F={?,M6}∪G3∪G4

DenoteG3={G1,…,Gn3} andG4={H1,…,Hn4}.

(1)n4=1. NowG4={H1}. Without loss of generality, we assume thatH1={1,2,3,4}.

(1.1)n3=1. NowG3={G1}. Then all the elements inG1∪{1,2,3,4} belong to at least half of the sets inF.

(1.2)n3≥2. For anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj={1,2,3,4}.

(1.2.1)n3is an even number and there is a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-1∪Gin3=M6. Then all the 6 elements inM6belong to half of the sets inG3and thus all the 4 elements in {1,2,3,4} belong to at least half of the sets inF.

(1.2.3) We can decomposeG3into two disjoint parts {Gi1,…,Gi2k} and {Gi2k+1,…,Gin3}, where {i1,…,in3}={1,…,n3},n3-2k≥2, and

(i)Gi1∪Gi2=…=Gi2k-1∪Gi2k=M6;

(ii) for any two different indexes {i,j} from {i2k+1,…,in3},Gi∪Gj={1,2,3,4}.

Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gi2k}. By Lemma 1.1, we know that all the 4 elements in {1,2,3,4} belong to at leastn3-2k-1 set(s) in {Gi2k+1,…,Gin3} and thus belong to at least half of the sets in {Gi2k+1,…,Gin3}. Hence in this case, all the 4 elements in {1,2,3,4} belong to at least half of the sets inF.

(2)n4≥2. For anyi,j=1,…,n4,i≠j, we must haveHi∪Hj=M6.

We claim that all the 6 elements inM6belong to at least half of the sets inG4.In fact, ifn4=2kis an even number, thenH1∪H2=…=H2k-1∪H2k=M6and thus all the 6 elements inM6belong to at least half of the sets inG4. Ifn4=2k+1 is an odd number, then by

H1∪H2=…=H2k-1∪H2k=M6,

we know that all the 4 elements inH2k+1belong to at least half of the sets inG4; by

we know that all the 4 elements inG1belong to at least half of the sets inG4; byH1∪H2k+1=M6, we know that all the 6 elements inM6belong to at least half of the sets inG4. Hence it is enough to show that there exist 3 elements inM6which belong to at least half of the sets inG3.

(2.1)n3=1. NowG3={G1}. Then all the 3 elements inG1satisfy the condition.

(2.2)n3≥2. For anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6or |Gi∪Gj|=4.

(2.2.1)n3is an even number and there is a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-1∪Gin3=M6. Then all the 6 elements inM6belong to half of the sets inG3.

(2.2.3) We can decomposeG3into two disjoint parts {Gi1,…,Gi2k} and {Gi2k+1,…,Gin3}, where {i1,…,in3}={1,…,n3},n3-2k≥2, and

(i)Gi1∪Gi2=…=Gi2k-1∪Gi2k=M6;

(ii) for any two different indexes {i,j} from {i2k+1,…,in3},|Gi∪Gj|=4.

Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gi2k}. Without loss of generality, we assume thatGi2k+1={1,2,3}. By (ii), we know that for anyj=i2k+2,…,in3,Gj∈{{1,2,4},{1,3,4},{2,3,4},{1,2,5},{1,3,5},{2,3,5},{1,2,6},{1,3,6},{2,3,6}}.

Denote

For anyA∈H4,B∈H5,C∈H6, we have

ByF={?,M6}∪G3∪G4, without loss of generality, we can assume that

F∩H4≠?,F∩H5=F∩H6=?.

Now, by Lemma 1.1, we know that all the 4 elements in {1,2,3,4} belong to at leastn3-2k-1 set(s) in {Gi2k+1,…,Gin3}, and thus belong to at least half of the sets inG3.

2.4 F={?,M6}∪G3∪G4∪G5

DenoteG3={G1,…,Gn3},G4={H1,…,Hn4} andG5={I1,…,In5}.

(1)n5=1. NowG5={I1}. Without loss of generality, we assume thatI1={1,2,3,4,5}.

(1.1)n4=1. NowG4={H1}.

(1.1.1)n3=1. NowG3={G1}. IfH1?I1, then all the 4 elements inH1belong to at least two sets among the three sets inG3∪G4∪G5and thus belong to at least half of the sets inF. IfH1I1, thenH1∪I1=M6and thus in this case all the 3 elements inG1belong to at least half of the sets inF.

(1.1.2)n3≥2. Now for anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj=I1={1,2,3,4,5} orGi∪Gj=H1.

(1.1.2.1)n3is an even number and there exists a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-1∪Gin3=M6. Then all the 6 elements inM6belong to half of the sets inG3. Hence all the elements inH1∪I1belong to at least half of the sets inF.

(1.1.2.2)n3is an odd number and there exists a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-2∪Gin3-1=M6. Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gin3-1}. IfH1?I1, then all the 4 elements inH1belong to at least two sets among the three sets in {Gin3,H1,I1} and thus belong to at least half of the sets inF. IfH1I1, thenH1∪I1=M6and thus in this case all the 3 elements inGin3belong to at least half of the sets inF.

(1.1.2.3) We can decomposeG3into two disjoint parts {Gi1,…,Gi2k} and {Gi2k+1,…,Gin3}, where {i1,…,in3}={1,…,n3},n3-2k≥2, and

(i)Gi1∪Gi2=…=Gi2k-1∪Gi2k=M6;

(ii) for any two different indexes {i,j} from {i2k+1,…,in3},Gi∪Gj=I1={1,2,3,4,5} orGi∪Gj=H1.

Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gi2k}.

(a)H1?{1,2,3,4,5}. Without loss of generality, we assume thatH1={1,2,3,4}.

(a.1)n3-2kis an even number and there exists a permutation (j1,…,jn3-2k) of (i2k+1,…,in3) such thatGj1∪Gj2=…=Gjn3-2k-1∪Gjn3-2k={1,2,3,4,5}. Then all the 5 elements in {1,2,3,4,5} belong to at least half of the sets in {Gi2k+1,…,Gin3}. Note that all the 5 elements in {1,2,3,4,5} belong to at least one of the two setsH1andI1. Then we know that in this case, all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(a.2)n3-2kis an odd number and there exists a permutation (j1,…,jn3-2k) of (i2k+1,…,in3) such thatGj1∪Gj2=…=Gjn3-2k-2∪Gjn3-2k-1={1,2,3,4,5}. Then all the 5 elements in {1,2,3,4,5} belong to at least half of the sets in {Gj1,…,Gjn3-2k-1}. Note that all the 4 elements in {1,2,3,4} belong to at least two sets among the three sets {Gjn3-2k,H1,I1}. Then we know that in this case, all the 4 elements in {1,2,3,4} belong to at least half of the sets inF.

(a.3) We can decompose {Gi2k+1,…,Gin3} into two disjoint parts {Gj1,…,Gj2l} and {Gj2l+1,…,Gjn3-2k}, where {j1,…,jn3-2k}={i2k+1,…,in3},n3-2k-2l≥2, and

(iii)Gj1∪Gj2=…=Gj2l-1∪Gj2l={1,2,3,4,5};

(iv) for any two different indexes {i,j} from {j2l+1,…,jn3-2k},Gi∪Gj=H1={1,2,3,4}.

Then all the 5 elements in {1,2,3,4,5} belong to at least half of the sets in {Gj1,…,Gj2l}. By Lemma 1.1, we know that all the 4 elements in {1,2,3,4} belong to at leastn3-2k-2l-1 set(s) in {Gj2l+1,…,Gjn3-2k} and thus belong to at least half of the sets in {Gj2l+1,…,Gjn3-2k}. Hence in this case, all the 4 elements in {1,2,3,4} belong to at least half of the sets inF.

(b)H1{1,2,3,4,5}. Without loss of generality, we assume thatH1={1,2,3,6}. By following the proof in (a), we can get that in this case all the 3 elements in {1,2,3} belong to at least half of the sets inF.

(1.2)n4≥2. Now for anyi,j=1,…,n4,i≠j, we haveHi∪Hj=M6orHi∪Hj=I1={1,2,3,4,5}.

(1.2.1)n4is an even number and there exists a permutation (i1,…,in4) of (1,…,n4) such thatHi1∪Hi2=…=Hin4-1∪Hin4=M6. Then all the 6 elements inM6belong to at least half of the sets inG4.

(1.2.1.1)n3=1. NowG3={G1}. In this case, all the elements inG1∪I1belong to at least half of the sets inF.

(1.2.1.2)n3≥2. Now for anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj=I1={1,2,3,4,5} or |Gi∪Gj|=4.

(a)n3is an even number and there exists a permutation (j1,…,jn3) of (1,…,n3) such thatGj1∪Gj2=…=Gjn3-1∪Gjn3=M6. Then all the 6 elements inM6belong to half of the sets inG3. Hence in this case all the 5 elements inI1belong to at least half of the sets inF.

(c)We can decomposeG3into two disjoint parts {Gj1,…,Gj2k} and {Gj2k+1,…,Gjn3}, where {j1,…,jn3}={1,…,n3},n3-2k≥2, and

(i)Gj1∪Gj2=…=Gj2k-1∪Gj2k=M6;

(ii) for any two different indexes {i,j} from {j2k+1,…,jn3},Gi∪Gj=I1={1,2,3,4,5} or |Gi∪Gj|=4.

Then all the 6 elements inM6belong to half of the sets in {Gj1,…,Gj2k}.

(c.1)n3-2kis an even number and there exists a permutation (m1,…,mn3-2k) of (j2k+1,…,jn3) such thatGm1∪Gm2=…=Gmn3-2k-1∪Gmn3-2k={1,2,3,4,5}. Hence in this case, all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(c.2)n3-2kis an odd number and there exists a permutation (m1,…,mn3-2k) of (j2k+1,…,jn3) such thatGm1∪Gm2=…=Gmn3-2k-2∪Gmn3-2k-1={1,2,3,4,5}. Then all the 5 elements in {1,2,3,4,5} belong to at least half of the sets in {Gm1,…,Gmn3-2k-1}. Note that all the 5 elements in {1,2,3,4,5} belong to at least one of the two setsGmn3-2kand {1,2,3,4,5}. Hence in this case, all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(c.3) We can decompose {Gj2k+1,…,Gjn3} into two disjoint parts {Gm1,…,Gm2l} and {Gm2l+1,…,Gmn3-2k}, where {m1,…,mn3-2k}={j2k+1,…,jn3},n3-2k-2l≥2, and

(iii)Gm1∪Gm2=…=Gm2l-1∪Gm2l={1,2,3,4,5};

(iv) for any two different indexes {i,j} from {m2l+1,…,mn3-2k},Gi∪Gj∈G4.

Then all the 5 elements in {1,2,3,4,5} belong to at least half of the sets in {Gm1,…,Gm2l}.

(c.3.1) There existst∈{m2l+1,…,mn3-2k} such thatGt?{1,2,3,4,5}. Without loss of generality, we assume thatGm2l+1={1,2,3}. Then for anyt∈{m2l+2,…,mn3-2k}, we haveGt∈H4∪H5∪H6, where

For simplicity, defineH:={Gm2l+1,…,Gmn3-2k}. We have the following 7 cases.

(c.3.1.1)H∩H4≠?,H∩H5=H∩H6=?.

(c.3.1.2)H∩H5≠?,H∩H4=H∩H6=?.

(c.3.1.3)H∩H6≠?,H∩H4=H∩H5=?.

(c.3.1.4)H∩H4≠?,H∩H5≠?,H∩H6=?.

(c.3.1.5)H∩H4≠?,H∩H6≠?,H∩H5=?.

(c.3.1.6)H∩H5≠?,H∩H6≠?,H∩H4=?.

(c.3.1.7)H∩H4≠?,H∩H5≠?,H∩H6≠?.

As to (c.3.1.1), by Lemma 1.1, we know that all the 4 elements in {1,2,3,4} belong to at leastn3-2k-1 set(s) inHand thus belong to at least half of the sets inH. Hence in this case, all the 4 elements in {1,2,3,4} belong to at least half of the sets inF.

As to (c.3.1.2) and (c.3.1.3), we can get that all the 3 elements in {1,2,3} belong to at least half of the sets inF.

As to (c.3.1.4), without loss of generality, we assume that {1,2,4}∈H∩H4. Then by (iv), we know thatH∩H5={{1,2,5}} and by (iv) again we get thatH∩H4={{1,2,4}}. Thus in this caseH={{1,2,3},{1,2,4},{1,2,5}}. Note that all the 5 elements in {1,2,3,4,5} belong to at least two sets among the 4 sets in {{1,2,3},{1,2,4},{1,2,5},{1,2,3,4,5}}. Then we obtain that all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

As to (c.3.1.5), without loss of generality, we assume that {1,2,4}∈H∩H4. Then by (iv), we know thatH∩H6={{1,2,6}} and by (iv) again we get thatH∩H4={{1,2,4}}. Thus in this caseH={{1,2,3},{1,2,4},{1,2,6}}. By {1,2,3}∪{1,2,4}∪{1,2,6}={1,2,3,4,6}∈G5={{1,2,3,4,5}}, we know that this case is impossible.

As to (c.3.1.6) and (c.3.1.7), by following the analysis to (c.3.1.5), we know that these two cases are impossible.

(c.3.2) For anyt∈{m2l+1,…,mn3-2k},Gt{1,2,3,4,5}. Without loss of generality, we assume thatGm2l+1={1,2,6}. Then by (iv), we know that for anyt=m2l+2,…,mn3-2k, we have

Gt∈{{1,3,6},{1,4,6},{1,5,6},{2,3,6},{2,4,6},{2,5,6}}.Without loss of generality, we assume that {1,3,6}∈{Gm2l+2,…,Gmn3-2k}. Then byG5={{1,2,3,4,5}}, we need only to consider the following two subcases.

(c.3.2.1) {Gm2l+1,…,Gmn3-2k}={{1,2,6},{1,3,6}}.

(c.3.2.2) {Gm2l+1,…,Gmn3-2k}={{1,2,6},{1,3,6},{2,3,6}}.

As to (c.3.2.1), all the 4 elements in {1,2,3,6} belong to at least two sets among the 3 sets in {{1,2,6},{1,3,6},{1,2,3,4,5}}. Hence in this case all the 3 elements in {1,2,3,6}∩{1,2,3,4,5} (i.e. {1,2,3}) belong to at least half of the sets inF.

As to (c.3.2.2), we can easily know that all the 3 elements in {1,2,3} belong to at least half of the sets inF.

(1.2.2)n4is an odd number and there exists a permutation (i1,…,in4) of (1,…,n4) such thatHi1∪Hi2=…=Hin4-2∪Hin4-1=M6. Then all the 6 elements inM6belong to at least half of the sets in {Hi1,…,Hin4-1}.

(1.2.2.1)n3=1. NowG3={G1}. IfHin4?I1, then all the 4 elements inHin4belong to at least two sets among the three sets in {G1,Hin4,I1} and thus all the 4 elements inHin4belong to at least half of the sets inF. IfHin4I1, thenHin4∪I1=M6and thus in this case all the 3 elements inG1belong to at least half of the sets inF.

(1.2.2.2)n3≥2. Now for anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj=I1={1,2,3,4,5} or |Gi∪Gj|=4.

(a)n3is an even number and there exists a permutation (j1,…,jn3) of (1,…,n3) such thatGj1∪Gj2=…=Gjn3-1∪Gjn3=M6. Then all the 6 elements inM6belong to half of the sets inG3. Hence in this case all the elements inHin4∪I1belong to at least half of the sets inF.

(b)n3is an odd number and there exists a permutation (j1,…,jn3) of (1,…,n3) such thatGj1∪Gj2=…=Gjn3-2∪Gjn3-1=M6. Then all the 6 elements inM6belong to half of the sets in {Gj1,…,Gjn3-1}. Now ifHin4?I1, then all the 4 elements inHin4belong to at least two sets among the three sets in {Gjn3,Hin4,I1} and thus all the 4 elements inHin4belong to at least half of the sets inF. IfHin4I1, thenHin4∪I1=M6and thus in this case all the 3 elements inGjn3belong to at least half of the sets inF.

(i)Gj1∪Gj2=…=Gj2k-1∪Gj2k=M6;

(ii) for any two different indexes {i,j} from {j2k+1,…,jn3},Gi∪Gj=I1={1,2,3,4,5} or |Gi∪Gj|=4.

Then all the 6 elements inM6belong to half of the sets in {Gj1,…,Gj2k}.

(c.1)n3-2kis an even number and there exists a permutation (m1,…,mn3-2k) of (j2k+1,…,jn3) such thatGm1∪Gm2=…=Gmn3-2k-1∪Gmn3-2k={1,2,3,4,5}, which together with the fact that all the 5 elements in {1,2,3,4,5} belong to at least one of the two setsHin4and {1,2,3,4,5}, implies that all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(c.2.1) IfHin4?{1,2,3,4,5}, then all the 4 elements inHin4belong to at least two sets among the three sets in {Gmn3-2k,Hin4,{1,2,3,4,5}}. Hence in this case, all the 4 elements inHin4belong to at least half of the sets inF.

(c.2.2) IfHin4{1,2,3,4,5}, thenHin4∪{1,2,3,4,5}=M6. Without loss of generality, we assume thatHin4={1,2,3,6}.

(c.2.2.1)Gmn3-2k?{1,2,3,4,5}. Then all the 3 elements inGmn3-2kbelong to at least two sets among the three sets in {Gmn3-2k,Hin4,{1,2,3,4,5}} and thus belong to at least half of the sets inF.

(c.2.2.2)Gmn3-2k{1,2,3,4,5}. ThenGmn3-2k∪{1,2,3,4,5}=M6. Hence all the 6 elements inM6belong to at least one of the two setsGmn3-2kand {1,2,3,4,5} and thus all the 4 elements inHin4belong to at least two sets among the three sets in {Gmn3-2k,Hin4,{1,2,3,4,5}}. Hence in this case all the elements inHin4∩{1,2,3,4,5} (i.e. {1,2,3}) belong to at least half of the sets inF.

(c.3) We can decompose {Gj2k+1,…,Gjn3} into two disjoint parts {Gm1,…,Gm2l} and {Gm2l+1,…,Gmn3-2k}, where {m1,…,mn3-2k}={j2k+1,…,jn3},n3-2k-2l≥2, and

(iii)Gm1∪Gm2=…=Gm2l-1∪Gm2l={1,2,3,4,5};

(iv) for any two different indexes {i,j} from {m2l+1,…,mn3-2k},Gi∪Gj∈G4.

Then all the 5 elements in {1,2,3,4,5} belong to at least half of the sets in {Gm1,…,Gm2l}.

(c.3.1)Hin4?{1,2,3,4,5}.

(c.3.1.1)

There existst∈{m2l+1,…,mn3-2k} such thatGt?{1,2,3,4,5}. Without loss of generality, we assume thatGm2l+1={1,2,3}. Then for anyt∈{m2l+2,…,mn3-2k}, we haveGt∈H4∪H5∪H6, where

For simplicity, defineH:={Gm2l+1,…,Gmn3-2k}. We have the following 7 cases.

(c.3.1.1.1)H∩H4≠?,H∩H5=H∩H6=?.

(c.3.1.1.2)H∩H5≠?,H∩H4=H∩H6=?.

(c.3.1.1.3)H∩H6≠?,H∩H4=H∩H5=?.

(c.3.1.1.4)H∩H4≠?,H∩H5≠?,H∩H6=?.

(c.3.1.1.5)H∩H4≠?,H∩H6≠?,H∩H5=?.

(c.3.1.1.6)H∩H5≠?,H∩H6≠?,H∩H4=?.

(c.3.1.1.7)H∩H4≠?,H∩H5≠?,H∩H6≠?.

By the analysis in (1.2.1.2)(c.3.1), we need only to consider the first four cases (c.3.1.1.1)-(c.3.1.1.4).

As to (c.3.1.1.1), by Lemma 1.1, we know that all the 4 elements in {1,2,3,4} belong to at least half of the sets inH. SinceHin4?{1,2,3,4,5}, we know that |Hin4∩{1,2,3,4}|≥3. Hence in this case, all the elements inHin4∩{1,2,3,4} belong to at least half of the sets inF.

As to (c.3.1.1.2) , by following the analysis in (c.3.1.1.1), we get that |Hin4∩{1,2,3,5}|≥3 and all the elements inHin4∩{1,2,3,5} belong to at least half of the sets inF.

As to (c.3.1.1.3), by Lemma 1.1, we know that all the 4 elements in {1,2,3,6} belong to at least half of the sets inH. We have the following 3 subcases.

(c.3.1.1.3-1)H∩H6=1. TakeH∩H6={{1,2,6}} for example. ByHin4?{1,2,3,4,5}, we know thatHin4∈{{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}.IfHin4={1,2,3,4}, then {1,2,6}∪{1,2,3,4}={1,2,3,4,6}∈G5={{1,2,3,4,5}}. It is impossible. Similarly, ifHin4∈{{1,2,3,5},{1,2,4,5}}, it is impossible. IfHin4∈{{1,3,4,5},{2,3,4,5}}, thenHin4∪{1,2,6}=M6. Now all the 3 elements in {1,2,3} belong to at least half of the sets inF.

(c.3.1.1.3-2)H∩H6=2. TakeH∩H6={{1,2,6},{1,3,6}} for example. By following analysis in (c.3.1.1.3-1), we get that all the 3 elements in {1,2,3} belong to at least half of the sets inF.

(c.3.1.1.3-3)H∩H6=3. NowH∩H6={{1,2,6},{1,3,6},{2,3,6}}. In this case, byG5={{1,2,3,4,5}}, we must haveHin4={1,3,4,5}. It is easy to check that in this case all the 3 elements in {1,2,3} belong to at least half of the sets inF.

(c.3.1.2) For anyt∈{m2l+1,…,mn3-2k},Gt{1,2,3,4,5}. Without loss of generality, we assume thatGm2l+1={1,2,6}. Then by (iv), we know that for anyt=m2l+2,…,mn3-2k, we haveGt∈{{1,3,6},{1,4,6},{1,5,6},{2,3,6},{2,4,6},{2,5,6}}.Without loss of generality, we assume that {1,3,6}∈{Gm2l+2,…,Gmn3-2k}. Then byG5={{1,2,3,4,5}}, we need only to consider the following two subcases.

(c.3.1.1.2-1) {Gm2l+1,…,Gmn3-2k}={{1,2,6},{1,3,6}}.

(c.3.1.1.2-2) {Gm2l+1,…,Gmn3-2k}={{1,2,6},{1,3,6},{2,3,6}}.

As to (c.3.1.1.2-1), we know that all the 3 elements in {1,2,3} belong to at least 2 sets among the 4 sets in {{1,2,6},{1,3,6},Hin4,I1}. Hence in this case, all the 3 elements in {1,2,3} belong to at least half of the sets inF.

As to (c.3.1.1.2-2), we can easily know that all the 3 elements in {1,2,3} belong to at least 3 sets among the 5 sets in {{1,2,6},{1,3,6},{2,3,6},Hin4,I1}. Hence in this case, all the 3 elements in {1,2,3} belong to at least half of the sets inF.

(c.3.2)Hin4{1,2,3,4,5}. ThenHin4∪{1,2,3,4,5}=M6. By following the analysis in (c.3.1), we can show that there exist 3 elements inM6which belong to at least half of the sets inF. We omit the details.

(1.2.3) We can decomposeG4into two disjoint parts {Hi1,…,Hi2k} and {Hi2k+1,…,Hin4}, where {i1,…,in4}={1,…,n4},n4-2k≥2, and

(i)Hi1∪Hi2=…=Hi2k-1∪Hi2k=M6;

(ii) for any two different indexes {i,j} from {i2k+1,…,in4}, we haveHi∪Hj=I1={1,2,3,4,5}.

Then all the 6 elements inM6belong to at least half of the sets in {Hi1,…,Hi2k}. By Lemma 1.1, we know that all the 5 elements in {1,2,3,4,5} belong to at leastn3-2k-1 set(s) in {Hi2k+1,…,Hin4} and thus belong to at least half of the sets in {Hi2k+1,…,Hin4}.

(1.2.3.1)n3=1. NowG3={G1}. Note that all the 5 elements inI1={1,2,3,4,5} belong to at least one of the two setsG1andI1. Then we obtain that all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(1.2.3.2)n3≥2. Now for anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj=I1={1,2,3,4,5} or |Gi∪Gj|=4.

(b)n3is an odd number and there exists a permutation (j1,…,jn3) of (1,…,n3) such thatGj1∪Gj2=…=Gjn3-2∪Gjn3-1=M6. Then all the 6 elements inM6belong to half of the sets in {Gj1,…,Gjn3-1}. Note that all the 5 elements inI1={1,2,3,4,5} belong to at least one of the two setsGjn3andI1. Then we obtain that all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(i)Gj1∪Gj2=…=Gj2k-1∪Gj2k=M6;

(ii) for any two different indexes {i,j} from {j2k+1,…,jn3},Gi∪Gj=I1={1,2,3,4,5} or |Gi∪Gj|=4.

Then all the 6 elements inM6belong to half of the sets in {Gj1,…,Gj2k}.

(c.1)n3-2kis an even number and there exists a permutation (m1,…,mn3-2k) of (j2k+1,…,jn3) such thatGm1∪Gm2=…=Gmn3-2k-1∪Gmn3-2k={1,2,3,4,5}. In this case, we get that all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(c.2)n3-2kis an odd number and there exists a permutation (m1,…,mn3-2k) of (j2k+1,…,jn3) such thatGm1∪Gm2=…=Gmn3-2k-2∪Gmn3-2k-1={1,2,3,4,5}. Then all the 5 elements in {1,2,3,4,5} belong to at least half of the sets in {Gm1,…,Gmn3-2k-1}. Note that all the 5 elements inI1={1,2,3,4,5} belong to at least one of the two setsGmn3-2kandI1. Then we obtain that all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inF.

(c.3) We can decompose {Gj2k+1,…,Gjn3} into two disjoint parts {Gm1,…,Gm2l} and {Gm2l+1,…,Gmn3-2k}, where {m1,…,mn3-2k}={j2k+1,…,jn3},n3-2k-2l≥2, and

(iii)Gm1∪Gm2=…=Gm2l-1∪Gm2l={1,2,3,4,5};

(iv) for any two different indexes {i,j} from {m2l+1,…,mn3-2k},Gi∪Gj∈G4.

Then all the 5 elements in {1,2,3,4,5} belong to at least half of the sets in {Gm1,…,Gm2l}. By following the analysis in (1.2.1.2)(c.3), we can get that there exist 3 elements inM6which belong to at least half of the sets inF.

(2.1)n4=1. NowG4={H1}. Without loss of generality, we assume thatH1={1,2,3,4}.

(2.1.1)n3=1. NowG3={G1}. In this case, all the elements inG1∪H1belong to at least half of the sets inG3∪G4.

(2.1.2)n3≥2. Now for anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj∈G5orGi∪Gj=H1.

(2.1.2.1)n3is an even number and there exists a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-1∪Gin3=M6. Then all the 6 elements inM6belong to half of the sets inG3. Hence in this case all the 4 elements inI1belong to at least half of the sets inG3∪G4.

(2.1.2.2)n3is an odd number and there exists a permutation (i1,…,in3) of (1,…,n3) such thatGi1∪Gi2=…=Gin3-2∪Gin3-1=M6. Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gin3-1}. In this case, all the elements inGi3∪I1belong to at least half of the sets inG3∪G4.

(2.1.2.3) We can decomposeG3into two disjoint parts {Gi1,…,Gi2k} and {Gi2k+1,…,Gin3}, where {i1,…,in3}={1,…,n3},n3-2k≥2, and

(i)Gi1∪Gi2=…=Gi2k-1∪Gi2k=M6;

(ii) for any two different indexes {i,j} from {i2k+1,…,in3},Gi∪Gj=H1={1,2,3,4} orGi∪Gj∈G5.

Then all the 6 elements inM6belong to half of the sets in {Gi1,…,Gi2k}.

(a)n3-2kis an even number and there exists a permutation (j1,…,jn3-2k) of (i2k+1,…,in3) such thatGj1∪Gj2=…=Gjn3-2k-1∪Gjn3-2k=H1={1,2,3,4}. Then all the 4 elements in {1,2,3,4} belong to at least half of the sets in {Gi2k+1,…,Gin3} and thus all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

(b)n3-2kis an odd number and there exists a permutation (j1,…,jn3-2k) of (i2k+1,…,in3) such thatGj1∪Gj2=…=Gjn3-2k-2∪Gjn3-2k-1=H1={1,2,3,4}. Then all the 4 elements in {1,2,3,4} belong to at least half of the sets in {Gj1,…,Gjn3-2k-1}. Note that all the the 4 elements in {1,2,3,4} belong to at least one of the two setsGjn3-2kand {1,2,3,4}. Then we get that all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

(c) We can decompose {Gi2k+1,…,Gin3} into two disjoint two parts {Gj1,…,Gj2l} and {Gj2l+1,…,Gjn3-2k}, where {j1,…,jn3-2k}={i2k+1,…,in3},n3-2k-2l≥2, and

(iii)Gj1∪Gj2=…=Gj2l-1∪Gj2l={1,2,3,4};

(iv) for any two different indexes {i,j} from {j2l+1,…,jn3-2k}, we haveGi∪Gj∈G5.

Then all the 4 elements in {1,2,3,4} belong to at least half of the sets in {Gj1,…,Gj2l}. For simplicity, defineH:={Gj2l+1,…,Gjn3-2k}. We have the following two subcases:

(c.1) There existsm∈{j2l+1,…,jn3-2k} such thatGm?{1,2,3,4}. Without loss of generality, we assume thatGj2l+1={1,2,3}. Then for anym=j2l+2,…,jn3-2k, we haveGm∈H4,5∪H4,6∪H5,6, where

Since |{1,4,5}∪{2,4,5}|=|{1,4,5}∪{3,4,5}|=|{2,4,5}∪{3,4,5}|=4, we get that |H∩H4,5|≤1. Similarly, we have |H∩H4,6|≤1,|H∩H5,6|≤1. Hence we need only to consider the following 7 cases.

(c.1.1) |H∩H4,5|=1,|H∩H4,6|=|H∩H5,6|=0.

(c.1.2) |H∩H4,6|=1,|H∩H4,5|=|H∩H5,6|=0.

(c.1.3) |H∩H5,6|=1,|H∩H4,5|=|H∩H4,6|=0.

(c.1.4) |H∩H4,5|=|H∩H4,6|=1,|H∩H5,6|=0.

(c.1.5) |H∩H4,5|=|H∩H5,6|=1,|H∩H4,6|=0.

(c.1.6) |H∩H4,6|=|H∩H5,6|=1,|H∩H4,5|=0.

(c.1.7) |H∩H4,5|=|H∩H4,6|=|H∩H5,6|=1.

As to (c.1.1), takeH∩H4,5={{1,4,5}} for example. NowH={{1,2,3},{1,4,5}}. Note that all the 4 elements in {1,2,3,4} belong to at least two sets among the three sets in {{1,2,3},{1,4,5},{1,2,3,4}}. Then we get that in this case, all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

As to (c.1.2), by following the analysis to (c.1.1), we get that all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

As to (c.1.3), by following the analysis to (c.1.1), we get that all the 3 elements in {1,2,3} belong to at least half of the sets inG3∪G4.

As to (c.1.4), takeH∩(H4,5∪H4,6)={{1,4,5},{2,4,6}} for example. NowH={{1,2,3},{1,4,5},{2,4,6}}. Note that all the 4 elements in {1,2,3,4} belong to at least two sets among the four sets in {{1,2,3},{1,4,5},{2,4,6},{1,2,3,4}}. Then we get that in this case, all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

As to (c.1.5), takeH∩(H4,5∪H4,6)={{1,4,5},{2,5,6}} for example. NowH={{1,2,3},{1,4,5},{2,5,6}}. Note that all the 4 elements in {1,2,3,4} belong to at least two sets among the four sets in {{1,2,3},{1,4,5},{2,5,6},{1,2,3,4}}. Then we get that in this case, all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

As to (c.1.6), takeH∩(H4,6∪H5,6)={{1,4,6},{2,5,6}} for example. NowH={{1,2,3},{1,4,6},{2,5,6}}. Note that all the 4 elements in {1,2,3,4} belong to at least two sets among the four sets in {{1,2,3},{1,4,6},{2,5,6},{1,2,3,4}}. Then we get that in this case, all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

As to (c.1.7), takeH∩H4,5={{1,4,5},{2,4,6},{3,5,6}} for example. NowH={{1,2,3},{1,4,5},{2,4,6},{3,5,6}}. Note that all the 4 elements in {1,2,3,4} belong to at least 3 sets among the 5 sets in {{1,2,3},{1,4,5},{2,4,6},{3,5,6},{1,2,3,4}}. Then we get that in this case, all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

(c.2) For anym∈{j2l+1,…,jn3-2k},Gm{1,2,3,4}. ThenH?H5∪H6∪H5,6, where

H5={{{1,2,5},{1,3,5},{1,4,5},{2,3,5},{2,4,5},{3,4,5}},
H6={{{1,2,6},{1,3,6},{1,4,6},{2,3,6},{2,4,6},{3,4,6}},
H5,6={{1,5,6},{2,5,6},{3,5,6},{4,5,6}}.

By (iv), we can easily get that

|H∩H5|≤2,|H∩H6|≤2,|H∩H5,6|≤1.

(c.2.1)H∩H5,6=Φ. Without loss of generality, we assume that {1,2,5}∈HandGj2l+1={1,2,5}. Then by (iv), we know that for anym∈{j2l+2,…,jn3-2k},Gm∈{{3,4,5},{1,3,6},{1,4,6},{2,3,6},{2,4,6}}. By (iv) again, we need only to consider the following 14 cases.

(c.2.1.1)H={{1,2,5},{3,4,5}}

(c.2.1.2)H={{1,2,5},{1,3,6}}

(c.2.1.3)H={{1,2,5},{1,4,6}}

(c.2.1.4)H={{1,2,5},{2,3,6}}

(c.2.1.5)H={{1,2,5},{2,4,6}}

(c.2.1.6)H={{1,2,5},{3,4,5},{1,3,6}}

(c.2.1.7)H={{1,2,5},{3,4,5},{1,4,6}}

(c.2.1.8)H={{1,2,5},{3,4,5},{2,3,6}}

(c.2.1.9)H={{1,2,5},{3,4,5},{2,4,6}}

(c.2.1.10)H={{1,2,5},{1,3,6},{2,4,6}}

(c.2.1.11)H={{1,2,5},{1,4,6},{2,3,6}}

(c.2.1.12)H={{1,2,5},{1,3,6},{2,4,6}}

(c.2.1.13)H={{1,2,5},{3,4,5},{1,3,6},{2,4,6}}

(c.2.1.14)H={{1,2,5},{3,4,5},{1,4,6},{2,3,6}}

As to (c.2.1.1), all the 4 elements in {1,2,3,4} belong to at least two sets among the three sets in {{1,2,5},{3,4,5},{1,2,3,4}}. Then we get that all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

As to (c.2.1.2) and (c.2.1.4), all the 3 elements in {1,2,3} belong to at least half of the sets inG3∪G4.

As to (c.2.1.3) and (c.2.1.5), all the 3 elements in {1,2,4} belong to at least half of the sets inG3∪G4.

As to (c.2.1.6), all the 4 elements in {1,2,3,4} belong to at least two sets among the four sets in {{1,2,5},{3,4,5},{1,3,6},{1,2,3,4}}. Then we get that all the 4 elements in {1,2,3,4} belong to at least half of the sets inG3∪G4.

As to (c.2.1.7)-(c.2.1.12), it is easy to check that all the 4 elements in {1,2,3,4} belong to at least two sets among the four sets inH∪{{1,2,3,4}} and thus belong to at least half of the sets inG3∪G4.

As to (c.2.1.13) and (c.2.1.14), it is easy to check that all the 4 elements in {1,2,3,4} belong to at least three sets among the 5 sets inH∪{{1,2,3,4}} and thus belong to at least half of the sets inG3∪G4.

(c.2.2)H∩H5,6≠Φ. Without loss of generality, we assume that {1,5,6}∈HandGj2l+1={1,5,6}. Then by (iv), we know that for anym∈{j2l+2,…,jn3-2k},Gm∈{{2,3,5},{2,4,5},{3,4,5},{2,3,6},{2,4,6},{3,4,6}}. By (iv) again, we need only to consider the following 3 cases.

(c.2.2.1) |H∩{{2,3,5},{2,4,5},{3,4,5}}|=1,|H∩{{2,3,6},{2,4,6},{3,4,6}}|=0.

(c.2.2.2) |H∩{{2,3,5},{2,4,5},{3,4,5}}|=0,|H∩{{2,3,6},{2,4,6},{3,4,6}}|=1.

(c.2.2.3) |H∩{{2,3,5},{2,4,5},{3,4,5}}|=1,|H∩{{2,3,6},{2,4,6},{3,4,6}}|=1.

As to (c.2.2.1), takeH∩{{2,3,5},{2,4,5},{3,4,5}}={{2,3,5}} for example. NowH={{1,5,6},{2,3,5}}. Now all the 3 elements in {1,2,3} belong to at least two sets among the three sets inH∪{{1,2,3,4}} and thus belong to at least half of the sets inG3∪G4.

As to (c.2.2.2), takeH∩{{2,3,6},{2,4,6},{3,4,6}}={{2,3,6}} for example. NowH={{1,5,6},{2,3,6}}. Now all the 3 elements in {1,2,3} belong to at least two sets among the three sets inH∪{{1,2,3,4}} and thus belong to at least half of the sets inG3∪G4.

As to (c.2.2.3), takeH={{1,2,5},{2,3,5},{2,4,6}} for example. Now all the 4 elements in {1,2,3,4} belong to at least two sets among the four sets inH∪{{1,2,3,4}} and thus belong to at least half of the sets inG3∪G4.

(2.2)n4≥2. For anyi,j=1,…,n4,i≠j, we haveHi∪Hj=M6orHi∪Hj∈G5.

(2.2.1)n4is an even number and there exists a permutation (i1,…,in4) of (1,…,n4) such thatHi1∪Hi2=…=Hin4-1∪Hin4=M6. Then all the 6 elements inM6belong to at least half of the sets inG4. Hence it is enough to show that there exist 3 elements inM6which belong to at least half of the sets inG3orG3∪G5.

(2.2.1.1)n3=1. NowG3={G1}, and all the 3 elements inG1satisfy the condition.

(2.2.1.2)n3=2. NowG3={G1,G2} and all the 3 elements inG1∪G2belong to at least one of the two sets inG3.

(2.2.1.3)n3≥3. For anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj∈G4∪G5.

(a)n3is an even number and there exists a permutation (j1,…,jn3) of (1,…,n3) such thatGj1∪Gj2=…=Gjn3-1∪Gjn3=M6. Then all the 6 elements inM6belong to half of the sets inG3.

(i)Gj1∪Gj2=…=Gj2k-1∪Gj2k=M6;

(ii) for any two different indexes {i,j} from {j2k+1,…,jn3},Gi∪Gj∈G4∪G5.

Then all the 6 elements inM6belong to half of the sets in {Gj1,…,Gj2k}. Without loss of generality, we assume thatGj2k+1={1,2,3}. For anyl=j2k+2,…,jn3, we haveGl∈{{1,2,4},{1,2,5},{1,2,6}, {1,3,4},{1,3,5},{1,3,6},{1,4,5},{1,4,6},{1,5,6},{2,3,4},{2,3,5},{2,3,6},{2,4,5},{2,4,6},{2,5,6},{3,4,5},{3,4,6},{3,5,6}}. For simplicity, denoteH={Gj2k+1,…,Gjn3}. By (ii), we know that |H|≤10. Then we have the following 9 cases:

(c.1) |H|=2. NowH={Gj2k+1,Gjn3} and all the elements inGj2k+1∪Gjn3belong to at least one of the two sets inHand thus belong to at least half of the sets inG3.

(c.2) |H|=3. (c.3) |H|=4.

(c.4) |H|=5. (c.5) |H|=6.

(c.6) |H|=7. (c.7) |H|=8.

(c.8) |H|=9. (c.9) |H|=10.

As to the cases (c.2)～(c.9), we only give the proof for (c.2), the proofs for the other cases are similar. We omit the details.

As to (c.2),H={Gj2k+1,Gj2k+2,Gjn3} and we have the following 4 cases:

(c.2.1) For any 2-element subset {i,j} of {j2k+1,j2k+2,jn3},Gi∪Gj∈G4andGj2k+1∪Gj2k+2∪Gjn3∈G4. Take H={{1,2,3},{1,2,4},{2,3,4}} for example. Now by Lemma 1.1. we know that all the 4 elements in {1,2,3,4} belong to at least 2 sets inHand thus belong to at least half of the sets inG3.

(c.2.2) For any 2-element subset {i,j} of {j2k+1,j2k+2,jn3},Gi∪Gj∈G4andGj2k+1∪Gj2k+2∪Gjn3∈G5. TakeH={{1,2,3},{1,2,4},{1,2,5}} for example. Now {1,2,3,4,5}∈G5and thus we have the following 3 cases.

(c.2.2.1)n5=1. ThenG5={{1,2,3,4,5}}. Now all the 5 elements in {1,2,3,4,5} belong to at least two sets among the 4 sets inH∪G5and thus belong to at least half of the sets inG3∪G5. (In fact, by the assumption thatn5≥2, we don’t need consider this case. We write it here for the analysis in the following (c.2.2.3)).

(c.2.2.2)n5=2. TakeG5={{1,2,3,4,5},{1,2,3,4,6}} for example. Now it easy to check that all the 4 elements in {1,2,3,4} belong to at least 3 sets among the 5 sets inH∪G5and thus belong to at least half of the sets inG3∪G5.

(c.2.2.3)n5≥3. Now by Lemma 1.1, we know that all the 6 elements inM6belong to at leastn5-2 set(s) inG5{{1,2,3,4,5}} and thus belong to at least half of the sets inG5{{1,2,3,4,5}}. Then by (c.2.2.1), we know that now all the 5 elements in {1,2,3,4,5} belong to at least half of the sets inG3∪G5.

(c.2.3) For any 2-element subset {i,j} of {j2k+1,j2k+2,jn3},Gi∪Gj∈G5. TakeH={{1,2,3},{1,4,5},{2,5,6}} for example. Now {{1,2,3,4,5},{1,2,3,5,6},{1,2,4,5,6}}?G5and thus we have the following 3 cases:

(c.2.3.1)n5=3. ThenG5={{1,2,3,4,5},{1,2,3,5,6},{1,2,4,5,6}}. Now all the 6 elements inM6belong to at least 3 sets among the 6 sets inH∪G5and thus belong to at least half of the sets inG3∪G5.

(c.2.3.2)n5=4. Without loss of generality, we assume that {1,2,3,4,6}∈G5. Then by the analysis in (c.2.3.1), we know that all the 5 elements in {1,2,3,4,6} belong to at least 4 sets among the 7 sets inH∪G5and thus belong to at least half of the sets inG3∪G5.

(c.2.3.3)n5≥5. By Lemma 1.1, we know that all the 6 elements inM6belong to at least |G5{{1,2,3,4,5},{1,2,3,5,6},{1,2,4,5,6}}|-1 set(s) inG5{{1,2,3,4,5},{1,2,3,5,6},{1,2,4,5,6}} and thus belong to at least half of the sets inG5{{1,2,3,4,5},{1,2,3,5,6},{1,2,4,5,6}}. Hence in this case, by (c.2.3.1), we know that all the 6 elements inM6belong to at least half of the sets inG3∪G5.

(c.2.4) |{{i,j}|{i,j}?{j2k+1,j2k+2,jn3},Gi∪Gj∈G5}|=2. TakeH={{1,2,3},{1,2,4},{1,5,6}} for example. Now {{1,2,3,5,6},{1,2,4,5,6}}?G5. By following the analysis in (c.2.2) and (c.2.3), we can get that there exist at least 3 elements inM6which belong to at least half of the sets inG3∪G5.

(c.2.5) |{{i,j}|{i,j}?{j2k+1,j2k+2,jn3},Gi∪Gj∈G5}|=1. TakeH={{1,2,3},{1,2,5},{2,5,6}} for example. Now {1,2,3,5,6}∈G5. By following the analysis in (c.2.2) and (c.2.3), we can get that there exist at least 3 elements inM6which belong to at least half of the sets inG3∪G5.

(2.2.2)n4is an odd number and there exists a permutation (i1,…,in4) of (1,…,n4) such thatHi1∪Hi2=…=Hin4-2∪Hin4-1=M6. Then all the 6 elements inM6belong to at least half of the sets in {Hi1,…,Hin4-1}. Hence it is enough to show that there exist 3 elements inM6which belong to at least half of the sets in {Hin4}∪G3or {Hin4}∪G3∪G5. Without loss of generality, we assume thatHin4={1,2,3,4}.

(2.2.2.1)n3=1. NowG3={G1}, and all the elements inHin4∪G1belong to at least one of the two sets in {Hin4}∪G3.

(2.2.2.2)n3≥2. For anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj∈G4∪G5.

(a)n3is an even number and there exists a permutation (j1,…,jn3) of (1,…,n3) such thatGj1∪Gj2=…=Gjn3-1∪Gjn3=M6. Then all the 4 elements inHin4belong to at least half of the sets in {Hin4}∪G3.

(i)Gj1∪Gj2=…=Gj2k-1∪Gj2k=M6;

(ii) for any two different indexes {i,j} from {j2k+1,…,jn3},Gi∪Gj∈G4∪G5.

Then all the 6 elements inM6belong to half of the sets in {Gj1,…,Gj2k}. We have the following two cases.

(c.1) There existsm∈{j2k+1,…,jn3} such thatGm∪{1,2,3,4}=M6. Without loss of generality, we assume thatGj2k+1={1,5,6}. Then for anyl=j2k+2,…,jn3, we haveGk∈{{1,2,4},{1,2,5},{1,2,6},{1,3,4},{1,3,5},{1,3,6},{1,4,5},{1,4,6},{2,3,5},{2,3,6},{2,4,5},{2,4,6},{2,5,6},{3,4,5},{3,4,6},{3,5,6}}.

(c.2) For anym∈{j2k+1,…,jn3},Gm∪{1,2,3,4}≠M6. Then {Gj2k+1,…,Gjn3}?{{1,2,3},{1,2,4},{1,2,5},{1,2,6},{1,3,4},{1,3,5},{1,3,6},{1,4,5},{1,4,6},{2,3,4},{2,3,5},{2,3,6},{2,4,5},{2,4,6},{3,4,5},{3,4,6}}.

As to (c.1) and (c.2), by following the analysis in (2.2.1), we get that there exist at least 3 elements inM6which belong to at least half of the sets in {Hin4}∪G3∪G5. We omit the details.

(1.2.3) We can decomposeG4into two disjoint parts {Hi1,…,Hi2k} and {Hi2k+1,…,Hin4}, where {i1,…,in4},n4-2k≥2, and

(i)Hi1∪Hi2=…=Hin4-1∪Hin4=M6;

(ii) for any two different indexes {i,j} from {i2k+1,…,in4},Hi∪Hj∈G5.

Then all the 6 elements inM6belong to at least half of the sets in {Hi1,…,Hi2k}. Without loss of generality, we assume thatHi2k+1={1,2,3,4}. Then by (ii), we get that for anyj=i2k+2,…,in4,Hj∈H5∪H6, whereH5={{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}}，H6={{1,2,3,6},{1,2,4,6},{1,3,4,6},{2,3,4,6}}. For simplicity, denoteH={Hi2k+1,…,Hin4}. Then we have the following 3 cases.

(2.2.3.1)H∩H5≠Φ,H∩H6=Φ. Now, we have the following 4 cases.

(a) |H∩H5|=1; (b) |H∩H5|=2,

In the following, we only give the proof for (a). The proofs for other cases are similar. We omit the details. Without loss of generality, we assume thatH∩H5={{1,2,3,5}} and thusH={{1,2,3,4},{1,2,3,5}}.

(a.1)n3=1. NowG3={G1}. Obviously, all the 3 elements in {1,2,3} belong to at least two sets among the three sets inH∪G3and thus belong to at least half of the sets inF.

(a.2)n3≥2. For anyi,j=1,…,n3,i≠j, we haveGi∪Gj=M6orGi∪Gj∈G4∪G5.

(a.2.1)n3is an even number and there exists a permutation (j1,…,jn3) of (1,…,n3) such thatGj1∪Gj2=…=Gjn3-1∪Gjn3=M6. Then all the 6 elements inM6belong to half of the sets inG3. Now all the 5 elements in {1,2,3,4,5} belong to at least one of the two sets inHand thus belong to at least half of the sets inF.

(a.2.2)n3is an odd number and there exists a permutation (j1,…,jn3) of (1,…,n3) such thatGj1∪Gj2=…=Gjn3-2∪Gjn3-1=M6. Then all the 6 elements inM6belong to half of the sets in {Gj1,…,Gjn3-1}. Now, all the 3 elements in {1,2,3} belong to at least two sets among the three sets inH∪{Gjn3} and thus belong to at least half of the sets inF.

(a.2.3) we can decomposeG3into two disjoint parts {Gj1,…,Gj2k} and {Gj2k+1,…,Gjn3}, where {j1,…,jn3}={1,…,n3},n3-2k≥2, and

(i)Gj1∪Gj2=…=Gj2k-1∪Gj2k=M6;

(ii) for any two different indexes {i,j} from {j2k+1,…,jn3},Gi∪Gj∈G4∪G5.

Then all the 6 elements inM6belong to half of the sets in {Gj1,…,Gj2k}. Hence in this case, it is enough to show that there exist at least 3 elements inM6which belong to at least half of the sets inH∪{Gj2k+1,…,Gjn3} orH∪{Gj2k+1,…,Gjn3}∪G5, whereH={{1,2,3,4},{1,2,3,5}}.

(a.2.3.1) There existsm∈{j2k+1,…,jn3} such thatGm={1,2,3}={1,2,3,4}∪{1,2,3,5}. Without loss of generality, we assume thatGj2k+1={1,2,3}.

(a.2.3.2) There existsm∈{j2k+1,…,jn3} such thatGm?{1,2,3,4} butGm{1,2,3,5} and for anym∈{j2k+1,…,jn3},Gm≠{1,2,3}. Without loss of generality, we assume thatGj2k+1={1,2,4}.

(a.2.3.3) There existsm∈{j2k+1,…,jn3} such thatGm?{1,2,3,5} butGm{1,2,3,4} and for anym∈{j2k+1,…,jn3},Gm≠{1,2,3}. Without loss of generality, we assume thatGj2k+1={1,2,5}.

(a.2.3.4) For anym∈{j2k+1,…,jn3},Gm{1,2,3,4} andGm{1,2,3,5}. NowH?{{1,2,6},{1,3,6},{1,4,5},{1,4,6},{1,5,6},{2,3,6},{2,4,5},{2,4,6},{2,5,6},{3,4,5},{3,4,6},{3,5,6},{4,5,6}}.

For the above 4 cases, by following the proof in (2.2.1.3), we can get that there exist at least 3 elements inM6which belong to at least half of the sets inH∪{Gj2k+1,…,Gjn3}∪G5and thus belong to at least half of the sets inF.

(2.2.3.2)H∩H6≠?,H∩H5=?. The proof is similar to (2.2.3.1). We omit the details.

(2.2.3.3)H∩H5≠?,H∩H6≠?. Without loss of generality, we assume that {1,2,3,5}∈H∩H5, then by (ii) we know thatH∩H6={{1,2,3,6}} andH∩H5={{1,2,3,5}}. NowH={{1,2,3,4},{1,2,3,5},{1,2,3,6}}. By following the proof for (2.2.3.1), we get that there exist at least 3 elements inM6which belong to at least half of the sets inF.