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

The Saturation Spectrum for Antichains of Subsets

  • Published:
Order Aims and scope Submit manuscript

Abstract

Extending a classical theorem of Sperner, we characterize the integers m such that there exists a maximal antichain of size m in the Boolean lattice Bn, that is, the power set of \([n]:=\{1,2,\dots ,n\}\), ordered by inclusion. As an important ingredient in the proof, we initiate the study of an extension of the Kruskal-Katona theorem which is of independent interest. For given positive integers t and k, we ask which integers s have the property that there exists a family \(\mathcal F\) of k-sets with \(|{\mathcal {F}}|=t\) such that the shadow of \(\mathcal {F}\) has size s, where the shadow of \(\mathcal F\) is the collection of (k − 1)-sets that are contained in at least one member of \(\mathcal F\). We provide a complete answer for \(t\leqslant k+1\). Moreover, we prove that the largest integer which is not the shadow size of any family of k-sets is \(\sqrt 2k^{3/2}+\sqrt [4]{8}k^{5/4}+O(k)\).

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

Data Availability

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

References

  1. Anderson, I.: Combinatorics of Finite Sets. Dover Publications, Mineola, N.Y (2002)

    MATH  Google Scholar 

  2. Barefoot, C., Casey, K., Fisher, D., Fraughnaugh, K., Harary, F.: Size in maximal triangle-free graphs and minimal graphs of diameter 2. Discrete Math. 138(1-3), 93–99 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  3. Dutton, R.D., Brigham, R.C.: Computationally efficient bounds for the Catalan numbers. European J. Combinatorics 7(3), 211–213 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  4. Faudree, J.R., Faudree, R.J., Schmitt, J.R.: A survey of minimum saturated graphs. Electr. J. Combinatorics, vol. 1000 (2011)

  5. Frankl, P., Matsumoto, M., Ruzsa, I. Z., Tokushige, N.: Minimum shadows in uniform hypergraphs and a generalization of the Takagi function. J. Combinatorial Theory Series A 69(1), 125–148 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  6. Gerbner, D., Keszegh, B., Lemons, N., Palmer, C., Pávölgyi, D., Patkós, B.: Saturating Sperner families. Graphs Combinatorics 29(5), 1355–1364 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  7. Gould, R.J.: Developments on saturated graphs. In: Chung, F., Graham, R., Hoffman, F., Mullin, R.C., Hogben, L., West, D.B. (eds.) 50 years of combinatorics, graph theory, and computing. Taylor & Francis, Chap. 7, pp. 111–133 (2019)

  8. Griggs, J.R., Hartmann, S., Kalinowski, T., Leck, U., Roberts, I.T.: Minimum weight flat antichains of subsets. Order 38(3), 441–453 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  9. Griggs, J.R., Kalinowski, T., Leck, U., Roberts, I.T., Schmitz, M.: Sizes of maximal flat antichains of subsets. In preparation (2022)

  10. Grüttmüller, M., Hartmann, S., Kalinowski, T., Leck, U., Roberts, I.T.: Maximal flat antichains of minimum weight. Electr. J. Combinatorics 16 (1), R69 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Kalinowski, T., Leck, U., Roberts, I.T.: Maximal antichains of minimum size. Electr. J. Combinatorics 20(2), P3 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  12. Katona, G.O.H.: A theorem of finite sets. In: Erdős, P., Katona, G.O.H. (eds.) Theory of graphs. Akadémiai Kiadó, pp. 187–207 (1968)

  13. Keszegh, B., Lemons, N., Martin, R.R., Pálvölgyi, D., Patkós, B.: Induced and non-induced poset saturation problems. J. Combinatorial Theory Series A 184, 105497 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kruskal, J.B.: The number of simplices in a complex. In: Bellman, R.E. (ed.) Mathematical optimization techniques. University of California Press, pp. 251–278 (1963)

  15. Leck, U.: Extremalprobleme für den Schatten in Posets. Ph.D. Thesis, Freie Universität Berlin (1995)

    Google Scholar 

  16. Lovász, L.: Combinatorial problems and exercises, Problem 13.31, Amsterdam: North-Holland (1979)

  17. Morrison, N., Noel, J.A., Scott, A.: On saturated k-Sperner systems. Electr. J. Combinatorics, vol. 21(3) (2014)

  18. Patkós, B.: Supersaturation and stability for forbidden subposet problems. J. Combinatorial Theory Series A 136, 220–237 (2015)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We are grateful to two anonymous referees for their constructive comments which helped us to improve the presentation of the arguments, and for pointing out references which were useful for putting our results into the context of related work.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of South Carolina, Columbia, SC, 29208, USA

    Jerrold R. Griggs

  2. Fakultät für angewandte Computer- und Biowissenschaften, Hochschule Mittweida, Germany

    Thomas Kalinowski

  3. School of Science and Technology, University of New England, Armidale, NSW, Australia

    Thomas Kalinowski

  4. Institut für Mathematik, Europa-Universität Flensburg, Flensburg, Germany

    Uwe Leck & Michael Schmitz

  5. College of Education, Charles Darwin University, Darwin, NT, Australia

    Ian T. Roberts

Authors
  1. Jerrold R. Griggs
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Kalinowski
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Uwe Leck
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ian T. Roberts
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Michael Schmitz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Uwe Leck.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The research of Jerrold Griggs is supported in part by grant #282896 from the Simons Foundation.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Griggs, J.R., Kalinowski, T., Leck, U. et al. The Saturation Spectrum for Antichains of Subsets. Order 40, 537–574 (2023). https://doi.org/10.1007/s11083-022-09622-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11083-022-09622-6

Keywords

Search

Navigation