Title of article
No four subsets forming an N
Author/Authors
Griggs، نويسنده , , Jerrold R. and Katona، نويسنده , , Gyula O.H.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2008
Pages
9
From page
677
To page
685
Abstract
We survey results concerning the maximum size of a family F of subsets of an n-element set such that a certain configuration is avoided. When F avoids a chain of size two, this is just Spernerʹs theorem. Here we give bounds on how large F can be such that no four distinct sets A , B , C , D ∈ F satisfy A ⊂ B , C ⊂ B , C ⊂ D . In this case, the maximum size satisfies ( n ⌊ n 2 ⌋ ) ( 1 + 1 n + Ω ( 1 n 2 ) ) ⩽ | F | ⩽ ( n ⌊ n 2 ⌋ ) ( 1 + 2 n + O ( 1 n 2 ) ) , which is very similar to the best-known bounds for the more restrictive problem of F avoiding three sets B , C , D such that C ⊂ B , C ⊂ D .
Keywords
Spernerיs theorem , Boolean lattice , Extremal set theory
Journal title
Journal of Combinatorial Theory Series A
Serial Year
2008
Journal title
Journal of Combinatorial Theory Series A
Record number
1531298
Link To Document