Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/105072
Title: | Cross-intersecting non-empty uniform subfamilies of hereditary families |
Authors: | Borg, Peter |
Keywords: | Mathematics Intersection theory (Mathematics) Combinatorial analysis |
Issue Date: | 2019 |
Publisher: | Elsevier Ltd |
Citation: | Borg, P. (2019). Cross-intersecting non-empty uniform subfamilies of hereditary families. European Journal of Combinatorics, 78, 256-267. |
Abstract: | Two families A and B of sets are cross-t-intersecting if each set in A intersects each set in B in at least t elements. A family H is hereditary if for each set A in H, all the subsets of A are in H. Let H(r) denote the family of r-element sets in H. We show that for any integers t, r, and s with 1 ≤ t ≤ r ≤ s, there exists an integer c(r, s, t) such that the following holds for any hereditary family H whose maximal sets are of size at least c(r, s, t). If A is a nonempty subfamily of H(r) , B is a non-empty subfamily of H(s) , A and B are cross-t-intersecting, and |A| + |B| is maximum under the given conditions, then for some set I in H with t ≤ |I| ≤ r, either A = {A ∈ H(r) : I ⊆ A} and B = {B ∈ H(s) : |B ∩ I| ≥ t}, or r = s, t < |I|, A = {A ∈ H(r) : |A ∩ I| ≥ t}, and B = {B ∈ H(s) : I ⊆ B}. We give c(r, s, t) explicitly. The result was conjectured by the author for t = 1 and generalizes well-known results for the case where H is a power set. |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/105072 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Cross_intersecting_non_empty_uniform_subfamilies_of_hereditary_families_2019.pdf | 404.05 kB | Adobe PDF | View/Open |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.