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

preprint2013arXivOpen access

Abstract

We say that a set AA \emph{tt-intersects} a set BB if AA and BB have at least tt common elements. Two families A\mathcal{A} and B\mathcal{B} are said to be \emph{cross-tt-intersecting} if each set in A\mathcal{A} tt-intersects each set in B\mathcal{B}. For any positive integers nn and rr, let ([n]r){[n] \choose r} denote the family of all rr-element subsets of {1,2,…,n}\{1,2,\dots, n\}. We show that for any integers rr, ss and tt with 1≤t≤r≤s1 \leq t \leq r \leq s, there exists an integer n0(r,s,t)n_0(r,s,t) such that for any integer n≥n0(r,s,t)n \geq n_0(r,s,t), if A⊂([n]r)\mathcal{A} \subset {[n] \choose r} and B⊂([n]s)\mathcal{B} \subset {[n] \choose s} such that A\mathcal{A} and B\mathcal{B} are cross-tt-intersecting, then ∣A∣∣B∣≤(n−tr−t)(n−ts−t)|\mathcal{A}||\mathcal{B}| \leq {n-t \choose r-t}{n-t \choose s-t}, and equality holds if and only if for some T∈([n]t)T \in {[n] \choose t}, A={A∈([n]r) ⁣:T⊂A}\mathcal{A} = \{A \in {[n] \choose r} \colon T \subset A\} and B={B∈([n]s) ⁣:T⊂B}\mathcal{B} = \{B \in {[n] \choose s} \colon T \subset B\}. This verifies a conjecture of Hirschorn.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.