Cross-intersecting integer sequences

Original · EN

We call (a₁,, aₙ) an r-partial sequence if exactly r of its entries are positive integers and the rest are all zero. For c = (c₁,, cₙ) with 1 ≤ c₁ ≤ ≤ cₙ, let S c⁽ʳ⁾ be the set of r-partial sequences (a₁,, aₙ) with 0 ≤ aᵢ ≤ cᵢ for each i in {1,, n}, and let S c⁽ʳ⁾(1) be the set of members of S c⁽ʳ⁾ which have a₁ = 1. We say that (a₁,, aₙ) meets (b₁,, bₘ) if aᵢ = bᵢ ≠ 0 for some i. Two sets A and B of sequences are said to be cross-intersecting if each sequence in A meets each sequence in B. Let d = (d₁,, dₘ) with 1 ≤ d₁ ≤ ≤ dₘ. Let A S c⁽ʳ⁾ and B S d⁽ˢ⁾ such that A and B are cross-intersecting. We show that |A||B| ≤ |S c⁽ʳ⁾(1)||S d⁽ˢ⁾(1)| if either c₁ ≥ 3 and d₁ ≥ 3 or c = d and r = s = n. We also determine the cases of equality. We obtain this by proving a general cross-intersection theorem for weighted sets. The bound generalises to one for k ≥ 2 cross-intersecting sets.