Stability conjecture for optimal cross-intersecting families

Let Ω1=Ω2=2[n]\Omega_1=\Omega_2=2^{[n]}, let μ1,μ2\mu_1,\mu_2 be the product measures defined above, and let Ui()={xΩi:x}U_i^{(\ell)}=\{x\in\Omega_i:\ell\in x\}. Assume the condition on the coordinate probabilities in the original theorem holds, and suppose that p1,p2<1/2p_1,p_2<1/2.

Stability conjecture. There exists a constant c=c(p1,p2)c=c(p_1,p_2) such that, for every pair of cross-intersecting families U1Ω1U_1\subset\Omega_1 and U2Ω2U_2\subset\Omega_2 satisfying

μ1(U1)μ2(U2)>(1ε)p1p2,\mu_1(U_1)\mu_2(U_2)>(1-\varepsilon)p_1p_2,

there is an [n]\ell\in[n] such that

max{μ1(U1U1()),μ2(U2U2())}<cε.\max\bigl\{\mu_1(U_1\triangle U_1^{(\ell)}),\mu_2(U_2\triangle U_2^{(\ell)})\bigr\}<c\sqrt{\varepsilon}.

The conjecture asserts quantitative closeness to an optimal coordinate-star pair when the product of measures is close to the extremal value. The source gives no resolution of this stability statement.

Sources & referencesView supporting material

Primary source

Sho Suda, Hajime Tanaka and Norihide Tokushige, “A semidefinite programming approach to a cross-intersection problem with measures”, arXiv:1504.00135 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.