\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
%\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/1212.6955v1}{\texttt{arXiv:1212.6955v1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}


\title{\bf A sharp bound for the product of weights of cross-intersecting families}
%\title{A cross-intersection theorem for weighted subsets of a set}

\author{Peter Borg\\
\small Department of Mathematics\\[-0.8ex]
\small University of Malta\\[-0.8ex] 
\small Malta\\
\small\tt peter.borg@um.edu.mt
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Dec 15, 2015}{Dec 5, 2016}\\
\small Mathematics Subject Classifications: 05D05}

\begin{document}

\maketitle

\begin{abstract}

Two families $\mathcal{A}$ and $\mathcal{B}$ of sets are said to be \emph{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.

\bigskip\noindent \textbf{Keywords:} cross-intersecting families, weighted set, integer sequence, multiset
\end{abstract}

\section{Introduction} \label{Intro}

Unless otherwise stated, we shall use small letters such as $x$ to
denote elements of a set or non-negative integers or functions,
capital letters such as $X$ to denote sets, and calligraphic
letters such as $\mathcal{F}$ to denote \emph{families}
(i.e.~sets whose elements are sets themselves). It is to be
assumed that arbitrary sets and families are \emph{finite}. We call a set $A$ an \emph{$r$-element set}, or simply an \emph{$r$-set}, if
its size $|A|$ is $r$. For a set $X$, the \emph{power set of $X$} (that is, the family of all subsets of $X$) is denoted by $2^X$, the family of all $r$-element subsets of $X$ is denoted by ${X \choose r}$, and the family of all subsets of $X$ that have at most $r$ elements is denoted by ${X \choose \leq r}$. The set of all positive integers is denoted by $\mathbb{N}$. For any $m,n \in \mathbb{N}$ with $m < n$, the set $\{i \in \mathbb{N} \colon m \leq i \leq n\}$ is denoted by $[m,n]$. We abbreviate $[1,n]$ to $[n]$.

We say that a set $A$ \emph{intersects} a set $B$ if $A$ and $B$ contain at least one common element. A family $\mathcal{A}$ of sets is said to be \emph{intersecting} if for every $A, B \in \mathcal{A}$, $A$ and $B$ intersect. Families $\mathcal{A}_1, \dots, \mathcal{A}_k$ are said to be \emph{cross-intersecting} if for every $i$ and $j$ in $[k]$ with $i \neq j$, each set in $\mathcal{A}_i$ intersects each set in $\mathcal{A}_j$. 

For $x \in X$ and $\mathcal{F} \subseteq 2^X$, we denote the family $\{F \in \mathcal{F} \colon x \in F\}$ by $\mathcal{F}(x)$. If $\mathcal{F}(x) \neq \emptyset$, then we call $\mathcal{F}(x)$ the \emph{star of $\mathcal{F}$} with \emph{centre} $x$. A star of a family is the simplest example of an intersecting subfamily.

One of the most popular endeavours in extremal set theory is that of determining the size of a largest intersecting subfamily of a given family $\mathcal{F}$. This took off with \cite{EKR}, which features the classical result, known as the Erd\H os--Ko--Rado (EKR) Theorem, that says that if $r \leq n/2$, then the size of a largest intersecting subfamily of ${[n] \choose r}$ is the size ${n-1 \choose r-1}$ of every star of ${[n] \choose r}$. There are various proofs of the EKR Theorem, two of which are particularly short and beautiful: Katona's \cite{K}, introducing the elegant cycle method, and Daykin's \cite{D}, using the fundamental Kruskal--Katona Theorem \cite{Ka,Kr}. Various generalizations and analogues have been obtained; of particular note are the results in \cite{Kat,F_t1,W,AK1}. The EKR Theorem inspired a wealth of results that establish how large a system of sets can be under certain intersection conditions; see \cite{DF,F,F2,Borg7,FT3}.

For intersecting subfamilies of a given family $\mathcal{F}$,
the natural question to ask is how large they can be. For
cross-intersecting families, two natural parameters arise: the
sum and the product of sizes of the cross-intersecting
families. It is therefore natural to consider the problem of
maximizing the sum or the product of sizes of $k$ cross-intersecting subfamilies (not necessarily distinct or non-empty) of a given family $\mathcal{F}$. In \cite{Borg8}, this problem is analysed in a general way, and it is shown that for $k$ sufficiently large it reduces to the problem of maximizing the size of an intersecting subfamily of $\mathcal{F}$. Solutions have been obtained for various families, as outlined in \cite{Borg8,Borg10}. %(see \cite{Borg8}), including ${[n] \choose r}$ \cite{H,Pyber, MT,Bey3,Borg4,WZ}, $2^{[n]}$ \cite{MT2,Borg8} and families of integer sequences \cite{Moon,Borg,WZ,Zhang,Tok3}. 
Wang and Zhang \cite{WZ} solved the maximum sum problem for an important class of families that includes ${[n] \choose r}$ and many others, elegantly combining the method in \cite{Borg4,Borg3,Borg2,BL2,Borg5} and the \emph{no-homomorphism lemma} \cite{AC,CK}. The solution for ${[n] \choose r}$ had been obtained by Hilton \cite{H} and is the first result that addressed the cross-intersection problem described above. 
Pyber \cite{Pyber} solved the maximum product problem for ${[n] \choose r}$ (see also \cite{MT,Bey3}).

The maximum product problem for ${[n] \choose \leq r}$ has been solved in \cite{Borg10}, which actually provides the solution to the more general problem where the cross-intersecting families do not necessarily come from the same family.

\begin{theorem}[\cite{Borg10}] \label{bullthm} If $m, n \in \mathbb{N}$, $r \in [m]$, $s \in [n]$, $\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 \sum_{i=1}^r {m-1 \choose i-1} \sum_{j=1}^s {n-1 \choose j-1},\] 
%
and equality holds if $\mathcal{A} = \{A \in {[m] \choose \leq r} \colon 1 \in A\}$ and $\mathcal{B} = \{B \in {[n] \choose \leq s} \colon 1 \in B\}$.
\end{theorem}
%
We consider the more general setting where the sets are assigned \emph{weights} (positive real numbers). The weight of a family is the sum of weights of its members, and the objective is to maximize the product of weights of the cross-intersecting families. Before stating our main result, we need some additional definitions and notation. We also point out that, as explained in the next section, a product result such as Theorem~\ref{bullthm}, where the product is maximum when the cross-intersecting families are stars with a particular center, automatically yields an EKR-type result and generalizes to one for $k \geq 2$ cross-intersecting families.

For any $i, j \in [n]$, let $\delta_{i,j} \colon 2^{[n]} \rightarrow 2^{[n]}$ be defined by
%
\[ \delta_{i,j}(A) = \left\{ \begin{array}{ll}
(A \backslash \{j\}) \cup \{i\} & \mbox{if $j \in A$ and $i \notin
A$};\\
A & \mbox{otherwise,}
\end{array} \right. \]
%
and let $\Delta_{i,j} \colon 2^{2^{[n]}} \rightarrow 2^{2^{[n]}}$ be the \emph{compression operation} defined by
%
\[\Delta_{i,j}(\mathcal{A}) = \{\delta_{i,j}(A) \colon A \in
\mathcal{A}\} \cup \{A \in \mathcal{A} \colon \delta_{i,j}(A) \in \mathcal{A}\}.\]
%
The compression operation was introduced in the seminal paper \cite{EKR}. The paper \cite{F} provides a survey on the properties and uses of compression (also called \emph{shifting}) operations in extremal set theory. All our new results make use of compression operations.

If $i < j$, then we call $\Delta_{i,j}$ a \emph{left-compression}. A family $\mathcal{F} \subseteq 2^{[n]}$ is said to be
\emph{compressed} if $\Delta_{i,j}(\mathcal{F}) = \mathcal{F}$ for every $i,j \in [n]$ with $i < j$. In other words, $\mathcal{F}$ is compressed if it is invariant under left-compressions. Note that $\mathcal{F}$ is compressed if and only if $(F \backslash \{j\}) \cup \{i\} \in \mathcal{F}$ whenever $i < j$, $j \in F \in \mathcal{F}$ and $i \in [n] \backslash F$.

A family $\mathcal{H}$ is said to be \emph{hereditary} if for each $H \in \mathcal{H}$, all the subsets of $H$ are in $\mathcal{H}$. Thus,
a family is hereditary if and only if it is a union of power sets. The family ${[n] \choose \leq r}$ (which is $2^{[n]}$ if $r = n$) is an example of a hereditary family that is compressed. We mention that one of the central problems in extremal set theory is a conjecture of Chv\'{a}tal \cite{Chv} that claims that at least one of the largest interesting subfamilies of any hereditary family $\mathcal{H}$ is a star of $\mathcal{H}$; a similar conjecture for \emph{levels} of $\mathcal{H}$ is made and partially solved in \cite{Borg9}, and generalizes \cite[Conjecture~7]{HT}.

Let $\mathbb{R}^+$ denote the set of positive real numbers. For a non-empty family $\mathcal{F}$, a function $w \colon \mathcal{F} \rightarrow \mathbb{R}^+$ (a \emph{weight} function), and a subfamily $\mathcal{A}$ of $\mathcal{F}$, the sum $\sum_{A \in \mathcal{A}} w(A)$ (of \emph{weights} of sets in $\mathcal{A}$) is called the \emph{$w$-weight of $\mathcal{A}$}. With a slight abuse of notation, the $w$-weight of $\mathcal{A}$ is denoted by $w(\mathcal{A})$. %For convenience, we abbreviate $w^{(\mathcal{F})}(\mathcal{A})$ to $w(\mathcal{A})$. 
Note that if $\mathcal{A}$ is empty, then $w(\mathcal{A})$ is the \emph{empty sum}, which is $0$ by convention.

The following is our main result, which we will prove in Section~\ref{Weightedsection}.

\begin{theorem}\label{xintweight} Let $m, n \in \mathbb{N}$, and let $u,v \in \{0\} \cup \mathbb{R}^+$ such that $u+v \geq 2$. Let $\emptyset \neq \mathcal{G} \subseteq 2^{[m]}$ and $\emptyset \neq \mathcal{H} \subseteq 2^{[n]}$ such that $\mathcal{G}$ and $\mathcal{H}$ are hereditary and compressed. Let $g \colon \mathcal{G} \rightarrow \mathbb{R}^+$ and $h \colon \mathcal{H} \rightarrow \mathbb{R}^+$ be functions such that \\
(a) $g(G) \geq (1+u)g(G')$ for every $G, G' \in \mathcal{G}$ with $\emptyset \neq G \subsetneq G'$, \\
(b) $h(H) \geq (1+v)h(H')$ for every $H, H' \in \mathcal{H}$ with $\emptyset \neq H \subsetneq H'$, \\
(c) $g(\delta_{i,j}(G)) \geq g(G)$ for every $G \in \mathcal{G}$ and every $i,j \in [m]$ with $i < j$, and \\
(d) $h(\delta_{i,j}(H)) \geq h(H)$ for every $H \in \mathcal{H}$ and every $i,j \in [n]$ with $i < j$. \\
If $\mathcal{A} \subseteq \mathcal{G}$ and $\mathcal{B} \subseteq \mathcal{H}$ such that $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then
%
\[g(\mathcal{A}) h(\mathcal{B}) \leq g(\mathcal{G}(1)) h(\mathcal{H}(1)).\]
%
Moreover, if $u \neq 0$ and $v \neq 0$, then equality holds if and only if $\mathcal{A} = \mathcal{G}(a)$ and $\mathcal{B} = \mathcal{H}(a)$ for some $a \in [m] \cap [n]$ such that $g(\mathcal{G}(a)) = g(\mathcal{G}(1))$ and $h(\mathcal{H}(a)) = h(\mathcal{H}(1))$.  
\end{theorem}
%
\noindent
In \cite{Borg10}, it is proved that the result also holds if $g(G) = 1 = h(H)$ for every $G \in \mathcal{G}$ and every $H \in \mathcal{H}$; Theorem~\ref{bullthm} is the special case where $\mathcal{G} = {[m] \choose \leq r}$ and $\mathcal{H} = {[n] \choose \leq s}$.

The proof of Theorem~\ref{xintweight} is based on induction, compression, and a subfamily alteration. The method can be summarized as follows. We use induction on $m + n$. We take $\mathcal{A}$ and $\mathcal{B}$ to be such that the product of their weights is maximum. The challenging part is the case $m = n$. The first problem that arises is that we can have a set $A \in \mathcal{A}$ and a set $B \in \mathcal{B}$ that intersect only in $n$; in this case, we cannot simply remove $n$ and apply the induction hypothesis. Thus, we consider two alterations: removing $A$ from $\mathcal{A}$ and adding $B \backslash \{n\}$ to $\mathcal{B}$, and removing $B$ from $\mathcal{B}$ and adding $A \backslash \{n\}$ to $\mathcal{A}$. This yields two new pairs of cross-intersecting families. The second problem is that the product of the weights of a new pair obtained in this way may become smaller. The critical part of the proof is the observation that if we assume that this happens for both pairs, then we can construct a new pair of cross-intersecting families for which the product of weights is larger than that for $\mathcal{A}$ and $\mathcal{B}$ (unless we have the trivial case $m = n = 2$), hence contradicting the initial assumption.



\section{Applications of Theorem~\ref{xintweight}}

We will show that Theorem~\ref{xintweight} yields cross-intersection results for integer sequences and for multisets. 
 
We represent a sequence $a_1, \dots, a_n$ by an $n$-tuple $(a_1, \dots, a_n)$, and we say that it is of \emph{length $n$}. We call a sequence of positive integers a \emph{positive sequence}. We call $(a_1, \dots, a_n)$ an \emph{$r$-partial sequence} if exactly $r$ of its entries are positive integers and the rest are all zero. Thus an $n$-partial sequence of length $n$ is positive. A sequence $(c_1, \dots, c_n)$ is said to be \emph{increasing} if $c_1 \leq \dots \leq c_n$. We call an increasing positive sequence an \emph{IP sequence}. 

We call $\{(x_1,y_1), \dots, (x_r,y_r)\}$ a \emph{labeled set} (following \cite{Borg}) if $x_1, \dots, x_r$ are distinct. For any IP sequence ${\bf c} = (c_1, \dots, c_n)$ and any $r \in [n]$, let $\mathcal{L}_{{\bf c}}^{(r)}$ be the family of all labeled sets $\{(x_1,y_{x_1}), \dots, (x_r, y_{x_r})\}$ such that $\{x_1, \dots, x_r\} \in {[n] \choose r}$ and $y_{x_j} \in [c_{x_j}]$ for each $j \in [r]$. We may abbreviate $\mathcal{L}_{{\bf c}}^{(n)}$ to $\mathcal{L}_{{\bf c}}$. For any sets $Y_1, \dots, Y_n$, let $Y_1 \times \dots \times Y_n$ denote the \emph{Cartesian product of $Y_1, \dots, Y_n$}, that is, the set of sequences $(y_1, \dots, y_n)$ such that $y_i \in Y_i$ for each $i \in [n]$. Note that $\mathcal{L}_{{\bf c}} = \{\{(1,y_1), \dots, (n,y_n)\} \colon y_i \in [c_i] \mbox{ for each } i \in [n]\}$, so $\mathcal{L}_{{\bf c}}$ is isomorphic to $[c_1] \times \dots \times [c_n]$. Let $L_{{\bf c}}^{(r)}$ denote the set of all $r$-partial sequences in $(\{0\} \cup [c_1]) \times \dots \times (\{0\} \cup [c_n])$. By associating $(y_1, \dots, y_n) \in L_{{\bf c}}^{(r)}$ with the labeled set $\{(i,y_i) \colon i \in [n], \, y_i \neq 0\}$ in $\mathcal{L}_{{\bf c}}^{(r)}$, we obtain that $\mathcal{L}_{{\bf c}}^{(r)}$ and $L_{{\bf c}}^{(r)}$ are isomorphic. %Also note that $\mathcal{L}_{{\bf c}}^{(r)}$ is isomorphic to the set of $r$-partial sequences $(y_1, \dots, y_n)$ such that for some $R \in {[n] \choose r}$, $y_i \in [c_i]$ for each $i \in R$ (and hence $y_j = 0$ for each $j \in [n] \backslash R$). 

In Section~\ref{Proofmain}, we prove the following result.

\begin{theorem} \label{mainpartial} Let ${\bf c} = (c_1, \dots, c_m)$ and ${\bf d} = (d_1, \dots, d_n)$ be IP sequences such that $c_1 \geq 2$, $d_1 \geq 2$, and $c_1 + d_1 \geq 6$. Let $r \in [m]$ and $s \in [n]$. If $\mathcal{A} \subseteq \mathcal{L}_{{\bf c}}^{(r)}$ and  $\mathcal{B} \subseteq \mathcal{L}_{{\bf d}}^{(s)}$ such that $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then
%
\[|\mathcal{A}||\mathcal{B}| \leq \Bigg{(} \sum_{I \in {[2,m] \choose r-1}} \prod_{i \in I} c_i \Bigg{)} \Bigg{(} \sum_{J \in {[2,n] \choose s-1}}\prod_{j \in J} d_j \Bigg{)}.\]
%
Moreover, if $c_1 \geq 3$ and $d_1 \geq 3$, then equality holds if and only if $\mathcal{A} = \mathcal{L}_{{\bf c}}^{(r)}((p,q))$ and $\mathcal{B} = \mathcal{L}_{{\bf d}}^{(s)}((p,q))$ for some $p \in [m] \cap [n]$ with $c_p = c_1$ and $d_p = d_1$, and some $q \in [c_1] \cap [d_1]$.
\end{theorem}
%
We say that $(a_1, \dots, a_m)$ \emph{meets} $(b_1, \dots, b_n)$ if $a_i = b_i \neq 0$ for some $i \in [m] \cap [n]$. %For any IP sequence ${\bf e} = (e_1, \dots, e_l)$, let $L_{{\bf e}}^{(r)}$ be the set of all $r$-partial sequences in $\{0\} \cup [e_1] \times \dots \times \{0\} \cup [e_l]$. 
Thus, Theorem~\ref{mainpartial} is equivalent to the following: for $\bf c$, $\bf d$, $r$ and $s$ as in Theorem~\ref{mainpartial}, if $A \subseteq L_{{\bf c}}^{(r)}$ and $B \subseteq L_{{\bf d}}^{(s)}$ such that each member of $A$ meets each member of $B$, then $|A||B| \leq \left( \sum_{I \in {[2,m] \choose r-1}} \prod_{i \in I} c_i \right) \left( \sum_{J \in {[2,n] \choose s-1}}\prod_{j \in J} d_j \right)$; moreover, if $c_1 \neq 1$ and $d_1 \neq 1$, then equality holds if and only if $A = \{(a_1, \dots, a_m) \in L_{{\bf c}}^{(r)} \colon a_p = q\}$ and $B = \{(b_1, \dots, b_n) \in L_{{\bf d}}^{(s)} \colon b_p = q\}$ for some $p \in [m] \cap [n]$ with $c_p = c_1$ and $d_p = d_1$, and some $q \in [c_1] \cap [d_1]$.

It is immediate from Theorem~\ref{mainpartial} that ${\bf c}$ and ${\bf d}$ do not need to be increasing as long as there exists $p \in [m] \cap [n]$ such that $c_p = \min\{c_1, \dots, c_m\}$ and $d_p = \min\{d_1, \dots, d_n\}$, in which case the maximum product is $|\mathcal{L}_{{\bf c}}^{(r)}((p,1))| |\mathcal{L}_{{\bf d}}^{(s)}((p,1))|$; it is not clear what happens if this is not the case. Theorem~\ref{mainpartial} does not always hold for $c_1 = d_1 = 1$; indeed, if $c_1 = c_m = d_1 = d_n = 1$, $m = n$ and $m/2 < r = s < m$, then any two sequences in $\mathcal{L}_{{\bf c}}^{(r)}$ intersect, and hence we can take $\mathcal{A} = \mathcal{B} = \mathcal{L}_{{\bf c}}^{(r)}$. The case where $3 \leq c_1 + d_1 \leq 5$ seems to require special treatment and remains a problem to be investigated. However, for the special case where ${\bf c} = {\bf d}$ and $r = n$, we easily obtain from Theorem~\ref{mainpartial} the sharp bound for all values of $c_1$, given by the following.

\begin{theorem} \label{main} If ${\bf c}$ is an IP sequence, $\mathcal{A}, \mathcal{B} \subseteq \mathcal{L}_{{\bf c}}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then
%
\[|\mathcal{A}||\mathcal{B}| \leq |\mathcal{L}_{{\bf c}}((1,1))|^2.\]
%
\end{theorem}
% 
\noindent
This result is also proved in Section~\ref{Proofmain}. It was first established in the preliminary version \cite{arxiver} of this paper. An alternative proof has been obtained by Pach and Tardos \cite{PT}. 

Sum versions of Theorems~\ref{mainpartial} and \ref{main} are given in \cite{BL2} and \cite{Borg}, respectively (see also \cite{WZ}). The EKR problem for $\mathcal{L}_{{\bf c}}$ and $\mathcal{L}_{{\bf c}}^{(r)}$ has been widely studied, and several results have been obtained. The EKR-type version of Theorem~\ref{main} (that is, the solution to the problem of maximizing the size of an intersecting subfamily of $\mathcal{L}_{\bf c}$) is given in \cite{B,L,Borg} (for $c_1 = c_n$, this is given in a stronger form in \cite{FF2,AK2,FT2}). The EKR problem for $\mathcal{L}_{\bf c}^{(r)}$ has been solved \cite{DF,HST,Bey2}; see \cite{DF,E,BL,EFK,Bey1} for $c_1 = c_n$, \cite{HST} for $c_1 \geq 2$, and \cite{Bey2} for $c_1 = 1$. The special case $c_1 = c_n$ of Theorem~\ref{main} was treated by Moon \cite{Moon} (for $c_1 \geq 3$), Tokushige \cite{Tok3} (for $c_1 \geq 4$) and Zhang \cite{Zhang} (for $c_1 \geq 4$) via an induction argument, an eigenvalue method and Katona's cycle method, respectively. Allowing $\bf c$ to be increasing appears to be a significant relaxation for the product problem. Our approach is based on the idea of generalizing the setting enough for induction to work. The setting of Theorem~\ref{xintweight} not only allows us to deal with the more general problem for $\mathcal{L}_{{\bf c}}^{(r)}$, but also to obtain Theorem~\ref{mainpartial}, where the cross-intersecting families can come from different families.
 
Our second application of Theorem~\ref{xintweight} is a cross-intersection result for multisets. 

A \emph{multiset} is a collection $A$ of objects such that each object possibly appears more than once in $A$. Thus the difference between a multiset and a set is that a multiset may have repetitions of its elements. We can uniquely represent a multiset $A$ of positive integers by an IP sequence $(a_1, \dots, a_r)$, where $a_1, \dots, a_r$ form $A$. Thus we will take multisets to be IP sequences. For $A = (a_1, \dots, a_r)$, the \emph{support of $A$} is the set $\{a_1, \dots, a_r\}$ and will be denoted by ${\rm S}_A$; thus, ${\rm S}_A$ is the set of distinct elements of $A$. For any $n, r \in \mathbb{N}$, let $M_{n,r}$ denote the set of all multisets $(a_1, \dots, a_r)$ such that $a_1, \dots, a_r \in [n]$; thus $M_{n,r} = \{(a_1, \dots, a_r) \colon a_1 \leq \dots \leq a_r, \, a_1, \dots, a_r \in [n]\}$. An elementary counting result is that \[|M_{n,r}| = {n+r-1 \choose r}.\]

With a slight abuse of terminology, we say that a multiset $A$ \emph{intersects} a multiset $B$ if $A$ and $B$ have at least one common element, that is, if ${\rm S}_A$ intersects ${\rm S}_B$. A set $\mathcal{A}$ of multisets is said to be \emph{intersecting} if every two multisets in $\mathcal{A}$ intersect, and $k$ sets $\mathcal{A}_1, \dots, \mathcal{A}_k$ of multisets are said to be \emph{cross-intersecting} if for every $i,j \in [k]$ with $i \neq j$, each multiset in $\mathcal{A}_i$ intersects each multiset in $\mathcal{A}_j$.

In Section~\ref{multisection}, we prove the following result.

\begin{theorem}\label{multithm} If $r, s \in \mathbb{N}$, $u, v \in \{0\} \cup \mathbb{R}^+$, $u + v \geq 2$, $m \geq (2+u)(r-1)+s-1$, $n \geq (2+v)(s-1)+r-1$, $\mathcal{A} \subseteq M_{m,r}$, $\mathcal{B} \subseteq M_{n,s}$, and $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, then
%
\[|\mathcal{A}||\mathcal{B}| \leq {m+r-2 \choose r-1}{n+s-2 \choose s-1}.\]
% 
Moreover, if $u \neq 0$ and $v \neq 0$, then the bound is attained if and only if for some $a \in [m] \cap [n]$, $\mathcal{A} = \left\{ A \in M_{m,r} \colon a \in {\rm S}_A \right\}$ and $\mathcal{B} = \left\{ B \in M_{n,s} \colon a \in {\rm S}_B \right\}$.
\end{theorem}
%
EKR-type results for multisets have been obtained in \cite{MP,FGV}. To the best of the author's knowledge, Theorem~\ref{multithm} is the first cross-intersection result for multisets. It is an analogue of the product version in \cite{Pyber, MT} of the EKR Theorem.
 
As indicated in Section~\ref{Intro}, the results above imply EKR-type theorems. In general, if $\mathcal{I} \subseteq \mathcal{F}$, $k \geq 2$, and the sum or the product of sizes of $k$ cross-intersecting subfamilies $\mathcal{A}_1, \dots, \mathcal{A}_k$ of $\mathcal{F}$ is maximum when $\mathcal{A}_1 = \dots = \mathcal{A}_k = \mathcal{I}$, then $\mathcal{I}$ is a largest intersecting subfamily of $\mathcal{F}$. Indeed, the cross-intersection condition implies that every two sets $A$ and $B$ in $\mathcal{I}$ intersect (as $A \in \mathcal{A}_1$ and $B \in \mathcal{A}_2$), and by taking an intersecting subfamily $\mathcal{A}$ of $\mathcal{F}$, and setting $\mathcal{B}_1 = \dots = \mathcal{B}_k = \mathcal{A}$, we obtain that $\mathcal{B}_1, \dots, \mathcal{B}_k$ are cross-intersecting, and hence $|\mathcal{A}| \leq |\mathcal{I}|$ as $k|\mathcal{A}| = \sum_{i=1}^k |\mathcal{B}_i| \leq \sum_{i=1}^k |\mathcal{A}_i| = k|\mathcal{I}|$ or $|\mathcal{A}|^k = \prod_{i=1}^k |\mathcal{B}_i| \leq \prod_{i=1}^k |\mathcal{A}_i| = |\mathcal{I}|^k$. Similarly, if the sum or the product of weights is maximum when $\mathcal{A}_1 = \dots = \mathcal{A}_k = \mathcal{I}$, then $\mathcal{I}$ is an intersecting subfamily of $\mathcal{F}$ of maximum weight.

As also indicated in Section~\ref{Intro}, the results above generalize for $k \geq 2$ families. For example, applying the line of argument in the proof of \cite[Theorem~1.2]{Borg11} to Theorem~\ref{xintweight} yields the following generalization of Theorem~\ref{xintweight}. 

\begin{theorem}\label{xintweightgen} Let $k \geq 2$, $n_1, \dots, n_k \in \mathbb{N}$, and $u_1, \dots, u_k \in \{0\} \cup \mathbb{R}^+$ such that $u_i+u_j \geq 2$ for every $i,j \in [k]$ with $i \neq j$. For each $i \in [k]$, let $\emptyset \neq \mathcal{H}_i \subseteq 2^{[n_i]}$ such that $\mathcal{H}_i$ is hereditary and compressed, and let $h_i \colon \mathcal{H}_i \rightarrow \mathbb{R}^+$ be a function such that \\
(a) $h_i(H) \geq (1+u_i)h_i(H')$ for every $H, H' \in \mathcal{H}_i$ with $H \subsetneq H'$, and\\
(b) $h_i(\delta_{p,q}(H)) \geq h_i(H)$ for every $H \in \mathcal{H}_i$ and every $p,q \in [n_i]$ with $p < q$. \\
If $\mathcal{A}_1, \dots, \mathcal{A}_k$ are cross-intersecting families such that $\mathcal{A}_i \subseteq \mathcal{H}_i$ for each $i \in [k]$, then
%
\[\prod_{i=1}^k h_i(\mathcal{A}_i) \leq \prod_{i=1}^k h_i(\mathcal{H}_i(1)).\]
%
Moreover, equality holds if and only if $\mathcal{A}_i = \mathcal{H}_i(a)$ for some $a \in [\min\{n_1, \dots, n_k\}]$ such that $h_i(\mathcal{H}_i(a)) = h_i(\mathcal{H}_i(1))$ for each $i \in [k]$.  
\end{theorem}
%
\noindent
We simply observe that $\left( \prod_{i=1}^k a_i \right)^{k-1} = \prod_{i=1}^{k-1} \prod_{j \in [k] \backslash [i]} a_ia_j$ %(see also \cite[Lemma~5.2]{Borg8} with $p = 2$) 
and that if $\mathcal{A}_1, \dots, \mathcal{A}_k$ are cross-intersecting, then any $\mathcal{A}_i$ and $\mathcal{A}_j$ with $i \neq j$ are cross-intersecting.  Thus, if, for example, $\mathcal{A}_1, \dots, \mathcal{A}_k$ are as in Theorem~\ref{xintweightgen}, $a_i = h_i(\mathcal{A}_i)$ for each $i \in [k]$, and $b_i = h_i(\mathcal{H}_i(1))$ for each $i \in [k]$, then Theorem~\ref{xintweight} gives us $\prod_{i=1}^{k-1} \prod_{j \in [k] \backslash [i]} a_ia_j \leq \prod_{i=1}^{k-1} \prod_{j \in [k] \backslash [i]} b_ib_j$, and hence $\left( \prod_{i=1}^k a_i \right)^{k-1} \leq \left( \prod_{i=1}^k b_i \right)^{k-1}$ (giving $\prod_{i=1}^k a_i \leq \prod_{i=1}^k b_i$, as required).

We now start working towards the proofs of Theorems~\ref{xintweight}, \ref{mainpartial}, \ref{main} and \ref{multithm}. 




\section{Proof of the main result} \label{Weightedsection} 

This section is dedicated to the proof of Theorem~\ref{xintweight}.

For the extremal cases, we shall use the following lemma.

\begin{lemma}\label{complemma1} Let $\mathcal{H}$ be a compressed subfamily of $2^{[n]}$, and let $w \colon \mathcal{H} \rightarrow \mathbb{R}^+$ such that  $w(\delta_{i,j}(H)) \geq w(H)$ for every $H \in \mathcal{H}$ and every $i,j \in [n]$ with $i < j$. Then $w(\mathcal{H}(a)) \leq w(\mathcal{H}(1))$ for each $a \in [n]$.
\end{lemma}
%
\begin{proof} Let $a \in [n]$. Let $\mathcal{D} = \Delta_{1,a}(\mathcal{H}(a))$. Since $\mathcal{H}$ is compressed, $\mathcal{D} \subseteq \mathcal{H}$. Thus it is immediate from the definitions of $\mathcal{D}$ and $w$ that $w(\mathcal{D}) \geq w(\mathcal{H}(a))$. The result follows if we show that $\mathcal{D} \subseteq \mathcal{H}(1)$. Let $D \in \mathcal{D}$. If $D \notin \mathcal{H}(a)$, then $D = \delta_{1,a}(H) \neq H$ for some $H \in \mathcal{H}(a)$, and hence $1 \in D$. Suppose $D \in \mathcal{H}(a)$. If we assume that $\delta_{1,a}(D) \notin \mathcal{H}(a)$, then we obtain $D \notin \Delta_{1,a}(\mathcal{H}(a))$, contradicting $D \in \mathcal{D}$. Hence $\delta_{1,a}(D) \in \mathcal{H}(a)$. Thus, since $a \in D$ and $a \in \delta_{1,a}(D)$, $1 \in D$. \end{proof}

We need to use the following well-known properties of compressions. It is straightforward that for $i, j \in [n]$ and $\mathcal{A} \subseteq 2^{[n]}$,
%
\[|\Delta_{i,j}(\mathcal{A})| = |\mathcal{A}|.\] 
%
Moreover, we have the following. 

\begin{lemma}\label{compcross} Let $\mathcal{A}$ and $\mathcal{B}$ be cross-intersecting subfamilies of $2^{[n]}$.\\
(i) For any $i, j \in [n]$, $\Delta_{i,j}(\mathcal{A})$ and $\Delta_{i,j}(\mathcal{B})$ are cross-intersecting subfamilies of $2^{[n]}$.\\
(ii) If $r, s \in [n]$, $\mathcal{A} \subseteq {[n] \choose \leq r}$, $\mathcal{B} \subseteq {[n] \choose \leq s}$, and $\mathcal{A}$ and $\mathcal{B}$ are compressed, then 
%
\[A \cap B \cap [r+s-1] \neq \emptyset\] 
%
for any $A \in \mathcal{A}$ and any $B \in \mathcal{B}$.\\
(iii) For some $h \in \mathbb{N}$, there exist $i_1, \dots, i_h, j_1, \dots, j_h \in [n]$ such that $i_1 < j_1, \dots, i_h < j_h$, and $\Delta_{i_h,j_h} \circ \dots \circ \Delta_{i_1,j_1}(\mathcal{A})$ and $\Delta_{i_h,j_h} \circ \dots \circ \Delta_{i_1,j_1}(\mathcal{B})$ are cross-intersecting and compressed.
\end{lemma}
%
\noindent
A proof of Lemma~\ref{compcross} is essentially given in \cite[Section~2]{Borg11} (see also \cite{F}). The only difference is that in \cite{Borg11}, part (ii) is proved for $\mathcal{A} \subseteq {[n] \choose r}$ and $\mathcal{B} \subseteq {[n] \choose s}$; however, the argument carries forward for $\mathcal{A} \subseteq {[n] \choose \leq r}$ and $\mathcal{B} \subseteq {[n] \choose \leq s}$.

\begin{proof}[Proof of Theorem~\ref{xintweight}] We use induction on $m + n$. The basis is $m + n = 2$ with $m = n = 1$, in which case the result is trivial. Now consider $m + n > 2$. We may assume that $m \leq n$. If $m = 1$, then the result is trivial too, so we consider $m \geq 2$. If at least one of $\mathcal{G}$ and $\mathcal{H}$ is $\{\emptyset\}$, then we trivially have $g(\mathcal{A})h(\mathcal{B}) = 0 = g(\mathcal{G}(1))h(\mathcal{H}(1))$. Thus, we will assume that $\mathcal{G} \neq \{\emptyset\}$ and $\mathcal{H} \neq \{\emptyset\}$, meaning that each of $\mathcal{G}$ and $\mathcal{H}$ contain at least one non-empty set. Since $\mathcal{G}$ and $\mathcal{H}$ are hereditary and compressed, we clearly have $\{1\} \in \mathcal{G}$ and $\{1\} \in \mathcal{H}$. So $g(\mathcal{G}(1)) > 0$ and $h(\mathcal{H}(1)) > 0$. Let $\mathcal{A} \subseteq \mathcal{G}$ and $\mathcal{B} \subseteq  \mathcal{H}$ such that $g(\mathcal{A}) h(\mathcal{B})$ is maximum under the condition that $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting. Since $\mathcal{G}(1)$ and $\mathcal{H}(1)$ are cross-intersecting, it follows that 
%
\begin{equation} g(\mathcal{A}) h(\mathcal{B}) \geq g(\mathcal{G}(1)) h(\mathcal{H}(1)) > 0. \label{main0.1}
\end{equation} 

We will first show that we may assume that $\mathcal{A}$ and $\mathcal{B}$ are compressed.

By Lemma~\ref{compcross}(iii), we can apply left-compressions to $\mathcal{A}$ and $\mathcal{B}$ simultaneously until we obtain two compressed cross-intersecting families $\mathcal{A}^*$ and $\mathcal{B}^*$ such that $|\mathcal{A}^*| = |\mathcal{A}|$ and $|\mathcal{B}^*| = |\mathcal{B}|$. Since $\mathcal{G}$ and $\mathcal{H}$ are compressed, $\mathcal{A}^* \subseteq \mathcal{G}$ and $\mathcal{B}^* \subseteq \mathcal{H}$. From (b) we obtain $g(\mathcal{A}) \leq g(\mathcal{A}^*)$ and $h(\mathcal{B}) \leq h(\mathcal{B}^*)$. By the choice of $\mathcal{A}$ and $\mathcal{B}$, we actually have $g(\mathcal{A}) = g(\mathcal{A}^*)$ and $h(\mathcal{B}) = h(\mathcal{B}^*)$. 

We now show that we may also work with $\mathcal{A}^*$ and $\mathcal{B}^*$ for the purpose of establishing the second part of the theorem (that is, the characterization of the extremal structures for $u \neq 0 \neq v$). Suppose that $\mathcal{A}^* = \mathcal{G}(c)$ and $\mathcal{B}^* = \mathcal{H}(c)$ for some $c \in [m] \cap [n]$ such that $g(\mathcal{G}(c)) = g(\mathcal{G}(1))$ and $h(\mathcal{H}(c)) = h(\mathcal{H}(1))$. Then $g(\mathcal{G}(c)) > 0$ and $h(\mathcal{H}(c)) > 0$. So $\mathcal{G}(c) \neq \emptyset$  and $\mathcal{H}(c) \neq \emptyset$. Thus, since $\mathcal{G}$ and $\mathcal{H}$ are hereditary, $\{c\} \in \mathcal{A}^*$ and $\{c\} \in \mathcal{B}^*$. So $\{a\} \in \mathcal{A}$ for some $a \in [m]$, and $\{b\} \in \mathcal{B}$ for some $b \in [n]$. Since $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, we have $a = b$, $\mathcal{A} \subseteq \mathcal{G}(a)$ and $\mathcal{B} \subseteq \mathcal{H}(a)$. Since $\mathcal{G}(a)$ and $\mathcal{H}(a)$ are cross-intersecting, it follows by the choice of $\mathcal{A}$ and $\mathcal{B}$ that $\mathcal{A} = \mathcal{G}(a)$, $\mathcal{B} = \mathcal{H}(a)$, and $g(\mathcal{G}(a))h(\mathcal{H}(a)) \geq g(\mathcal{G}(1))h(\mathcal{H}(1))$. Since Lemma~\ref{complemma1} gives us $g(\mathcal{G}(a)) \leq g(\mathcal{G}(1))$ and $h(\mathcal{H}(a)) \leq h(\mathcal{H}(1))$, it follows that we actually have $g(\mathcal{G}(a))h(\mathcal{H}(a)) = g(\mathcal{G}(1))h(\mathcal{H}(1))$, $g(\mathcal{G}(a)) = g(\mathcal{G}(1))$ and $h(\mathcal{H}(a)) = h(\mathcal{H}(1))$.

Therefore, we may (and will) assume that $\mathcal{A}$ and $\mathcal{B}$ are compressed. 

Define $\mathcal{H}_0 = \{H \in \mathcal{H} \colon n \notin H\}$
and $\mathcal{H}_1 = \{H \backslash \{n\} \colon n \in H \in
\mathcal{H}\}$. Define $\mathcal{G}_0$, $\mathcal{G}_1$,
$\mathcal{A}_0$, $\mathcal{A}_1$, $\mathcal{B}_0$ and
$\mathcal{B}_1$ similarly. Since $\mathcal{A}$, $\mathcal{B}$,
$\mathcal{G}$ and $\mathcal{H}$ are compressed, we clearly have
that $\mathcal{A}_0$, $\mathcal{A}_1$, $\mathcal{B}_0$,
$\mathcal{B}_1$, $\mathcal{G}_0$, $\mathcal{G}_1$,
$\mathcal{H}_0$ and $\mathcal{H}_1$ are compressed. Since
$\mathcal{G}$ and $\mathcal{H}$ are hereditary, we clearly have
that $\mathcal{G}_0$, $\mathcal{G}_1$, $\mathcal{H}_0$ and
$\mathcal{H}_1$ are hereditary, $\mathcal{G}_1 \subseteq \mathcal{G}_0$ and $\mathcal{H}_1 \subseteq \mathcal{H}_0$. If $\mathcal{G}_1 = \emptyset$, then $\mathcal{G} \subseteq 2^{[m-1]}$, and hence we obtain the result immediately from the induction hypothesis. The same occurs if $\mathcal{H}_1 = \emptyset$. So we assume that $\mathcal{G}_1$ and $\mathcal{H}_1$ are non-empty. Since $\mathcal{G}_1 \subseteq \mathcal{G}_0$ and $\mathcal{H}_1 \subseteq \mathcal{H}_0$, $\mathcal{G}_0$ and $\mathcal{H}_0$ are non-empty too. Obviously, we have $\mathcal{A}_0 \subseteq \mathcal{G}_0 \subseteq 2^{[m-1]}$,
$\mathcal{A}_1 \subseteq \mathcal{G}_1 \subseteq 2^{[m-1]}$,
$\mathcal{B}_0 \subseteq \mathcal{H}_0 \subseteq 2^{[n-1]}$ and
$\mathcal{B}_1 \subseteq \mathcal{H}_1 \subseteq 2^{[n-1]}$.

Let $h_0 : \mathcal{H}_0 \rightarrow \mathbb{R}^+$ such that $h_0(H) = h(H)$ for each $H \in \mathcal{H}_0$. Let $h_1 : \mathcal{H}_1 \rightarrow \mathbb{R}^+$ such that $h_1(H) = h(H \cup \{n\})$ for each $H \in \mathcal{H}_1$ (note that $H \cup \{n\} \in \mathcal{H}(n)$ by definition of $\mathcal{H}_1$). By (b) and (d), we have the following consequences. For any $A, B \in \mathcal{H}_0$ with $\emptyset \neq A \subsetneq B$,
%
\begin{equation} h_0(A) = h(A) \geq (1+v)h(B) = (1+v)h_0(B). \label{main1}
\end{equation}
%
For any $C \in \mathcal{H}_0$ and any $i,j \in [n-1]$ with $i < j$,
%
\begin{equation} h_0(\delta_{i,j}(C)) = h(\delta_{i,j}(C)) \geq h(C) = h_0(C). \label{main2}
\end{equation}
%
For any $A, B \in \mathcal{H}_1$ with $\emptyset \neq A \subsetneq B$,
%
\begin{equation} h_1(A) = h(A \cup \{n\}) \geq (1+v)h(B \cup \{n\}) = (1+v)h_1(B). \label{main3}
\end{equation}
%
For any $C \in \mathcal{H}_1$ and any $i,j \in [n-1]$ with $i < j$,
%
\begin{equation} h_1(\delta_{i,j}(C)) = h(\delta_{i,j}(C) \cup \{n\}) = h(\delta_{i,j}(C \cup \{n\})) \geq h(C \cup \{n\}) = h_1(C). \label{main4}
\end{equation}
%
Thus, we have shown that properties (b) and (d) are inherited by $h_0$ and $h_1$.

Since $\mathcal{B} = \mathcal{B}_0 \cup \mathcal{B}(n)$, $\mathcal{B}_0 \cap \mathcal{B}(n) = \emptyset$ and $\mathcal{B}(n) = \{B \cup \{n\} \colon B \in \mathcal{B}_1\}$, we have
%
\begin{equation} h(\mathcal{B}) = h(\mathcal{B}_0) + h(\mathcal{B}(n)) = h_0(\mathcal{B}_0) + h_1(\mathcal{B}_1). \label{main4.2}
\end{equation}
%
Along the same lines,
%
\begin{align} h(\mathcal{H}(1)) &= h(\mathcal{H}_0(1)) + h(\{H \in \mathcal{H} \colon 1, n \in H\}) \nonumber \\
&= h_0(\mathcal{H}_0(1)) + h(\{H \cup \{n\} \colon H \in \mathcal{H}_1(1)\}) \nonumber \\
&= h_0(\mathcal{H}_0(1)) + h_1(\mathcal{H}_1(1)). \label{main4.3}
\end{align}
%

Suppose $m < n$.  Clearly, $\mathcal{A}$ and $\mathcal{B}_0$ are
cross-intersecting. Since $m < n$, no set in $\mathcal{A}$ contains $n$, and hence $\mathcal{A}$ and $\mathcal{B}_1$ are cross-intersecting. Thus, by the induction hypothesis,
%
\begin{equation} g(\mathcal{A})h_j(\mathcal{B}_j) \leq g(\mathcal{G}(1))h_j(\mathcal{H}_j(1)) \quad \mbox{for each $j \in \{0, 1\}$}. \label{main4.4}
\end{equation}
%
Together with (\ref{main4.2}) and (\ref{main4.3}), this gives us
%
\begin{align} g(\mathcal{A})h(\mathcal{B})
%&= g(\mathcal{A}) \left(h_0
%(\mathcal{B}_0) + h_1(\mathcal{B}_1) \right) %\nonumber \\
&= g(\mathcal{A})h_0(\mathcal{B}_0) + g(\mathcal{A})h_1(\mathcal{B}_1) \nonumber \\
&\leq g(\mathcal{G}(1))h_0(\mathcal{H}_0(1)) + g(\mathcal{G}(1))h_1(\mathcal{H}_1(1)) \nonumber \\
&= g(\mathcal{G}(1))h(\mathcal{H}(1)). \label{main4.45}
\end{align}
%
This establishes the first part of the theorem for $m < n$, and we now verify the second part for this case. By (\ref{main0.1}), equality holds throughout in (\ref{main4.45}). Thus, in (\ref{main4.4}), we actually have equality. Suppose $u \neq 0$ and $v \neq 0$. Then, by the induction hypothesis, for each $j \in \{0,1\}$ we have $\mathcal{A} = \mathcal{G}(a_j)$ and $\mathcal{B}_j = \mathcal{H}_j(a_j)$ for some $a_j \in [m]$ such that $g(\mathcal{G}(a_j)) = g(\mathcal{G}(1))$ and $h_j(\mathcal{H}_j(a_j)) = h_j(\mathcal{H}_j(1))$. So $g(\mathcal{G}(a_0)) > 0$, and hence $\mathcal{G}(a_0) \neq \emptyset$. Thus, since $\mathcal{G}$ is hereditary, $\{a_0\} \in \mathcal{A}$. Since $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, $\mathcal{B} \subseteq \mathcal{H}(a_0)$. Since $\mathcal{G}(a_0)$ and $\mathcal{H}(a_0)$ are cross-intersecting, it follows by the choice of $\mathcal{A}$ and $\mathcal{B}$ that $\mathcal{A} = \mathcal{G}(a_0)$ and $\mathcal{B} = \mathcal{H}(a_0)$. Thus, since $g(\mathcal{A})h(\mathcal{B}) = g(\mathcal{G}(1))h(\mathcal{H}(1))$, and since Lemma~\ref{complemma1} gives us $g(\mathcal{G}(a_0)) \leq g(\mathcal{G}(1))$ and $h(\mathcal{H}(a_0)) \leq h(\mathcal{H}(1))$, we have $g(\mathcal{G}(a_0)) = g(\mathcal{G}(1))$ and $h(\mathcal{H}(a_0)) = h(\mathcal{H}(1))$.\medskip

Now suppose $m=n$. Similarly to $h_0$ and $h_1$, let $g_0 : \mathcal{G}_0 \rightarrow \mathbb{R}^+$ such that $g_0(G) = g(G)$ for each $G \in \mathcal{G}_0$, and let $g_1 : \mathcal{G}_1 \rightarrow \mathbb{R}^+$ such that $g_1(G) = g(G \cup \{n\})$ for each $G \in \mathcal{G}_1$ (note that, since $m = n$, $G \cup \{n\} \in \mathcal{G}(n)$ by definition of $\mathcal{G}_1$). Then properties (a) and (c) are inherited by $g_0$ and $g_1$ in the same way (b) and (d) are inherited by $h_0$ and $h_1$ as shown above; that is, similarly to (\ref{main1})--(\ref{main4}), we have the following. For any $A, B \in \mathcal{G}_0$ with $\emptyset \neq A \subsetneq B$,
%
\begin{equation} g_0(A) \geq (1+u)g_0(B). \label{main5}
\end{equation}
%
For any $C \in \mathcal{G}_0$ and any $i,j \in [n-1]$ with $i < j$,
%
\begin{equation} g_0(\delta_{i,j}(C)) \geq g_0(C). \label{main6}
\end{equation}
%
For any $A, B \in \mathcal{G}_1$ with $\emptyset \neq A \subsetneq B$,
%
\begin{equation} g_1(A) \geq (1+u)g_1(B). \label{main7}
\end{equation}
%
For any $C \in \mathcal{G}_1$ and any $i,j \in [n-1]$ with $i < j$,
%
\begin{equation} g_1(\delta_{i,j}(C)) \geq g_1(C). \label{main8}
\end{equation}

Similarly to (\ref{main4.2}) and (\ref{main4.3}), we have
%
\begin{gather} g(\mathcal{A}) = g_0(\mathcal{A}_0) + g_1(\mathcal{A}_1), \label{main4.1} \\
g(\mathcal{G}(1)) = g_0(\mathcal{G}_0(1)) + g_1(\mathcal{G}_1(1)). \label{main4.6}
\end{gather}
%

Clearly, $\mathcal{A}_0$ and $\mathcal{B}_0$ are cross-intersecting, and, since $n = m$, so are $\mathcal{A}_0$ and $\mathcal{B}_1$, and also $\mathcal{A}_1$ and $\mathcal{B}_0$.

Let us first assume that $\mathcal{A}_1$ and $\mathcal{B}_1$ are cross-intersecting too. Then, by the induction hypothesis,
%
\begin{equation} g_i(\mathcal{A}_i)h_j(\mathcal{B}_j) \leq g_i(\mathcal{G}_i(1))h_j(\mathcal{H}_j(1)) \quad \mbox{for any $i, j \in \{0, 1\}$.} \label{main4.5}
\end{equation}
%
Together with (\ref{main4.2}), (\ref{main4.3}), (\ref{main4.1}) and (\ref{main4.6}), this gives us
%
\begin{align} g(\mathcal{A})h(\mathcal{B}) &= g_0(\mathcal{A}_0) h_0(\mathcal{B}_0) + g_0(\mathcal{A}_0) h_1(\mathcal{B}_1) + \nonumber \\
& \quad \mbox{ } g_1(\mathcal{A}_1) h_0(\mathcal{B}_0) + g_1(\mathcal{A}_1)h_1(\mathcal{B}_1) \nonumber \\
&\leq g_0(\mathcal{G}_0(1))h_0(\mathcal{H}_0(1)) + g_0(\mathcal{G}_0(1))h_1(\mathcal{H}_1(1)) + \nonumber \\
& \quad \mbox{ } g_1(\mathcal{G}_1(1))h_0(\mathcal{H}_0(1)) + g_1(\mathcal{G}_1(1))h_1(\mathcal{H}_1(1)) \nonumber \\
&= g(\mathcal{G}(1))h(\mathcal{H}(1)). \nonumber
\end{align}
%
By (\ref{main0.1}), equality holds throughout, and hence $g(\mathcal{A})h(\mathcal{B}) = g(\mathcal{G}(1))h(\mathcal{H}(1))$. So in (\ref{main4.5}) we actually have equality. Suppose $u \neq 0 \neq v$. By the induction hypothesis, we particularly have $\mathcal{A}_0 = \mathcal{G}_0(a_0)$ and $\mathcal{B}_0 = \mathcal{H}_0(a_0)$ for some $a_0 \in [n-1]$ such that $g_0(\mathcal{G}_0(a_0)) = g_0(\mathcal{G}_0(1))$ and $h_0(\mathcal{H}_0(a_0)) = h_0(\mathcal{H}_0(1))$. Recall that $\{1\} \in \mathcal{G}$. So $\{1\} \in \mathcal{G}_0$, and hence $g_0(\mathcal{G}_0(1)) > 0$. So $g_0(\mathcal{G}_0(a_0)) > 0$, and hence $\mathcal{G}_0(a_0) \neq \emptyset$. Thus, since $\mathcal{G}$ is hereditary, $\{a_0\} \in \mathcal{A}$. Since $\mathcal{A}_0$ and $\mathcal{B}$ are cross-intersecting, $\mathcal{B} \subseteq \mathcal{H}(a_0)$. Similarly, we obtain $\mathcal{A} \subseteq \mathcal{G}(a_0)$. As in the case $m < n$, we conclude that $\mathcal{A} = \mathcal{G}(a_0)$, $\mathcal{B} = \mathcal{H}(a_0)$, $g(\mathcal{G}(a_0)) = g(\mathcal{G}(1))$ and $h(\mathcal{H}(a_0)) = h(\mathcal{H}(1))$.\medskip

Suppose that $\mathcal{A}_1$ and $\mathcal{B}_1$ are not cross-intersecting. Then there exists $A_1 \in \mathcal{A}_1$ such that $A_1 \cap B = \emptyset$ for some $B \in \mathcal{B}_1$. Let $B_1 = [n-1] \backslash A_1$, $A_1' = A_1 \cup \{n\}$, $B_1' = B_1 \cup \{n\}$. Since $A_1 \in \mathcal{A}_1$, $A_1' \in \mathcal{A}$.

If $A_1 = [n-1]$, then $B = B_1$. Suppose $A_1 \neq [n-1]$ and $B \neq B_1$. Then $B \subsetneq [n-1] \backslash A_1$, and hence $[n-1] \backslash (A_1 \cup B) \neq \emptyset$. Let $c \in [n-1] \backslash (A_1 \cup B)$. Since $B \in \mathcal{B}_1$, $B \cup \{n\} \in \mathcal{B}$. Let $C = \delta_{c,n}(B \cup \{n\})$. Since $c \notin B \cup \{n\}$, $C = B \cup \{c\}$. Since $\mathcal{B}$ is compressed, $C \in \mathcal{B}$. However, since $c \notin A_1'$ and $A_1 \cap B = \emptyset$, we have $A_1' \cap C = \emptyset$, which is a contradiction as $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting. 

We have therefore shown that
%
\begin{equation}\mbox{$B_1$ is the unique set in $\mathcal{B}_1$ that does not intersect $A_1$.} \label{main8.1}
\end{equation}
%
%One of the implications of this is that $B_i' \in \mathcal{B}$ for each %$i \in [k]$.
By a similar argument,
%
\begin{equation}\mbox{$A_1$ is the unique set in $\mathcal{A}_1$ that does not intersect $B_1$.} \label{main8.2}
\end{equation}
%
Since $B_1 \in \mathcal{B}_1$, $B_1' \in \mathcal{B}$. Since $\mathcal{A}$ and $\mathcal{B}$ are compressed, %we particularly %have
%
\begin{equation} \mbox{$\delta_{p,n}(A_1') \in \mathcal{A}$ \quad and \quad $\delta_{p,n}(B_1') \in \mathcal{B}$ \quad for each $p \in [n-1]$.} \label{main9}
\end{equation}

Since $A_1 \cap B_1' = A_1 \cap B_1 = \emptyset$ and $B_1 \cap A_1' = B_1 \cap A_1 = \emptyset$, we have $A_1 \notin \mathcal{A}$ and $B_1 \notin \mathcal{B}$. Let $\mathcal{A}' = \mathcal{A} \cup \{A_1\}$, $\mathcal{A}'' = \mathcal{A} \backslash \{A_1'\}$, $\mathcal{B}' = \mathcal{B} \backslash \{B_1'\}$, $\mathcal{B}'' = \mathcal{B} \cup \{B_1\}$. By (\ref{main8.1}), $\mathcal{A}'$ and $\mathcal{B}'$ are cross-intersecting. By (\ref{main8.2}), $\mathcal{A}''$ and $\mathcal{B}''$ are cross-intersecting. Since $\mathcal{G}$ and $\mathcal{H}$ are hereditary, and since $A_1' \in \mathcal{A} \subseteq \mathcal{G}$ and $B_1' \in \mathcal{B} \subseteq \mathcal{H}$, we have $A_1 \in \mathcal{G}$ and $B_1 \in \mathcal{H}$, and hence $\mathcal{A}', \mathcal{A}'' \subseteq \mathcal{G}$ and $\mathcal{B}', \mathcal{B}'' \subseteq \mathcal{H}$. 

Let $x = g(\mathcal{A})$ and $x_1 = g(A_1')$. Let $y = h(\mathcal{B})$ and $y_1 = h(B_1')$. We have
%
\begin{align} &g(\mathcal{A}') = x + g(A_1) \geq x + (1+u)g(A_1') = x + (1+u)x_1,  \nonumber \\
&g(\mathcal{A}'') = x - g(A_1') = x - x_1, \nonumber \\
&h(\mathcal{B}') = y - h(B_1') = y - y_1, \nonumber \\
&h(\mathcal{B}'') = y + h(B_1) \geq y + (1+v)h(B_1') = y + (1+v)y_1.  \nonumber
\end{align}
%
By the choice of $\mathcal{A}$ and $\mathcal{B}$, 
%
\[g(\mathcal{A}')h(\mathcal{B}') \leq g(\mathcal{A})h(\mathcal{B}) \quad \mbox{and} \quad g(\mathcal{A}'')h(\mathcal{B}'') \leq g(\mathcal{A})h(\mathcal{B}).\]
%
So we have

%
\begin{align} &(x + (1+u)x_1)(y - y_1) \leq xy \quad \mbox{and} \quad (x - x_1)(y + (1+v)y_1) \leq xy \nonumber \\
&\Rightarrow (1+u)x_1y \leq xy_1 + (1+u)x_1y_1 \quad \mbox{and} \quad (1+v)xy_1 \leq x_1y + (1+v)x_1y_1 \nonumber \\
&\Rightarrow  (1+u)x_1y + (1+v)xy_1 \leq (xy_1 + (1+u)x_1y_1) + (x_1y + (1+v)x_1y_1) \nonumber \\
&\Rightarrow  ux_1y + vxy_1 \leq (2+u+v)x_1y_1. \label{main9.1}
\end{align}
%

Suppose $A_1 \neq \emptyset$ and $B_1 \neq \emptyset$. It follows by definition of $B_1$ that  $[n-1] \backslash A_1 \neq \emptyset$ and $[n-1] \backslash B_1 \neq \emptyset$. Let $a \in [n-1] \backslash A_1$ and $b \in [n-1] \backslash B_1$. Let $A_1'' = \delta_{a,n}(A_1')$ and $B_1'' = \delta_{b,n}(B_1')$. So $A_1'' \neq A_1'$ and $B_1'' \neq B_1'$. By (\ref{main9}), $A_1'' \in \mathcal{A}$ and $B_1'' \in \mathcal{B}$. By (b), $g(A_1'') \geq g(A_1')$ and $h(B_1'') \geq h(B_1')$. We therefore have $x \geq x_1 + g(A_1'') \geq 2x_1$ and $y \geq y_1 + h(B_1'') \geq 2y_1$. By (\ref{main9.1}), we have 
%
\begin{align} (2+u+v)x_1y_1 &\geq ux_1y + vxy_1 \geq ux_1(2y_1) + v(2x_1)y_1 \nonumber \\
&= (2u+2v)x_1y_1 \geq (2+u+v)x_1y_1 \nonumber
\end{align}
%
(since we are given that $u+v \geq 2$), and hence equality holds throughout. Thus $x = 2x_1$ and $y = 2y_1$. Consequently, we have $\mathcal{A} = \{A_1', A_1''\}$, $\mathcal{B} = \{B_1', B_1''\}$, $g(A_1'') = g(A_1')$ and $h(B_1'') = h(B_1')$. Let $A_2 = [|A_1'|]$, $B_2 = [|B_1'|]$ and $I = \{1\}$. Since $\mathcal{G}$ is compressed and $A_1' \in \mathcal{A} \subseteq \mathcal{G}$, $A_2 \in \mathcal{G}$ and $g(A_2) \geq g(A_1')$. Similarly, $B_2 \in \mathcal{H}$ and $h(B_2) \geq h(B_1')$. Since $A_1 \neq \emptyset$, we have $|A_1'| \geq 2$, and hence $|A_2| \geq 2$. Since $\mathcal{G}$ is hereditary and $I \subsetneq A_2 \in \mathcal{G}$, $I \in \mathcal{G}$ and $g(I) \geq (1+u)g(A_2)$. Similarly, $I \in \mathcal{H}$ and $h(I) \geq (1+v)h(B_2)$. Let $\mathcal{C} = \{I,A_2\}$ and $\mathcal{D} = \{I,B_2\}$. So $\mathcal{C} \subseteq \mathcal{G}$ and $\mathcal{D} \subseteq \mathcal{H}$. Also, $\mathcal{C}$ and $\mathcal{D}$ are cross-intersecting. We have 
%
\begin{align} g(\mathcal{C}) h(\mathcal{D}) &= (g(I) + g(A_2))(h(I) + h(B_2)) \nonumber \\ 
& \geq ((2+u)g(A_2))((2+v)h(B_2)) \geq (2+u)(2+v)g(A_1')h(B_1') \nonumber \\
&= (2+u)(2+v)x_1y_1 = (2+u)(2+v)\frac{x}{2}\frac{y}{2} \nonumber \\
&> xy = g(\mathcal{A}) h(\mathcal{B}) \quad \mbox{(since $u+v \geq 2$, $u \geq 0$, and $v \geq 0$)}, \nonumber
\end{align}
%
which contradicts the choice of $\mathcal{A}$ and $\mathcal{B}$.

Therefore, $A_1 = \emptyset$ or $B_1 = \emptyset$.

Suppose $A_1 = \emptyset$. Then $A_1' = \{n\}$ and $B_1' = [n]$. By (\ref{main9}), the sets $\{1\}, \dots, \{n\}$ are all in $\mathcal{A}$, and obviously no proper subset of $[n]$ intersects each of these sets. Thus, by the cross-intersection condition, $B_1'$ is the only set that is in $\mathcal{B}$. So 
%
\[h(\mathcal{B}'') = h(B_1') + h(B_1) \geq h(B_1') + (1+v)h(B_1') = (2+v)h(B_1') = (2+v)h(\mathcal{B}).\] 
%
Since $\{1\}, \dots, \{n\} \in \mathcal{A}$ and $A_1' = \{n\}$, we have
%
\begin{equation} ng(A_1') \leq g(A_1') + \sum_{p=1}^{n-1} g(\delta_{p,n}(A_1')) = \sum_{p=1}^n g(\{p\}) \leq g(\mathcal{A}), \label{main10}
\end{equation} 
%
and hence $g(A_1') \leq g(\mathcal{A})/n$. Since $g(\mathcal{A}'') = g(\mathcal{A}) - g(A_1')$, $g(\mathcal{A}'') \geq \frac{n-1}{n}g(\mathcal{A})$. Thus $g(\mathcal{A}'') h(\mathcal{B}'') \geq \frac{n-1}{n}g(\mathcal{A}) (2+v)h(\mathcal{B}) \geq g(\mathcal{A}) h(\mathcal{B})$. Since $g(\mathcal{A}'')h(\mathcal{B}'') \leq g(\mathcal{A}) h(\mathcal{B})$ (by the choice of $\mathcal{A}$ and $\mathcal{B}$), it follows that $g(\mathcal{A}'')h(\mathcal{B}'') = g(\mathcal{A}) h(\mathcal{B})$, $v = 0$, $n = 2$, and $g(\mathcal{A}'') = \frac{1}{2}g(\mathcal{A})$. Thus $g(\mathcal{A}) = 2g(A_1') = ng(A_1')$, and hence, by (\ref{main10}), we obtain $\mathcal{A} = \{\{1\}, \{2\}\}$ and $g(\{1\}) = g(\{2\})$.  We have $\mathcal{A}'' = \{\{1\}\} \subseteq \mathcal{G}(1)$ and $\mathcal{B}'' = \{B_1, B_1'\} = \{\{1\}, [2]\} \subseteq \mathcal{H}(1)$. Thus $g(\mathcal{A}) h(\mathcal{B}) \leq g(\mathcal{G}(1)) h(\mathcal{H}(1))$.

Similarly, if $B_1 = \emptyset$, then $g(\mathcal{A})h(\mathcal{B}) = g(\mathcal{A}') h(\mathcal{B}')$, $u = 0$, $n = 2$, $\mathcal{A}' = \{A_1, A_1'\} = \{\{1\}, [2]\} \subseteq \mathcal{G}(1)$ and $\mathcal{B}' = \{\{1\}\} \subseteq \mathcal{H}(1)$. Thus $g(\mathcal{A}) h(\mathcal{B}) \leq g(\mathcal{G}(1)) h(\mathcal{H}(1))$.\end{proof} 

%From the last part of the proof, we immediately obtain a characterisation of the extremal structures for the case $n = m = 2$ too. 



\section{Proofs of Theorems~\ref{mainpartial} and \ref{main}} \label{Proofmain}

In this section, we use Theorem~\ref{xintweight} to prove Theorems~\ref{mainpartial} and \ref{main}. Recall that for any IP sequence ${\bf c} = (c_1, \dots, c_n)$ and any $r \in [n]$, $\mathcal{L}_{{\bf c}}^{(r)}$ denotes the family 
%
\[\left\{ \{(x_1,y_{x_1}), \dots, (x_r, y_{x_r})\} \colon \{x_1, \dots, x_r\} \in {[n] \choose r}, \, y_{x_j} \in [c_{x_j}] \mbox{ for each } j \in [r] \right\}.\]
%
Let $\mathcal{L}_{\bf c}^{(\leq r)}$ denote the union $\bigcup_{i = 1}^r \mathcal{L}_{\bf c}^{(i)}$.

We start by defining a compression operation for labeled sets. For any $x, y \in \mathbb{N}$, let
%
\[ \gamma_{x,y}(A) = \left\{ \begin{array}{ll}
(A \backslash \{(x,y)\}) \cup \{(x,1)\} & \mbox{if $(x,y) \in A$};\\
A & \mbox{otherwise}
\end{array} \right. \]
%
for any labeled set $A$, and let
%
\[\Gamma_{x,y}(\mathcal{A}) = \{\gamma_{x,y}(A) \colon A \in \mathcal{A}, \gamma_{x,y}(A) \notin \mathcal{A}\} \cup \{A \in \mathcal{A} \colon \gamma_{x,y}(A) \in
\mathcal{A}\}\]
%
for any family $\mathcal{A}$ of labeled sets.

Note that $|\Gamma_{x,y}(\mathcal{A})| = |\mathcal{A}|$ and that if $\mathcal{A} \subseteq \mathcal{L}_{\bf c}^{(r)}$, then $\Gamma_{x,y}(\mathcal{A}) \subseteq \mathcal{L}_{\bf c}^{(r)}$. It is easy to check that if $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting families of labeled sets, then so are $\Gamma_{x,y}(\mathcal{A})$ and $\Gamma_{x,y}(\mathcal{B})$. We prove more than this.

\begin{lemma}\label{gamma} Let ${\bf c} = (c_1, \dots, c_m)$ and ${\bf d} = (d_1, \dots, d_n)$ be IP sequences. Let $x,y \in \mathbb{N}$, $y \geq 2$. Let $l = \max\{m,n\}$ and $h = \max\{c_m, d_n\}$. Let $V \subseteq [l] \times [2,h]$. Let $\mathcal{A} \subseteq \mathcal{L}_{\bf c}^{(\leq m)}$ and $\mathcal{B} \subseteq \mathcal{L}_{\bf d}^{(\leq n)}$ such that $(A \cap B) \backslash V \neq \emptyset$ for every $A \in \mathcal{A}$ and every $B \in \mathcal{B}$. Then $(C \cap D) \backslash (V \cup \{(x,y)\}) \neq \emptyset$ for every $C \in \Gamma_{x,y}(\mathcal{A})$ and every $D \in \Gamma_{x,y}(\mathcal{B})$.
\end{lemma}
%
\begin{proof} Let $C \in \Gamma_{x,y}(\mathcal{A})$ and $D \in \Gamma_{x,y}(\mathcal{B})$. We first show that $(C \cap D) \backslash
V \neq \emptyset$. Let $C' = (C \backslash \{(x,1)\}) \cup \{(x,y)\}$. If $C \in \mathcal{A}$ and $D \in \mathcal{B}$, then $(C \cap D) \backslash V \neq \emptyset$. If $C \notin \mathcal{A}$ and $D \notin \mathcal{B}$, then $(x,1)$ is in both $C$ and $D$, and hence, since $(x,1) \notin V$, $(x,1) \in (C \cap D) \backslash V$. Suppose $C \notin \mathcal{A}$ and $D \in \mathcal{B}$.  So $(x,1) \in C$ and $C' \in \mathcal{A}$. If $(x,y) \notin D$, then, since $C' \in \mathcal{A}$ and $D \in \mathcal{B}$, $0 < |(C' \cap D) \backslash V| \leq |(C \cap D) \backslash V|$. If $(x,y) \in D$, then $\gamma_{x,y}(D) \in \mathcal{B}$ (because otherwise $D \notin \Gamma_{x,y}(\mathcal{B})$), and hence, since $C' \in \mathcal{A}$, $0 < |(C' \cap \gamma_{x,y}(D)) \backslash V| = |(C \cap D) \backslash V|$. Similarly, if $C \in \mathcal{A}$ and $D \notin \mathcal{B}$, then $(C \cap D) \backslash
V \neq \emptyset$.

Now suppose $(C \cap D) \backslash (V \cup \{(x,y)\}) = \emptyset$.
Since $(C \cap D) \backslash V \neq \emptyset$, $(x,y) \in C \cap D$. So $C, \gamma_{x,y}(C) \in \mathcal{A}$, $D, \gamma_{x,y}(D) \in \mathcal{B}$ and $|(C \cap \gamma_{x,y}(D)) \backslash V| = |(C \cap D) \backslash (V \cup \{(x,y)\})| = 0$, a contradiction.\end{proof}

\begin{corollary}\label{deltacor} Let ${\bf c} = (c_1, \dots, c_m), {\bf d} = (d_1, \dots, d_n), h$ and $l$ be as in Lemma~\ref{gamma}. Let $\mathcal{A} \subseteq \mathcal{L}_{\bf c}^{(\leq m)}$ and $\mathcal{B} \subseteq \mathcal{L}_{\bf d}^{(\leq n)}$ such that $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting. Let
%
\begin{align} \mathcal{A}^* &= \Gamma_{l,h} \circ \dots \circ \Gamma_{l,2} \circ \dots \circ \Gamma_{2,h} \circ \dots \circ \Gamma_{2,2} \circ \Gamma_{1,h} \circ \dots \circ \Gamma_{1,2}(\mathcal{A}),\nonumber \\
\mathcal{B}^* &= \Gamma_{l,h} \circ \dots \circ \Gamma_{l,2} \circ \dots \circ \Gamma_{2,h} \circ \dots \circ \Gamma_{2,2} \circ \Gamma_{1,h} \circ \dots \circ \Gamma_{1,2}(\mathcal{B}). \nonumber
\end{align}
%
Then $A \cap B \cap ([l] \times [1]) \neq \emptyset$ for any $A \in \mathcal{A}^*$ and any $B \in \mathcal{B}^*$.
\end{corollary}
%
\begin{proof} Let $Z = [l] \times [2,h]$. By repeated application of Lemma~\ref{gamma} (starting with $V = \emptyset$), 
$(A \cap B) \backslash Z \neq \emptyset$ for any $A \in \mathcal{A}^*$ and any $B \in \mathcal{B}^*$. The result follows since $(A \cap B) \backslash Z = A \cap B \cap ([l] \times [1])$.\end{proof}

The next lemma is needed for the characterization of the extremal structures in Theorems~\ref{mainpartial} and \ref{main}. 

\begin{lemma}\label{ss_cross_int} Let ${\bf c} = (c_1, \dots, c_m), {\bf d} = (d_1, \dots, d_n), h$ and $l$ be as in Lemma~\ref{gamma}. Suppose $c_1 \geq 2$, $d_1 \geq 2$ and $c_1 + d_1 \geq 5$. Let $r \in [m]$ and $s \in [n]$. Let $\mathcal{A} \subseteq \mathcal{L}_{\bf c}^{(r)}$ and $\mathcal{B} \subseteq \mathcal{L}_{\bf d}^{(s)}$ such that $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting. Suppose $\Gamma_{x,y}(\mathcal{A}) = \mathcal{L}_{\bf c}^{(r)}((u,v))$ and $\Gamma_{x,y}(\mathcal{B}) = \mathcal{L}_{\bf d}^{(s)}((u,v))$ for some $(x,y), (u,v) \in [l] \times [h]$. Then $\mathcal{A} = \mathcal{L}_{\bf c}^{(r)}((w,z))$ and $\mathcal{B} = \mathcal{L}_{\bf d}^{(s)}((w,z))$ for some $(w,z) \in [l] \times [h]$.
\end{lemma}
%
\begin{proof} Since $c_1 + d_1 \geq 5$, we have $c_1 \geq 3$ or $d_1 \geq 3$. We may assume that $c_1 \geq 3$. 

Suppose $\mathcal{A} = \Gamma_{x,y}(\mathcal{A})$. Then $\mathcal{A} = \mathcal{L}_{\bf c}^{(r)}((u,v))$. Clearly, for each $B \in \mathcal{L}_{\bf d}^{(s)}$ with $(u,v) \notin B$, there exists a set in $\mathcal{L}_{\bf c}^{(r)}((u,v))$ that does not intersect $B$. Thus $\mathcal{B} \subseteq \mathcal{L}_{\bf d}^{(s)}((u,v))$. Since $\Gamma_{x,y}(\mathcal{B}) = \mathcal{L}_{\bf d}^{(s)}((u,v))$, it follows that $\mathcal{B} = \mathcal{L}_{\bf d}^{(s)}((u,v))$.

Now suppose $\mathcal{A} \neq \Gamma_{x,y}(\mathcal{A})$. So there exists $A_1 \in \mathcal{A} \backslash \Gamma_{x,y}(\mathcal{A})$ such that $\gamma_{x,y}(A_1) \in \Gamma_{x,y}(\mathcal{A}) \backslash \mathcal{A}$. Let $A_1' = \gamma_{x,y}(A_1)$. Thus $(x,y) \in A_1$ and $(u,v) \in A_1' = (A_1 \backslash \{(x,y)\}) \cup \{(x,1)\}$. 

Suppose that $(u,v) \neq (x,1)$. Then $(u,v) \in A_1$. So $A_1 \in \mathcal{L}_{\bf c}^{(r)}((u,v))$, and hence $A_1 \in \Gamma_{x,y}(\mathcal{A})$, a contradiction. 

Therefore, $(u,v) = (x,1)$. Since $A_1 \neq A_1'$, $(x,y) \neq (x,1)$.

Let $A^* \in \mathcal{L}_{\bf c}^{(r)}((x,y))$. Let $x_1, \dots, x_{s-1}$ be distinct elements of $[n] \backslash \{x\}$. For each $i \in [n]$, let $D_i = \{i\} \times [d_i]$. We are given that $3 \leq d_1 \leq \dots \leq d_n$. By definition of a labeled set, for each $i \in [n]$ we have $|A \cap D_i| \leq 1$ for all $A \in \mathcal{L}_{\bf c}^{(r)}$. Thus, $|D_i \backslash (A_1 \cup A^*)| \geq d_i - 2 \geq 1$ for each $i \in [n]$. For each $i \in [s-1]$, let $y_i \in D_i \backslash (A_1 \cup A^*)$. Let $B^* = \{(x,y), (x_1,y_1), \dots, (x_{s-1},y_{s-1})\}$. So $B^* \in \mathcal{L}_{\bf d}^{(s)}((x,y))$. Since $\Gamma_{x,y}(\mathcal{B}) = \mathcal{L}_{\bf d}^{(s)}((x,1))$, either $B^* \in \mathcal{B}$ or $\gamma_{x,y}(B^*) \in \mathcal{B}$. However, $\gamma_{x,y}(B^*) \cap A_1 = \emptyset$. So $B^* \in \mathcal{B}$. Since $\Gamma_{x,y}(\mathcal{A}) = \mathcal{L}_{\bf c}^{(r)}((x,1))$, either $A^* \in \mathcal{A}$ or $\gamma_{x,y}(A^*) \in \mathcal{A}$. However, $\gamma_{x,y}(A^*) \cap B^* = \emptyset$. So $A^* \in \mathcal{A}$. 

We have therefore shown that $\mathcal{L}_{\bf c}^{(r)}((x,y)) \subseteq \mathcal{A}$ (when $\mathcal{A} \neq \Gamma_{x,y}(\mathcal{A})$). Since $|\Gamma_{x,y}(\mathcal{A})| = |\mathcal{L}_{\bf c}^{(r)}((x,1))| = |\mathcal{L}_{\bf c}^{(r)}((x,y))|$, we actually have $\mathcal{A} = \mathcal{L}_{\bf c}^{(r)}((x,y))$. As above, it follows that $\mathcal{B} \subseteq \mathcal{L}_{\bf d}^{(s)}((x,y))$. Since $|\Gamma_{x,y}(\mathcal{B})| = |\mathcal{L}_{\bf d}^{(s)}((x,1))| = |\mathcal{L}_{\bf d}^{(s)}((x,y))|$, $\mathcal{B} = \mathcal{L}_{\bf d}^{(s)}((x,y))$.\end{proof}

\begin{lemma}\label{lemmaweighted} %Let $n \in \mathbb{N}$. Let %$\mathcal{H} = 2^{[n]}$.
Let ${\bf c}$ be an IP sequence $(c_1, \dots, c_n)$ and let $r \in [n]$. Let $w \colon {[n] \choose \leq r} \rightarrow \mathbb{N}$ such that for each $A \in {[n] \choose \leq r}$,
%
\[w(A) = \left| \left\{ L \in \mathcal{L}_{\bf c}^{(r)} \colon L \cap ([n] \times [1]) = A \times [1] \right\} \right|.\]
%
Then: \\
(i) $w(A) \geq (c_1-1)w(A')$ for any $A, A' \in {[n] \choose \leq r}$ with $A \subsetneq A'$. \\
(ii) $w(\delta_{i,j}(A)) \geq w(A)$ for any $A \in {[n] \choose \leq r}$ and any $i,j \in [n]$ with $i < j$.
\end{lemma}
%
\begin{proof} %We have $w(A) = \sum_{I %\in {[n] \backslash A \choose r - |A|}}\prod_{i \in I}(c_i - 1)$ for %each $A \in {[n] \choose \leq r}$.\\
(i) Let $A, A' \in {[n] \choose \leq r}$ with $A \subsetneq A'$. Let $B = A' \backslash A$. So $|B| \geq 1$. For each $L \in \mathcal{L}_{\bf c}^{(r)}$, let $\sigma(L) = \{i \in [n] \colon (i,a) \in L \mbox{ for some } a \in [c_i]\}$. We have
%
\begin{align} w(A) &\geq \left| \left\{ L \in \mathcal{L}_{\bf c}^{(r)} \colon L \cap ([n] \times [1]) = A \times [1], \, B \subset \sigma(L) \right\} \right| \nonumber \\
&= \sum_{E \in {[n] \backslash (A \cup B) \choose r - |A| - |B|}} \prod_{b \in B} (c_b - 1) \prod_{e \in E} (c_e - 1) = \prod_{b \in B} (c_b - 1) \left( \sum_{E \in {[n] \backslash A' \choose r - |A'|}} \prod_{e \in E} (c_e - 1) \right) \nonumber \\
&= w(A') \prod_{b \in B} (c_b - 1) \geq (c_1-1)^{|B|}w(A') \geq (c_1-1)w(A'). \nonumber
\end{align}
%
(ii) Let $A \in {[n] \choose \leq r}$, and let $i,j \in [n]$ with $i < j$. Suppose $\delta_{i,j}(A) \neq A$. Then $j \in A$, $i \notin A$ and $\delta_{i,j}(A) = (A \backslash \{j\}) \cup \{i\}$. Let $B = A \backslash \{j\}$, $\mathcal{E}_0 = {[n] \backslash (B \cup \{i, j\}) \choose r - |A|}$, $\mathcal{E}_1 = \left\{E \in {[n] \backslash (B \cup \{i\}) \choose r - |A|} \colon j \in E \right\}$, $\mathcal{E}_2 = \left \{E \in {[n] \backslash (B \cup \{j\}) \choose r - |A|} \colon i \in E \right\}$.  We have
%
\begin{align} w(B \cup \{i\}) &= \sum_{E \in {[n] \backslash (B \cup \{i\}) \choose r - |A|}}\prod_{e \in E}(c_e - 1) = \sum_{D \in \mathcal{E}_0}\prod_{d \in D}(c_d - 1) + \sum_{F \in \mathcal{E}_1}\prod_{f \in F}(c_f - 1) \nonumber \\
&\geq \sum_{D \in \mathcal{E}_0}\prod_{d \in D}(c_d - 1) + \sum_{F \in \mathcal{E}_1}\prod_{f \in F}(c_f - 1)\frac{c_i-1}{c_j-1} \quad \quad \mbox{(since $c_i \leq c_j$)} \nonumber \\
&= \sum_{D \in \mathcal{E}_0}\prod_{d \in D}(c_d - 1) + \sum_{F \in \mathcal{E}_2}\prod_{f \in F}(c_f - 1) = \sum_{E \in {[n] \backslash (B \cup \{j\}) \choose r - |A|}}\prod_{e \in E}(c_e - 1) \nonumber \\
&= w(B \cup \{j\}), \nonumber
\end{align}
%
and hence $w(\delta_{i,j}(A)) \geq w(A)$.\end{proof}

We now prove Theorem~\ref{mainpartial}, and then we prove Theorem~\ref{main}.

\begin{proof}[Proof of Theorem~\ref{mainpartial}.] Let $\mathcal{X} = \{X \in \mathcal{L}_{\bf c}^{(r)} \colon (1,1) \in X\}$ and $\mathcal{Y} = \{Y \in \mathcal{L}_{\bf d}^{(s)} \colon (1,1) \in Y\}$. Note that $|\mathcal{X}| = \sum_{I \in {[2,m] \choose r-1}} \prod_{i \in I} c_i$ and $|\mathcal{Y}| = \sum_{J \in {[2,n] \choose s-1}}\prod_{j \in J} d_j$, so our first aim is to show that $|\mathcal{A}||\mathcal{B}| \leq |\mathcal{X}||\mathcal{Y}|$.

Let $\mathcal{G} = {[m] \choose \leq r}$. Let $v \colon \mathcal{G} \rightarrow \mathbb{N}$ such that for each $G \in \mathcal{G}$,
%
\[v(G) = \left| \left\{ L \in \mathcal{L}_{\bf c}^{(r)} \colon L \cap ([m] \times [1]) = G \times [1] \right\} \right|.\]
%
Let $\mathcal{H} = {[n] \choose \leq s}$. Let $w \colon \mathcal{H} \rightarrow \mathbb{N}$ such that for each $H \in \mathcal{H}$,
%
\[w(H) = \left| \left\{ L \in \mathcal{L}_{\bf d}^{(s)} \colon L \cap ([n] \times [1]) = H \times [1] \right\} \right|.\]
%
Let $l = \max\{m,n\}$ and $h = \max\{c_m, d_n\}$. Let
%
%
\begin{align} \mathcal{A}^* &= \Gamma_{l,h} \circ \dots \circ \Gamma_{l,2} \circ \dots \circ \Gamma_{2,h} \circ \dots \circ \Gamma_{2,2} \circ \Gamma_{1,h} \circ \dots \circ \Gamma_{1,2}(\mathcal{A}),\nonumber \\
\mathcal{B}^* &= \Gamma_{l,h} \circ \dots \circ \Gamma_{l,2} \circ \dots \circ \Gamma_{2,h} \circ \dots \circ \Gamma_{2,2} \circ \Gamma_{1,h} \circ \dots \circ \Gamma_{1,2}(\mathcal{B}). \nonumber
\end{align}
%
Now let
%
\begin{align} \mathcal{C} &= \left\{G \in \mathcal{G} \colon E \cap ([m] \times [1]) = G \times [1] \mbox{ for some } E \in \mathcal{A}^* \right\}, \nonumber \\
\mathcal{D} &= \left\{H \in \mathcal{H} \colon F \cap ([n] \times [1]) = H \times [1] \mbox{ for some } F \in \mathcal{B}^* \right\}. \nonumber
\end{align}
%
So $\mathcal{C} \subseteq \mathcal{G}$, $\mathcal{D} \subseteq \mathcal{H}$, and by Corollary~\ref{deltacor}, $\mathcal{C}$ and $\mathcal{D}$ are cross-intersecting. We have $\mathcal{A}^* \subseteq \bigcup_{C \in \mathcal{C}} \{L \in \mathcal{L}_{\bf c}^{(r)} \colon L \cap ([m] \times [1]) = C \times [1]\}$ and $\mathcal{B}^* \subseteq \bigcup_{D \in \mathcal{D}} \{L \in \mathcal{L}_{\bf d}^{(s)} \colon L \cap ([n] \times [1]) = D \times [1]\}$. So 
%
\begin{equation} |\mathcal{A}^*| \leq \sum_{C \in \mathcal{C}} v(C) = v(\mathcal{C}) \quad \mbox{and} \quad |\mathcal{B}^*| \leq \sum_{D \in \mathcal{D}} w(D) = w(\mathcal{D}). \label{maingen.1}
\end{equation} 
%(see Section~\ref{Weightedsection}).
Since $|\mathcal{A}| = |\mathcal{A}^*|$ and $|\mathcal{B}| = |\mathcal{B}^*|$, we therefore have 
%
\begin{equation} |\mathcal{A}| \leq v(\mathcal{C}) \quad \mbox{and} \quad |\mathcal{B}| \leq w(\mathcal{D}). \label{maingen.15}
\end{equation}
%
Let $\mathcal{I} = \{G \in \mathcal{G} \colon 1 \in G\}$ and $\mathcal{J} = \{H \in \mathcal{H} \colon 1 \in H\}$. By Lemma~\ref{lemmaweighted} and Theorem~\ref{xintweight}, 
%
\begin{equation} v(\mathcal{C}) w(\mathcal{D}) \leq v(\mathcal{I}) w(\mathcal{J}). \label{maingen.2}
\end{equation}  
%
Now
%
\begin{align} v(\mathcal{I}) &= \sum_{I \in \mathcal{I}} v(I) = \sum_{I \in \mathcal{I}} \left| \left\{L \in \mathcal{L}_{\bf c}^{(r)} \colon L \cap ([m] \times [1]) = I \times [1] \right\} \right| \nonumber \\
&= \left|\bigcup_{I \in \mathcal{I}} \left \{L \in \mathcal{L}_{\bf c}^{(r)} \colon L \cap ([m] \times [1]) = I \times [1] \right\} \right| = |\mathcal{X}| \nonumber %\label{maingen.3}
\end{align}
%
and similarly $w(\mathcal{J}) = |\mathcal{Y}|$. Together with (\ref{maingen.15}) and (\ref{maingen.2}), this gives us $|\mathcal{A}||\mathcal{B}| \leq |\mathcal{X}||\mathcal{Y}|$. 

Suppose $|\mathcal{A}||\mathcal{B}| = |\mathcal{X}||\mathcal{Y}|$. Then all the inequalities in (\ref{maingen.1})--(\ref{maingen.2}) are equalities. The equalities in (\ref{maingen.1}) imply that $\mathcal{A}^* = \bigcup_{C \in \mathcal{C}} \{L \in \mathcal{L}_{\bf c}^{(r)} \colon L \cap ([m] \times [1]) = C \times [1]\}$ and $\mathcal{B}^* = \bigcup_{D \in \mathcal{D}} \{L \in \mathcal{L}_{\bf d}^{(s)} \colon L \cap ([n] \times [1]) = D \times [1]\}$. Suppose $c_1 \geq 3$ and $d_1 \geq 3$. By Lemma~\ref{lemmaweighted} and Theorem~\ref{xintweight}, equality in (\ref{maingen.2}) gives us that for some $p \in [m] \cap [n]$, $\mathcal{C} = \mathcal{G}(p)$ and $\mathcal{D} = \mathcal{H}(p)$. % such that $v(\mathcal{G}(a)) = v(\mathcal{I})$ and $w(\mathcal{H}(a)) = w(\mathcal{J})$.
It follows that $\mathcal{A}^* = \{L \in \mathcal{L}_{\bf c}^{(r)} \colon (p,1) \in L\}$ and $\mathcal{B}^* = \{L \in \mathcal{L}_{\bf d}^{(s)} \colon (p,1) \in L\}$. By Lemma~\ref{ss_cross_int}, $\mathcal{A} = \{L \in \mathcal{L}_{\bf c}^{(r)} \colon (p,q) \in L\}$ and $\mathcal{B} = \{L \in \mathcal{L}_{\bf d}^{(s)} \colon (p,q) \in L\}$ for some $q \in [c_p] \cap [d_p]$. So $\mathcal{A}$ is a star of $\mathcal{L}_{\bf c}^{(r)}$ with centre $(p,q)$, and $\mathcal{B}$ is a star of $\mathcal{L}_{\bf d}^{(s)}$ with centre $(p,q)$. Now clearly $\mathcal{X}$ is a star of $\mathcal{L}_{\bf c}^{(r)}$ of maximum size, and $\mathcal{Y}$ is a star of $\mathcal{L}_{\bf d}^{(s)}$ of maximum size. Thus, since $|\mathcal{A}||\mathcal{B}| = |\mathcal{X}||\mathcal{Y}|$, $|\mathcal{A}| = |\mathcal{X}|$ and $|\mathcal{B}| = |\mathcal{Y}|$. So $\mathcal{A}$ is a star of $\mathcal{L}_{\bf c}^{(r)}$ of maximum size, and hence we must have $c_p = c_1$. Similarly, $d_p = d_1$.\end{proof}

\begin{proof}[Proof of Theorem~\ref{main}.] Since $|\mathcal{A}| \leq |\mathcal{L}_{\bf c}|$ and $|\mathcal{B}| \leq |\mathcal{L}_{\bf c}|$, the result is trivial if $c_1 = 1$. If $c_1 \geq 3$, then the result is given by Theorem~\ref{mainpartial}. %with $r = s = m = n$ and ${\bf c} = {\bf d}$.

Finally, suppose $c_1 = 2$. Let mod$^*$ be the usual modulo operation with the exception that for any $a,b \in \mathbb{N}$, $(ba) \mbox{ mod$^*$ } a$ is $a$ rather than $0$. Let $\theta : \mathcal{L}_{\bf c} \rightarrow \mathcal{L}_{\bf c}$ such that $\theta(E) = \{(i,(j+1) \mbox{ mod$^*$ } c_i) \colon (i,j) \in E\}$ for each $E \in \mathcal{L}_{\bf c}$. Clearly, $\theta$ is a bijection, and $\theta(E) \cap E = \emptyset$ for each $E \in \mathcal{L}_{\bf c}$. Thus, since $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, $\theta(C) \notin \mathcal{B}$ for each $C \in \mathcal{A}$, and hence $|\mathcal{B}| \leq |\mathcal{L}_{\bf c}| - |\mathcal{A}|$. Since $0 \leq \left(|\mathcal{A}| - \frac{1}{2}|\mathcal{L}_{\bf c}| \right)^2 = |\mathcal{A}|^2 - |\mathcal{A}||\mathcal{L}_{\bf c}| + \frac{1}{4}|\mathcal{L}_{\bf c}|^2$, we have $|\mathcal{A}|(|\mathcal{L}_{\bf c}| - |\mathcal{A}|) \leq \left( \frac{1}{2}|\mathcal{L}_{\bf c}| \right)^2$, and hence $|\mathcal{A}||\mathcal{B}| \leq \left( \frac{1}{c_1}|\mathcal{L}_{\bf c}| \right)^2 = |\mathcal{L}_{\bf c}((1,1))|^2$.\end{proof}



\section{Proof of Theorem~\ref{multithm}} \label{multisection}

In this section, we use Theorem~\ref{xintweight} to prove Theorem~\ref{multithm}. Recall that for any $n, r \in \mathbb{N}$, $M_{n,r}$ denotes the set $\{(a_1, \dots, a_r) \colon a_1 \leq \dots \leq a_r, \, a_1, \dots, a_r \in [n]\}$.

%With a slight abuse of notation, for a set $\mathcal{A}$ of multisets, we denote the family $\{{\rm S}_A \colon A \in \mathcal{A}\}$ by ${\rm S}_{\mathcal{A}}$. 
For any family $\mathcal{F}$ of sets, let $\mathcal{F}^{(r)}$ denote the family $\{F \in \mathcal{F} \colon |F| = r\}$, and let $M_{n,r,\mathcal{F}}$ denote the set $\{A \in M_{n,r} \colon {\rm S}_{A} \in \mathcal{F}\}$.

\begin{lemma}\label{multicomp} If $n, r \in \mathbb{N}$, $i,j \in [n]$, and $\mathcal{F} \subseteq 2^{[n]}$, then $|M_{n,r,\Delta_{i,j}(\mathcal{F})}| = |M_{n,r,\mathcal{F}}|$.
\end{lemma}
%
\begin{proof} Let $\mathcal{I} = \Delta_{i,j}(\mathcal{F})$. Clearly, $|\mathcal{I}^{(p)}| = |\mathcal{F}^{(p)}|$ for each $p \in [n]$. We have
%
\begin{align} |M_{n,r,\mathcal{I}}| &= \sum_{I \in \mathcal{I}} |M_{n,r,\{I\}}| = \sum_{p = 1}^n \sum_{I \in \mathcal{I}^{(p)}} |M_{n,r,\{I\}}| = \sum_{p = 1}^n |\mathcal{I}^{(p)}| |M_{n,r,\{[p]\}}|\nonumber \\
&= \sum_{p = 1}^n |\mathcal{F}^{(p)}| |M_{n,r,\{[p]\}}| = \sum_{p = 1}^n \sum_{F \in \mathcal{F}^{(p)}} |M_{n,r,\{F\}}| = \sum_{F \in \mathcal{F}} |M_{n,r,\{F\}}| = |M_{n,r,\mathcal{F}}|, \nonumber
\end{align}
%
as required.\end{proof}

\begin{proof}[Proof of Theorem~\ref{multithm}.] %Let $\mathcal{A}' = M_{m,r,{\rm S}_{\mathcal{A}}}$ and Let $\mathcal{B}' = M_{n,s,{\rm S}_{\mathcal{B}}}$. 
Let $\mathcal{A}$ and $\mathcal{B}$ be as in the statement of the theorem. Let $\mathcal{C} = \{{\rm S}_A \colon A \in \mathcal{A}\}$ and $\mathcal{D} = \{{\rm S}_B \colon B \in \mathcal{B}\}$. Clearly, $\mathcal{A} \subseteq M_{m,r,\mathcal{C}}$ and $\mathcal{B} \subseteq M_{n,s,\mathcal{D}}$. Since $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting, $\mathcal{C}$ and $\mathcal{D}$ are cross-intersecting. 

By Lemma~\ref{compcross}(iii), we can apply left-compressions to $\mathcal{C}$ and $\mathcal{D}$ simultaneously until we obtain two compressed cross-intersecting families $\mathcal{C}^*$ and $\mathcal{D}^*$, respectively. Since $\mathcal{C} \subseteq {[m] \choose \leq r}$ and $\mathcal{D} \subseteq {[n] \choose \leq s}$, we have $\mathcal{C}^* \subseteq {[m] \choose \leq r}$ and $\mathcal{D}^* \subseteq {[n] \choose \leq s}$. By Lemma~\ref{compcross}(ii),
%
\begin{equation} \mbox{$C \cap D \cap [r+s-1] \neq \emptyset$ for any $C \in \mathcal{C}^*$ and any $D \in \mathcal{D}^*$.} \label{mrs1}
\end{equation}
%

Let $p = r+s-1$. Let $\mathcal{G} = {[p] \choose \leq r}$ and $\mathcal{H} = {[p] \choose \leq s}$. Let $g : \mathcal{G} \rightarrow \mathbb{N}$ such that $g(G) = {m+r-p-1 \choose r-|G|}$ for each $G \in \mathcal{G}$. Let $h : \mathcal{H} \rightarrow \mathbb{N}$ such that $h(H) = {n+s-p-1 \choose s-|H|}$ for each $H \in \mathcal{H}$. 

For every $F, G \in \mathcal{G}$ with $\emptyset \neq F \subsetneq G$ and $|F| = |G|-1$, we have

%
\begin{align} \frac{g(F)-(1+u)g(G)}{{m+r-p-1 \choose r-|F|}} &= 1 - \frac{(1+u){m+r-p-1 \choose r-|F|-1}}{{m+r-p-1 \choose r-|F|}} = 1 - \frac{(1+u)(r-|F|)}{m-p+|F|} \nonumber \\
&= \frac{m-p+|F|-(1+u)(r-|F|)}{m-p+|F|} \geq \frac{m-p+1-(1+u)(r-1)}{m-p+|F|} \nonumber \\
&= \frac{m-(2+u)(r-1)-s+1}{m-p+|F|} \geq 0, \nonumber %\\
%&\geq \frac{(2+u)(s-1)+r-1-((2+u)(r-1)+s-1)}{m-p+|F|} \geq 0, \nonumber 
\end{align}
%
and hence $g(F) \geq (1+u)g(G)$. It follows that $g(F) \geq (1+u)g(G)$ for every $F, G \in \mathcal{G}$ with $\emptyset \neq F \subsetneq G$. Similarly, $h(F) \geq (1+v)g(H)$ for every $F, H \in \mathcal{H}$ with $\emptyset \neq F \subsetneq H$.

We have $g(\delta_{i,j}(G)) = g(G)$ for every $G \in \mathcal{G}$ and every $i,j \in [p]$. Similarly, $h(\delta_{i,j}(H)) = h(H)$ for every $H \in \mathcal{H}$ and every $i,j \in [p]$.

Let $\mathcal{E} = \{C \cap [p] \colon C \in \mathcal{C}^*\}$ and $\mathcal{F} = \{D \cap [p] \colon D \in \mathcal{D}^*\}$. Then $\mathcal{E} \subseteq \mathcal{G}$, $\mathcal{F} \subseteq \mathcal{H}$, and, by (\ref{mrs1}), $\mathcal{E}$ and $\mathcal{F}$ are cross-intersecting. By Theorem~\ref{xintweight},
%
\begin{equation} g(\mathcal{E}) h(\mathcal{F}) \leq g(\mathcal{G}(1)) h(\mathcal{H}(1)), \label{mrs2}
\end{equation}
%
and if $u \neq 0 \neq v$, then equality holds only if $\mathcal{E} = \mathcal{G}(a)$ and $\mathcal{F} = \mathcal{H}(a)$ for some $a \in [p]$.

Let $\mathcal{M} = \{A \in M_{m,r} \colon {\rm S}_A \cap [p] = E \mbox{ for some } E \in \mathcal{E}\}$. Note that $M_{m,r,\mathcal{C}^*} \subseteq \mathcal{M}$. By Lemma~\ref{multicomp}, $|M_{m,r,\mathcal{C}}| = |M_{m,r,\mathcal{C}^*}|$. Since $\mathcal{A} \subseteq M_{m,r,\mathcal{C}}$, we have
%
\begin{align} |\mathcal{A}| &\leq |M_{m,r,\mathcal{C}^*}| \leq |\mathcal{M}| = \sum_{E \in \mathcal{E}} |\{A \in M_{m,r} \colon {\rm S}_A \cap [p] = E\}|  \nonumber \\
&= \sum_{E \in \mathcal{E}} |\{(a_1, \dots, a_{r-|E|}) \colon a_1 \leq  \dots \leq a_{r-|E|}, \, a_1, \dots, a_{r-|E|} \in E \cup [p+1,m]\}|  \nonumber  \\
&= \sum_{E \in \mathcal{E}} |M_{|E|+m-p,r-|E|}| = \sum_{E \in \mathcal{E}} {m+r-p-1 \choose r-|E|} = g(\mathcal{E}).
\label{mrs3} 
\end{align}
%
Similarly, 
%
\begin{equation} |\mathcal{B}| \leq h(\mathcal{F}). \label{mrs4}
\end{equation}
%
By (\ref{mrs2})--(\ref{mrs4}), 
%
\begin{equation} |\mathcal{A}||\mathcal{B}| \leq g(\mathcal{G}(1)) h(\mathcal{H}(1)). \label{mrs5}
\end{equation}
%
Now, similarly to (\ref{mrs3}),
%
\begin{align} g(\mathcal{G}(1)) &= \left| \left\{A \in M_{m,r} \colon {\rm S}_A \cap [p] = E \mbox{ for some $E \in \mathcal{G}(1)$} \right\} \right| \nonumber \\
&= \left| \left\{A \in M_{m,r} \colon 1 \in {\rm S}_A \right\} \right| = {m+r-2 \choose r-1}. \nonumber
\end{align}
%
Similarly, $h(\mathcal{H}(1)) = {n+s-2 \choose s-1}$. By (\ref{mrs5}), it follows that
%
\[|\mathcal{A}||\mathcal{B}| \leq {m+r-2 \choose r-1}{n+s-2 \choose s-1},\]
%
as required.

Suppose $|\mathcal{A}||\mathcal{B}| = {m+r-2 \choose r-t}{n+s-2 \choose s-t}$ and $u \neq 0 \neq v$. Then equality holds throughout in each of (\ref{mrs2})--(\ref{mrs5}), and hence $\mathcal{E} = \mathcal{G}(a)$ and $\mathcal{F} = \mathcal{H}(a)$ for some $a \in [p]$. Having equality throughout in (\ref{mrs3}) implies that $M_{m,r,\mathcal{C}^*} = \mathcal{M} = \{A \in M_{m,r} \colon a \in {\rm S}_A\}$. Thus $\{a\} \in \mathcal{C}^*$, and hence there exists $a_1 \in [m]$ such that $\{a_1\} \in \mathcal{C}$. Similarly, there exists $a_2 \in [n]$ such that $\{a_2\} \in \mathcal{D}$. Since $\mathcal{C}$ and $\mathcal{D}$ are cross-intersecting, we have $a_1 = a_2$, $\mathcal{C} \subseteq \{C \in {[m] \choose \leq r} \colon a_1 \in C\}$, and $\mathcal{D} \subseteq \{D \in {[n] \choose \leq s} \colon a_1 \in D\}$. Consequently, $\mathcal{A} \subseteq \left\{ A \in M_{m,r} \colon a_1 \in {\rm S}_A \right\}$ and $\mathcal{B} \subseteq \left\{ B \in M_{n,s} \colon a_1 \in {\rm S}_B \right\}$.  Since $|\mathcal{A}||\mathcal{B}| = {m+r-2 \choose r-1}{n+s-2 \choose s-1}$, both inclusion relations are actually equalities.\end{proof}

\subsection*{Acknowledgements}
The author wishes to thank the anonymous referees for checking the paper carefully and providing remarks that led to an improvement in the presentation.

\begin{thebibliography}{10}

\bibitem{AK1} R.~Ahlswede and L.H. Khachatrian.  \newblock The complete
intersection theorem for systems of finite sets.  \newblock {\em European J. Combin.}, 18:125--136, 1997.

\bibitem{AK2} R. Ahlswede and L.H. Khachatrian.  \newblock The Diametric Theorem in Hamming spaces---Optimal Anticodes.  \newblock {\em  Adv. in Appl. Math.}, 20:429--449, 1998.

\bibitem{AC} M.O. Albertson and K.L. Collins.  \newblock Homomorphisms of 3-chromatic graphs.  \newblock {\em  Discrete Math.}, 54:127--132, 1985.

\bibitem{B} C. Berge.  \newblock Nombres de coloration de l'hypergraphe h-parti complet.  \newblock In {\em Hypergraph Seminar}, volume 411 of {\em Lecture Notes in Math.}, pages 13--20. Springer, Berlin, 1974.

\bibitem{Bey2} C. Bey.  \newblock An intersection theorem for weighted sets.  \newblock {\em  Discrete Math.}, 235:145--150, 2001.

\bibitem{Bey3} C. Bey.  \newblock On cross-intersecting families of sets.  \newblock {\em  Graphs Combin.}, 21:161--168, 2005. 

\bibitem{Bey1} C. Bey.  \newblock The Erd\H{o}s-Ko-Rado bound for the function lattice.  \newblock {\em  Discrete Appl. Math.}, 95:115--125, 1999.

%\bibitem{BE} C. Bey and K. Engel, Old and new results for the weighted t-intersection problem via AK-methods, In: Numbers, Information and Complexity, Alth\"{o}fer, Ingo, Eds. et al., Dordrecht: Kluwer Academic Publishers, 2000, pp. 45--74.

\bibitem{BL} B. Bollob\'{a}s and I. Leader.  \newblock An Erd\H os-Ko-Rado theorem for signed sets.  \newblock {\em Comput. Math. Appl.}, 34:9-13, 1997.

\bibitem{Borg10} P. Borg.  \newblock A cross-intersection theorem for subsets of a set.  \newblock {\em Bull. London. Math. Soc.}, 47:248--256, 2015.

\bibitem{Borg4} P. Borg.  \newblock A short proof of a cross-intersection theorem of Hilton.  \newblock {\em Discrete Math.}, 309:4750--4753, 2009.

\bibitem{Borg3} P. Borg.  \newblock Cross-intersecting families of
permutations.  \newblock {\em J. Combin. Theory Ser. A}, 117:483--487, 2010.

\bibitem{Borg2} P. Borg.  \newblock Cross-intersecting families of partial permutations.  \newblock {\em SIAM J. Disc. Math.}, 24:600--608, 2010.

\bibitem{arxiver} P. Borg.  \newblock Cross-intersecting integer sequences, \arxiv{1}.

\bibitem{Borg5} P. Borg.  \newblock Cross-intersecting sub-families of
hereditary families.  \newblock {\em J. Combin. Theory Ser. A}, 119:871--881, 2012.

\bibitem{Borg9} P. Borg.  \newblock Extremal $t$-intersecting sub-families of hereditary families.  \newblock {\em J. London Math. Soc.}, 79:167--185, 2009.

\bibitem{Borg} P. Borg.  \newblock Intersecting and cross-intersecting
families of labeled sets.  \newblock {\em Electron. J. Combin.}, 15:\#N9, 2008.

\bibitem{Borg7} P. Borg.  \newblock Intersecting families of sets and
permutations:~a survey.  \newblock In A.R. Baswell (Ed.), {\em Advances in Mathematics Research}, volume 16, pages 283--299. Nova Science Publishers, Inc., Hauppauge, New York, 2011.

%\bibitem{Borg1} P. Borg.  \newblock Intersecting systems of signed sets, Electron. J. Combin. 14 (2007) $\#$R41.

%\bibitem{Borg6} P. Borg.  \newblock On $t$-intersecting families of signed sets and permutations, Discrete Math. 309 (2009), 3310--3317.

\bibitem{Borg11} P. Borg.  \newblock The maximum product of sizes of cross-$t$-intersecting uniform families.  \newblock {\em Australas. J. Combin.}, 60:69--78, 2014.

\bibitem{Borg8} P. Borg.  \newblock The maximum sum and the maximum product of sizes of cross-intersecting families.  \newblock {\em European J. Combin.}, 35:117--130, 2014.

\bibitem{BL2} P. Borg and I. Leader.  \newblock Multiple cross-intersecting families of signed sets.  \newblock {\em J. Combin. Theory Ser. A}, 117:583--588, 2010.

\bibitem{CK} P.J. Cameron and C.Y. Ku.  \newblock Intersecting families of permutations.  \newblock {\em European J. Combin.}, 24:881--890, 2003.

\bibitem{Chv} V. Chv\'{a}tal.  \newblock Unsolved Problem No.~7. \newblock In C. Berge, D.K. Ray-Chaudhuri (Eds.), {\em Hypergraph Seminar}, volume 411 of {\em Lecture Notes in Mathematics}. Springer, Berlin, 1974.

\bibitem{D} D.E. Daykin.  \newblock Erd\H os-Ko-Rado from Kruskal--Katona.  \newblock {\em J. Combin. Theory Ser. A}, 17:254--255, 1974.

\bibitem{DF} M. Deza and P. Frankl.  \newblock The Erd\H os--Ko--Rado theorem---22 years later.  \newblock {\em SIAM J. Algebraic Discrete Methods}, 4:419--431, 1983.

\bibitem{E} K. Engel.  \newblock An Erd\H os-Ko-Rado theorem for the subcubes of a cube.  \newblock {\em Combinatorica}, 4:133--140, 1984.

\bibitem{EFK} P.L. Erd\H os, U. Faigle, and W. Kern.  \newblock A group-theoretic setting for some intersecting Sperner families.  \newblock {\em Combin. Probab. Comput.}, 1:323--334, 1992.

\bibitem{EKR} P. Erd\H os, C. Ko, and R. Rado.  \newblock Intersection
theorems for systems of finite sets.  \newblock {\em Quart. J. Math. Oxford (2)}, 12:313--320, 1961.

\bibitem{F2} P. Frankl.  \newblock Extremal set systems. \newblock In R.L. Graham, M. Gr\"{o}tschel, and L. Lov\'{a}sz (Eds.), {\em Handbook of Combinatorics}, volume 2, pages 1293--1329. Elsevier, Amsterdam, 1995.

\bibitem{F_t1} P. Frankl.  \newblock The Erd\H os-Ko-Rado Theorem is true
for $n = ckt$. \newblock In {\em Combinatorics} (5th Hungarian Colloquium, Keszthely, June/July 1976, Proceedings, Volume 2), volume~18 of {\em Colloquia mathematica Societatis J\'{a}nos Bolyai}, pages 365--375. North-Holland, Amsterdam, 1978.

\bibitem{F} P. Frankl.  \newblock The shifting technique in extremal set theory. \newblock In C. Whitehead (Ed.), {\em Surveys in Combinatorics 1987}, volume 123 of {\em London Mathematical Society Lecture Note Series}, pages 81--110. Cambridge University Press, Cambridge, 1987.

\bibitem{FF2} P. Frankl and Z. F\"{u}redi.  \newblock The Erd\H os-Ko-Rado Theorem for integer sequences.  \newblock {\em SIAM J. Algebraic Discrete Methods}, 1:376--381, 1980.

\bibitem{FT2} P. Frankl and N. Tokushige.  \newblock The Erd\H os-Ko-Rado theorem for integer sequences.  \newblock {\em Combinatorica}, 19:55--63, 1999.

\bibitem{FT3} P. Frankl and N. Tokushige.  \newblock Invitation to intersection problems for finite sets.  \newblock {\em J. Combin. Theory Ser. A}, 144:157--211, 2016.

%\bibitem{FLST} P. Frankl, S.J. Lee, M. Siggers, and N. Tokushige.  \newblock An Erd\H{o}s-Ko-Rado theorem for cross t-intersecting families, arXiv:1303.0657.

\bibitem{FGV} Z. F\"{u}redi, D. Gerbner, and M. Vizer.  \newblock A discrete isodiametric result: the Erd\H{o}s--Ko--Rado theorem for multisets.  \newblock {\em European  J. Combin.}, 48:224--233, 2015.

%\bibitem{G} H.-D.O.F. Gronau, More on the Erd\H os-Ko-Rado theorem for integer sequences, J. Combin. Theory Ser. A 35 (1983) 279--288.

\bibitem{H} A.J.W. Hilton.  \newblock An intersection theorem for a collection of families of subsets of a finite set.  \newblock {\em J. London Math. Soc. (2)}, 15:369--376, 1977.

%\bibitem{HM} A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford (2) 18 (1967), 369--384.

\bibitem{HST} F. Holroyd, C. Spencer, and J. Talbot.  \newblock Compression and Erd\H os--Ko--Rado graphs.  \newblock {\em Discrete Math.}, 293:155--164, 2005.

\bibitem{HT} F. Holroyd and J. Talbot.  \newblock Graphs with the Erd\H os--Ko--Rado property.  \newblock {\em Discrete Math.}, 293:165--176, 2005.

\bibitem{K} G.O.H. Katona.  \newblock A simple proof of the Erd\H os--Chao Ko--Rado theorem.  \newblock {\em J. Combin. Theory Ser. B}, 13:183--184, 1972.

\bibitem{Ka} G.O.H. Katona.  \newblock A theorem of finite sets. \newblock In {\em Theory of Graphs} (Proceedings of the Colloquium on Graph Theory, Held at Tihany, Hungary, September 1966), pages 187--207.
Akad\'{e}miai Kiad\'{o}, Budapest, 1968.

\bibitem{Kat} G.O.H. Katona.  \newblock Intersection theorems for systems of finite sets.  \newblock {\em Acta Math. Acad. Sci. Hungar.}, 15:329--337, 1964.

%\bibitem{Kl} D.J. Kleitman, On a combinatorial conjecture of Erd\H{o}s, J. Combin. Theory Ser. A 1 (1966), 209--214.

\bibitem{Kr} J.B. Kruskal.  \newblock The number of simplices in a
complex. In {\em Mathematical Optimization Techniques}, pages 251--278. University of California Press, Berkeley, California, 1963.

\bibitem{L} M.L. Livingston.  \newblock An ordered version of the Erd\H os-Ko-Rado Theorem.  \newblock {\em J. Combin. Theory Ser. A}, 26:162--165, 1979.

%\bibitem{MT2} M. Matsumoto, N. Tokushige, A generalization of the Katona theorem for cross $t$-intersecting families, Graphs Combin. 5 (1989), 159--171.

\bibitem{MT} M. Matsumoto and N. Tokushige.  \newblock The exact bound in the Erd\H os-Ko-Rado theorem for cross-intersecting families.  \newblock {\em J. Combin. Theory Ser. A}, 52:90--97, 1989.

\bibitem{MP} K. Meagher and A. Purdy.  \newblock An Erd\H os--Ko--Rado theorem for multisets.  \newblock {\em Electron. J. Combin.}, 18(1):\#P220, 2011.

%\bibitem{Meyer} J.-C. Meyer, Quelques probl\`{e}mes concernant les cliques des hypergraphes $k$-complets et $q$-parti $h$-complets, in: Hypergraph Seminar (Columbus, Ohio 1972), Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974, 127--139.

\bibitem{Moon} A. Moon.  \newblock An analogue of the Erd\H os-Ko-Rado theorem for the Hamming schemes $H(n,q)$.  \newblock {\em J. Combin. Theory Ser. A}, 32:386--390, 1982.

\bibitem{PT} J. Pach and G. Tardos.  \newblock Cross-intersecting families of vectors.  \newblock {\em Graphs Combin.}, 31:477--495, 2015.

\bibitem{Pyber} L. Pyber.  \newblock A new generalization of the Erd\H os--Ko--Rado theorem.  \newblock {\em J. Combin. Theory Ser. A}, 43:85--90, 1986.

\bibitem{Tok3} N. Tokushige.  \newblock Cross $t$-intersecting integer sequences from weighted Erd\H{o}s-Ko-Rado.  \newblock {\em Combin. Prob. Comput.}, 22:622--637, 2013. 

%\bibitem{Tok1} N. Tokushige.  \newblock On cross $t$-intersecting families of sets, J. Combin. Theory Ser. A 117 (2010), 1167--1177.

%\bibitem{Tok2} N. Tokushige.  \newblock The eigenvalue method for cross t-intersecting families, J. Algebr. Comb. 38 (2013), 653--662.

\bibitem{WZ} J. Wang and H. Zhang.  \newblock Cross-intersecting families and primitivity of symmetric systems.  \newblock {\em J. Combin. Theory Ser. A}, 118:455--462, 2011.

\bibitem{W} R.M. Wilson.  \newblock The exact bound in the Erd\H os--Ko--Rado theorem.  \newblock {\em Combinatorica}, 4:247--257, 1984.

\bibitem{Zhang} H. Zhang.  \newblock Cross-intersecting families of labeled sets.  \newblock {\em Electron. J. Combin.}, 20(1):\#P17, 2013.


\end{thebibliography}

\end{document}