The method of double chains for largest families with excluded subposets

被引:13
作者
Burcsi, Peter [1 ]
Nagy, Daniel T. [2 ]
机构
[1] Eotvos Lorand Univ, Fac Informat, Dept Comp Algebra, Budapest, Hungary
[2] Eotvos Lorand Univ, Budapest, Hungary
关键词
excluded subposet; Lubell's function; double chain;
D O I
10.5614/ejgta.2013.1.1.4
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a given finite poset P, La (n, P) denotes the largest size of a family F of subsets of [n] not containing P as a weak subposet. We exactly determine La (n, P) for infinitely many P posets. These posets are built from seven base posets using two operations. For arbitrary posets, an upper bound is given for La (n, P) depending on vertical bar P vertical bar and the size of the longest chain in P. To prove these theorems we introduce a new method, counting the intersections of F with double chains, rather than chains.
引用
收藏
页码:40 / 49
页数:10
相关论文
共 8 条
[1]  
Bukh B, 2009, ELECTRON J COMB, V16
[2]   Largest family without A ∨ B ⊆ C ∧ D [J].
De Bonis, A ;
Katona, GOH ;
Swanepoel, KJ .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2005, 111 (02) :331-336
[3]   ON A LEMMA OF LITTLEWOOD AND OFFORD [J].
ERDOS, P .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1945, 51 (12) :898-902
[4]   Diamond-free families [J].
Griggs, Jerrold R. ;
Li, Wei-Tian ;
Lu, Linyuan .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2012, 119 (02) :310-322
[5]   On Families of Subsets With a Forbidden Subposet [J].
Griggs, Jerrold R. ;
Lu, Linyuan .
COMBINATORICS PROBABILITY & COMPUTING, 2009, 18 (05) :731-748
[6]  
Katona GOH, 2008, BOLYAI SOC MATH STUD, V17, P119
[7]  
Lubell D., 1966, J COMBIN THEORY, V1, P299, DOI [10.1016/S0021-9800(66)80035-2, DOI 10.1016/S0021-9800(66)80035-2]
[8]   A clause about subsets in a fiurts set [J].
Sperner, E .
MATHEMATISCHE ZEITSCHRIFT, 1928, 27 :544-548