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

preprint2012arXivOpen access

Abstract

We say that a set AA \emph{tt-intersects} a set BB if AA and BB have at least tt common elements. A family A\mathcal{A} of sets is said to be \emph{tt-intersecting} if each set in A\mathcal{A} tt-intersects any other set in A\mathcal{A}. Families A1,A2,...,Ak\mathcal{A}_1, \mathcal{A}_2, ..., \mathcal{A}_k are said to be \emph{cross-tt-intersecting} if for any ii and jj in {1,2,...,k}\{1, 2, ..., k\} with i≠ji \neq j, any set in Ai\mathcal{A}_i tt-intersects any set in Aj\mathcal{A}_j. We prove that for any finite family F\mathcal{F} that has at least one set of size at least tt, there exists an integer κ≤∣F∣κ\leq |\mathcal{F}| such that for any k≥κk \geq κ, both the sum and the product of sizes of any kk cross-tt-intersecting sub-families A1,...,Ak\mathcal{A}_1, ..., \mathcal{A}_k (not necessarily distinct or non-empty) of F\mathcal{F} are maxima if A1=...=Ak=L\mathcal{A}_1 = ... = \mathcal{A}_k = \mathcal{L} for some largest tt-intersecting sub-family L\mathcal{L} of F\mathcal{F}. We then study the smallest possible value of κκ and investigate the case k<κk < κ; this includes a cross-intersection result for straight lines that demonstrates that it is possible to have F\mathcal{F} and κκ such that for any k<κk < κ, the configuration A1=...=Ak=L\mathcal{A}_1 = ... = \mathcal{A}_k = \mathcal{L} is neither optimal for the sum nor optimal for the product. We also outline solutions for various important families F\mathcal{F}, and we provide solutions for the case when F\mathcal{F} is a power set.

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.