Rigidity and stability for biased cross-intersecting families

Abstract

Let $\mathbf{p}=(p_1,\dots ,p_n)$ and $\mathbf{q}=(q_1,\dots ,q_n)$ belong to $(0,1/2{]}^n$, and let $\hat{I}{¼}_{\mathbf{p}}$ and $\hat{I}{¼}_{\mathbf{q}}$ be the associated measures on $2^{[n]}$. Suppose that $p_1{q}_1={\max }_{i\in [n]}{p}_i{q}_i$. We prove that every pair of cross-intersecting families $\mathcal{A},\mathcal{B}\subseteq 2^{[n]}$ satisfies the sharp inequality $\hat{I}{¼}_{\mathbf{p}}(\mathcal{A})\hat{I}{¼}_{\mathbf{q}}(\mathcal{B})\le p_1{q}_1$. This confirms a conjecture of Suda, Tanaka and Tokushige [Math. Program. 166 (2017) 113--130]. We also determine all equality cases. When $p_1{q}_1<1/4$, equality is attained only when both families consist of all subsets containing the same product-maximizing coordinate. At the endpoint $p_1{q}_1=1/4$, we identify precisely the additional extremal pairs, which are induced by half-sized increasing families on the coordinates satisfying $p_i=q_i=1/2$. We further resolve the remaining conjecture from the same paper by proving a dimension-free stability theorem. Assume that the first coordinate has maximum probability under both measures and that $p_1,q_1<1/2$. If $\hat{I}{¼}_{\mathbf{p}}(\mathcal{A})\hat{I}{¼}_{\mathbf{q}}(\mathcal{B})\ge (1-\epsilon )p_1{q}_1$, then there exists a coordinate $j$ such that both $\mathcal{A}$ and $\mathcal{B}$ are within $c(p_1,q_1)\epsilon$, in their respective measures, of the family of all subsets containing $j$. This improves the conjectured $O(\sqrt{\epsilon })$ bound to a linear one. The main new ingredient in the sharp measure theorem is a log-odds interpolation combined with induction on coordinate sections, while stability follows from a semidefinite estimate and a one-coordinate approximation theorem.

51 pages

Topics & keywords