The balanced-monotone-family success-probability conjecture

About 5 years old · traced to

Let B={0,1}nB=\{0,1\}^n, and let μ\mu be the uniform measure on BtB^t. A balanced monotone family is a set W⊆{0,1}nW\subseteq\{0,1\}^n containing precisely half the points and such that x∈Wx\in W and yi≥xiy_i\geq x_i for all ii imply y∈Wy\in W. Let pmonotone(t,n)p_{\mathrm{monotone}}(t,n) be the corresponding maximal success probability, and let

pmonotone(t):=lim⁡n→∞pmonotone(t,n).p_{\mathrm{monotone}}(t):=\lim_{n\to\infty}p_{\mathrm{monotone}}(t,n).

Balanced-monotone-family conjecture. The success probability pmonotone(t)p_{\mathrm{monotone}}(t) tends to 00 as tt grows. This is stronger than the intersecting-family conjecture because maximal intersecting families are balanced monotone families; its status is open in the source.

References

Primary source

Noga Alon, Ehud Friedgut, Gil Kalai and Guy Kindler, “The success probability in Levine's hat problem, and independent sets in graphs”, arXiv:2208.06858 (2023).

Additional references

2 papers in this index state this conjecture (2021–2022). The statement above is taken from the most recent of them; the others are arXiv:2103.01541.

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.