Stability conjecture for optimal cross-intersecting families

About 11 years old · traced to

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(U1△U1(ℓ)),μ2(U2△U2(ℓ))}<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.

References

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.