Exact extremal non-trivial cross-intersecting families

Biao Wu; Huajun Zhang

paper

Exact extremal non-trivial cross-intersecting families

arXiv:2411.16091

Abstract

Two families $A$ and $B$ of sets are called cross-intersecting if each pair of sets $A \in A$ and $B \in B$ has nonempty intersection. Let $A$ and $B$ be two cross-intersecting families of $k$ -subsets and $ℓ$ -subsets of $[n]$ . Matsumoto and Tokushige [J. Combin. Theory Ser. A 52 (1989) 90--97] studied the extremal problem of the size $∣ A ∣∣ B ∣$ and obtained the uniqueness of extremal families whenever $n \geq 2 ℓ \geq 2 k$ , building on the work of Pyber. This paper will explore the second extremal size of $∣ A ∣∣ B ∣$ and obtain that if $A$ and $B$ are not the subfamilies of Matsumoto--Tokushige's extremal families, then, for $n \geq 2 ℓ > 2 k$ or $n > 2 ℓ = 2 k$ , \begin{itemize} \item[1)]either $∣ A ∣∣ B ∣ \leq ((k - 1 n - 1) + (k - 1 n - 2)) (ℓ - 2 n - 2)$ with the unique extremal families (up to isomorphism) \[\mbox{ $A = {A \in (k [ n ]) : 1 \in A or 2 \in A}$ \quad and \quad $B = {B \in (ℓ [ n ]) : [2] \subseteq B}$ };\] \item[2)] or $∣ A ∣∣ B ∣ \leq ((k - 1 n - 1) + 1) ((ℓ - 1 n - 1) - (ℓ - 1 n - k - 1))$ with the unique extremal families (up to isomorphism) \[\mbox{ $A = {A \in (k [ n ]) : 1 \in A} \cup {[2, k + 1]}$ \quad and \quad $B = {B \in (ℓ [ n ]) : 1 \in B, B \cap [2, k + 1] \neq = \emptyset}$ .}\] \end{itemize} The bound `` $n \geq 2 ℓ > 2 k$ or $n > 2 ℓ = 2 k$ " is sharp for $n$ . To achieve the above results, we establish some size-sensitive inequalities for cross-intersecting families. As by-products, we will recover the main results of Frankl and Kupavskii [European J. Combin. 62 (2017) 263--271].

19 pages,comments are welcome!