Gerbner, Dániel and Methuku, Abhishek and Tompkins, Casey (2017) Intersecting P-free families. JOURNAL OF COMBINATORIAL THEORY SERIES A, 151. pp. 61-83. ISSN 0097-3165
|
Text
1506.00864v1.pdf Download (204kB) | Preview |
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. © 2017 Elsevier Inc.
| Item Type: | Article |
|---|---|
| Additional Information: | N1 Funding details: MTA, Magyar Tudományos Akadémia N1 Funding text: We would like to thank the two anonymous referees for their careful reading of the manuscript and valuable comments. The research of all three authors was partially supported by the National Research, Development and Innovation Office NKFIH, grant K116769, and the research of the first author was also partially supported by the János Bolyai Research Scholarship of the Hungarian Academy of Sciences. |
| Uncontrolled Keywords: | SPERNER; Intersecting set family; Forbidden poset; butterfly; antichain |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 13 Oct 2017 10:52 |
| Last Modified: | 13 Oct 2017 10:52 |
| URI: | http://real.mtak.hu/id/eprint/65650 |
Actions (login required)
 |
Edit Item |
