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

Profile polytopes of some classes of families

  • Original Paper
  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

The profile vector of a family F of subsets of an n-element set is (f 0,f 1,…,f n ) where f i denotes the number of the i-element members of F. The extreme points of the set of profile vectors for some class of families has long been studied. In this paper we introduce the notion of k-antichainpair families and determine the extreme points of the set of profile vectors of these families, extending results of Engel and P.L. Erdős regarding extreme points of the set of profile vectors of intersecting, co-intersecting Sperner families. Using this result we determine the extreme points of the set of profile vectors for some other classes of families, including complement-free k-Sperner families and self-complementary k-Sperner families. We determine the maximum cardinality of intersecting k-Sperner families, generalizing a classical result of Milner from k = 1.

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. A. Bernáth, D. Gerbner: Chain intersecting families, Graphs and Combinatorics 23 (2007), 353–366.

    Article  MathSciNet  MATH  Google Scholar 

  2. K. Engel: Sperner Theory, Encyclopedia of Mathematics and its Applications, 65. Cambridge University Press, Cambridge (1997)

    Google Scholar 

  3. K. Engel, P. L. Erdős: Sperner families satisfying additional conditions and their convex hulls, Graphs Combin. 5 (1989), 47–56.

    Article  MathSciNet  MATH  Google Scholar 

  4. P. L. Erdős, P. Frankl, G. O. H. Katona: Intersecting Sperner families and their convex hulls, Combinatorica 4 (1984), 21–34.

    Article  MathSciNet  Google Scholar 

  5. P. L. Erdős, P. Frankl, G. O. H. Katona: Extremal hypergraph problems and convex hulls, Combinatorica 5 (1985), 11–26.

    Article  MathSciNet  Google Scholar 

  6. D. Gerbner, B. Patkós: l-chain profile vectors, SIAM Journal on Discrete Mathematics 22 (2008), 185–193.

    Article  MathSciNet  MATH  Google Scholar 

  7. P. Frankl, G. O. H. Katona: Polytopes determined by hypergraph classes, European J. Combin. 63 (1985), 233–243.

    MathSciNet  Google Scholar 

  8. G. O. H. Katona: A Simple proof of the Erdős-Chao Ko-Rado theorem, J. Comb. Theory (B) 13 (1972), 183–184.

    Article  MathSciNet  MATH  Google Scholar 

  9. E. C. Milner: A combinatorial theorem on systems of sets, J. London Math. Soc. 43 (1968), 204–206.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Hungarian Academy of Sciences, Alfréd Rényi Institute of Mathematics, P.O.B. 127, Budapest, H-1364, Hungary

    Dániel Gerbner

Authors
  1. Dániel Gerbner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dániel Gerbner.

Additional information

Research supported by Hungarian Science Foundation EuroGIGA Grant OTKA NN 102029

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gerbner, D. Profile polytopes of some classes of families. Combinatorica 33, 199–216 (2013). https://doi.org/10.1007/s00493-013-2917-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-013-2917-y

Mathematics Subject Classification (2000)

Search

Navigation