Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/99120
標題: Families of Subsets Without a Given Poset in Double Chains and Boolean Lattices
作者: Jun-Yi Guo
Fei-Huang Chang
Hong-Bin Chen
Wei-Tian Li
李渭天
關鍵字: Extremal family;Poset-free families;Double counting;Interval chains;Graded poset
出版社: ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS
Project: Order, Volume 35, Issue 2, pp 349–362
摘要: 
Given a finite poset P, the intensively studied quantity La(n, P) denotes the largest size of a family of subsets of [n] not containing P as a weak subposet. Burcsi and Nagy (J. Graph Theory Appl. 1, 40–49 2013) proposed a double-chain method to get an upper bound La(n,P)≤12(|P|+h−2)(n⌊n/2⌋) for any finite poset P of height h. This paper elaborates their double-chain method to obtain a new upper bound
La(n,P)≤(|P|+h−α(GP)−22)(n⌊n2⌋)
for any graded poset P, where α(G P ) denotes the independence number of an auxiliary graph defined in terms of P. This result enables us to find more posets which verify an important conjecture by Griggs and Lu (J. Comb. Theory (Ser. A) 119, 310–322, 2012).
URI: http://hdl.handle.net/11455/99120
DOI: 10.1007/s11083-017-9436-1
Appears in Collections:應用數學系所

Show full item record
 

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.