The maximum product of sizes of cross-t-intersecting uniform families

2013/12/11 by Borg, Peter · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1312.3255

Abstract

We say that a set A t-intersects a set B if A and B have at least t common elements. Two families A and B are said to be cross-t-intersecting if each set in A t-intersects each set in B. For any positive integers n and r, let [n] \choose r denote the family of all r-element subsets of \1,2,…, n\. We show that for any integers r, s and t with 1 ≤ t ≤ r ≤ s, there exists an integer n₀(r,s,t) such that for any integer n ≥ n₀(r,s,t), if A ⊂ [n] \choose r and B ⊂ [n] \choose s such that A and B are cross-t-intersecting, then |A||B| ≤ n-t \choose r-tn-t \choose s-t, and equality holds if and only if for some T ∈ [n] \choose t, A = \A ∈ [n] \choose r \colon T ⊂ A\ and B = \B ∈ [n] \choose s \colon T ⊂ B\. This verifies a conjecture of Hirschorn.

Cited by

• The maximum product of sizes of cross-\(t\)-intersecting families

Related

• The maximum product of sizes of cross-intersecting families
• The maximum sum and maximum product of sizes of cross-intersecting\n families
• The maximum product of weights of cross-intersecting families
• Uniform cross-t-intersecting families: proving Hirschorn's conjecture up to polynomial factor
• The maximum sum of sizes of cross-intersecting families of subsets of a set