Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Published:
Order Aims and scope Submit manuscript

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 \({\mathrm La}(n,P)\le \frac {1}{2}(|P|+h-2)\left (\begin {array}{c}n \\ \lfloor {n/2}\rfloor \end {array}\right )\) for any finite poset P of height h. This paper elaborates their double-chain method to obtain a new upper bound

$${\mathrm La}(n,P)\le \left( \frac{|P|+h-\alpha(G_{P})-2}{2}\right)\left( \begin{array}{c}n \\ \lfloor{\frac{n}{2}}\rfloor\end{array}\right) $$

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

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bukh, B.: Set families with a forbidden poset. Elect. J. Combin. 16, R142 (2009). 11p.

    MathSciNet  MATH  Google Scholar 

  2. Burcsi, P., Nagy, D.T.: The method of double chains for largest families with excluded subposets. Elect. J. Graph Theory Appl. 1, 40–49 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Chen, H.-B., Li, W.-T.: A note on the largest size of families of sets with a forbidden poset. Order 31, 137–142 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cook, S.A.: The complexity of theorem-proving procedures. In: Conference Record of Third Annual ACM symposium on Theory of Computing, pp. 151–158. The Association for Computing Machinery, New York (1971)

  5. DeBonis, A., Katona, G.O.H.: Largest families without an r-fork. Order 24, 181–191 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  6. DeBonis, A., Katona, G.O.H., Swanepoel, K.J.: Largest family without A ∪ B ⊂ C ∩ D. J. Comb. Theory (Ser. A) 111, 331–336 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Erdős, P.: On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 51, 898–902 (1945)

    Article  MathSciNet  MATH  Google Scholar 

  8. Griggs, J.R., Katona, G.O.H.: No four subsets forming an N. J. Comb. Theory (Ser. A) 115, 677–685 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  9. Griggs, J.R., Li, W.-T.: Poset-free families and Lubell-boundedness. J. Comb. Theory (Ser. A) 134, 166–187 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  10. Griggs, J.R., Li, W.-T., Lu, L.: Diamond-free families. J. Comb. Theory (Ser. A) 119, 310–322 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  11. Griggs, J.R., Lu, L.: On families of subsets with a forbidden subposet. J. Comb. Theory (Ser. A) 119, 310–322 (2012)

    Article  Google Scholar 

  12. Grósz, D., Methuku, A., Tompkins, C.: An improvement of the general bound on the largest family of subsets avoiding a subposet P Order Pubished online: 22 March 2016 https://doi.org/10.1007/s11083-016-9390-3

  13. Grósz, D., Methuku, A., Tompkins, C.: An upper bound on the size of diamond-free families of sets, arXiv:1601.06332

  14. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

  15. Katona, G.O.H., Tarján, T.G.: Extremal problems with excluded subgraphs in the n-cube. In: Borowiecki, M., Kennedy, J.W., Syso, M.M. (eds.) Graph Theory, Łagów, 1981, Lecture Notes in Math., vol. 1018, pp. 84–93. Springer, Berlin (1983)

  16. Kramer, L., Martin, R.R., Young, M.: On diamond-free subposets of the Boolean lattice. J. Comb Theory (Ser. A) 120, 545–560 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  17. Lu, L.: On crown-free famililes of subsets. J. Comb. Theory (Ser. A) 126, 216–231 (2014)

    Article  MATH  Google Scholar 

  18. Lubell, D.: A short proof of Sperner’s lemma. J. Combin. Theory 1, 299 (1966)

    Article  MathSciNet  MATH  Google Scholar 

  19. Methuku, A., Tompkins, C.: Exact forbidden subposet results using chain decompositions of the cycle. Elect. J. Combinatorics 22, 4.29 (2015)

    MathSciNet  MATH  Google Scholar 

  20. Mirsky, L.: A dual of Dilworths decomposition theorem. Am. Math. Mon. 78(8), 876–877 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  21. Pálvőlgyi, D.: Weak embeddings of posets to the Boolean lattice, arXiv:160608226

  22. Patkós, B.: Induced and non-induced forbidden subposet problems. Elect. J. Combinatorics 22, 1.30 (2015)

    MathSciNet  MATH  Google Scholar 

  23. Sarkis, G., Shahriari, S., PCURC: Diamond-free subsets in the linear lattices. Order 31, 421–43 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  24. Sperner, E.: Ein Satz über Untermengen einer endlichen Menge. Math. Z. 27, 544–548 (1928)

    Article  MathSciNet  MATH  Google Scholar 

  25. Thanh, H.T.: An extremal problem with excluded subposets in the Boolean lattice. Order 15, 51–57 (1998)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to thank the anonymous reviewers for their valuable comments to improve the organization and presentation of this paper.

Author information

Authors and Affiliations

  1. Department of Mathematics, National Taiwan Normal University, Taipei, 11677, Taiwan

    Jun-Yi Guo

  2. Division of Preparatory Programs for Overseas Chinese Students, National Taiwan Normal University, New Taipei, 24449, Taiwan

    Fei-Huang Chang

  3. Department of Applied Mathematics, Feng Chia University, Taichung, 40724, Taiwan

    Hong-Bin Chen

  4. Department of Applied Mathematics, National Chung Hsing University, Taichung, 40227, Taiwan

    Wei-Tian Li

Authors
  1. Jun-Yi Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fei-Huang Chang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hong-Bin Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wei-Tian Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wei-Tian Li.

Additional information

Jun-Yi Guo research was supported by MOST-104-2115-M-003-010.

Fei-Huang Chang research was supported by MOST-104-2115-M-003-008-MY2.

Hong-Bin Chen research was supported by MOST-105-2115-M-035-006-MY2.

Wei-Tian Li research was supported by MOST-103-2115-M-005-003-MY2.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Guo, JY., Chang, FH., Chen, HB. et al. Families of Subsets Without a Given Poset in Double Chains and Boolean Lattices. Order 35, 349–362 (2018). https://doi.org/10.1007/s11083-017-9436-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11083-017-9436-1

Keywords

Search

Navigation