Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/45991
Title: | Cross-intersecting sub-families of hereditary families |
Authors: | Borg, Peter |
Keywords: | Intersection theory (Mathematics) Set theory Extremal problems (Mathematics) |
Issue Date: | 2012 |
Publisher: | Elsevier |
Citation: | Borg, P. (2012). Cross-intersecting sub-families of hereditary families. Journal of Combinatorial Theory, Series A, 119(4), 871-881. |
Abstract: | Families A 1,A 2,...,A k of sets are said to be cross-intersecting if for any i and j in {1, 2, ..., k} with i≠j, any set in Ai intersects any set in Aj. For a finite set X, let 2 X denote the power set of X (the family of all subsets of X). A family H is said to be hereditary if all subsets of any set in H are in H; so H is hereditary if and only if it is a union of power sets. We conjecture that for any non-empty hereditary sub-family H≠{θ} of 2 X and any k≥|X|+1, both the sum and the product of sizes of k cross-intersecting sub-families A 1,A 2,...,A k (not necessarily distinct or non-empty) of H are maxima if A 1=A 2=⋯=A k=S for some largest star S of H (a sub-family of H whose sets have a common element). We prove this for the case when H is compressed with respect to an element x of X, and for this purpose we establish new properties of the usual compression operation. As we will show, for the sum, the condition k≥|X|+1 is sharp. However, for the product, we actually conjecture that the configuration A 1=A 2=⋯=A k=S is optimal for any hereditary H and any k≥2, and we prove this for a special case. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/45991 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Cross-intersecting_sub-families_of_hereditary_families_2012.pdf Restricted Access | 196.35 kB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.