Mathematics – Combinatorics
Scientific paper
2011-02-03
Mathematics
Combinatorics
12 pages
Scientific paper
A family $\mathcal{A}$ of sets is said to be \emph{$t$-intersecting} if any two distinct sets in $\mathcal{A}$ have at least $t$ common elements. Families $\mathcal{A}_1, \mathcal{A}_2, ..., \mathcal{A}_k$ are said to be \emph{cross-$t$-intersecting} if for any $i$ and $j$ in $\{1, 2, ..., k\}$ with $i \neq j$, any set in $\mathcal{A}_i$ intersects any set in $\mathcal{A}_j$ on at least $t$ elements. We prove that for any finite family $\mathcal{F}$ that has at least one set of size at least $t$, there exists an integer $k_0 \leq |\mathcal{F}|$ such that for any $k \geq k_0$, both the sum and product of sizes of $k$ cross-$t$-intersecting sub-families $\mathcal{A}_1, \mathcal{A}_2, ..., \mathcal{A}_k$ (not necessarily distinct or non-empty) of $\mathcal{F}$ are a maximum if $\mathcal{A}_1 = \mathcal{A}_2 = ... = \mathcal{A}_k = \mathcal{L}$ for some largest $t$-intersecting sub-family $\mathcal{L}$ of $\mathcal{F}$. We then study the minimum value of $k_0$ and investigate the case $k < k_0$. We also prove that if $t=1$ and $\mathcal{F}$ is the family of all subsets of a set $X$, then the result holds with $k_0 = 2$ and $\mathcal{L}$ consisting of all subsets of $X$ which contain a fixed element $x$ of $X$.
No associations
LandOfFree
The maximum sum and product of sizes of cross-intersecting families does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The maximum sum and product of sizes of cross-intersecting families, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The maximum sum and product of sizes of cross-intersecting families will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-427729