The maximum sum and maximum product of sizes of cross-intersecting\n families

2011/02/03 by Peter Borg, Borg, Peter
Computer Science · Engineering · Mathematics · #05D05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1102.0667

openalex publication_date 2011/02/03 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28

Abstract

We say that a set A \t-intersects a set B if A and B have at\nleast t common elements. A family \A of sets is said to be\n\t-intersecting if each set in \A t-intersects any other\nset in \A. Families \A₁, \A₂, ...,\n\A_k are said to be \cross-t-intersecting if for any i and\nj in 1, 2, ..., k with i \≠ j, any set in \A_i\nt-intersects any set in \A_j. We prove that for any finite family\n\F that has at least one set of size at least t, there exists an\ninteger \κ \≤ |\F| such that for any k \≥ \κ, both the\nsum and the product of sizes of any k cross-t-intersecting sub-families\n\A₁, ..., \A_k (not necessarily distinct or non-empty) of\n\F are maxima if \A₁ = ... = \A_k = \L\nfor some largest t-intersecting sub-family \L of \F. We\nthen study the smallest possible value of \κ and investigate the case k\n< \κ; this includes a cross-intersection result for straight lines that\ndemonstrates that it is possible to have \F and \κ such that\nfor any k < \κ, the configuration \A₁ = ... = \A_k =\n\L is neither optimal for the sum nor optimal for the product. We\nalso outline solutions for various important families \F, and we\nprovide solutions for the case when \F is a power set.\n

Related

• The maximum product of sizes of cross-intersecting families
• The maximum product of sizes of cross-t-intersecting uniform families
• The maximum sum of sizes of cross-intersecting families of subsets of a set
• The maximum product of weights of cross-intersecting families
• The maximum sum of sizes of non-empty cross t-intersecting families