Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/75656
Title: | Cross-intersecting subfamilies of levels of hereditary families |
Authors: | Borg, Peter |
Keywords: | Mathematics Logic, Symbolic and mathematical Set theory Hypergraphs |
Issue Date: | 2020 |
Publisher: | Elsevier BV |
Citation: | Borg, P. (2020). Cross-intersecting subfamilies of levels of hereditary families. Discrete Mathematics, 343(8), 111900. |
Abstract: | A set A t-intersects a set B if A and B have at least t common elements. Families A1,A2, . . . ,Ak of sets are cross-t-intersecting if, for every i and j in {1, 2, . . . , k} with i ̸= j, each set in Ai t-intersects each set in Aj. An active problem in extremal set theory is to determine, for a given finite family F, the structure of k cross-t-intersecting subfamilies whose sum of sizes is largest. For a family H, the rth level H(r) of H is the family of sets in H of size r, and, for s ≤ r, H(s) is called a (≤ r)-level of H. We solve the problem for any union F of (≤ r)-levels of any union H of power sets of sets whose sizes are at least a certain integer n0, where n0 is independent of H and k but depends on r and t (dependence on r is inevitable, but dependence on t can be avoided). We show that there are only two possible optimal configurations. We also prove generalizations, whereby A1,A2, . . . ,Ak are not necessarily contained in the same union of levels. Erdős–Ko–Rado-type results follow, particularly the author’s analogous result for t-intersecting subfamilies of F. The problem for a level of a power set was solved for t = 1 by Hilton in 1977, and for any t by Wang and Zhang in 2011. This work draws inspiration from the Chvátal Conjecture and the Holroyd–Talbot Conjecture. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/75656 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Cross-intersecting_subfamilies_of_levels_of_hereditary_families_2020.pdf Restricted Access | 395.99 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.