Title of article :
Large -free and union-free subfamilies
Author/Authors :
Barلt، نويسنده , , Jلnos and Füredi، نويسنده , , Zoltلn and Kantor، نويسنده , , Ida and Kim، نويسنده , , Younjin and Patkَs، نويسنده , , Balلzs، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Pages :
4
From page :
101
To page :
104
Abstract :
For a property Γ and a family of sets F , let f ( F , Γ ) be the size of the largest subfamily of F having property Γ. For a positive integer m, let f ( m , Γ ) be the minimum of f ( F , Γ ) over all families of size m. A family F is said to be B d -free if it has no subfamily F ′ = { F I : I ⊆ [ d ] } of 2 d distinct sets such that for every I , J ⊆ [ d ] , both F I ∪ F J = F I ∪ J and F I ∩ F J = F I ∩ J hold. A family F is a-union free if F 1 ∪ ⋯ ∪ F a ≠ F a + 1 whenever F 1 , … , F a + 1 are distinct sets in F . We verify a conjecture of Erdős and Shelah that f ( m , B 2 -free ) = Θ ( m 2 / 3 ) . We also obtain lower and upper bounds for f ( m , B d -free ) and f ( m , a -union free ) .
Keywords :
Extremal set theory , union-free subfamilies , B d -free subfamilies
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
2011
Journal title :
Electronic Notes in Discrete Mathematics
Record number :
1455774
Link To Document :
بازگشت