Rigidity and stability for biased cross-intersecting families
Abstract
Let $\mathbf p=(p_1,\ldots,p_n)$ and $\mathbf q=(q_1,\ldots,q_n)$ belong to $(0,1/2]^n$, and let $\mu_{\mathbf p}$ and $\mu_{\mathbf q}$ be the associated measures on $2^{[n]}$. Suppose that $p_1q_1=\max_{i\in[n]}p_iq_i$. We prove that every pair of cross-intersecting families $\mathcal A,\mathcal B\subseteq2^{[n]}$ satisfies the sharp inequality $\mu_{\mathbf p}(\mathcal A)\mu_{\mathbf q}(\mathcal B)\leq p_1q_1$. This confirms a conjecture of Suda, Tanaka and Tokushige [Math. Program. 166 (2017) 113--130]. We also determine all equality cases. When $p_1q_1<1/4$, equality is attained only when both families consist of all subsets containing the same product-maximizing coordinate. At the endpoint $p_1q_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 $\mu_{\mathbf p}(\mathcal A)\mu_{\mathbf q}(\mathcal B)\geq(1-\varepsilon)p_1q_1$, then there exists a coordinate $j$ such that both $\mathcal A$ and $\mathcal B$ are within $c(p_1,q_1)\varepsilon$, in their respective measures, of the family of all subsets containing $j$. This improves the conjectured $O(\sqrt{\varepsilon})$ 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.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요