Abstract
We study the problem of determining the size of the largest intersecting P-free family for a given partially ordered set (poset) P. In particular, we find the exact size of the largest intersecting B-free family where B is the butterfly poset and classify the cases of equality. The proof uses a new generalization of the partition method of Griggs, Li and Lu. We also prove generalizations of two well-known inequalities of Bollobás and Greene, Katona and Kleitman in this case. Furthermore, we obtain a general bound on the size of the largest intersecting P-free family, which is sharp for an infinite class of posets originally considered by Burcsi and Nagy, when n is odd. Finally, we give a new proof of the bound on the maximum size of an intersecting k-Sperner family and determine the cases of equality.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 61-83 |
| Number of pages | 23 |
| Journal | Journal of Combinatorial Theory. Series A |
| Volume | 151 |
| DOIs | |
| State | Published - Oct 1 2017 |
| Externally published | Yes |
Keywords
- Antichain
- Butterfly
- Forbidden poset
- Intersecting set family
- Sperner
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Fingerprint
Dive into the research topics of 'Intersecting P-free families'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS