A sharp bound for the product of weights of cross-intersecting families

Peter Borg¹

¹Department of Mathematics University of Malta

The electronic journal of combinatorics, Tome 23 (2016) no. 4

Résumé

Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be cross-intersecting if each set in $\mathcal{A}$ intersects each set in $\mathcal{B}$. For any two integers $n$ and $k$ with $1 \leq k \leq n$, let ${[n] \choose \leq k}$ denote the family of subsets of $\{1, \dots, n\}$ of size at most $k$, and let $\mathcal{S}_{n,k}$ denote the family of sets in ${[n] \choose \leq k}$ that contain $1$. The author recently showed that if $\mathcal{A} \subseteq {[m] \choose \leq r}$, $\mathcal{B} \subseteq {[n] \choose \leq s}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then $|\mathcal{A}||\mathcal{B}| \leq \mathcal{S}_{m,r}||\mathcal{S}_{n,s}|$. We prove a version of this result for the more general setting of \emph{weighted} sets. We show that if $g : {[m] \choose \leq r} \rightarrow \mathbb{R}^+$ and $h : {[n] \choose \leq s} \rightarrow \mathbb{R}^+$ are functions that obey certain conditions, $\mathcal{A} \subseteq {[m] \choose \leq r}$, $\mathcal{B} \subseteq {[n] \choose \leq s}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then $$\sum_{A \in \mathcal{A}} g(A) \sum_{B \in \mathcal{B}} h(B) \leq \sum_{C \in \mathcal{S}_{m,r}} g(C) \sum_{D \in \mathcal{S}_{n,s}} h(D).$$The bound is attained by taking $\mathcal{A} = \mathcal{S}_{m,r}$ and $\mathcal{B} = \mathcal{S}_{n,s}$. We also show that this result yields new sharp bounds for the product of sizes of cross-intersecting families of integer sequences and of cross-intersecting families of multisets.

Détail

DOI : 10.37236/5782

Classification : 05D05, 05C65
Mots-clés : cross-intersecting families, weighted set, integer sequence, multiset