The paper determines the maximum total size of m non-empty pairwise cross-intersecting families with arbitrary allowed set sizes when n is at least the sum of the two largest allowed sizes, and characterizes all extremal families.
Non-empty pairwise cross-intersecting families
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
Two families $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting if $A\cap B\ne \emptyset$ for any $A\in \mathcal{A}$ and $B\in \mathcal{B}$. We call $t$ families $\mathcal{A}_1, \mathcal{A}_2,\dots, \mathcal{A}_t$ pairwise cross-intersecting families if $\mathcal{A}_i$ and $\mathcal{A}_j$ are cross-intersecting when $1\le i<j \le t$. Additionally, if $\mathcal{A}_j\ne \emptyset$ for each $j\in [t]$, then we say that $\mathcal{A}_1, \mathcal{A}_2,\dots, \mathcal{A}_t$ are non-empty pairwise cross-intersecting. Let $\mathcal{A}_1\subset{[n]\choose k_1}, \mathcal{A}_2\subset{[n]\choose k_2}, \dots, \mathcal{A}_t\subset{[n]\choose k_t}$ be non-empty pairwise cross-intersecting families with $t\geq 2$, $k_1\geq k_2\geq \cdots \geq k_t$, $n\ge k_1+k_2$ and $d_1, d_2, \dots, d_t$ be positive numbers. In this paper, we give a sharp upper bound of $\sum_{j=1}^td_j|\mathcal{A}_j|$ and characterize the families $\mathcal{A}_1, \mathcal{A}_2,\dots, \mathcal{A}_t$ attaining the upper bound. Our results unifies results of Frankl and Tokushige [J. Combin. Theory Ser. A 61 (1992)], Shi, Frankl and Qian [Combinatorica 42 (2022)], Huang and Peng \cite{huangpeng}, and Zhang-Feng \cite{ZF2023}. Furthermore, our result can be applied in the treatment for some $n<k_1+k_2$ while all previous known results do not have such an application. In the proof, a result of Kruskal-Katona is applied to allow us to consider only families $\mathcal{A}_i$ whose elements are the first $|\mathcal{A}_i|$ elements in lexicographic order. We bound $\sum_{i=1}^t{|\mathcal{A}_i|}$ by a single variable function $g(R)$, where $R$ is the last element of $\mathcal{A}_1$ in lexicographic order. One crucial and challenge part is to verify that $-g(R)$ has unimodality. We think that the unimodality of functions in this paper are interesting in their own, in addition to the extremal result.
fields
math.CO 1years
2024 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Non-uniform Cross-intersecting Families
The paper determines the maximum total size of m non-empty pairwise cross-intersecting families with arbitrary allowed set sizes when n is at least the sum of the two largest allowed sizes, and characterizes all extremal families.