The maximum product of sizes of cross-intersecting families

preprint2016arXivOpen access

Abstract

We say that a set AA tt-intersects a set BB if AA and BB have at least tt common elements. Two families A\mathcal{A} and B\mathcal{B} of sets are said to be cross-tt-intersecting if each set in A\mathcal{A} tt-intersects each set in B\mathcal{B}. A subfamily S\mathcal{S} of a family F\mathcal{F} is called a tt-star of F\mathcal{F} if the sets in S\mathcal{S} have tt common elements. Let l(F,t)l(\mathcal{F},t) denote the size of a largest tt-star of F\mathcal{F}. We call F\mathcal{F} a (≤r)(\leq r)-family if each set in F\mathcal{F} has at most rr elements. We determine a function c:N3→Nc : \mathbb{N}^3 \rightarrow \mathbb{N} such that the following holds. If A\mathcal{A} is a subfamily of a (≤r)(\leq r)-family F\mathcal{F} with l(F,t)≥c(r,s,t)l(F,t+1)l(\mathcal{F},t) \geq c(r,s,t)l(\mathcal{F},t+1), B\mathcal{B} is a subfamily of a (≤s)(\leq s)-family G\mathcal{G} with l(G,t)≥c(r,s,t)l(G,t+1)l(\mathcal{G},t) \geq c(r,s,t)l(\mathcal{G},t+1), and A\mathcal{A} and B\mathcal{B} are cross-tt-intersecting, then ∣A∣∣B∣≤l(F,t)l(G,t)|\mathcal{A}||\mathcal{B}| \leq l(\mathcal{F},t)l(\mathcal{G},t). Some known results follow from this, and we identify several natural classes of families for which the bound is attained.

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.