Two-state component-size conjecture for 1-independent percolation on the hypercube

At least 4 years old · documented by

Let QnQ_n be the nn-dimensional hypercube, let p∈(12,1]p\in (\frac{1}{2},1] be fixed, and let M1,≥p(Qn)\mathcal{M}_{1,\geq p}(Q_n) denote the 11-independent percolation measures on QnQ_n whose edge marginals are at least pp. For a measure μ\mu, write Hμ\mathbf{H}_{\mu} for the resulting random subgraph and C1(Hμ)C_1(\mathbf{H}_{\mu}) for its largest connected component. Two-state component-size conjecture. For all μ∈M1,≥p(Qn)\mu\in\mathcal{M}_{1,\geq p}(Q_n), with probability 1−o(1)1-o(1),

∣C1(Hμ)∣≥(1+2p−12−o(1))2n.\left\vert C_1\left(\mathbf{H}_{\mu}\right)\right\vert \geq \left(\frac{1+\sqrt{2p-1}}{2}-o(1)\right)2^n.

The conjecture says that the two-state measure asymptotically minimises the size of the largest component, extending the paper's exact finite-graph result and its corresponding asymptotic theorem for weakly pseudorandom graphs. It remains open for the hypercube.

References

Primary source

Victor Falgas-Ravry and Vincent Pfenninger, “1-independent percolation on Z^2 K_n”, arXiv:2106.08674 (2022).

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.