Families of Subsets Without a Given Poset in the Interval Chains

MaRDI QIDQ6273081zbMATH OpenFDO

Authors Junyi Guo, Fei-Huang Chang, Hongbin Chen, Wei-Tian Li

Publication date 2 May 2016

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: For two posets $P$ and $Q$, we say $Q$ is $P$-free if there does not exist any order-preserving injection from $P$ to $Q$. The speical case for $Q$ being the Boolean lattice $B_n$ is well-studied, and the optiamal value is denoted as $lanp$. Let us define $La(Q,P)$ to be the largest size of any $P$-free subposet of $Q$. In this paper, we give an upper bound for $La(Q,P)$ when $Q$ is a double chain and $P$ is any graded poset, which is better than the previous known upper bound, by means of finding the indpendence number of an auxiliary graph related to $P$. For the auxiliary graph, we can find its independence number in polynomial time. In addition, we give methods to construct the posets satisfying the Griggs-Lu conjecture.

This page was built for publication: Families of Subsets Without a Given Poset in the Interval Chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6273081)