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

doi:10.1007/s11083-017-9436-1

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^*

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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 boundLa(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).

Original language	English
Pages (from-to)	349-362
Number of pages	14
Journal	Order
Volume	35
Issue number	2
DOIs	https://doi.org/10.1007/s11083-017-9436-1
Publication status	Published - 2018 Jul 1

Keywords

Double counting
Extremal family
Graded poset
Interval chains
Poset-free families

ASJC Scopus subject areas

Algebra and Number Theory
Geometry and Topology
Computational Theory and Mathematics

Access to Document

10.1007/s11083-017-9436-1

Cite this

@article{44f9a8c99a2f4f109533660632dfb200,

title = "Families of Subsets Without a Given Poset in Double Chains and Boolean Lattices",

abstract = "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 boundLa(n,P)≤(|P|+h−α(GP)−22)(n⌊n2⌋)for any graded poset P, where α(GP) 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).",

keywords = "Double counting, Extremal family, Graded poset, Interval chains, Poset-free families",

author = "Guo, {Jun Yi} and Chang, {Fei Huang} and Chen, {Hong Bin} and Li, {Wei Tian}",

note = "Publisher Copyright: {\textcopyright} 2017, Springer Science+Business Media B.V.",

year = "2018",

month = jul,

day = "1",

doi = "10.1007/s11083-017-9436-1",

language = "English",

volume = "35",

pages = "349--362",

journal = "Order",

issn = "0167-8094",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Families of Subsets Without a Given Poset in Double Chains and Boolean Lattices

AU - Guo, Jun Yi

AU - Chang, Fei Huang

AU - Chen, Hong Bin

AU - Li, Wei Tian

PY - 2018/7/1

Y1 - 2018/7/1

N2 - 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 boundLa(n,P)≤(|P|+h−α(GP)−22)(n⌊n2⌋)for any graded poset P, where α(GP) 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).

AB - 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 boundLa(n,P)≤(|P|+h−α(GP)−22)(n⌊n2⌋)for any graded poset P, where α(GP) 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).

KW - Double counting

KW - Extremal family

KW - Graded poset

KW - Interval chains

KW - Poset-free families

UR - http://www.scopus.com/inward/record.url?scp=85028777159&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028777159&partnerID=8YFLogxK

U2 - 10.1007/s11083-017-9436-1

DO - 10.1007/s11083-017-9436-1

M3 - Article

AN - SCOPUS:85028777159

SN - 0167-8094

VL - 35

SP - 349

EP - 362

JO - Order

JF - Order

IS - 2

ER -

Families of Subsets Without a Given Poset in Double Chains and Boolean Lattices

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this